org.jgrapht.alg
Class StrongConnectivityInspector<V,E>

java.lang.Object
  extended by org.jgrapht.alg.StrongConnectivityInspector<V,E>

public class StrongConnectivityInspector<V,E>
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 "Cormen et al: Introduction to agorithms", Chapter 22.5. 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
Author:
Christian Soltenborn, Christian Hammer

Constructor Summary
StrongConnectivityInspector(DirectedGraph<V,E> directedGraph)
          The constructor of the StrongConnectivityInspector class.
 
Method Summary
 DirectedGraph<V,E> 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<java.util.Set<V>> 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<DirectedSubgraph<V,E>> 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<V,E> directedGraph)
The constructor of the StrongConnectivityInspector class.

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

getGraph

public DirectedGraph<V,E> 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<java.util.Set<V>> 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 Set s containing the strongly connected components

stronglyConnectedSubgraphs

public java.util.List<DirectedSubgraph<V,E>> 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