com.tensegrity.graph.algorithm
Class DFS

java.lang.Object
  com.tensegrity.graph.algorithm.DFS

Direct Known Subclasses:

BiconnectedDFS

public class DFS

extends java.lang.Object

This class implements the Depth-First-Search (DFS) algorithm with a cost of

O(|V| + |E|).

The visitor pattern is used for passing method pointers to the algorithm for specific algorithm uses.

Version:

$Id: DFS.java,v 1.16 2005/11/18 16:05:31 KevinCVS Exp $

Author:

Stepan Rutz

Constructor Summary

DFS()
Construct a new DFS object.

Method Summary

void	apply(Graph graph, DFSVisitor visitor) Applies the DFS algorithm with an arbitrary starting node.
void	apply(Graph graph, DFSVisitor visitor, Node startnode) Applies the DFS algorithm with the given starting node.
int	getDFSNumber(Node node) Returns the DFS order number of a given node.
Node	getDFSParent(Node node) Returns the parent of the node in the dfs forest or null.
java.util.ArrayList	getDFSSequence() Returns a random-access list of the node-order obtained by the DFS.
java.util.List	getRoots() Returns the roots of the trees in the DFS search forest.
boolean	isConnected() Returns true if the graph is strongly connected

Methods inherited from class java.lang.Object

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

Constructor Detail

DFS

public DFS()

Construct a new DFS object.

Method Detail

isConnected

public boolean isConnected()

Returns true if the graph is strongly connected

Returns:

true if the graph is strongly connected

getRoots

public java.util.List getRoots()

Returns the roots of the trees in the DFS search forest.

Returns:

the roots of the trees in the DFS search forest.

getDFSSequence

public java.util.ArrayList getDFSSequence()

Returns a random-access list of the node-order obtained by the DFS.

Returns:

a random-access list of the node-order obtained by the DFS.

getDFSNumber

public int getDFSNumber(Node node)

Returns the DFS order number of a given node. The item must have been in the graph at the time the algorithm was executed,

Parameters:

node - the node whose dfs number is retrieved.

Returns:

the dfs number of the node.

getDFSParent

public Node getDFSParent(Node node)

Returns the parent of the node in the dfs forest or null.

Parameters:

node - the node whose father is retrieved.

Returns:

the parent of the node in the dfs forest or null if the node is one of the roots of the trees in the dfs forest.

apply

public void apply(Graph graph,
                  DFSVisitor visitor)

Applies the DFS algorithm with an arbitrary starting node.

Parameters:

graph - the graph to search, may not be null.

visitor - the dfsvisitor whose callbacks to invoke during traversal, may not be null.

apply

public void apply(Graph graph,
                  DFSVisitor visitor,
                  Node startnode)

Applies the DFS algorithm with the given starting node.

Parameters:

graph - the graph to search, , may not be null.

visitor - the dfsvisitor whose callbacks to invoke during traversal, may not be null.

startnode - the node where to start the depth first searching, may be null.