Package org.jgrapht.alg.connectivity

Class KosarajuStrongConnectivityInspector<V,E>

java.lang.Object

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

Type Parameters:

V - the graph vertex type

E - the graph edge type

All Implemented Interfaces:

StrongConnectivityAlgorithm<V,E>

public class KosarajuStrongConnectivityInspector<V,E>
extends java.lang.Object

Computes strongly connected components of a directed graph. The algorithm is implemented after "Cormen et al: Introduction to algorithms", Chapter 22.5. It has a running time of $O(V + E)$.

Unlike ConnectivityInspector, this class does not implement incremental inspection. The full algorithm is executed at the first call of stronglyConnectedSets() or StrongConnectivityAlgorithm.isStronglyConnected().

Author:

Christian Soltenborn, Christian Hammer

Field Summary

Fields

Modifier and Type	Field	Description
protected Graph<V,E>	graph
protected java.util.List<java.util.Set<V>>	stronglyConnectedSets
protected java.util.List<Graph<V,E>>	stronglyConnectedSubgraphs

Constructor Summary

Constructors

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

Method Summary

Modifier and Type	Method	Description
Graph<Graph<V,E>,DefaultEdge>	getCondensation()	Compute the condensation of the given graph.
Graph<V,E>	getGraph()	Return the underlying graph.
java.util.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.
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.

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 java.util.List<java.util.Set<V>> stronglyConnectedSets

stronglyConnectedSubgraphs

protected java.util.List<Graph<V,E>> stronglyConnectedSubgraphs

Constructor Detail

KosarajuStrongConnectivityInspector

public KosarajuStrongConnectivityInspector(Graph<V,E> graph)

Constructor

Parameters:

graph - the input graph

Throws:

java.lang.NullPointerException - if the input graph is null

Method Detail

stronglyConnectedSets

public java.util.List<java.util.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

getStronglyConnectedComponents

public java.util.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