

PREV CLASS NEXT CLASS  FRAMES NO FRAMES  
SUMMARY: INNER  FIELD  CONSTR  METHOD  DETAIL: FIELD  CONSTR  METHOD 
java.lang.Object  +jdsl.graph.algo.DFS  +jdsl.graph.algo.FindCycleDFS
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.
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_ 
Constructor Summary  
FindCycleDFS()
Simple constructor initializes instance variables. 
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 EdgeIterator 
interestingIncidentEdges(Vertex v)
This method tells the DFS which graph edges to check. 
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 
Field Detail 
protected Sequence prospectiveCycle_
protected boolean done_
protected Vertex cycleStart_
Constructor Detail 
public FindCycleDFS()
Method Detail 
public void execute(InspectableGraph g, Vertex start)
DFS
execute
in class DFS
jdsl.graph.algo.DFS
g
 An InspectableGraph
on which to run a depth first
search.start
 The Vertex
at which to start the depth first
search.protected void startVisit(Vertex v)
startVisit
in class DFS
protected void finishVisit(Vertex v)
finishVisit
in class DFS
protected void traverseBackEdge(Edge e, Vertex from)
traverseBackEdge
in class DFS
protected boolean isDone()
isDone
in class DFS
public ObjectIterator getCycle()
protected EdgeIterator interestingIncidentEdges(Vertex v)
interestingIncidentEdges
in class DFS
v
  the Vertex to which the edges must be incident.


PREV CLASS NEXT CLASS  FRAMES NO FRAMES  
SUMMARY: INNER  FIELD  CONSTR  METHOD  DETAIL: FIELD  CONSTR  METHOD 