org._3pq.jgrapht.alg
Class StrongConnectivityInspector
java.lang.Objectorg._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 of
stronglyConnectedSets()
or
isStronglyConnected().
StrongConnectivityInspector
public StrongConnectivityInspector(DirectedGraph directedGraph)
The constructor of the StrongConnectivityInspector class.
directedGraph - the graph to inspect
getGraph
public DirectedGraph getGraph()
Returns the graph inspected by the StrongConnectivityInspector.
- the graph inspected by this StrongConnectivityInspector
isStronglyConnected
public boolean isStronglyConnected()
Returns true if the graph of this
StronglyConnectivityInspector instance is strongly
connected.
- true if the graph is strongly connected, false otherwise
stronglyConnectedSets
public List stronglyConnectedSets()
Computes a List of Sets, where each set contains
vertices which together form a strongly connected component within the
given graph.
List of Sets containing the strongly
connected components
stronglyConnectedSubgraphs
public List stronglyConnectedSubgraphs()
Computes a list of
DirectedSubgraphs 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.
- a list of subgraphs representing the strongly connected
components