## Class GabowStrongConnectivityInspector<V,​E>

• java.lang.Object
• org.jgrapht.alg.connectivity.GabowStrongConnectivityInspector<V,​E>
• Type Parameters:
V - the graph vertex type
E - the graph edge type
All Implemented Interfaces:
StrongConnectivityAlgorithm<V,​E>

public class GabowStrongConnectivityInspector<V,​E>
extends Object
Computes the strongly connected components of a directed graph. The implemented algorithm follows Cheriyan-Mehlhorn/Gabow's algorithm presented in Path-based depth-first search for strong and biconnected components by Gabow (2000). The running time is order of $O(|V|+|E|)$.
Author:
Sarah Komla-Ebri
• ### Field Detail

• #### graph

protected final Graph<V,​E> graph
• #### stronglyConnectedSets

protected List<Set<V>> stronglyConnectedSets
• #### stronglyConnectedSubgraphs

protected List<Graph<V,​E>> stronglyConnectedSubgraphs
• ### Constructor Detail

• #### GabowStrongConnectivityInspector

public GabowStrongConnectivityInspector​(Graph<V,​E> graph)
Constructor
Parameters:
graph - the graph to inspect
Throws:
NullPointerException - in case the graph is null
• ### Method Detail

• #### stronglyConnectedSets

public List<Set<V>> stronglyConnectedSets()
Description copied from interface: StrongConnectivityAlgorithm
Computes a List of Sets, where each set contains vertices which together form a strongly connected component within the given graph.
Returns:
List of Set s containing the strongly connected components
• #### getStronglyConnectedComponents

public List<Graph<V,​E>> 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 interface StrongConnectivityAlgorithm<V,​E>
Returns:
a list of subgraphs representing the strongly connected components
• #### getCondensation

public Graph<Graph<V,​E>,​DefaultEdge> 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 interface StrongConnectivityAlgorithm<V,​E>
Returns:
the condensation of the given graph