SCC

java.lang.Object
- org.stekikun.dolmen.common.SCC<Node>

Type Parameters:

Node - the type of nodes in the graph
```
public final class SCC<Node>
extends Object
```
Describes the strongly-connected components of some graph described by an implementation of SCC.Graph. The components are computed via of(Graph) using Tarjan's 1972 algorithm:
```
   Tarjan, R. E. (1972), "Depth-first search and linear graph algorithms", 
   SIAM Journal on Computing, 1 (2): 146–160
 
```
Components can then be investigated individually, all at once, or simply by using the representative(Object) function which maps every node in the graph to a unique node representing its strongly-connected component.
Author:

Stéphane Lescuyer

Nested Class Summary

Nested Classes
Modifier and Type Class and Description

static interface SCC.Graph<Node>
Interface describing a directed graph whose vertices can be indexed by integers.

Nested Classes
Modifier and Type	Class and Description
`static interface`	`SCC.Graph<Node>` Interface describing a directed graph whose vertices can be indexed by integers.

Method Summary

All Methods Static Methods Instance Methods Concrete Methods
Modifier and Type	Method and Description
`int`	`count()`
`void`	`iter(Consumer<List<Node>> f)` Iterates the given function `f` on all the strongly-connected components, in reverse topological order (i.e. a component is always visited before any of its successors).
`static <Node> SCC<Node>`	`of(SCC.Graph<Node> graph)` Computes and returns an instance of `SCC` which describes the strongly connected components of the given `graph`.
`Node`	`representative(Node n)` The node must belong to the graph for which this `SCC` was computed.
`List<Node>`	`scc(Node n)` The node must belong to the graph for which this `SCC` was computed.
`String`	`toString()`

Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait

- Method Detail
  - of
```
public static <Node> SCC<Node> of(SCC.Graph<Node> graph)
```
    Computes and returns an instance of SCC which describes the strongly connected components of the given graph.
    
    Parameters:
    
    graph -
    
    Returns:
    
    the strongly connected components of graph
    
    See Also:
    
    count(), scc(Object), iter(Consumer)
  - count
```
public int count()
```
    Returns:
    
    the number of different strongly-connected components
  - scc
```
public List<Node> scc(Node n)
```
    The node must belong to the graph for which this SCC was computed.
    
    Parameters:
    
    n -
    
    Returns:
    
    the strongly-connected component of the node n, where nodes are presented in no particular order
  - representative
```
public Node representative(Node n)
```
    The node must belong to the graph for which this SCC was computed. Representatives are such that two nodes n and m are in the same strongly-connected component if and only if representative(n) == representative(m).
    
    Parameters:
    
    n -
    
    Returns:
    
    the representative of n's strongly-connected component
  - iter
```
public void iter(Consumer<List<Node>> f)
```
    Iterates the given function f on all the strongly-connected components, in reverse topological order (i.e. a component is always visited before any of its successors). The relative order of nodes in each component is unspecified.
    
    Parameters:
    
    f -
  - toString
```
public String toString()
```
    Overrides:
    
    toString in class Object

Class SCC<Node>

Nested Class Summary

Method Summary

Methods inherited from class java.lang.Object

Method Detail

of

count

scc

representative

iter

toString