Java Reference
In-Depth Information
public class DirectedGraph<T> implements GraphInterface<T>
{
private DictionaryInterface<T, VertexInterface<T>> vertices;
private int edgeCount;
public DirectedGraph()
{
vertices = new LinkedDictionary<T, VertexInterface<T>>();
edgeCount = 0;
} // end default constructor
< Implementations of the graph operations go here. >
. . .
} // end DirectedGraph
29.17
Adding vertices. The method addVertex uses Vertex's constructor to create a new vertex. It then
adds the vertex to the dictionary by invoking the dictionary's method add :
public boolean addVertex(T vertexLabel)
{
VertexInterface<T> isDuplicate =
vertices.add(vertexLabel, new Vertex(vertexLabel));
return isDuplicate == null ; // was add to dictionary successful?
} // end addVertex
Notice that vertexLabel is the search key for the dictionary entry, and the new vertex is the associ-
ated value. Recall from the interface in Segment 19.4 of Chapter 19 that add returns null if the addi-
tion to the dictionary is successful. We use this fact to determine the return value for addVertex .
29.18
Adding edges. Methods such as addEdge that identify an existing vertex by its label must locate the ver-
tex within the dictionary vertices . To do this, they invoke the dictionary method getValue , using the
vertex label as the search key. Having located the two vertices that delineate the edge to be added, add-
Edge adds an edge to the adjacency list of the origin vertex. It does this by invoking Vertex 's connect
method. If the edge is added successfully, edgeCount is incremented. Thus, our graph's addEdge meth-
ods have the following definitions, one for weighted graphs and one for unweighted graphs:
public boolean addEdge(T begin, T end, double edgeWeight)
{
boolean result = false ;
VertexInterface<T> beginVertex = vertices.getValue(begin);
VertexInterface<T> endVertex = vertices.getValue(end);
if ( (beginVertex != null ) && (endVertex != null ) )
result = beginVertex.connect(endVertex, edgeWeight);
if (result)
edgeCount++;
return result;
} // end addEdge
public boolean addEdge(T begin, T end)
{
return addEdge(begin, end, 0);
} // end addEdge
Search WWH ::




Custom Search