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.

License:

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 stackimport 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 .. $]]);

Copyright © 1999-2019 by the D Language Foundation | Page generated by
Ddoc on Wed May 22 12:05:40 2019