Report a bug
Quickly fork, edit online, and submit a pull request for this page. Requires a signed-in GitHub account. This works well for small changes. If you'd like to make larger changes you may want to consider using a local clone.

# mir.graph.tarjan

This is a submodule of mir.graph.
Tarjan's strongly connected components algorithm.
Authors:
Ilya Yaroshenko
auto `tarjan`(bool RC = false, G, I = Unqual!(ForeachType!(ForeachType!G)))(G `graph`)
if (isUnsigned!I);
Classic Tarjan's strongly connected components algorithm.
Tarjan's algorithm is an algorithm in graph theory for finding the strongly connected components of a graph. It runs in linear time, matching the time bound for alternative methods including Kosaraju's algorithm and the path-based strong component algorithm.
The implementation is loop based. It does not use recursion and does not have stack overflow issues.

Complexity worst-case O(|V| + |E|).

Parameters:
 RC nogc mode, refcounted output G `graph` components (ndslice) sorted in the direction of traversal of the graph. Each component is an array of indeces.
Returns:
components (ndslice of arrays of indexes)

Note The implementation returns components sorted in the direction of traversal of the graph.

Examples:
```        4 <- 5 <- 6 -------> 7 -> 8 -> 11
|    ^   ^           ^    |
v    |   |           |    |
0 -> 1 -> 2 -> 3 -> 10     9 <---
```
```import mir.graph;
import mir.graph.tarjan;

GraphSeries!(string, uint) gs = [
"00": ["01"],
"01": ["02"],
"02": ["05", "03"],
"03": ["06", "10"],
"04": ["01"],
"05": ["04"],
"06": ["05", "07"],
"07": ["08"],
"08": ["09", "11"],
"09": ["07"],
"10": [],
"11": [],
].graphSeries;

static immutable result = [
,
[1, 2, 5, 4, 3, 6],
,
[7, 8, 9],
];

// chec GC interface
auto components = gs.data.tarjan;
assert(components == result);
// check @nogc interface
// Note: The lambda function is used here to show @nogc mode explicitly.
auto rccomponents = (() @nogc => gs.data.tarjan!true )();
assert(rccomponents == result);
```
Examples:
Tests that the graph 0 -> 1 -> 2 -> 3 -> 4 returns 4 components.
```import mir.graph;
import mir.graph.tarjan;

GraphSeries!(char, uint) gs = [
'a': ['b'],
'b': ['c'],
'c': ['d'],
'd': ['q'],
'q': [],
].graphSeries;

auto scc = gs.data.tarjan;

assert(scc == [, , , , ]);
```
Examples:
``` 0 <- 2 <-- 5 <--> 6
|  ^ ^ ^___
v_|  |     |      _
1 <- 3 <-> 4 <-- 7_|
```
```import mir.graph;
import mir.graph.tarjan;

auto gs = [
0: ,
1: ,
2: ,
3: [1, 2, 4],
4: [3, 2],
5: [2, 6],
6: ,
7: [4, 7],
].graphSeries;

auto components = gs.data.tarjan;

assert(components == [
,
[5, 6],
[3, 4],
[0, 1, 2],
]);
```
Examples:
``` 2 <-> 1
|    ^
v_0 /

```
```import mir.graph;
import mir.graph.tarjan;

auto gs = [
0: ,
1: ,
2: [0, 1],
].graphSeries;

auto components = gs.data.tarjan;

assert(components == [[0, 1, 2]]);
```
Examples:
Tests that a strongly connected graph, where components have to get through previously visited components to get to the graph root works properly
This test demonstrates a hard to detect bug, where vertices were being marked 'off-stack' after they were first visited, not when they were actually removed from the stack
```import mir.graph;
import mir.graph.tarjan;

auto root = 0;
auto lvl1 = [1,2,3,4,5,6,7,8,9,10];
auto lvl2 = [11,12,13,14,15,16,17,18,19,20];

int[][int] aar;
aar[root] = lvl1;
foreach(int v; lvl1)
aar[v] = lvl2;
foreach(int v; lvl2)
aar[v] = [root];

auto gs = aar.graphSeries;

auto components = gs.data.tarjan;

assert(components == [[root] ~ [lvl1] ~ lvl2 ~ lvl1[1 .. \$]]);
```