public class TarjanStronglyConnectedComponents extends Object implements Algorithm
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.
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)
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 and Description |
---|
TarjanStronglyConnectedComponents()
Build a new Tarjan algorithm.
|
Modifier and Type | Method and Description |
---|---|
void |
compute()
Run the algorithm.
|
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(String key)
Set the node attribute key where component index is stored.
|
public TarjanStronglyConnectedComponents()
public void init(org.graphstream.graph.Graph graph)
Algorithm
Algorithm.compute()
method to initialize or reset the algorithm according
to the new given graph.public void compute()
Algorithm
Algorithm.init(Graph)
method has to be called
before computing.compute
in interface Algorithm
Algorithm.init(Graph)
public void setIndexGenerator(TarjanStronglyConnectedComponents.IndexGenerator gen)
gen
- the new generatorpublic void setSCCIndexAttribute(String key)
key
- attribute key of component indexpublic String getSCCIndexAttribute()
Copyright © 2015. All rights reserved.