org.jscience.computing.graph.algorithms
Class StrongConnectivityInspector

java.lang.Object
  extended by org.jscience.computing.graph.algorithms.StrongConnectivityInspector

public class StrongConnectivityInspector
extends java.lang.Object

Complements the ConnectivityInspector class with the capability to compute the strongly connected components of a directed graph. The algorithm is implemented after "Corman et al: Introduction to agorithms", Chapter 25.2. It has a running time of O(V + E).

Unlike ConnectivityInspector, this class does not implement incremental inspection. The full algorithm is executed at the first call of stronglyConnectedSets() or isStronglyConnected().

Since:
Feb 2, 2005

Constructor Summary
StrongConnectivityInspector(DirectedGraph directedGraph)
          The constructor of the StrongConnectivityInspector class.
 
Method Summary
 DirectedGraph getGraph()
          Returns the graph inspected by the StrongConnectivityInspector.
 boolean isStronglyConnected()
          Returns true if the graph of this StronglyConnectivityInspector instance is strongly connected.
 java.util.List stronglyConnectedSets()
          Computes a List of Sets, where each set contains vertices which together form a strongly connected component within the given graph.
 java.util.List stronglyConnectedSubgraphs()
          

Computes a list of DirectedSubgraphs of the given graph.

 
Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
 

Constructor Detail

StrongConnectivityInspector

public StrongConnectivityInspector(DirectedGraph directedGraph)
The constructor of the StrongConnectivityInspector class.

Parameters:
directedGraph - the graph to inspect
Throws:
java.lang.IllegalArgumentException
Method Detail

getGraph

public DirectedGraph getGraph()
Returns the graph inspected by the StrongConnectivityInspector.

Returns:
the graph inspected by this StrongConnectivityInspector

isStronglyConnected

public boolean isStronglyConnected()
Returns true if the graph of this StronglyConnectivityInspector instance is strongly connected.

Returns:
true if the graph is strongly connected, false otherwise

stronglyConnectedSets

public java.util.List stronglyConnectedSets()
Computes a List of Sets, where each set contains vertices which together form a strongly connected component within the given graph.

Returns:
List of Sets containing the strongly connected components

stronglyConnectedSubgraphs

public java.util.List stronglyConnectedSubgraphs()

Computes a list of DirectedSubgraphs of the given graph. Each subgraph will represent a strongly connected component and will contain all vertices of that component. The subgraph will have an edge (u,v) iff u and v are contained in the strongly connected component.

NOTE: Calling this method will first execute stronglyConnectedSets(). If you don't need subgraphs, use that method.

Returns:
a list of subgraphs representing the strongly connected components