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

1 // Represents an edge in the graph.
2 class Edge
3 {
4 public Vertex dest; // Second vertex in Edge
5 public double cost; // Edge cost
6
7 public Edge( Vertex d, double c )
8 {
9 dest = d;
10 cost = c;
11 }
12 }

figure 14.6
The basic item stored
in an adjacency list

1 // Represents a vertex in the graph.
2 class Vertex
3 {
4 public String name; // Vertex name
5 public List<Edge> adj; // Adjacent vertices
6 public double dist; // Cost
7 public Vertex prev; // Previous vertex on shortest path
8 public int scratch;// Extra variable used in algorithm
9
10 public Vertex( String nm )
11 { name = nm; adj = new LinkedList<Edge>( ); reset( ); }
12
13 public void reset( )
14

figure 14.7
The Vertex class
stores information for
each vertex

{ dist = Graph.INFINITY; prev = null; pos = null; scratch = 0; }

15 }

Everything else follows from our preceding description. The reset method
is used to initialize the (shaded) data members that are computed by the
shortest-path algorithms; it is called when a shortest-path computation is
restarted.
We are now ready to examine the Graph class skeleton, which is shown
in Figure 14.8. The vertexMap field stores the map. The rest of the class pro-
vides methods that perform initialization, add vertices and edges, print the
shortest path, and perform various shortest-path calculations. We discuss
each routine when we examine its implementation.
First, we consider the constructor. The default creates an empty map
via field initialization; that works, so we accept it.