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

29.19

Testing for an edge. The method hasEdge begins like addEdge , by locating the two vertices that
define the desired edge. With the origin vertex in hand, hasEdge invokes Vertex 's method
getNeighborIterator and searches the origin's adjacency list for the desired edge. In the follow-
ing implementation, you can see why defining the equals method in Vertex is important.

public boolean hasEdge(T begin, T end)
{

boolean found = false ;
VertexInterface<T> beginVertex = vertices.getValue(begin);
VertexInterface<T> endVertex = vertices.getValue(end);
if ( (beginVertex != null ) && (endVertex != null ) )
{

Iterator<VertexInterface<T>> neighbors =
beginVertex.getNeighborIterator();
while (!found && neighbors.hasNext())
{

VertexInterface<T> nextNeighbor = neighbors.next();
if (endVertex.equals(nextNeighbor))
found = true ;
} // end while
} // end if
return found;
} // end hasEdge

29.20

Miscellaneous methods. The methods isEmpty , clear , getNumberOfVertices , and getNumber -
OfEdges have the following simple implementations:

public boolean isEmpty()
{

return vertices.isEmpty();
} // end isEmpty
public void clear()
{

vertices.clear();
edgeCount = 0;
} // end clear
public int getNumberOfVertices()
{

return vertices.getSize();
} // end getNumberOfVertices
public int getNumberOfEdges()
{

return edgeCount;
} // end getNumberOfEdges

29.21

Resetting vertices. You saw in Segment 29.11 that the class Vertex has the data fields visited ,
previousVertex , and cost . These fields are necessary for the implementation of the graph algo-
rithms that we introduced in the previous chapter. Once you have searched a graph for a shortest
path, for example, many of the vertices will have been visited and marked accordingly. Before you
could perform a topological sort on the same graph, you would have to reset the field visited for
each vertex in the graph.
The following method resetVertices sets the fields visited , previousVertex , and
cost to their initial values. To do so, the method uses one of the iterators declared in the