Module org.jgrapht.core
Package org.jgrapht.alg.connectivity
Class KosarajuStrongConnectivityInspector<V,E>
java.lang.Object
org.jgrapht.alg.connectivity.KosarajuStrongConnectivityInspector<V,E>
 Type Parameters:
V
 the graph vertex typeE
 the graph edge type
 All Implemented Interfaces:
StrongConnectivityAlgorithm<V,
E>
Computes strongly connected components of a directed graph. The algorithm is implemented after
"Cormen et al: Introduction to algorithms", 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
StrongConnectivityAlgorithm.isStronglyConnected()
.
 Author:
 Christian Soltenborn, Christian Hammer

Field Summary

Constructor Summary

Method Summary

Field Details

graph

stronglyConnectedSets

stronglyConnectedSubgraphs


Constructor Details

KosarajuStrongConnectivityInspector
Constructor Parameters:
graph
 the input graph Throws:
NullPointerException
 if the input graph is null


Method Details

stronglyConnectedSets
Description copied from interface:StrongConnectivityAlgorithm
Computes aList
ofSet
s, where each set contains vertices which together form a strongly connected component within the given graph. Returns:
List
ofSet
s containing the strongly connected components

getGraph
Description copied from interface:StrongConnectivityAlgorithm
Return the underlying graph. Specified by:
getGraph
in interfaceStrongConnectivityAlgorithm<V,
E>  Returns:
 the underlying graph

isStronglyConnected
public boolean isStronglyConnected()Description copied from interface:StrongConnectivityAlgorithm
Returns true if the graph is strongly connected, false otherwise. Specified by:
isStronglyConnected
in interfaceStrongConnectivityAlgorithm<V,
E>  Returns:
 true if the graph is strongly connected, false otherwise

getStronglyConnectedComponents
Description copied from interface:StrongConnectivityAlgorithm
Computes a list of subgraphs 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. Specified by:
getStronglyConnectedComponents
in interfaceStrongConnectivityAlgorithm<V,
E>  Returns:
 a list of subgraphs representing the strongly connected components

getCondensation
Description copied from interface:StrongConnectivityAlgorithm
Compute the condensation of the given graph. If each strongly connected component is contracted to a single vertex, the resulting graph is a directed acyclic graph, the condensation of the graph. Specified by:
getCondensation
in interfaceStrongConnectivityAlgorithm<V,
E>  Returns:
 the condensation of the given graph
