Class GabowStrongConnectivityInspector<V,E>

java.lang.Object

org.jgrapht.alg.connectivity.AbstractStrongConnectivityInspector<V,E>

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 AbstractStrongConnectivityInspector<V,E>

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|)$.

Nested Class Summary

Nested Classes

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

Field Summary

Fields

Modifier and Type	Field	Description
private int	c
private Deque<GabowStrongConnectivityInspector.VertexNumber<V>>	stackB
private Deque<GabowStrongConnectivityInspector.VertexNumber<V>>	stackS
private Map<V, GabowStrongConnectivityInspector.VertexNumber<V>>	vertexToVertexNumber

Fields inherited from class AbstractStrongConnectivityInspector

graph, stronglyConnectedSets, stronglyConnectedSubgraphs

Constructor Summary

Constructors

Constructor	Description
GabowStrongConnectivityInspector(Graph<V,E> graph)	Constructor

Method Summary

Modifier and Type	Method	Description
private Set<V>	createSCCVertexSetAndNumberVertices(GabowStrongConnectivityInspector.VertexNumber<V> v)
private void	createVertexNumber()
private void	dfsVisit(GabowStrongConnectivityInspector.VertexNumber<V> v)
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.

Methods inherited from class AbstractStrongConnectivityInspector

getCondensation, getGraph, getStronglyConnectedComponents, isStronglyConnected

Methods inherited from class Object

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

Field Details

stackS

private Deque<GabowStrongConnectivityInspector.VertexNumber<V>> stackS

stackB

private Deque<GabowStrongConnectivityInspector.VertexNumber<V>> stackB

vertexToVertexNumber

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

c

private int c

Constructor Details

GabowStrongConnectivityInspector

public GabowStrongConnectivityInspector(Graph<V,E> graph)

Constructor

Parameters:

graph - the graph to inspect

Throws:

NullPointerException - in case the graph is null

Method Details

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

createVertexNumber

private void createVertexNumber()

dfsVisit

private void dfsVisit(GabowStrongConnectivityInspector.VertexNumber<V> v)

createSCCVertexSetAndNumberVertices

private Set<V> createSCCVertexSetAndNumberVertices(GabowStrongConnectivityInspector.VertexNumber<V> v)