Graphs and paths - Data Structures and Problem Solving Using Java - page 536

1 // Graph class: evaluate shortest paths.
2 //
3 // CONSTRUCTION: with no parameters.
4 //
5 // ******************PUBLIC OPERATIONS**********************
6 // void addEdge( String v, String w, double cvw )
7 // --> Add additional edge
8 // void printPath( String w ) --> Print path after alg is run
9 // void unweighted( String s ) --> Single-source unweighted
10 // void dijkstra( String s ) --> Single-source weighted
11 // void negative( String s ) --> Single-source negative weighted
12 // void acyclic( String s ) --> Single-source acyclic
13 // ******************ERRORS*********************************
14 // Some error checking is performed to make sure that graph is ok
15 // and that graph satisfies properties needed by each
16 // algorithm. Exceptions are thrown if errors are detected.
17
18 public class Graph
19 {
20 public static final double INFINITY = Double.MAX_VALUE;
21
22 public void addEdge( String sourceName, String destName, double cost )
23 { /* Figure 14.10 */ }
24 public void printPath( String destName )
25 { /* Figure 14.13 */ }
26 public void unweighted( String startName )
27 { /* Figure 14.22 */ }
28 public void dijkstra( String startName )
29 { /* Figure 14.27 */ }
30 public void negative( String startName )
31 { /* Figure 14.29 */ }
32 public void acyclic( String startName )
33 { /* Figure 14.32 */ }
34
35 private Vertex getVertex( String vertexName )
36 { /* Figure 14.9 */ }
37 private void printPath( Vertex dest )
38 { /* Figure 14.12 */ }
39 private void clearAll( )
40 { /* Figure 14.11 */ }
41
42

private Map<String,Vertex> vertexMap = new HashMap<String,Vertex>( );

43 }
44
45 // Used to signal violations of preconditions for
46 // various shortest path algorithms.
47 class GraphException extends RuntimeException
48 {
49 public GraphException( String name )
50 { super( name ); }
51 }

figure 14.8
The Graph class skeleton