org.graphstream.algorithm

## Class TarjanStronglyConnectedComponents

• java.lang.Object
• org.graphstream.algorithm.TarjanStronglyConnectedComponents
• All Implemented Interfaces:
Algorithm

```public class TarjanStronglyConnectedComponents
extends java.lang.Object
implements Algorithm```
Tarjan's Algorithm is a graph theory algorithm for finding the strongly connected components of a graph.

## Overview from Wikipedia

The algorithm takes a directed graph as input, and produces a partition of the graph's vertices into the graph's strongly connected components. Every vertex of the graph appears in a single strongly connected component, even if it means a vertex appears in a strongly connected component by itself (as is the case with tree-like parts of the graph, as well as any vertex with no successor or no predecessor).

The basic idea of the algorithm is this: a depth-first search begins from an arbitrary start node (and subsequent depth-first searches are conducted on any nodes that have not yet been found). The search does not explore any node that has already been explored. The strongly connected components form the subtrees of the search tree, the roots of which are the roots of the strongly connected components.

The nodes are placed on a stack in the order in which they are visited. When the search returns from a subtree, the nodes are taken from the stack and it is determined whether each node is the root of a strongly connected component. If a node is the root of a strongly connected component, then it and all of the nodes taken off before it form that strongly connected component.

## Usage

This algorithm use an attribute to store the component's index of each node. This attribute can be customized using `setSCCIndexAttribute(String)`. Index is generate with an index generator that can be customized using `setIndexGenerator(IndexGenerator)`

Computational Complexity:
O( | V | + | E | )
Scientific Reference:
Tarjan, R. E. (1972), "Depth-first search and linear graph algorithms", SIAM Journal on Computing 1 (2): 146–160, doi:10.1137/0201010
• ### Nested Class Summary

Nested Classes
Modifier and Type Class and Description
`static interface ` `TarjanStronglyConnectedComponents.IndexGenerator`
Defines objects able to generator index.
`static class ` `TarjanStronglyConnectedComponents.IntegerIndexGenerator`
Defines an index generator producing a sequence of integer as indexes.
• ### Constructor Summary

Constructors
Constructor and Description
`TarjanStronglyConnectedComponents()`
Build a new Tarjan algorithm.
• ### Method Summary

All Methods
Modifier and Type Method and Description
`void` `compute()`
Run the algorithm.
`java.lang.String` `defaultMessage()`
`java.lang.String` `getSCCIndexAttribute()`
Get the node attribute key where component index is stored.
`void` `init(org.graphstream.graph.Graph graph)`
Initialization of the algorithm.
`void` `setIndexGenerator(TarjanStronglyConnectedComponents.IndexGenerator gen)`
Set the generator of components indexes.
`void` `setSCCIndexAttribute(java.lang.String key)`
Set the node attribute key where component index is stored.
• ### Methods inherited from class java.lang.Object

`equals, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait`
• ### Constructor Detail

• #### TarjanStronglyConnectedComponents

`public TarjanStronglyConnectedComponents()`
Build a new Tarjan algorithm.
• ### Method Detail

• #### init

`public void init(org.graphstream.graph.Graph graph)`
Description copied from interface: `Algorithm`
Initialization of the algorithm. This method has to be called before the `Algorithm.compute()` method to initialize or reset the algorithm according to the new given graph.
Specified by:
`init` in interface `Algorithm`
Parameters:
`graph` - The graph this algorithm is using.
• #### compute

`public void compute()`
Description copied from interface: `Algorithm`
Run the algorithm. The `Algorithm.init(Graph)` method has to be called before computing.
Specified by:
`compute` in interface `Algorithm`
`Algorithm.init(Graph)`
• #### setIndexGenerator

`public void setIndexGenerator(TarjanStronglyConnectedComponents.IndexGenerator gen)`
Set the generator of components indexes.
Parameters:
`gen` - the new generator
• #### setSCCIndexAttribute

`public void setSCCIndexAttribute(java.lang.String key)`
Set the node attribute key where component index is stored.
Parameters:
`key` - attribute key of component index
• #### getSCCIndexAttribute

`public java.lang.String getSCCIndexAttribute()`
Get the node attribute key where component index is stored.
Returns:
the attribute key
• #### defaultMessage

`public java.lang.String defaultMessage()`