Class StrongConnectivityInspector<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 of stronglyConnectedSets()
or isStronglyConnected()
.
- Since:
- Feb 2, 2005
- Author:
- Christian Soltenborn, Christian Hammer
-
Constructor Summary
ConstructorsConstructorDescriptionStrongConnectivityInspector
(DirectedGraph<V, E> directedGraph) The constructor of the StrongConnectivityInspector class. -
Method Summary
Modifier and TypeMethodDescriptiongetGraph()
Returns the graph inspected by the StrongConnectivityInspector.boolean
Returns true if the graph of thisStronglyConnectivityInspector
instance is strongly connected.Computes a list ofDirectedSubgraph
s of the given graph.
-
Constructor Details
-
StrongConnectivityInspector
The constructor of the StrongConnectivityInspector class.- Parameters:
directedGraph
- the graph to inspect- Throws:
IllegalArgumentException
-
-
Method Details
-
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
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
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
-