WEIGHTED GRAPHS AND APPLICATIONS - Introduction to Java Programming: Comprehensive Version - page 1066

«interface»
Graph<V>

AbstractGraph<V>

WeightedGraph<V>

+WeightedGraph()
+WeightedGraph(vertices: V[], edges: int[][])

Constructs an empty graph.
Constructs a weighted graph with the specified edges and the
number of vertices in arrays.
Constructs a weighted graph with the specified edges and the
number of vertices.
Constructs a weighted graph with the specified edges in an
array and the number of vertices.
Constructs a weighted graph with the specified edges in a list
and the number of vertices.
Displays all edges and weights.
Returns the weight on the edge from u to v. Throw an
exception if the edge does not exist.
Adds a weighted edge to the graph and throws an
IllegalArgumentException if u, v, or w is invalid. If
(u, v) is already in the graph, the new weight is set.
Returns a minimum spanning tree starting from vertex 0.
Returns a minimum spanning tree starting from vertex v .
Returns all single-source shortest paths.

+WeightedGraph(vertices: List<V>, edges:
List<WeightedEdge>)
+WeightedGraph(edges: int[][],
numberOfVertices: int)
+WeightedGraph(edges: List<WeightedEdge>,
numberOfVertices: int)
+printWeightedEdges(): void
+getWeight(int u, int v): double

+addEdges(u: int, v: int, weight: double): void

+getMinimumSpanningTree(): MST
+getMinimumSpanningTree(index: int): MST
+getShortestPath(index: int): ShortestPathTree

F IGURE 29.4

WeightedGraph extends AbstractGraph .

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.

L ISTING 29.2

WeightedGraph.java
1 import java.util.*;
2
3 public class WeightedGraph<V> extends AbstractGraph<V> {
4 /** Construct an empty */
5 public WeightedGraph() {
6 }
7
8 /** Construct a WeightedGraph from vertices and edged in arrays */
9 public WeightedGraph(V[] vertices, int [][] edges) {
10 createWeightedGraph(java.util.Arrays.asList(vertices), edges);
11 }
12
13 /** Construct a WeightedGraph from vertices and edges in list */
14 public WeightedGraph( int [][] edges, int numberOfVertices) {
15 List<V> vertices = new ArrayList<>();
16 for ( int i = 0 ; i < numberOfVertices; i++)
17 vertices.add((V)( new Integer(i)));
18
19 createWeightedGraph(vertices, edges);
20 }
21

no-arg constructor

constructor

constructor