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

We can now look at the main methods. The getVertex method is shown
in Figure 14.9. We consult the map to get the Vertex entry. If the Vertex
does not exist, we create a new Vertex and update the map. The addEdge
method, shown in Figure 14.10 is short. We get the corresponding Vertex
entries and then update an adjacency list.

Edges are added
by insertions in the
appropriate adja-
cency list.

The members that are eventually computed by the shortest-path algo-
rithm are initialized by the routine clearAll , shown in Figure 14.11. The
next routine, printPath , prints a shortest path after the computation has
been performed. As we mentioned earlier, we can use the prev member to
trace back the path, but doing so gives the path in reverse order. This order
is not a problem if we use recursion: The vertices on the path to dest are
the same as those on the path to dest 's previous vertex (on the path), fol-
lowed by dest . This strategy translates directly into the short recursive
routine shown in Figure 14.12, assuming of course that a path actually
exists. The printPath routine, shown in Figure 14.13, performs this check
first and then prints a message if the path does not exist. Otherwise, it calls
the recursive routine and outputs the cost of the path.

The clearAll rou-
tine clears out the
data members so
that the shortest
path algorithms
can begin.

The printPath rou-
tine prints the
shortest path after
the algorithm has
run.

1 /**
2 * If vertexName is not present, add it to vertexMap.
3 * In either case, return the Vertex.
4 */
5 private Vertex getVertex( String vertexName )
6 {
7 Vertex v = vertexMap.get( vertexName );
8 if( v == null )
9 {
10 v = new Vertex( vertexName );
11 vertexMap.put( vertexName, v );
12 }
13 return v;
14 }

figure 14.9
The getVertex routine
returns the Vertex
object that represents
vertexName , creating
the object if it needs
to do so

1 /**
2 * Add a new edge to the graph.
3 */
4 public void addEdge( String sourceName, String destName, double cost )
5 {
6 Vertex v = getVertex( sourceName );
7 Vertex w = getVertex( destName );
8 v.adj.add( new Edge( w, cost ) );
9 }

figure 14.10
Add an edge to the graph