tarjan

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|).

pragma(inline, false)

@optmath

auto

tarjan

(

bool RC = false

I = Unqual!(ForeachType!(ForeachType!G))

)

(

G graph

)

if (

isUnsigned!I

)

Parameters

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

Return Value

Type: auto

components (ndslice of arrays of indices)

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

Most of other Tarjan implementations returns reverse order.

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 = [
    [0],
    [1, 2, 5, 4, 3, 6],
    [10],
    [7, 8, 9],
    [11]];

// 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);

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 == [[0], [1], [2], [3], [4]]);

0 <- 2 <-- 5 <--> 6
|  ^ ^ ^___       
v_|  |     |      _ 
1 <- 3 <-> 4 <-- 7_|

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

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

auto components = gs.data.tarjan;

assert(components == [
    [7],
    [5, 6],
    [3, 4],
    [0, 1, 2],
]);

2 <-> 1
|    ^
v_0 /

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

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

auto components = gs.data.tarjan;

assert(components == [[0, 1, 2]]);

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[0]] ~ lvl2 ~ lvl1[1 .. $]]);

tarjan

Parameters

Return Value

Examples

See Also

Meta

Source