Class KosarajuStrongConnectivityInspector<V,E>

java.lang.Object

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

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

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 AbstractStrongConnectivityInspector.isStronglyConnected().

Nested Class Summary

Nested Classes

Modifier and Type	Class	Description
private static class	KosarajuStrongConnectivityInspector.VertexData<V>
private static final class	KosarajuStrongConnectivityInspector.VertexData1<V>
private static final class	KosarajuStrongConnectivityInspector.VertexData2<V>

Field Summary

Fields

Modifier and Type	Field	Description
private LinkedList<KosarajuStrongConnectivityInspector.VertexData<V>>	orderedVertices
private Map<V, KosarajuStrongConnectivityInspector.VertexData<V>>	vertexToVertexData

Fields inherited from class AbstractStrongConnectivityInspector

graph, stronglyConnectedSets, stronglyConnectedSubgraphs

Constructor Summary

Constructors

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

Method Summary

Modifier and Type	Method	Description
private void	createVertexData()
private void	dfsVisit(Graph<V,E> visitedGraph, KosarajuStrongConnectivityInspector.VertexData<V> vertexData, Set<V> vertices)
private void	resetVertexData()
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

orderedVertices

private LinkedList<KosarajuStrongConnectivityInspector.VertexData<V>> orderedVertices

vertexToVertexData

private Map<V, KosarajuStrongConnectivityInspector.VertexData<V>> vertexToVertexData

Constructor Details

KosarajuStrongConnectivityInspector

public KosarajuStrongConnectivityInspector(Graph<V,E> graph)

Constructor

Parameters:

graph - the input graph

Throws:

NullPointerException - if the input 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

createVertexData

private void createVertexData()

dfsVisit

private void dfsVisit(Graph<V,E> visitedGraph,
 KosarajuStrongConnectivityInspector.VertexData<V> vertexData,
 Set<V> vertices)

resetVertexData

private void resetVertexData()