y.algo
Class Dfs

java.lang.Object
  |
  +--y.algo.Dfs

public class Dfs

extends Object

Framework class for depth first search (DFS) based algorithms. To write graph algorithms that are based on a depth first search one can extend this class and overwrite appropriate callback methods provided by this class.

Field Summary

protected static Object	BLACK Node state specifier.
protected static Object	GRAY Node state specifier.
protected NodeMap	stateMap NodeMap that indicates the state of the nodes as they are visited by this algorithm.
protected static Object	WHITE Node state specifier.

Constructor Summary

Dfs()
Instantiates a new Dfs object.

Method Summary

protected void	lookFurther(Node v) Callback method that will be invoked whenever dfs continues its search at a new root node.
protected void	postTraverse(Edge edge, Node node) Callback method that will be invoked after the search returns from the given node.
protected void	postVisit(Node node, int dfsNumber, int compNumber) Callback method that will be invoked whenever a node visit has been completed.
protected void	preTraverse(Edge edge, Node node, boolean treeEdge) Callback method that will be invoked if the given edge will be looked at in the search the first (and only) time.
protected void	preVisit(Node node, int dfsNumber) Callback method that will be invoked whenever a formerly unvisited node gets visited the first time.
void	setDirectedMode(boolean directed) Whether or not to interpret the edges of the graph as directed.
void	setLookFurtherMode(boolean lookFurther) Whether or not to continue the depth first search after all nodes reachable from the first node were visited.
void	start(Graph graph) Starts a depth first search on the given graph.
void	start(Graph graph, Node start) Starts a depth first search on the given graph.

Methods inherited from class java.lang.Object

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

Field Detail

stateMap

protected NodeMap stateMap

NodeMap that indicates the state of the nodes as they are visited by this algorithm. Possible states of a node are WHITE, GRAY and BLACK.

WHITE

protected static final Object WHITE

Node state specifier. Indicates that a node was not yet visited.

GRAY

protected static final Object GRAY

Node state specifier. Indicates that a node was already visited but has not been completed yet, i.e. it is still part of an active path of the dfs tree.

BLACK

protected static final Object BLACK

Node state specifier. Indicates that the node has been completed, i.e. it has been visited before and is not part of an active path in the dfs tree anymore.

Constructor Detail

Dfs

public Dfs()

Instantiates a new Dfs object.

Method Detail

setDirectedMode

public void setDirectedMode(boolean directed)

Whether or not to interpret the edges of the graph as directed.

By default directed mode is disabled.

setLookFurtherMode

public void setLookFurtherMode(boolean lookFurther)

Whether or not to continue the depth first search after all nodes reachable from the first node were visited.

By default look further mode is active.

start

public void start(Graph graph)

Starts a depth first search on the given graph. The first node in the graph will be visited first.

start

public void start(Graph graph,
                  Node start)

Starts a depth first search on the given graph. The given node will be visited first.

preVisit

protected void preVisit(Node node,
                        int dfsNumber)

Callback method that will be invoked whenever a formerly unvisited node gets visited the first time. The given int is the dfsnumber of that node.

By default this method does nothing

postVisit

protected void postVisit(Node node,
                         int dfsNumber,
                         int compNumber)

Callback method that will be invoked whenever a node visit has been completed. The dfs number and the completion number of the given node will be passed in. By defualt this method does nothing

preTraverse

protected void preTraverse(Edge edge,
                           Node node,
                           boolean treeEdge)

Callback method that will be invoked if the given edge will be looked at in the search the first (and only) time.

The given node is the node that will be visited next iff treeEdge == true. By default this method does nothing

postTraverse

protected void postTraverse(Edge edge,
                            Node node)

Callback method that will be invoked after the search returns from the given node. The node has been reached via the given edge. By default this method does nothing.

lookFurther

protected void lookFurther(Node v)

Callback method that will be invoked whenever dfs continues its search at a new root node. By default this method does nothing