Package org.jgrapht.alg

Class GabowStrongConnectivityInspector<V,E>

java.lang.Object

org.jgrapht.alg.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 java.lang.Object
implements StrongConnectivityAlgorithm<V,E>

Allows obtaining 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

Nested Class Summary

Nested Classes

Modifier and Type	Class	Description
private static class	GabowStrongConnectivityInspector.VertexNumber<V>

Field Summary

Fields

Modifier and Type	Field	Description
private java.util.Deque<java.lang.Integer>	B
private int	c
private DirectedGraph<V,E>	graph
private java.util.Deque<GabowStrongConnectivityInspector.VertexNumber<V>>	stack
private java.util.List<java.util.Set<V>>	stronglyConnectedSets
private java.util.List<DirectedSubgraph<V,E>>	stronglyConnectedSubgraphs
private java.util.Map<V,GabowStrongConnectivityInspector.VertexNumber<V>>	vertexToVertexNumber

Constructor Summary

Constructors

Constructor	Description
GabowStrongConnectivityInspector(DirectedGraph<V,E> directedGraph)	The constructor of GabowStrongConnectivityInspector class.

Method Summary

Modifier and Type	Method	Description
private void	createVertexNumber()
private void	dfsVisit(DirectedGraph<V,E> visitedGraph, GabowStrongConnectivityInspector.VertexNumber<V> v)
DirectedGraph<V,E>	getGraph()	Returns the graph inspected
boolean	isStronglyConnected()	Returns true if the graph instance is strongly connected.
java.util.List<java.util.Set<V>>	stronglyConnectedSets()	Computes a List of Sets, where each set contains vertices which together form a strongly connected component within the given graph.
java.util.List<DirectedSubgraph<V,E>>	stronglyConnectedSubgraphs()	Computes a list of DirectedSubgraphs of the given graph.

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Field Detail

graph

private final DirectedGraph<V,E> graph

stack

private java.util.Deque<GabowStrongConnectivityInspector.VertexNumber<V>> stack

stronglyConnectedSets

private java.util.List<java.util.Set<V>> stronglyConnectedSets

stronglyConnectedSubgraphs

private java.util.List<DirectedSubgraph<V,E>> stronglyConnectedSubgraphs

vertexToVertexNumber

private java.util.Map<V,GabowStrongConnectivityInspector.VertexNumber<V>> vertexToVertexNumber

B

private java.util.Deque<java.lang.Integer> B

c

private int c

Constructor Detail

GabowStrongConnectivityInspector

public GabowStrongConnectivityInspector(DirectedGraph<V,E> directedGraph)

The constructor of GabowStrongConnectivityInspector class.

Parameters:

directedGraph - the graph to inspect

Throws:

java.lang.IllegalArgumentException - in case the graph is null

Method Detail

getGraph

public DirectedGraph<V,E> getGraph()

Returns the graph inspected

Specified by:

getGraph in interface StrongConnectivityAlgorithm<V,E>

Returns:

the graph inspected

isStronglyConnected

public boolean isStronglyConnected()

Returns true if the graph instance is strongly connected.

Specified by:

isStronglyConnected in interface StrongConnectivityAlgorithm<V,E>

Returns:

true if the graph is strongly connected, false otherwise

stronglyConnectedSets

public java.util.List<java.util.Set<V>> stronglyConnectedSets()

Computes a List of Sets, where each set contains vertices which together form a strongly connected component within the given graph.

Specified by:

stronglyConnectedSets in interface StrongConnectivityAlgorithm<V,E>

Returns:

List of Set s containing the strongly connected components

stronglyConnectedSubgraphs

public java.util.List<DirectedSubgraph<V,E>> 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.

Specified by:

stronglyConnectedSubgraphs in interface StrongConnectivityAlgorithm<V,E>

Returns:

a list of subgraphs representing the strongly connected components

createVertexNumber

private void createVertexNumber()

dfsVisit

private void dfsVisit(DirectedGraph<V,E> visitedGraph,
                      GabowStrongConnectivityInspector.VertexNumber<V> v)