Class StrongConnectivityInspector<V,E>
- java.lang.Object
-
- org.jgrapht.alg.StrongConnectivityInspector<V,E>
-
public class StrongConnectivityInspector<V,E> extends java.lang.Object
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
- Author:
- Christian Soltenborn, Christian Hammer
-
-
Constructor Summary
Constructors Constructor Description StrongConnectivityInspector(DirectedGraph<V,E> directedGraph)
The constructor of the StrongConnectivityInspector class.
-
Method Summary
All Methods Instance Methods Concrete Methods Modifier and Type Method Description DirectedGraph<V,E>
getGraph()
Returns the graph inspected by the StrongConnectivityInspector.boolean
isStronglyConnected()
Returns true if the graph of thisStronglyConnectivityInspector
instance is strongly connected.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.
-
-
-
Constructor Detail
-
StrongConnectivityInspector
public StrongConnectivityInspector(DirectedGraph<V,E> directedGraph)
The constructor of the StrongConnectivityInspector class.- Parameters:
directedGraph
- the graph to inspect- Throws:
java.lang.IllegalArgumentException
-
-
Method Detail
-
getGraph
public DirectedGraph<V,E> getGraph()
Returns the graph inspected by the StrongConnectivityInspector.- Returns:
- the graph inspected by this StrongConnectivityInspector
-
isStronglyConnected
public boolean isStronglyConnected()
Returns true if the graph of thisStronglyConnectivityInspector
instance is strongly connected.- 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.- 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.- Returns:
- a list of subgraphs representing the strongly connected components
-
-