Module org.jgrapht.core
Package org.jgrapht.alg.connectivity
Class GabowStrongConnectivityInspector<V,E>
java.lang.Object
org.jgrapht.alg.connectivity.AbstractStrongConnectivityInspector<V,E>
org.jgrapht.alg.connectivity.GabowStrongConnectivityInspector<V,E>
- Type Parameters:
V
- the graph vertex typeE
- the graph edge type
- All Implemented Interfaces:
StrongConnectivityAlgorithm<V,
E>
Computes the strongly connected components of a directed graph. The implemented algorithm follows
Cheriyan-Mehlhorn/Gabow's algorithm presented in Path-based depth-first search for strong and
biconnected components by Gabow (2000). The running time is order of $O(|V|+|E|)$.
-
Nested Class Summary
Nested ClassesModifier and TypeClassDescriptionprivate static final class
-
Field Summary
FieldsModifier and TypeFieldDescriptionprivate int
private Map
<V, GabowStrongConnectivityInspector.VertexNumber<V>> Fields inherited from class org.jgrapht.alg.connectivity.AbstractStrongConnectivityInspector
graph, stronglyConnectedSets, stronglyConnectedSubgraphs
-
Constructor Summary
Constructors -
Method Summary
Modifier and TypeMethodDescriptionprivate void
private void
Methods inherited from class org.jgrapht.alg.connectivity.AbstractStrongConnectivityInspector
getCondensation, getGraph, getStronglyConnectedComponents, isStronglyConnected
-
Field Details
-
stackS
-
stackB
-
vertexToVertexNumber
-
c
private int c
-
-
Constructor Details
-
GabowStrongConnectivityInspector
Constructor- Parameters:
graph
- the graph to inspect- Throws:
NullPointerException
- in case the 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
-
createVertexNumber
private void createVertexNumber() -
dfsVisit
-
createSCCVertexSetAndNumberVertices
private Set<V> createSCCVertexSetAndNumberVertices(GabowStrongConnectivityInspector.VertexNumber<V> v)
-