Module org.jgrapht.core
Package org.jgrapht.alg.connectivity
Class KosarajuStrongConnectivityInspector<V,E>
java.lang.Object
org.jgrapht.alg.connectivity.AbstractStrongConnectivityInspector<V,E>
org.jgrapht.alg.connectivity.KosarajuStrongConnectivityInspector<V,E>
- Type Parameters:
V
- the graph vertex typeE
- the graph edge type
- All Implemented Interfaces:
StrongConnectivityAlgorithm<V,
E>
public class KosarajuStrongConnectivityInspector<V,E>
extends AbstractStrongConnectivityInspector<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
AbstractStrongConnectivityInspector.isStronglyConnected()
.
-
Nested Class Summary
Nested ClassesModifier and TypeClassDescriptionprivate static class
private static final class
private static final class
-
Field Summary
FieldsModifier and TypeFieldDescriptionprivate Map
<V, KosarajuStrongConnectivityInspector.VertexData<V>> Fields inherited from class org.jgrapht.alg.connectivity.AbstractStrongConnectivityInspector
graph, stronglyConnectedSets, stronglyConnectedSubgraphs
-
Constructor Summary
Constructors -
Method Summary
Methods inherited from class org.jgrapht.alg.connectivity.AbstractStrongConnectivityInspector
getCondensation, getGraph, getStronglyConnectedComponents, isStronglyConnected
-
Field Details
-
orderedVertices
-
vertexToVertexData
-
-
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
-
createVertexData
private void createVertexData() -
dfsVisit
-
resetVertexData
private void resetVertexData()
-