net.datastructures
Class DFS

java.lang.Object
  net.datastructures.DFS

Direct Known Subclasses:

ConnectivityDFS, FindCycleDFS, FindPathDFS

public abstract class DFS

extends Object

Generic depth first search traversal of a graph using the template method pattern. A subclass should override various methods to add functionality.

Field Summary

protected Graph	G
protected static Object	STATUS
protected static Object	UNVISITED
protected static Object	VISITED
protected Object	visitResult

Constructor Summary

DFS()

Method Summary

protected Object	dfsTraversal(Vertex v) Recursive template method for a generic DFS traversal.
abstract Object	execute(Graph g, Vertex start, Object info) Execute a depth first search traversal on graph g, starting from a vertex v, optionally passing in an information object (info)
protected void	finishVisit(Vertex v) Called after we finish the visit for a vertex (v).
protected void	init(Graph g) Initialize the graph g for a traversal.
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 has been visited.
protected Object	result() Returns a result of a visit (if needed).
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).
protected void	unVisit(DecorablePosition p) Mark a position as unvisited.
protected void	visit(DecorablePosition p) Mark a position as visited.

Methods inherited from class java.lang.Object

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

Field Detail

G

protected Graph G

visitResult

protected Object visitResult

STATUS

protected static Object STATUS

VISITED

protected static Object VISITED

UNVISITED

protected static Object UNVISITED

Constructor Detail

DFS

public DFS()

Method Detail

execute

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

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

Parameters:

g - Input graph.

start - Start vertex of the traversal.

info - Auxiliary information (to be used by subclasses).

init

protected void init(Graph g)

Initialize the graph g for a traversal.

dfsTraversal

protected Object dfsTraversal(Vertex v)

Recursive template method for a generic DFS traversal.

Parameters:

v - Start vertex of the traversal

Returns:

result of the traversal

visit

protected void visit(DecorablePosition p)

Mark a position as visited.

unVisit

protected void unVisit(DecorablePosition p)

Mark a position as unvisited.

isVisited

protected boolean isVisited(DecorablePosition p)

Test if a position has been visited.

initResult

protected void initResult()

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

startVisit

protected void startVisit(Vertex v)

Called when we encounter a vertex (v).

finishVisit

protected void finishVisit(Vertex v)

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

traverseDiscovery

protected void traverseDiscovery(Edge e,
                                 Vertex from)

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

traverseBack

protected void traverseBack(Edge e,
                            Vertex 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 Object result()

Returns a result of a visit (if needed).