Report a bug
If you spot a problem with this page, click here to create a Github issue.
Improve this page
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(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:
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.

See Also:
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;

auto components = gs.data.tarjan;

assert(components == [
    [0],
    [1, 2, 5, 4, 3, 6],
    [10],
    [7, 8, 9],
    [11]]);
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 == [[0], [1], [2], [3], [4]]);
Examples:
 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],
]);
Examples:
 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]]);
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[0]] ~ lvl2 ~ lvl1[1 .. $]]);