org.jgrapht.alg

## Class 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|).
Since:
September, 2013
Author:
Sarah Komla-Ebri
• ### Field Summary

Fields
Modifier and Type Field and Description
protected Graph<V,E> graph
protected List<Set<V>> stronglyConnectedSets
protected List<DirectedSubgraph<V,E>> stronglyConnectedSubgraphs
• ### Constructor Summary

Constructors
Constructor and Description
GabowStrongConnectivityInspector(Graph<V,E> graph)
Constructor
• ### Method Summary

All Methods
Modifier and Type Method and Description
Graph<Graph<V,E>,DefaultEdge> getCondensation()
Compute the condensation of the given graph.
Graph<V,E> getGraph()
Return the underlying graph.
List<Graph<V,E>> getStronglyConnectedComponents()
Computes a list of subgraphs of the given graph.
boolean isStronglyConnected()
Returns true if the graph is strongly connected, false otherwise.
List<Set<V>> stronglyConnectedSets()
Computes a List of Sets, where each set contains vertices which together form a strongly connected component within the given graph.
List<DirectedSubgraph<V,E>> stronglyConnectedSubgraphs()
Deprecated.
• ### Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
• ### Field Detail

• #### graph

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

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

protected List<DirectedSubgraph<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
• #### getGraph

public Graph<V,E> getGraph()
Description copied from interface: StrongConnectivityAlgorithm
Return the underlying graph.
Specified by:
getGraph in interface StrongConnectivityAlgorithm<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 interface StrongConnectivityAlgorithm<V,E>
Returns:
true if the graph is strongly connected, false otherwise
• #### stronglyConnectedSubgraphs

@Deprecated
public List<DirectedSubgraph<V,E>> stronglyConnectedSubgraphs()
Deprecated.
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:
stronglyConnectedSubgraphs in interface StrongConnectivityAlgorithm<V,E>
Returns:
a list of subgraphs representing 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