org._3pq.jgrapht.alg

Class 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().

Author:
Christian Soltenborn
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.
List
stronglyConnectedSets()
Computes a List of Sets, where each set contains vertices which together form a strongly connected component within the given graph.
List
stronglyConnectedSubgraphs()
Computes a list of DirectedSubgraphs of the given graph.

Constructor Details

StrongConnectivityInspector

public StrongConnectivityInspector(DirectedGraph directedGraph)
The constructor of the StrongConnectivityInspector class.
Parameters:
directedGraph - the graph to inspect

Method Details

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 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 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