Module org.jgrapht.core
Package org.jgrapht.alg.connectivity
Class GabowStrongConnectivityInspector<V,E>
java.lang.Object
org.jgrapht.alg.connectivity.GabowStrongConnectivityInspector<V,E>
 Type Parameters:
V
 the graph vertex typeE
 the graph edge type
 All Implemented Interfaces:
StrongConnectivityAlgorithm<V,
E>
Computes the strongly connected components of a directed graph. The implemented algorithm follows
CheriyanMehlhorn/Gabow's algorithm presented in Pathbased depthfirst search for strong and
biconnected components by Gabow (2000). The running time is order of $O(V+E)$.
 Author:
 Sarah KomlaEbri, Hannes Wellmann

Field Summary

Constructor Summary

Method Summary

Field Details

graph

stronglyConnectedSets

stronglyConnectedSubgraphs


Constructor Details

GabowStrongConnectivityInspector
Constructor Parameters:
graph
 the graph to inspect Throws:
NullPointerException
 in case the graph is null


Method Details

stronglyConnectedSets
Description copied from interface:StrongConnectivityAlgorithm
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

getGraph
Description copied from interface:StrongConnectivityAlgorithm
Return the underlying graph. Specified by:
getGraph
in interfaceStrongConnectivityAlgorithm<V,
E>  Returns:
 the underlying graph

isStronglyConnected
public boolean isStronglyConnected()Description copied from interface:StrongConnectivityAlgorithm
Returns true if the graph is strongly connected, false otherwise. Specified by:
isStronglyConnected
in interfaceStrongConnectivityAlgorithm<V,
E>  Returns:
 true if the graph is strongly connected, false otherwise

getStronglyConnectedComponents
Description copied from interface:StrongConnectivityAlgorithm
Computes a list of subgraphs 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. Specified by:
getStronglyConnectedComponents
in interfaceStrongConnectivityAlgorithm<V,
E>  Returns:
 a list of subgraphs representing the strongly connected components

getCondensation
Description copied from interface:StrongConnectivityAlgorithm
Compute the condensation of the given graph. If each strongly connected component is contracted to a single vertex, the resulting graph is a directed acyclic graph, the condensation of the graph. Specified by:
getCondensation
in interfaceStrongConnectivityAlgorithm<V,
E>  Returns:
 the condensation of the given graph
