Class KosarajuStrongConnectivityInspector<V,E>
- java.lang.Object
-
- org.jgrapht.alg.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 java.lang.Object implements StrongConnectivityAlgorithm<V,E>
Complements the
ConnectivityInspector
class with the capability to compute the strongly connected components of a directed graph. The algorithm is implemented after "Cormen et al: Introduction to agorithms", 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()
orisStronglyConnected()
.- Since:
- Feb 2, 2005
-
-
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 DirectedGraph<V,E>
graph
private java.util.LinkedList<KosarajuStrongConnectivityInspector.VertexData<V>>
orderedVertices
private java.util.List<java.util.Set<V>>
stronglyConnectedSets
private java.util.List<DirectedSubgraph<V,E>>
stronglyConnectedSubgraphs
private java.util.Map<V,KosarajuStrongConnectivityInspector.VertexData<V>>
vertexToVertexData
-
Constructor Summary
Constructors Constructor Description KosarajuStrongConnectivityInspector(DirectedGraph<V,E> directedGraph)
The constructor of the StrongConnectivityAlgorithm class.
-
Method Summary
All Methods Instance Methods Concrete Methods Modifier and Type Method Description private void
createVertexData()
private void
dfsVisit(DirectedGraph<V,E> visitedGraph, KosarajuStrongConnectivityInspector.VertexData<V> vertexData, java.util.Set<V> vertices)
DirectedGraph<V,E>
getGraph()
Returns the graph inspected by the StrongConnectivityAlgorithm.boolean
isStronglyConnected()
Returns true if the graph of thisStronglyConnectivityInspector
instance is strongly connected.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.java.util.List<DirectedSubgraph<V,E>>
stronglyConnectedSubgraphs()
Computes a list ofDirectedSubgraph
s of the given graph.
-
-
-
Field Detail
-
graph
private final DirectedGraph<V,E> graph
-
orderedVertices
private java.util.LinkedList<KosarajuStrongConnectivityInspector.VertexData<V>> orderedVertices
-
stronglyConnectedSets
private java.util.List<java.util.Set<V>> stronglyConnectedSets
-
stronglyConnectedSubgraphs
private java.util.List<DirectedSubgraph<V,E>> stronglyConnectedSubgraphs
-
vertexToVertexData
private java.util.Map<V,KosarajuStrongConnectivityInspector.VertexData<V>> vertexToVertexData
-
-
Constructor Detail
-
KosarajuStrongConnectivityInspector
public KosarajuStrongConnectivityInspector(DirectedGraph<V,E> directedGraph)
The constructor of the StrongConnectivityAlgorithm class.- Parameters:
directedGraph
- the graph to inspect- Throws:
java.lang.IllegalArgumentException
- if the input graph is null
-
-
Method Detail
-
getGraph
public DirectedGraph<V,E> getGraph()
Returns the graph inspected by the StrongConnectivityAlgorithm.- Specified by:
getGraph
in interfaceStrongConnectivityAlgorithm<V,E>
- Returns:
- the graph inspected by this StrongConnectivityAlgorithm
-
isStronglyConnected
public boolean isStronglyConnected()
Returns true if the graph of thisStronglyConnectivityInspector
instance is strongly connected.- Specified by:
isStronglyConnected
in interfaceStrongConnectivityAlgorithm<V,E>
- Returns:
- true if the graph is strongly connected, false otherwise
-
stronglyConnectedSets
public 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.- Specified by:
stronglyConnectedSets
in interfaceStrongConnectivityAlgorithm<V,E>
- Returns:
List
ofSet
s containing the strongly connected components
-
stronglyConnectedSubgraphs
public java.util.List<DirectedSubgraph<V,E>> stronglyConnectedSubgraphs()
Computes a list of
DirectedSubgraph
s 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.NOTE: Calling this method will first execute
stronglyConnectedSets()
. If you don't need subgraphs, use that method.- Specified by:
stronglyConnectedSubgraphs
in interfaceStrongConnectivityAlgorithm<V,E>
- Returns:
- a list of subgraphs representing the strongly connected components
-
createVertexData
private void createVertexData()
-
dfsVisit
private void dfsVisit(DirectedGraph<V,E> visitedGraph, KosarajuStrongConnectivityInspector.VertexData<V> vertexData, java.util.Set<V> vertices)
-
resetVertexData
private void resetVertexData()
-
-