net.datastructures
Class FindCycleDFS<V,E>

java.lang.Object
  net.datastructures.DFS<V,E,Object,Iterable<Position>>
      net.datastructures.FindCycleDFS<V,E>

public class FindCycleDFS<V,E>
extends DFS<V,E,Object,Iterable<Position>>

This class specializes DFS to find a cycle.

Field Summary

protected PositionList<Position>	cycle
protected Vertex<V>	cycleStart
protected boolean	done

Fields inherited from class net.datastructures.DFS

graph, info, start, STATUS, UNVISITED, VISITED, visitResult

Constructor Summary

FindCycleDFS()

Method Summary

Iterable<Position>	finalResult(Iterable<Position> r) Returns the final result of the DFS execute method.
protected void	finishVisit(Vertex<V> v) Called after we finish the visit for a vertex (v).
protected boolean	isDone() Determines whether the traversal is done early.
void	setup() Executes the DFS algorithm.
protected void	startVisit(Vertex<V> v) Called when we encounter a vertex (v).
protected void	traverseBack(Edge<E> e, Vertex<V> from) Called when we traverse a back edge (e) from a vertex (from).
protected void	traverseDiscovery(Edge<E> e, Vertex<V> from) Called when we traverse a discovery edge (e) from a vertex (from).

Methods inherited from class net.datastructures.DFS

dfsTraversal, execute, 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 PositionList<Position> cycle

done

protected boolean done

cycleStart

protected Vertex<V> cycleStart

Constructor Detail

FindCycleDFS

public FindCycleDFS()

Method Detail

setup

public void setup()

Executes the DFS algorithm.

Overrides:

setup in class DFS<V,E,Object,Iterable<Position>>

Parameters:

info - unused

startVisit

protected void startVisit(Vertex<V> v)

Description copied from class: DFS

Called when we encounter a vertex (v).

Overrides:

startVisit in class DFS<V,E,Object,Iterable<Position>>

finishVisit

protected void finishVisit(Vertex<V> v)

Description copied from class: DFS

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

Overrides:

finishVisit in class DFS<V,E,Object,Iterable<Position>>

traverseDiscovery

protected void traverseDiscovery(Edge<E> e,
                                 Vertex<V> from)

Description copied from class: DFS

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

Overrides:

traverseDiscovery in class DFS<V,E,Object,Iterable<Position>>

traverseBack

protected void traverseBack(Edge<E> e,
                            Vertex<V> from)

Description copied from class: DFS

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

Overrides:

traverseBack in class DFS<V,E,Object,Iterable<Position>>

isDone

protected boolean isDone()

Description copied from class: DFS

Determines whether the traversal is done early.

Overrides:

isDone in class DFS<V,E,Object,Iterable<Position>>

finalResult

public Iterable<Position> finalResult(Iterable<Position> r)

Description copied from class: DFS

Returns the final result of the DFS execute method.

Overrides:

finalResult in class DFS<V,E,Object,Iterable<Position>>