edu.gwu.algtest
Interface DirectedGraphSearchAlgorithm
- All Superinterfaces:
- Algorithm, UndirectedGraphSearchAlgorithm
- public interface DirectedGraphSearchAlgorithm
- extends UndirectedGraphSearchAlgorithm
Algorithms that traverse a directed graph implement interface
DirectedGraphSearchAlgorithm.
Not all methods need to be implemented to make a graph search algorithm useful.
Often the most important method is the one that returns the number of connected
components (using depth-first search). Before calling any of the methods, the
initialize method is called with the number of vertices.
Next, the insert method is called repeatedly until all edges are given
to the algorithm, analogous to the insert operation of a data structure.
NOTE: the number of edges is not given to the algorithm at
the time of initialization. After the all edges are inserted, one or more
of the other methods are called.
Next, observe that adjacency lists don't often specify the order in which
vertices appear in any particular vertex list. We will use the term "standard ordering"
for the ordering where newly inserted vertices are always added to the rear of
the appropriate list. This will make the adjacency list representation unique
for a particular set of insertions.
RELATIONSHIP WITH UndirectedGraphSearchAlgorithm:
DirectedGraphSearchAlgorithm extends the interface for
undirected-graph algorithm. All inherited methods make sense except
insertUndirectedEdge; for this method, a directed-graph algorithm
can simply report an error. To return the number of connected components (but not
strongly-connected, treat the edges as undirected).
|
Method Summary |
void |
insertDirectedEdge(int startVertex,
int endVertex,
double weight)
insertDirectedEdge is called with the endpoints of the edge
to be added. |
int |
numStronglyConnectedComponents()
numStronglyConnectedComponents should return
the number of strongly-connected components in a directed graph. |
int[] |
strongComponentLabels()
strongComponentLabels should return the component label
for each vertex for an undirected graph. |
| Methods inherited from interface edu.gwu.algtest.UndirectedGraphSearchAlgorithm |
articulationEdges, articulationVertices, breadthFirstVisitOrder, componentLabels, depthFirstCompletionOrder, depthFirstVisitOrder, existsCycle, existsOddCycle, initialize, insertUndirectedEdge, numConnectedComponents |
insertDirectedEdge
public void insertDirectedEdge(int startVertex,
int endVertex,
double weight)
insertDirectedEdge is called with the endpoints of the edge
to be added. The algorithm should treat this as a single directed edge.
Thus, a call with startVertex=0 and endVertex=1
indicates a directed edge from node 0 to node 1. It is possible that
a future call will include startVertex=1 and endVertex=0
if there is to be a directed edge going the other way. Thus, in this case,
only a single entry is made in an adjacency-list or matrix representation.
Note: we will allow self-loops to be input, i.e., an edge from a vertex to itself.
If the graph is not specified as a weighted graph, the weight parameter can
ignored.
- Parameters:
startVertex - an int valueendVertex - an int valueweight - a double value
numStronglyConnectedComponents
public int numStronglyConnectedComponents()
numStronglyConnectedComponents should return
the number of strongly-connected components in a directed graph.
- Returns:
- an
int value
strongComponentLabels
public int[] strongComponentLabels()
strongComponentLabels should return the component label
for each vertex for an undirected graph.
When the call int[] compLabels = alg.strongComponentLabels()
(where alg is the algorithm instance) is made,
compLabels[i] is the component to which vertex i belongs.
The component numbering should start at 0. If insertions are done properly,
the component labelling will be unique.
- Returns:
- an
int[] value