jdsl.graph.algo
Class DirectedFindCycleDFS
java.lang.Object

+jdsl.graph.algo.DFS

+jdsl.graph.algo.DirectedDFS

+jdsl.graph.algo.DirectedFindCycleDFS
 public class DirectedFindCycleDFS
 extends DirectedDFS
This class specializes DFS to determine if the connected component
of the start vertex contains a cycle and if so return it. The
algorithm creates an ObjectIterator of vertices in the cycle or an
empty ObjectIterator if there is no cycle. The ObjectIterator is
accessed via the getCycle() method.
This algorithm works specifically on directed graphs.
 Version:
 $Revision: 1.2 $, $Date: 1999/08/31 20:36:44 $
 Author:
 Natasha Gelfand, Keith Schmidt (kas)
 See Also:
DFS
Field Summary 
protected Vertex 
cycleStart_
The Vertex which has been encountered twice on one path, proving
that a cycle exists. 
protected boolean 
done_
This is set to true if a cycle is found, alerting the DFS to
finish early 
protected Sequence 
prospectiveCycle_
This stores a list of Vertices which are being checked to see if
there is a cycle among them. 
Fields inherited from class jdsl.graph.algo.DFS 
BACK_EDGE, CROSS_EDGE, EDGE_TYPE, FINISH_TIME, FORWARD_EDGE, graph_, PARENT, START_TIME, TREE_EDGE, TREE_NUMBER, treeNum_, UNSEEN, UNVISITED, VERTEX_STATUS, VISITED, VISITING, visitResult_ 
Method Summary 
void 
execute(InspectableGraph g,
Vertex start)
Runs the depth first search algorithm on a graph. 
protected void 
finishVisit(Vertex v)
Once the visit has ended, they are removed from the prospective
cyclic path. 
ObjectIterator 
getCycle()
Returns an ObjectIterator containing all of the Vertices in the
found cycle. 
protected boolean 
isDone()
Returns true iff a cycle has been found. 
protected void 
startVisit(Vertex v)
As new vertices are visited, they are added to the prospective
cyclic path. 
protected void 
traverseBackEdge(Edge e,
Vertex from)
When a back edge has been encountered, the graph has a cycle. 
Methods inherited from class jdsl.graph.algo.DFS 
cleanup, dfsVisit, execute, finishTime, isBackEdge, isCrossEdge, isForwardEdge, isTreeEdge, isUnseen, isUnvisited, isVisited, isVisiting, parent, startTime, status, traverseCrossEdge, traverseForwardEdge, traverseTreeEdge, treeNumber, type 
Methods inherited from class java.lang.Object 
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait 
prospectiveCycle_
protected Sequence prospectiveCycle_
 This stores a list of Vertices which are being checked to see if
there is a cycle among them.
done_
protected boolean done_
 This is set to true if a cycle is found, alerting the DFS to
finish early
cycleStart_
protected Vertex cycleStart_
 The Vertex which has been encountered twice on one path, proving
that a cycle exists.
DirectedFindCycleDFS
public DirectedFindCycleDFS()
 Simple constructor initializes instance variables.
execute
public void execute(InspectableGraph g,
Vertex start)
 Description copied from class:
DFS
 Runs the depth first search algorithm on a graph.
 Overrides:
execute
in class DFS
 Following copied from class:
jdsl.graph.algo.DFS
 Parameters:
g
 An InspectableGraph
on which to run a depth first
search.start
 The Vertex
at which to start the depth first
search.
startVisit
protected void startVisit(Vertex v)
 As new vertices are visited, they are added to the prospective
cyclic path.
 Overrides:
startVisit
in class DFS
finishVisit
protected void finishVisit(Vertex v)
 Once the visit has ended, they are removed from the prospective
cyclic path.
 Overrides:
finishVisit
in class DFS
traverseBackEdge
protected void traverseBackEdge(Edge e,
Vertex from)
 When a back edge has been encountered, the graph has a cycle.
 Overrides:
traverseBackEdge
in class DFS
isDone
protected boolean isDone()
 Returns true iff a cycle has been found.
 Overrides:
isDone
in class DFS
getCycle
public ObjectIterator getCycle()
 Returns an ObjectIterator containing all of the Vertices in the
found cycle.