y.algo
Class Dfs

java.lang.Object
  y.algo.Dfs

public class Dfs
extends java.lang.Object

Framework class for implementing depth first search (DFS) based algorithms.

A depth first search starts from a specified node and traverses the neighbors within a branch as deeply as possible (i.e., without visiting any vertex twice) before backtracking.

A depth first search traversal induces a DFS forest that may consist of more than one DFS tree. Based on these trees, the edges are divided into four categories (see example):

• Tree Edges: The edges of the DFS forest.
• Back edges: Non-tree edges that connect nodes with their ancestors in the DFS tree. Self-loops are also considered as back edges.
• Forward edges: Edges that connect nodes of the DFS tree to one of their descendants.
• Cross edges: All other edges.

During a DFS run each node of the graph can be in one of the following states:

• Undiscovered: A node that has not been visited yet.
• Discovered but not finished: A node that has been already visited, but has not been completed yet, i.e. it is still part of an active path of the DFS tree.
• Finished: A node that has been completed, i.e. it has been visited before and is not part of an active path of the DFS tree anymore.

Graph algorithms, which are based on a depth first search, can extend this class and override appropriate callback methods provided by this class.

Example of a DFS traversal. Node labels indicate the order in which nodes are visited. Solid edges are the edges of the DFS tree while dashed edges represent back, forward and cross edges.

Field Summary

protected static java.lang.Object	BLACK A constant indicating a node has been completed.
protected static java.lang.Object	GRAY A constant indicating a node has already been visited, but has not been completed yet.
protected NodeMap	stateMap A NodeMap that holds for each Node an Object indicating the current state of the given node as it is visited by this algorithm.
protected static java.lang.Object	WHITE A constant indicating a node has not been visited yet.

Constructor Summary

Dfs()
Creates a new Dfs instance with default settings.

Method Summary

protected void	cancel() Cancels the depth first search.
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 DFS has returned 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 considered the first (and only) time during the DFS.
protected void	preVisit(Node node, int dfsNumber) Callback method that will be invoked whenever a formerly unvisited node gets visited for the first time.
void	setDirectedMode(boolean directed) Specifies whether or not to interpret the edges of the graph as directed.
void	setLookFurtherMode(boolean lookFurther) Specifies whether or not to continue the depth first search after all nodes reachable from the first node have been 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 from a given Node of the input 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

A NodeMap that holds for each Node an Object indicating the current state of the given node as it is visited by this algorithm. Each node will be assigned one of the WHITE, GRAY or BLACK objects that describe the state of the nodes.

WHITE

protected static final java.lang.Object WHITE

A constant indicating a node has not been visited yet.

GRAY

protected static final java.lang.Object GRAY

A constant indicating a node has already been visited, but has not been completed yet. Such a node is still part of an active path of the DFS tree.

BLACK

protected static final java.lang.Object BLACK

A constant indicating a node has been completed. Such a node has been visited before and is no longer part of an active path of the DFS tree.

Constructor Detail

Dfs

public Dfs()

Creates a new Dfs instance with default settings.

Method Detail

setDirectedMode

public void setDirectedMode(boolean directed)

Specifies whether or not to interpret the edges of the graph as directed.

Default Value:

The default value is false. Graphs are considered undirected.

Parameters:

directed - true if the edges are considered as directed, false otherwise

setLookFurtherMode

public void setLookFurtherMode(boolean lookFurther)

Specifies whether or not to continue the depth first search after all nodes reachable from the first node have been visited.

Default Value:

The default value is true.

Parameters:

lookFurther - true if the depth first search should continue, false otherwise

start

public void start(Graph graph)

Starts a depth first search on the given graph.

The first node of the graph will be visited first.

Parameters:

graph - the input graph

start

public void start(Graph graph,
                  Node start)

Starts a depth first search from a given Node of the input graph.

If the given start node is null, this method returns silently.

Parameters:

graph - the input graph

start - the given start node

preVisit

protected void preVisit(Node node,
                        int dfsNumber)

Callback method that will be invoked whenever a formerly unvisited node gets visited for the first time.

By default, this method does nothing. It may be overridden to support custom implementations.

Parameters:

node - the given node

dfsNumber - the DFS number of the given node

postVisit

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

Callback method that will be invoked whenever a node visit has been completed.

By default, this method does nothing. It may be overridden to support custom implementations.

Parameters:

node - the given node

dfsNumber - the DFS number of the given node

compNumber - the completion number of the given node

preTraverse

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

Callback method that will be invoked if the given edge will be considered the first (and only) time during the DFS.

By default, this method does nothing. It may be overridden to support custom implementations.

Parameters:

edge - the given edge

node - the node to be visited next only if treeEdge == true

treeEdge - true if the node will be visited, false otherwise

postTraverse

protected void postTraverse(Edge edge,
                            Node node)

Callback method that will be invoked after the DFS has returned from the given node.

By default, this method does nothing. It may be overridden to support custom implementations.

Parameters:

edge - the given edge

node - the node that has been reached via the given edge

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. It may be overridden to support custom implementations.

Parameters:

v - the new root node

cancel

protected void cancel()

Cancels the depth first search.

It may be overridden to support custom implementations.