nz.ac.waikato.jdsl.graph.algo
Class FindCycleDFS

java.lang.Object
  nz.ac.waikato.jdsl.graph.algo.DFS
      nz.ac.waikato.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:

JDSL 2.1.1

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

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

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

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.

Returns:

EdgeIterator An Iterator over interesting edges incident to the parameter Vertex