net.datastructures
Class FindCycleDFS

java.lang.Object
  net.datastructures.DFS
      net.datastructures.FindCycleDFS

public class FindCycleDFS

extends DFS

A specialization of a generic DFS used to find a cycle in a graph.

Author:

Roberto Tamassia, Michael Goodrich, Eric Zamore

Field Summary

protected List	cycle
protected Vertex	cycleStart
protected boolean	done

Fields inherited from class net.datastructures.DFS

G, STATUS, UNVISITED, VISITED, visitResult

Constructor Summary

FindCycleDFS()

Method Summary

Object	execute(Graph g, Vertex start, Object info) Executes the DFS algorithm.
protected void	finishVisit(Vertex v) Called after we finish the visit for a vertex (v).
protected boolean	isDone() Determines whether the traversal is done early.
protected void	startVisit(Vertex v) Called when we encounter a vertex (v).
protected void	traverseBack(Edge e, Vertex from) Called when we traverse a back edge (e) from a vertex (from).
protected void	traverseDiscovery(Edge e, Vertex from) Called when we traverse a discovery edge (e) from a vertex (from).

Methods inherited from class net.datastructures.DFS

dfsTraversal, init, initResult, isVisited, result, unVisit, visit

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Field Detail

cycle

protected List cycle

done

protected boolean done

cycleStart

protected Vertex cycleStart

Constructor Detail

FindCycleDFS

public FindCycleDFS()

Method Detail

execute

public Object execute(Graph g,
                      Vertex start,
                      Object info)

Executes the DFS algorithm.

Specified by:

execute in class DFS

Parameters:

g - Input graph

start - Start vertex

info - Unused variable (can be anything)

Returns:

Iterator containing an alternating sequence of vertices and edges starting and ending with the same vertex, or an empty iterator if the graph contains no cycles.

startVisit

protected void startVisit(Vertex v)

Description copied from class: DFS

Called when we encounter a vertex (v).

Overrides:

startVisit in class DFS

finishVisit

protected void finishVisit(Vertex v)

Description copied from class: DFS

Called after we finish the visit for a vertex (v).

Overrides:

finishVisit in class DFS

traverseDiscovery

protected void traverseDiscovery(Edge e,
                                 Vertex from)

Description copied from class: DFS

Called when we traverse a discovery edge (e) from a vertex (from).

Overrides:

traverseDiscovery in class DFS

traverseBack

protected void traverseBack(Edge e,
                            Vertex from)

Description copied from class: DFS

Called when we traverse a back edge (e) from a vertex (from).

Overrides:

traverseBack in class DFS

isDone

protected boolean isDone()

Description copied from class: DFS

Determines whether the traversal is done early.

Overrides:

isDone in class DFS