net.datastructures

Class FindCycleDFS<V,E>

java.lang.Object

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

net.datastructures.FindCycleDFS<V,E>

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

This class specializes DFS to find a cycle.

Field Summary

Fields

Modifier and Type	Field and Description
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

Constructors

Constructor and Description
FindCycleDFS()

Method Summary

Modifier and Type	Method and Description
java.lang.Iterable<Position>	finalResult(java.lang.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,java.lang.Object,java.lang.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,java.lang.Object,java.lang.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,java.lang.Object,java.lang.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,java.lang.Object,java.lang.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,java.lang.Object,java.lang.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,java.lang.Object,java.lang.Iterable<Position>>

finalResult

public java.lang.Iterable<Position> finalResult(java.lang.Iterable<Position> r)

Description copied from class: DFS

Returns the final result of the DFS execute method.

Overrides:

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