Graph Implementations - Data Structures and Abstractions with Java - page 761

BinaryNode more than simple accessor and mutator operations. The same is true now for the imple-
mentation of the ADT graph. In fact, the specifications of the ADT graph that you saw in the previ-
ous chapter (Segment 28.25) omit the operations necessary to implement various graph algorithms.
We assign these operations to the vertices.
The structure of a vertex is more like the structure of a node in a general tree than the structure
of a node in a binary tree. Both the general node in Figure 24-8 and a vertex reference a list that you
use to address other nodes or vertices.

Specifying the Class Vertex
29.5

Identifying vertices. First, we need a way to identify the vertices in a graph. One simple way is to use
either integers or strings. A more general approach—the one we used in the previous chapter—labels
each vertex with an object. This label will be a data field of the class Vertex . One operation of Vertex ,
then, is to retrieve a vertex's label. We'll use the constructor to set the label, omitting a mutator method
for this field.

29.6

Visiting vertices. The algorithms that we discussed in the previous chapter required us to mark cer-
tain vertices when they were visited. We therefore give operations to Vertex that mark a vertex as
visited, test whether a vertex has been visited, and remove the mark.

29.7

The adjacency list. As we mentioned earlier in this chapter, a vertex's adjacency list indicates its
neighbors. Rather than placing this list within the class of graphs, it is more convenient to make it a
part of the class Vertex . Soon we will define a simple class Edge whose instances we will place in
these adjacency lists. Thus, a particular vertex's adjacency list contains the edges that leave the ver-
tex. Each edge indicates its weight, if any, and references the vertex that ends the edge. Vertex then
needs methods to add edges to the adjacency list. These methods essentially connect a vertex to its
neighbors.
In addition, we must provide access to the adjacency list for a given vertex. Thus, we define an
iterator that returns a vertex's neighbors, as well as an iterator that returns the weights of the edges
to those neighbors. For convenience, we also include a method to test whether a vertex has at least
one neighbor.
As you will see, the adjacency list is the only place where we need instances of Edge . Thus,
Edge is an implementation detail that we can hide within Vertex as an inner class.

29.8

Path operations. While finding a path through a graph, we must be able to locate the vertex that
comes before a given vertex on the path—in other words, the vertex's predecessor. Thus, we need
set, get, and test operations for a vertex's predecessor. Certain algorithms find the path with the
shortest length or the path that has the smallest weight, or cost. A vertex can record either the length
or the weight of the path from the origin to itself. Thus, we have operations that set and get this
recorded value.

29.9

The Java interface. The interface in Listing 29-1 specifies the vertex operations that we have just
introduced. The generic type T represents the data type of the object that labels a vertex.

LISTING 29-1

An interface for the vertices in a graph

package GraphPackage;
import java.util.Iterator;
public interface VertexInterface<T>