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>
public class GabowStrongConnectivityInspector<V,E> extends AbstractStrongConnectivityInspector<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 Classes Modifier and Type Class Description private static class
GabowStrongConnectivityInspector.VertexNumber<V>
-
Field Summary
Fields Modifier and Type Field Description private int
c
private java.util.Deque<GabowStrongConnectivityInspector.VertexNumber<V>>
stackB
private java.util.Deque<GabowStrongConnectivityInspector.VertexNumber<V>>
stackS
private java.util.Map<V,GabowStrongConnectivityInspector.VertexNumber<V>>
vertexToVertexNumber
-
Fields inherited from class org.jgrapht.alg.connectivity.AbstractStrongConnectivityInspector
graph, stronglyConnectedSets, stronglyConnectedSubgraphs
-
-
Constructor Summary
Constructors Constructor Description GabowStrongConnectivityInspector(Graph<V,E> graph)
Constructor
-
Method Summary
All Methods Instance Methods Concrete Methods Modifier and Type Method Description private java.util.Set<V>
createSCCVertexSetAndNumberVertices(GabowStrongConnectivityInspector.VertexNumber<V> v)
private void
createVertexNumber()
private void
dfsVisit(GabowStrongConnectivityInspector.VertexNumber<V> v)
java.util.List<java.util.Set<V>>
stronglyConnectedSets()
Computes aList
ofSet
s, where each set contains vertices which together form a strongly connected component within the given graph.-
Methods inherited from class org.jgrapht.alg.connectivity.AbstractStrongConnectivityInspector
getCondensation, getGraph, getStronglyConnectedComponents, isStronglyConnected
-
-
-
-
Field Detail
-
stackS
private java.util.Deque<GabowStrongConnectivityInspector.VertexNumber<V>> stackS
-
stackB
private java.util.Deque<GabowStrongConnectivityInspector.VertexNumber<V>> stackB
-
vertexToVertexNumber
private java.util.Map<V,GabowStrongConnectivityInspector.VertexNumber<V>> vertexToVertexNumber
-
c
private int c
-
-
Method Detail
-
stronglyConnectedSets
public java.util.List<java.util.Set<V>> 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
private void dfsVisit(GabowStrongConnectivityInspector.VertexNumber<V> v)
-
createSCCVertexSetAndNumberVertices
private java.util.Set<V> createSCCVertexSetAndNumberVertices(GabowStrongConnectivityInspector.VertexNumber<V> v)
-
-