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

/** Gets an unvisited neighbor, if any, of this vertex.
@return either a vertex that is an unvisited neighbor or null
if no such neighbor exists */
public VertexInterface<T> getUnvisitedNeighbor();

/** Records the previous vertex on a path to this vertex.
@param predecessor the vertex previous to this one along a path

*/
public void setPredecessor(VertexInterface<T> predecessor);

/** Gets the recorded predecessor of this vertex.
@return either this vertex's predecessor or null if no predecessor
was recorded */
public VertexInterface<T> getPredecessor();

/** Sees whether a predecessor was recorded.
@return true if a predecessor was recorded for this vertex */
public boolean hasPredecessor();

/** Records the cost of a path to this vertex.
@param newCost the cost of the path */
public void setCost( double newCost);

/** Gets the recorded cost of the path to this vertex.
@return the cost of the path */
public double getCost();
} // end VertexInterface

The Inner Class Edge
29.10

As we mentioned, we will place instances of the class Edge in a vertex's adjacency list to indicate
the edges that originate at the vertex. Thus, each edge must record both the vertex that ends it and
the edge's weight, if any. Recording an edge weight is the only reason we need a class of edges. For
unweighted graphs, we could simply place vertices in the adjacency list. Using edge objects, how-
ever, allows us to use one class of vertices for both weighted and unweighted graphs.
Since Vertex is the only class that uses Edge , we make Edge an inner class of Vertex . Listing 29-2
shows an implementation of Edge . We provide a data field for an edge's weight, if any. For unweighted
graphs, we will set this field to zero rather than creating a class of unweighted edges.

LISTING 29-2

The protected class Edge , as an inner class of Vertex

protected class Edge
{

private VertexInterface<T> vertex; // end vertex
private double weight;