|
||||||||||
PREV CLASS NEXT CLASS | FRAMES NO FRAMES | |||||||||
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD |
java.lang.Objectnz.ac.waikato.jdsl.graph.algo.DFS
nz.ac.waikato.jdsl.graph.algo.DirectedDFS
nz.ac.waikato.jdsl.graph.algo.DirectedFindCycleDFS
public class DirectedFindCycleDFS
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.
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 nz.ac.waikato.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 | |
---|---|
DirectedFindCycleDFS()
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 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 nz.ac.waikato.jdsl.graph.algo.DirectedDFS |
---|
interestingIncidentEdges |
Methods inherited from class nz.ac.waikato.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 DirectedFindCycleDFS()
Method Detail |
---|
public void execute(InspectableGraph g, Vertex start)
DFS
execute
in class 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()
|
||||||||||
PREV CLASS NEXT CLASS | FRAMES NO FRAMES | |||||||||
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD |