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

visited = false ;
previousVertex = null ;
cost = 0;
} // end constructor

< Implementations of the vertex operations go here. >
. . .

protected class Edge
{

< See Listing 29-2. >
} // end Edge
} // end Vertex

Note: The data fields of the class Vertex facilitate the implementation of the algorithms
presented in the previous chapter. For example, the fields previousVertex and cost are use-
ful in a breadth-first search for the cheapest path from one vertex to another.

29.12

The two connect methods. Each method connect places an edge into a vertex's adjacency list. We
first implement the method for weighted graphs and then use it to implement the method for
unweighted graphs. Preventing the addition of an edge that either exists in the graph already or con-
nects a vertex with itself consumes most of the method's effort. Once those details are complete,
connect simply calls the ADT list's add method to add the edge.

public boolean connect(VertexInterface<T> endVertex, double edgeWeight)
{

boolean result = false ;
if (! this .equals(endVertex))
{ // vertices are distinct
Iterator<VertexInterface<T>> neighbors = this .getNeighborIterator();
boolean duplicateEdge = false ;
while (!duplicateEdge && neighbors.hasNext())
{

VertexInterface<T> nextNeighbor = neighbors.next();
if (endVertex.equals(nextNeighbor))
duplicateEdge = true ;
} // end while
if (!duplicateEdge)
{

edgeList.add( new Edge(endVertex, edgeWeight));
result = true ;
} // end if
} // end if
return result;
} // end connect
public boolean connect(VertexInterface<T> endVertex)
{

return connect(endVertex, 0);
} // end connect