Class StrongConnectivityInspector
- java.lang.Object
-
- org._3pq.jgrapht.alg.StrongConnectivityInspector
-
public class StrongConnectivityInspector 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 "Corman et al: Introduction to agorithms", Chapter 25.2. 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
-
-
Constructor Summary
Constructors Constructor Description StrongConnectivityInspector(DirectedGraph directedGraph)
The constructor of the StrongConnectivityInspector class.
-
Method Summary
All Methods Instance Methods Concrete Methods Modifier and Type Method Description DirectedGraph
getGraph()
Returns the graph inspected by the StrongConnectivityInspector.boolean
isStronglyConnected()
Returns true if the graph of thisStronglyConnectivityInspector
instance is strongly connected.java.util.List
stronglyConnectedSets()
Computes aList
ofSet
s, where each set contains vertices which together form a strongly connected component within the given graph.java.util.List
stronglyConnectedSubgraphs()
Computes a list ofDirectedSubgraph
s of the given graph.
-
-
-
Constructor Detail
-
StrongConnectivityInspector
public StrongConnectivityInspector(DirectedGraph directedGraph)
The constructor of the StrongConnectivityInspector class.- Parameters:
directedGraph
- the graph to inspect- Throws:
java.lang.IllegalArgumentException
-
-
Method Detail
-
getGraph
public DirectedGraph 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 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 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
-
-