Paul NgugiThe WeightedGraph class extends AbstractGraph.
The preceding chapter designed the Graph interface, the AbstractGraph class, and the UnweightedGraph class for modeling graphs. Following this pattern, we design WeightedGraph as a subclass of AbstractGraph, as shown in Figure below.
WeightedGraph simply extends AbstractGraph with five constructors for creating concrete WeightedGraph instances. WeightedGraph inherits all methods from AbstractGraph, overrides the clear and addVertex methods, implements a new addEdge method for adding a weighted edge, and also introduces new methods for obtaining minimum spanning trees and for finding all single-source shortest paths. Minimum spanning trees and shortest paths will be introduced in Sections Minimum spanning trees and shortest paths, respectively.
The code below implements WeightedGraph. Edge adjacency lists (lines 38–63) are used internally to store adjacent edges for a vertex. When a WeightedGraph is constructed, its edge adjacency lists are created (lines 47 and 57). The methods getMinimumSpanningTree() (lines 99–138) and getShortestPath() (lines 156–197) will be introduced in upcoming sections.
package demo;
import java.util.*;
public class WeightedGraph<V> extends AbstractGraph<V> {
/** Construct an empty */
public WeightedGraph() {}
/** Construct a WeightedGraph from vertices and edged in arrays */
public WeightedGraph(V[] vertices, int[][] edges) {
createWeightedGraph(java.util.Arrays.asList(vertices), edges);
}
/** Construct a WeightedGraph from vertices and edges in list */
public WeightedGraph(int[][] edges, int numberOfVertices) {
List<V> vertices = new ArrayList<>();
for (int i = 0; i < numberOfVertices; i++)
vertices.add((V)(new Integer(i)));
createWeightedGraph(vertices, edges);
}
/** Construct a WeightedGraph for vertices 0, 1, 2 and edge list */
public WeightedGraph(List<V> vertices, List<WeightedEdge> edges) {
createWeightedGraph(vertices, edges);
}
/** Construct a WeightedGraph from vertices 0, 1, and edge array */
public WeightedGraph(List<WeightedEdge> edges, int numberOfVertices) {
List<V> vertices = new ArrayList<>();
for (int i = 0; i < numberOfVertices; i++)
vertices.add((V)(new Integer(i)));
createWeightedGraph(vertices, edges);
}
/** Create adjacency lists from edge arrays */
private void createWeightedGraph(List<V> vertices, int[][] edges) {
this.vertices = vertices;
for (int i = 0; i < vertices.size(); i++) {
neighbors.add(new ArrayList<Edge>()); // Create a list for vertices
}
for (int i = 0; i < edges.length; i++) {
neighbors.get(edges[i][0]).add(new WeightedEdge(edges[i][0], edges[i][1], edges[i][2]));
}
}
/** Create adjacency lists from edge lists */
private void createWeightedGraph(List<V> vertices, List<WeightedEdge> edges) {
this.vertices = vertices;
for (int i = 0; i < vertices.size(); i++) {
neighbors.add(new ArrayList<Edge>()); // Create a list for vertices
}
for (WeightedEdge edge: edges) {
neighbors.get(edge.u).add(edge); // Add an edge into the list
}
}
/** Return the weight on the edge (u, v) */
public double getWeight(int u, int v) throws Exception {
for (Edge edge : neighbors.get(u)) {
if (edge.v == v) {
return ((WeightedEdge)edge).weight;
}
}
throw new Exception("Edge does not exit");
}
/** Display edges with weights */
public void printWeightedEdges() {
for (int i = 0; i < getSize(); i++) {
System.out.print(getVertex(i) + " (" + i + "): ");
for (Edge edge : neighbors.get(i)) {
System.out.print("(" + edge.u + ", " + edge.v + ", " + ((WeightedEdge)edge).weight + ") ");
}
System.out.println();
}
}
/** Add edges to the weighted graph */
public boolean addEdge(int u, int v, double weight) {
return addEdge(new WeightedEdge(u, v, weight));
}
/** Get a minimum spanning tree rooted at vertex 0 */
public MST getMinimumSpanningTree() {
return getMinimumSpanningTree(0);
}
/** Get a minimum spanning tree rooted at a specified vertex */
public MST getMinimumSpanningTree(int startingVertex) {
// cost[v] stores the cost by adding v to the tree
double[] cost = new double[getSize()];
for (int i = 0; i < cost.length; i++) {
cost[i] = Double.POSITIVE_INFINITY; // Initial cost
}
cost[startingVertex] = 0; // Cost of source is 0
int[] parent = new int[getSize()]; // Parent of a vertex
parent[startingVertex] = -1; // startingVertex is the root
double totalWeight = 0; // Total weight of the tree thus far
List<Integer> T = new ArrayList<>();
// Expand T
while (T.size() < getSize()) {
// Find smallest cost v in V - T
int u = -1; // Vertex to be determined
double currentMinCost = Double.POSITIVE_INFINITY;
for (int i = 0; i < getSize(); i++) {
if (!T.contains(i) && cost[i] < currentMinCost) {
currentMinCost = cost[i];
u = i;
}
}
T.add(u); // Add a new vertex to T
totalWeight += cost[u]; // Add cost[u] to the tree
// Adjust cost[v] for v that is adjacent to u and v in V - T
for (Edge e : neighbors.get(u)) {
if (!T.contains(e.v) && cost[e.v] > ((WeightedEdge)e).weight) {
cost[e.v] = ((WeightedEdge)e).weight;
parent[e.v] = u;
}
}
} // End of while
return new MST(startingVertex, parent, T, totalWeight);
}
/** MST is an inner class in WeightedGraph */
public class MST extends Tree {
private double totalWeight; // Total weight of all edges in the tree
public MST(int root, int[] parent, List<Integer> searchOrder, double totalWeight) {
super(root, parent, searchOrder);
this.totalWeight = totalWeight;
}
public double getTotalWeight() {
return totalWeight;
}
}
/** Find single source shortest paths */
public ShortestPathTree getShortestPath(int sourceVertex) {
// cost[v] stores the cost of the path from v to the source
double[] cost = new double[getSize()];
for (int i = 0; i < cost.length; i++) {
cost[i] = Double.POSITIVE_INFINITY; // Initial cost set to infinity
}
cost[sourceVertex] = 0; // Cost of source is 0
// parent[v] stores the previous vertex of v in the path
int[] parent = new int[getSize()];
parent[sourceVertex] = -1; // The parent of source is set to -1
// T stores the vertices whose path found so far
List<Integer> T = new ArrayList<>();
// Expand T
while (T.size() < getSize()) {
// Find smallest cost v in V - T
int u = -1; // Vertex to be determined
double currentMinCost = Double.POSITIVE_INFINITY;
for (int i = 0; i < getSize(); i++) {
if (!T.contains(i) && cost[i] < currentMinCost) {
currentMinCost = cost[i];
u = i;
}
}
T.add(u); // Add a new vertex to T
// Adjust cost[v] for v that is adjacent to u and v in V - T
for (Edge e : neighbors.get(u)) {
if (!T.contains(e.v) && cost[e.v] > cost[u] + ((WeightedEdge)e).weight) {
cost[e.v] = cost[u] + ((WeightedEdge)e).weight;
parent[e.v] = u;
}
}
} // End of while
// Create a ShortestPathTree
return new ShortestPathTree(sourceVertex, parent, T, cost);
}
/** ShortestPathTree is an inner class in WeightedGraph */
public class ShortestPathTree extends Tree {
private double[] cost; // cost[v] is the cost from v to source
/** Construct a path */
public ShortestPathTree(int source, int[] parent, List<Integer> searchOrder, double[] cost) {
super(source, parent, searchOrder);
this.cost = cost;
}
/** Return the cost for a path from the root to vertex v */
public double getCost(int v) {
return cost[v];
}
/** Print paths from all vertices to the source */
public void printAllPaths() {
System.out.println("All shortest paths from " + vertices.get(getRoot()) + " are:");
for (int i = 0; i < cost.length; i++) {
printPath(i); // Print a path from i to the source
System.out.println("(cost: " + cost[i] + ")"); // Path cost
}
}
}
}
The WeightedGraph class extends the AbstractGraph class (line 3). The properties vertices and neighbors in AbstractGraph are inherited in WeightedGraph.neighbors is a list. Each element is the list is another list that contains edges. For unweighted graph, each edge is an instance of AbstractGraph.Edge. For a weighted graph, each edge is an instance of WeightedEdge. WeightedEdge is a subtype of Edge. So you can add a weighted edge into neighbors.get(i) for a weighted graph (line 47).
The code below gives a test program that creates a graph for the one in Figure below and another graph for the one in Figure below a.
package demo;
public class TestWeightedGraph {
public static void main(String[] args) {
String[] vertices = {"Seattle", "San Francisco", "Los Angeles", "Denver", "Kansas City", "Chicago", "Boston", "New York", "Atlanta", "Miami", "Dallas", "Houston"};
int[][] edges = {
{0, 1, 807}, {0, 3, 1331}, {0, 5, 2097},
{1, 0, 807}, {1, 2, 381}, {1, 3, 1267},
{2, 1, 381}, {2, 3, 1015}, {2, 4, 1663}, {2, 10, 1435},
{3, 0, 1331}, {3, 1, 1267}, {3, 2, 1015}, {3, 4, 599}, {3, 5, 1003},
{4, 2, 1663}, {4, 3, 599}, {4, 5, 533}, {4, 7, 1260}, {4, 8, 864}, {4, 10, 496},
{5, 0, 2097}, {5, 3, 1003}, {5, 4, 533}, {5, 6, 983}, {5, 7, 787},
{6, 5, 983}, {6, 7, 214},
{7, 4, 1260}, {7, 5, 787}, {7, 6, 214}, {7, 8, 888},
{8, 4, 864}, {8, 7, 888}, {8, 9, 661}, {8, 10, 781}, {8, 11, 810},
{9, 8, 661}, {9, 11, 1187},
{10, 2, 1435}, {10, 4, 496}, {10, 8, 781}, {10, 11, 239},
{11, 8, 810}, {11, 9, 1187}, {11, 10, 239}
};
WeightedGraph<String> graph1 = new WeightedGraph<>(vertices, edges);
System.out.println("The number of vertices in graph1: " + graph1.getSize());
System.out.println("The vertex with index 1 is " + graph1.getVertex(1));
System.out.println("The index for Miami is " + graph1.getIndex("Miami"));
System.out.println("The edges for graph1:");
graph1.printWeightedEdges();
edges = new int[][] {
{0, 1, 2}, {0, 3, 8},
{1, 0, 2}, {1, 2, 7}, {1, 3, 3},
{2, 1, 7}, {2, 3, 4}, {2, 4, 5},
{3, 0, 8}, {3, 1, 3}, {3, 2, 4}, {3, 4, 6},
{4, 2, 5}, {4, 3, 6}
};
WeightedGraph<Integer> graph2 = new WeightedGraph<>(edges, 5);
System.out.println("\nThe edges for graph2:");
graph2.printWeightedEdges();
}
}
The number of vertices in graph1: 12
The vertex with index 1 is San Francisco
The index for Miami is 9
The edges for graph1:
Vertex 0: (0, 1, 807) (0, 3, 1331) (0, 5, 2097)
Vertex 1: (1, 2, 381) (1, 0, 807) (1, 3, 1267)
Vertex 2: (2, 1, 381) (2, 3, 1015) (2, 4, 1663) (2, 10, 1435)
Vertex 3: (3, 4, 599) (3, 5, 1003) (3, 1, 1267)
(3, 0, 1331) (3, 2, 1015)
Vertex 4: (4, 10, 496) (4, 8, 864) (4, 5, 533) (4, 2, 1663)
(4, 7, 1260) (4, 3, 599)
Vertex 5: (5, 4, 533) (5, 7, 787) (5, 3, 1003)
(5, 0, 2097) (5, 6, 983)
Vertex 6: (6, 7, 214) (6, 5, 983)
Vertex 7: (7, 6, 214) (7, 8, 888) (7, 5, 787) (7, 4, 1260)
Vertex 8: (8, 9, 661) (8, 10, 781) (8, 4, 864)
(8, 7, 888) (8, 11, 810)
Vertex 9: (9, 8, 661) (9, 11, 1187)
Vertex 10: (10, 11, 239) (10, 4, 496) (10, 8, 781) (10, 2, 1435)
Vertex 11: (11, 10, 239) (11, 9, 1187) (11, 8, 810)
The edges for graph2:
Vertex 0: (0, 1, 2) (0, 3, 8)
Vertex 1: (1, 0, 2) (1, 2, 7) (1, 3, 3)
Vertex 2: (2, 3, 4) (2, 1, 7) (2, 4, 5)
Vertex 3: (3, 1, 3) (3, 4, 6) (3, 2, 4) (3, 0, 8)
Vertex 4: (4, 2, 5) (4, 3, 6)
The program creates graph1 for the graph in Figure above in lines 3–27. The vertices for graph1 are defined in lines 3–5. The edges for graph1 are defined in lines 7–24. The edges are represented using a two-dimensional array. For each row i in the array, edges[i][0] and edges[i][1] indicate that there is an edge from vertex edges[i][0] to vertex edges[i][1] and the weight for the edge is edges[i][2]. For example, {0, 1, 807} (line 8) represents the edge from vertex 0 (edges[0][0]) to vertex 1 (edges[0][1]) with weight 807 (edges[0][2]). {0, 5, 2097} (line 8) represents the edge from vertex 0 (edges[2][0]) to vertex 5 (edges[2][1]) with weight 2097 (edges[2][2]). Line 35 invokes the printWeightedEdges() method on graph1 to display all edges in graph1.
The program creates the edges for graph2 for the graph in Figure above a in lines 37–44. Line 46 invokes the printWeightedEdges() method on graph2 to display all edges in graph2.
