com.tensegrity.graph.algorithm
Class BiconnectedDFS

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

All Implemented Interfaces:

DFSVisitor

public class BiconnectedDFS

extends DFS

implements DFSVisitor

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

O(|V| + |E|).

The biconnected components of the graph are found during a visit. Use method getBiconnectedComponents() after the search is complete to query the found biconnected components.

Version:

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

Author:

Stepan Rutz

Nested Class Summary

static class

BiconnectedDFS.BiComponent This class represents a single biconnected component which consists of nodes and edges.

Constructor Summary

BiconnectedDFS()
Constructs a new empty BiconnectedBFS search context.

Method Summary

void	afterRecursion(Graph graph, Edge edge, Node node) Callback invoked right after the recursion in the dfs algorithm.
void	apply(Graph graph) Starts the algorithm.
void	backEdge(Graph graph, Edge edge) Callback invoked each time a backedge is encountered for the first time.
void	beforeRecursion(Graph graph, Edge edge, Node node) Callback invoked right before the recursion in the dfs algorithm.
void	endGraph(Graph graph) Callback invoked after the dfs algorithm completed its work.
void	endNode(Graph graph, Node node, Node father) Callback invoked after the dfs algorithm has processed a single node (and all children recursively).
java.util.List	getArticulationPoints() Returns the list of articulation points (which are nodes).
java.util.List	getBiconnectedComponents() Returns a list of the biconnected components which are of the type BiconnectedDFS.BiComponent.
boolean	isBiconnected() Returns true if the graph is entirely biconnected.
void	startDFSTree(Graph graph, Node node) Callback invoked each time a new dfs-tree is started in the dfs search forest.
void	startGraph(Graph graph) Callback invoked before the dfs algorithm starts its work.
void	startNode(Graph graph, Node node, Node father) Callback invoked before the dfs algorithm processes a single node.
void	usedAdjacentNodeEncountered(Graph graph, Edge edge, Node node) If the adjacent nodes of the current node are scanned and an already processed node is encountered, this method is invoked.

Methods inherited from class com.tensegrity.graph.algorithm.DFS

apply, apply, getDFSNumber, getDFSParent, getDFSSequence, getRoots, isConnected

Methods inherited from class java.lang.Object

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

Constructor Detail

BiconnectedDFS

public BiconnectedDFS()

Constructs a new empty BiconnectedBFS search context.

Method Detail

getBiconnectedComponents

public java.util.List getBiconnectedComponents()

Returns a list of the biconnected components which are of the type BiconnectedDFS.BiComponent.

Returns:

list of the biconnected components.

getArticulationPoints

public java.util.List getArticulationPoints()

Returns the list of articulation points (which are nodes).

Returns:

list of articulation points.

isBiconnected

public boolean isBiconnected()

Returns true if the graph is entirely biconnected. That means that the number of biconnected components is exactly equal to 1.

Returns:

true if the entire graph is biconnected (aka consists of one single biconnected component), false otherwise

apply

public void apply(Graph graph)

Starts the algorithm.

Parameters:

graph - the Graph to process, may not be null.

startGraph

public void startGraph(Graph graph)

Description copied from interface: DFSVisitor

Callback invoked before the dfs algorithm starts its work.

Specified by:

startGraph in interface DFSVisitor

Parameters:

graph - graph the algorithm is working upon.

endGraph

public void endGraph(Graph graph)

Description copied from interface: DFSVisitor

Callback invoked after the dfs algorithm completed its work.

Specified by:

endGraph in interface DFSVisitor

Parameters:

graph - graph the algorithm is working upon.

startNode

public void startNode(Graph graph,
                      Node node,
                      Node father)

Description copied from interface: DFSVisitor

Callback invoked before the dfs algorithm processes a single node.

Specified by:

startNode in interface DFSVisitor

Parameters:

graph - graph the algorithm is working upon.

node - the currently processed node

father - the predecessor of the node, or null if the node has no predecessor in the dfs search order.

endNode

public void endNode(Graph graph,
                    Node node,
                    Node father)

Description copied from interface: DFSVisitor

Callback invoked after the dfs algorithm has processed a single node (and all children recursively).

Specified by:

endNode in interface DFSVisitor

Parameters:

graph - graph the algorithm is working upon.

node - the currently processed node

father - the predecessor of the node, or null if the node has no predecessor in the dfs search order.

beforeRecursion

public void beforeRecursion(Graph graph,
                            Edge edge,
                            Node node)

Description copied from interface: DFSVisitor

Callback invoked right before the recursion in the dfs algorithm.

Specified by:

beforeRecursion in interface DFSVisitor

Parameters:

graph - graph the algorithm is working upon.

edge - the edge that lead to the recursion.

node - the node that is going to be examined recursively next.

afterRecursion

public void afterRecursion(Graph graph,
                           Edge edge,
                           Node node)

Description copied from interface: DFSVisitor

Callback invoked right after the recursion in the dfs algorithm.

Specified by:

afterRecursion in interface DFSVisitor

Parameters:

graph - graph the algorithm is working upon.

edge - the edge that lead to the recursion.

node - the node that was just recently examined recursively.

backEdge

public void backEdge(Graph graph,
                     Edge edge)

Description copied from interface: DFSVisitor

Callback invoked each time a backedge is encountered for the first time.

Specified by:

backEdge in interface DFSVisitor

Parameters:

graph - graph the algorithm is working upon.

edge - the backedge.

usedAdjacentNodeEncountered

public void usedAdjacentNodeEncountered(Graph graph,
                                        Edge edge,
                                        Node node)

Description copied from interface: DFSVisitor

If the adjacent nodes of the current node are scanned and an already processed node is encountered, this method is invoked.

Specified by:

usedAdjacentNodeEncountered in interface DFSVisitor

Parameters:

graph - graph the algorithm is working upon.

edge - the edge that connected the already seen node.

node - the node that was already visited.

startDFSTree

public void startDFSTree(Graph graph,
                         Node node)

Description copied from interface: DFSVisitor

Callback invoked each time a new dfs-tree is started in the dfs search forest. The passed node is the root node of the single dfs-tree.

Specified by:

startDFSTree in interface DFSVisitor

Parameters:

graph - graph the algorithm is working upon.

node - the root node of one dfs tree.