Weighted Graph Extension

Problem Statement

Write a Java program that modifies an undirected graph implementation to support weighted edges by storing weights in the adjacency list. The program should allow adding weighted edges and retrieving the weight of an edge between two vertices, using an adjacency list representation with a custom edge structure. The graph remains undirected, and the program should test adding and retrieving edge weights with various graphs, including graphs with positive weights, empty graphs, and single-vertex graphs. You can visualize this as a network of cities where roads have distances (weights), and you need to store and query these distances efficiently.

Input:

• An undirected graph with vertices as integers (0 to n-1).
• The number of vertices n and a list of weighted edges (triplets [u, v, weight]).
• Queries to retrieve the weight of specific edges (u, v). Output: A confirmation of edge additions and the retrieved weights for queried edges, or -1 if the edge doesn’t exist, along with a string representation of the graph’s adjacency list for clarity. Constraints:
• The number of vertices n is between 0 and 10^5.
• Edges are triplets [u, v, weight] where 0 ≤ u, v < n, and weight is a positive integer in [1, 10^9].
• The graph is undirected (edge [u, v, weight] implies [v, u, weight]). Example:
• Input: n = 4, edges = [[0, 1, 5], [1, 2, 3], [2, 3, 7]], queries = [[0, 1], [1, 3]]
• Output:
  • Added edges successfully
  • Weight(0, 1) = 5
  • Weight(1, 3) = -1
  • "Adjacency List: {0=[(1, 5)], 1=[(0, 5), (2, 3)], 2=[(1, 3), (3, 7)], 3=[(2, 7)]}"
• Explanation: Edge (0, 1) has weight 5; edge (1, 3) doesn’t exist.
• Input: n = 0, edges = [], queries = [[0, 1]]
• Output:
  • Added edges successfully
  • Weight(0, 1) = -1
  • "Adjacency List: {}"
• Explanation: Empty graph, no edges.

Pseudocode

CLASS Edge
    SET destination to integer
    SET weight to integer
ENDCLASS

FUNCTION createGraph(n, edges)
    CREATE adjList as new HashMap
    FOR i from 0 to n-1
        SET adjList[i] to empty list
    ENDFOR
    FOR each edge [u, v, weight] in edges
        CREATE edge1 as new Edge(v, weight)
        CREATE edge2 as new Edge(u, weight)
        ADD edge1 to adjList[u]
        ADD edge2 to adjList[v]
    ENDFOR
    RETURN adjList
ENDFUNCTION

FUNCTION getEdgeWeight(adjList, u, v)
    FOR each edge in adjList[u]
        IF edge.destination equals v THEN
            RETURN edge.weight
        ENDIF
    ENDFOR
    RETURN -1
ENDFUNCTION

FUNCTION toString(adjList)
    CREATE result as new StringBuilder
    APPEND "Adjacency List: {" to result
    FOR each vertex in adjList
        APPEND vertex and "=" to result
        APPEND "[" to result
        FOR each edge in adjList[vertex]
            APPEND "(" and edge.destination and ", " and edge.weight and ")" to result
            IF edge is not last THEN
                APPEND ", " to result
            ENDIF
        ENDFOR
        APPEND "]" to result
        IF vertex is not last THEN
            APPEND ", " to result
        ENDIF
    ENDFOR
    APPEND "}" to result
    RETURN result as string
ENDFUNCTION

FUNCTION main()
    SET testCases to array of (n, edges, queries) pairs
    FOR each testCase in testCases
        PRINT test case details
        SET adjList to createGraph(testCase.n, testCase.edges)
        FOR each query [u, v] in testCase.queries
            CALL getEdgeWeight(adjList, u, v)
            PRINT query result
        ENDFOR
        PRINT graph using toString
    ENDFOR
ENDFUNCTION

Algorithm Steps

1. Define an Edge class with: a. destination (integer for the target vertex). b. weight (integer for the edge weight).
2. Modify createGraph: a. Create a HashMap adjList mapping vertices to lists of Edge objects. b. Initialize empty lists for vertices 0 to n-1. c. For each edge [u, v, weight], add Edge(v, weight) to u’s list and Edge(u, weight) to v’s list.
3. Define getEdgeWeight: a. Search u’s adjacency list for an edge with destination v. b. Return the weight if found, else -1.
4. Define toString: a. Convert adjacency list to a string, e.g., "{0=[(1, 5)], 1=[(0, 5), (2, 3)], ...}".
5. In main, test with: a. A graph with weighted edges and valid/invalid queries. b. An empty graph. c. A single-vertex graph. d. A graph with a single edge.

Java Implementation

import java.util.*;

public class WeightedGraphExtension {
    // Edge class to store destination and weight
    static class Edge {
        int destination;
        int weight;

        Edge(int destination, int weight) {
            this.destination = destination;
            this.weight = weight;
        }

        @Override
        public String toString() {
            return "(" + destination + ", " + weight + ")";
        }
    }

    // Creates adjacency list representation with weighted edges
    private Map<Integer, List<Edge>> createGraph(int n, int[][] edges) {
        Map<Integer, List<Edge>> adjList = new HashMap<>();
        for (int i = 0; i < n; i++) {
            adjList.put(i, new ArrayList<>());
        }
        for (int[] edge : edges) {
            int u = edge[0], v = edge[1], weight = edge[2];
            adjList.get(u).add(new Edge(v, weight));
            adjList.get(v).add(new Edge(u, weight)); // Undirected graph
        }
        return adjList;
    }

    // Retrieves the weight of edge (u, v)
    public int getEdgeWeight(Map<Integer, List<Edge>> adjList, int u, int v) {
        List<Edge> edges = adjList.getOrDefault(u, new ArrayList<>());
        for (Edge edge : edges) {
            if (edge.destination == v) {
                return edge.weight;
            }
        }
        return -1; // Edge not found
    }

    // Converts graph to string (adjacency list)
    public String toString(Map<Integer, List<Edge>> adjList) {
        StringBuilder result = new StringBuilder("Adjacency List: {");
        List<Integer> vertices = new ArrayList<>(adjList.keySet());
        Collections.sort(vertices); // For consistent output
        for (int i = 0; i < vertices.size(); i++) {
            int vertex = vertices.get(i);
            result.append(vertex).append("=[");
            List<Edge> edges = adjList.get(vertex);
            for (int j = 0; j < edges.size(); j++) {
                result.append(edges.get(j));
                if (j < edges.size() - 1) {
                    result.append(", ");
                }
            }
            result.append("]");
            if (i < vertices.size() - 1) {
                result.append(", ");
            }
        }
        result.append("}");
        return result.toString();
    }

    // Helper class for test cases
    static class TestCase {
        int n;
        int[][] edges;
        int[][] queries;

        TestCase(int n, int[][] edges, int[][] queries) {
            this.n = n;
            this.edges = edges;
            this.queries = queries;
        }
    }

    // Main method to test weighted graph
    public static void main(String[] args) {
        WeightedGraphExtension graph = new WeightedGraphExtension();

        // Test cases
        TestCase[] testCases = {
            // Graph with weighted edges
            new TestCase(
                4,
                new int[][]{{0, 1, 5}, {1, 2, 3}, {2, 3, 7}},
                new int[][]{{0, 1}, {1, 3}}
            ),
            // Empty graph
            new TestCase(
                0,
                new int[][]{},
                new int[][]{{0, 1}}
            ),
            // Single vertex
            new TestCase(
                1,
                new int[][]{},
                new int[][]{{0, 0}}
            ),
            // Single edge
            new TestCase(
                2,
                new int[][]{{0, 1, 10}},
                new int[][]{{0, 1}, {1, 0}}
            )
        };

        // Run test cases
        for (int i = 0; i < testCases.length; i++) {
            System.out.println("Test case " + (i + 1) + ":");
            System.out.println("Vertices: " + testCases[i].n);
            System.out.println("Edges: " + Arrays.deepToString(testCases[i].edges));
            Map<Integer, List<Edge>> adjList = graph.createGraph(testCases[i].n, testCases[i].edges);
            System.out.println("Added edges successfully");
            System.out.println("Queries:");
            for (int[] query : testCases[i].queries) {
                int u = query[0], v = query[1];
                int weight = graph.getEdgeWeight(adjList, u, v);
                System.out.println("Weight(" + u + ", " + v + ") = " + weight);
            }
            System.out.println(graph.toString(adjList) + "\n");
        }
    }
}

Output

Running the main method produces:

Test case 1:
Vertices: 4
Edges: [[0, 1, 5], [1, 2, 3], [2, 3, 7]]
Added edges successfully
Queries:
Weight(0, 1) = 5
Weight(1, 3) = -1
Adjacency List: {0=[(1, 5)], 1=[(0, 5), (2, 3)], 2=[(1, 3), (3, 7)], 3=[(2, 7)]}

Test case 2:
Vertices: 0
Edges: []
Added edges successfully
Queries:
Weight(0, 1) = -1
Adjacency List: {}

Test case 3:
Vertices: 1
Edges: []
Added edges successfully
Queries:
Weight(0, 0) = -1
Adjacency List: {0=[]}

Test case 4:
Vertices: 2
Edges: [[0, 1, 10]]
Added edges successfully
Queries:
Weight(0, 1) = 10
Weight(1, 0) = 10
Adjacency List: {0=[(1, 10)], 1=[(0, 10)]}

Explanation:

• Test case 1: Edge (0, 1) has weight 5; edge (1, 3) doesn’t exist.
• Test case 2: Empty graph, no edges, weight query returns -1.
• Test case 3: Single vertex, no edges, weight query returns -1.
• Test case 4: Single edge (0, 1) with weight 10, both directions return 10.

How It Works

• Edge: Stores destination vertex and weight.
• createGraph: Builds an adjacency list mapping vertices to lists of Edge objects, adding undirected edges (u→v, v→u) with weights.
• getEdgeWeight: Searches u’s adjacency list for v, returns weight or -1 if not found.
• toString: Formats adjacency list with edge weights, sorting vertices for consistency.
• Example Trace (Test case 1):
  • Add edges: (0, 1, 5), (1, 2, 3), (2, 3, 7).
  • Query (0, 1): Find edge (1, 5) in 0’s list, return 5.
  • Query (1, 3): No edge to 3 in 1’s list, return -1.
• Main Method: Tests graph with weighted edges, empty graph, single vertex, and single edge.

Complexity Analysis Table

Note:

• n is the number of vertices, e is the number of edges, degree(u) is the number of neighbors of vertex u.
• Time complexity: O(n + e) for createGraph (initialize lists and add edges); O(degree(u)) average for getEdgeWeight (search u’s list); O(n log n + e) for toString (sorting vertices).
• Space complexity: O(n + e) for createGraph and toString (adjacency list); O(1) for getEdgeWeight (no additional storage).
• Worst case: O(n + e) time and space for dense graphs; O(n) for getEdgeWeight in dense graphs.

✅ Tip: Use a custom Edge class to store destination and weight, making it easy to extend the adjacency list for weighted graphs. Ensure undirected edges are added bidirectionally.

⚠ Warning: Validate vertex indices in queries to avoid accessing undefined adjacency lists. Handle non-existent edges by returning -1 to indicate no connection.