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 ofstronglyConnectedSets()
orAbstractStrongConnectivityInspector.isStronglyConnected()
.
-
-
Nested Class Summary
Nested Classes Modifier and Type Class Description private static class
KosarajuStrongConnectivityInspector.VertexData<V>
private static class
KosarajuStrongConnectivityInspector.VertexData1<V>
private static class
KosarajuStrongConnectivityInspector.VertexData2<V>
-
Field Summary
Fields Modifier and Type Field Description private java.util.LinkedList<KosarajuStrongConnectivityInspector.VertexData<V>>
orderedVertices
private java.util.Map<V,KosarajuStrongConnectivityInspector.VertexData<V>>
vertexToVertexData
-
Fields inherited from class org.jgrapht.alg.connectivity.AbstractStrongConnectivityInspector
graph, stronglyConnectedSets, stronglyConnectedSubgraphs
-
-
Constructor Summary
Constructors Constructor Description KosarajuStrongConnectivityInspector(Graph<V,E> graph)
Constructor
-
Method Summary
All Methods Instance Methods Concrete Methods Modifier and Type Method Description private void
createVertexData()
private void
dfsVisit(Graph<V,E> visitedGraph, KosarajuStrongConnectivityInspector.VertexData<V> vertexData, java.util.Set<V> vertices)
private void
resetVertexData()
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
-
orderedVertices
private java.util.LinkedList<KosarajuStrongConnectivityInspector.VertexData<V>> orderedVertices
-
vertexToVertexData
private java.util.Map<V,KosarajuStrongConnectivityInspector.VertexData<V>> vertexToVertexData
-
-
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
-
createVertexData
private void createVertexData()
-
dfsVisit
private void dfsVisit(Graph<V,E> visitedGraph, KosarajuStrongConnectivityInspector.VertexData<V> vertexData, java.util.Set<V> vertices)
-
resetVertexData
private void resetVertexData()
-
-