jdsl.graph.algo
Class FindCycleDFS

java.lang.Object
  |
  +--jdsl.graph.algo.DFS
        |
        +--jdsl.graph.algo.FindCycleDFS

public class FindCycleDFS
extends DFS

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.

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_
 
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

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.
Constructor Detail

FindCycleDFS

public FindCycleDFS()
Simple constructor initializes instance variables.
Method Detail

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.

interestingIncidentEdges

protected EdgeIterator interestingIncidentEdges(Vertex v)
This method tells the DFS which graph edges to check. This one chooses all of them
Overrides:
interestingIncidentEdges in class DFS
Parameters:
v - - the Vertex to which the edges must be incident.