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:
- JDSL 2.0.6
- 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.