net.datastructures

Class DFS<V,E,I,R>

java.lang.Object

net.datastructures.DFS<V,E,I,R>

Direct Known Subclasses:

ComponentsDFS, ConnectivityDFS, FindCycleDFS, FindPathDFS

public class DFS<V,E,I,R>
extends java.lang.Object

Generic DFS traversal of a graph using the template method pattern. Parameterized types: V, the type for the elements stored at vertices E, the type for the elements stored at edges I, the type for the information object passed to the execute method R, the type for the result object returned by the DFS

Field Summary

Fields

Modifier and Type	Field and Description
protected Graph<V,E>	graph
protected I	info
protected Vertex<V>	start
protected static java.lang.Object	STATUS
protected static java.lang.Object	UNVISITED
protected static java.lang.Object	VISITED
protected R	visitResult

Constructor Summary

Constructors

Constructor and Description
DFS()

Method Summary

Modifier and Type	Method and Description
protected R	dfsTraversal(Vertex<V> v) Recursive template method for a generic DFS traversal.
R	execute(Graph<V,E> g, Vertex<V> s, I in) Execute a depth first search traversal on graph g, starting from a start vertex s, passing in an information object (in)
protected R	finalResult(R 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 void	initResult() Initializes result (called first, once per vertex visited).
protected boolean	isDone() Determines whether the traversal is done early.
protected boolean	isVisited(DecorablePosition<?> p) Test if a position (vertex or edge) has been visited.
protected R	result() Returns a result of a visit (if needed).
protected void	setup() Setup method that is called prior to the DFS execution.
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).
protected void	unVisit(DecorablePosition<?> p) Mark a position (vertex or edge) as unvisited.
protected void	visit(DecorablePosition<?> p) Mark a position (vertex or edge) as visited.

Methods inherited from class java.lang.Object

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

Field Detail

graph

protected Graph<V,E> graph

start

protected Vertex<V> start

info

protected I info

visitResult

protected R visitResult

STATUS

protected static java.lang.Object STATUS

VISITED

protected static java.lang.Object VISITED

UNVISITED

protected static java.lang.Object UNVISITED

Constructor Detail

DFS

public DFS()

Method Detail

execute

public R execute(Graph<V,E> g,
                 Vertex<V> s,
                 I in)

Execute a depth first search traversal on graph g, starting from a start vertex s, passing in an information object (in)

dfsTraversal

protected R dfsTraversal(Vertex<V> v)

Recursive template method for a generic DFS traversal.

visit

protected void visit(DecorablePosition<?> p)

Mark a position (vertex or edge) as visited.

unVisit

protected void unVisit(DecorablePosition<?> p)

Mark a position (vertex or edge) as unvisited.

isVisited

protected boolean isVisited(DecorablePosition<?> p)

Test if a position (vertex or edge) has been visited.

setup

protected void setup()

Setup method that is called prior to the DFS execution.

initResult

protected void initResult()

Initializes result (called first, once per vertex visited).

startVisit

protected void startVisit(Vertex<V> v)

Called when we encounter a vertex (v).

finishVisit

protected void finishVisit(Vertex<V> v)

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

traverseDiscovery

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

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

traverseBack

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

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

isDone

protected boolean isDone()

Determines whether the traversal is done early.

result

protected R result()

Returns a result of a visit (if needed).

finalResult

protected R finalResult(R r)

Returns the final result of the DFS execute method.