Package org.graph4j.connectivity

Class TarjanStrongConnectivity

java.lang.Object

org.graph4j.DirectedGraphAlgorithm

org.graph4j.connectivity.TarjanStrongConnectivity

All Implemented Interfaces:

StrongConnectivityAlgorithm

public class TarjanStrongConnectivity
extends DirectedGraphAlgorithm
implements StrongConnectivityAlgorithm

Tarjan's strongly connected components algorithm is an algorithm in graph theory for finding the strongly connected components (SCCs) of a directed graph. It runs in linear time, matching the time bound for alternative methods including Kosaraju's algorithm and the path-based strong component algorithm.

Author:

Cristian Frăsinaru

Field Summary

Fields inherited from class org.graph4j.DirectedGraphAlgorithm

graph, stronglyConnected

Constructor Summary

Constructors

Constructor	Description
TarjanStrongConnectivity(Digraph digraph)

Method Summary

Modifier and Type	Method	Description
protected void	compute(boolean checkOnly)
Digraph<Digraph,Integer>	createCondensation()	Each strongly connected component is contracted to a single vertex, the resulting graph is a directed acyclic graph, the condensation.
List<Digraph>	getStronglyConnectedComponents()
List<VertexSet>	getStronglyConnectedSets()
boolean	isStronglyConnected()	Returns true if the digraph is strongly connected.

Methods inherited from class java.lang.Object

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

Constructor Details

TarjanStrongConnectivity

public TarjanStrongConnectivity(Digraph digraph)

Method Details

isStronglyConnected

public boolean isStronglyConnected()

Description copied from class: DirectedGraphAlgorithm

Returns true if the digraph is strongly connected.

Specified by:

isStronglyConnected in interface StrongConnectivityAlgorithm

Overrides:

isStronglyConnected in class DirectedGraphAlgorithm

Returns:

true if the digraph is strongly connected.

getStronglyConnectedSets

public List<VertexSet> getStronglyConnectedSets()

Specified by:

getStronglyConnectedSets in interface StrongConnectivityAlgorithm

Returns:

a list of vertex sets, each representing the vertices of a strongly connected component.

getStronglyConnectedComponents

public List<Digraph> getStronglyConnectedComponents()

Specified by:

getStronglyConnectedComponents in interface StrongConnectivityAlgorithm

Returns:

a list of digraphs, each representing a strongly connected component.

compute

protected void compute(boolean checkOnly)

createCondensation

public Digraph<Digraph,Integer> createCondensation()

Description copied from interface: StrongConnectivityAlgorithm

Each strongly connected component is contracted to a single vertex, the resulting graph is a directed acyclic graph, the condensation. Each vertex of the condensation is labeled with the corresponding strongly connected component. Each edge vu of the condensation is labeled with the number of edges from the component of v to to the component of u in the original digrpah.

Specified by:

createCondensation in interface StrongConnectivityAlgorithm

Returns:

the condensation digraph.