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