Tarjan: Difference between revisions
m (→{{header|zkl}}: tweak) |
(Go solution) |
||
Line 82: | Line 82: | ||
} |
} |
||
}</lang> |
}</lang> |
||
=={{header|Go}}== |
|||
<lang go>package main |
|||
import ( |
|||
"fmt" |
|||
"math/big" |
|||
) |
|||
// (same data as zkl example) |
|||
var g = [][]int{ |
|||
0: {1}, |
|||
2: {0}, |
|||
5: {2, 6}, |
|||
6: {5}, |
|||
1: {2}, |
|||
3: {1, 2, 4}, |
|||
4: {5, 3}, |
|||
7: {4, 7, 6}, |
|||
} |
|||
func main() { |
|||
tarjan(g, func(c []int) { fmt.Println(c) }) |
|||
} |
|||
// the function calls the emit argument for each component identified. |
|||
// each component is a list of nodes. |
|||
func tarjan(g [][]int, emit func([]int)) { |
|||
var indexed, stacked big.Int |
|||
index := make([]int, len(g)) |
|||
lowlink := make([]int, len(g)) |
|||
x := 0 |
|||
var S []int |
|||
var sc func(int) bool |
|||
sc = func(n int) bool { |
|||
index[n] = x |
|||
indexed.SetBit(&indexed, n, 1) |
|||
lowlink[n] = x |
|||
x++ |
|||
S = append(S, n) |
|||
stacked.SetBit(&stacked, n, 1) |
|||
for _, nb := range g[n] { |
|||
if indexed.Bit(nb) == 0 { |
|||
if !sc(nb) { |
|||
return false |
|||
} |
|||
if lowlink[nb] < lowlink[n] { |
|||
lowlink[n] = lowlink[nb] |
|||
} |
|||
} else if stacked.Bit(nb) == 1 { |
|||
if index[nb] < lowlink[n] { |
|||
lowlink[n] = index[nb] |
|||
} |
|||
} |
|||
} |
|||
if lowlink[n] == index[n] { |
|||
var c []int |
|||
for { |
|||
last := len(S) - 1 |
|||
w := S[last] |
|||
S = S[:last] |
|||
stacked.SetBit(&stacked, w, 0) |
|||
c = append(c, w) |
|||
if w == n { |
|||
emit(c) |
|||
break |
|||
} |
|||
} |
|||
} |
|||
return true |
|||
} |
|||
for n := range g { |
|||
if indexed.Bit(n) == 0 && !sc(n) { |
|||
return |
|||
} |
|||
} |
|||
}</lang> |
|||
{{out}} |
|||
<pre> |
|||
[2 1 0] |
|||
[6 5] |
|||
[4 3] |
|||
[7] |
|||
</pre> |
|||
=={{header|zkl}}== |
=={{header|zkl}}== |
Revision as of 22:19, 21 May 2017
This page uses content from Wikipedia. The original article was at Graph. The list of authors can be seen in the page history. As with Rosetta Code, the text of Wikipedia is available under the GNU FDL. (See links for details on variance) |
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. Tarjan's Algorithm is named for its discoverer, Robert Tarjan.
- References
- The article on Wikipedia.
C#
<lang csharp>using System; using System.Collections.Generic;
class Node { public int LowLink { get; set; } public int Index { get; set; } public int N { get; }
public Node(int n) { N = n; Index = -1; LowLink = 0; } }
class Graph { public HashSet<Node> V { get; } public Dictionary<Node, HashSet<Node>> Adj { get; }
/// <summary> /// Tarjan's strongly connected components algorithm /// </summary> public void Tarjan() { var index = 0; // number of nodes var S = new Stack<Node>();
Action<Node> StrongConnect = null; StrongConnect = (v) => { // Set the depth index for v to the smallest unused index v.Index = index; v.LowLink = index;
index++; S.Push(v);
// Consider successors of v foreach (var w in Adj[v]) if (w.Index < 0) { // Successor w has not yet been visited; recurse on it StrongConnect(w); v.LowLink = Math.Min(v.LowLink, w.LowLink); } else if (S.Contains(w)) // Successor w is in stack S and hence in the current SCC v.LowLink = Math.Min(v.LowLink, w.Index);
// If v is a root node, pop the stack and generate an SCC if (v.LowLink == v.Index) { Console.Write("SCC: ");
Node w; do { w = S.Pop(); Console.Write(w.N + " "); } while (w != v);
Console.WriteLine(); } };
foreach (var v in V) if (v.Index < 0) StrongConnect(v); } }</lang>
Go
<lang go>package main
import (
"fmt" "math/big"
)
// (same data as zkl example) var g = [][]int{
0: {1}, 2: {0}, 5: {2, 6}, 6: {5}, 1: {2}, 3: {1, 2, 4}, 4: {5, 3}, 7: {4, 7, 6},
}
func main() {
tarjan(g, func(c []int) { fmt.Println(c) })
}
// the function calls the emit argument for each component identified. // each component is a list of nodes. func tarjan(g [][]int, emit func([]int)) {
var indexed, stacked big.Int index := make([]int, len(g)) lowlink := make([]int, len(g)) x := 0 var S []int var sc func(int) bool sc = func(n int) bool { index[n] = x indexed.SetBit(&indexed, n, 1) lowlink[n] = x x++ S = append(S, n) stacked.SetBit(&stacked, n, 1) for _, nb := range g[n] { if indexed.Bit(nb) == 0 { if !sc(nb) { return false } if lowlink[nb] < lowlink[n] { lowlink[n] = lowlink[nb] } } else if stacked.Bit(nb) == 1 { if index[nb] < lowlink[n] { lowlink[n] = index[nb] } } } if lowlink[n] == index[n] { var c []int for { last := len(S) - 1 w := S[last] S = S[:last] stacked.SetBit(&stacked, w, 0) c = append(c, w) if w == n { emit(c) break } } } return true } for n := range g { if indexed.Bit(n) == 0 && !sc(n) { return } }
}</lang>
- Output:
[2 1 0] [6 5] [4 3] [7]
zkl
<lang zkl>class Tarjan{
// input: graph G = (V, Es) // output: set of strongly connected components (sets of vertices) // Ick: class holds global state for strongConnect(), otherwise inert const INDEX=0, LOW_LINK=1, ON_STACK=2; fcn init(graph){ var index=0, stack=List(), components=List(), G=List.createLong(graph.len(),0);
// convert graph to ( (index,lowlink,onStack),(id,links)), ...) // sorted by id foreach v in (graph){ G[v[0]]=T( L(Void,Void,False),v) }
foreach v in (G){ if(v[0][INDEX]==Void) strongConnect(v) }
println("List of strongly connected components:"); foreach c in (components){ println(c.reverse().concat(",")) }
returnClass(components); // over-ride return of class instance } fcn strongConnect(v){ // v is ( (index,lowlink,onStack), (id,links) ) // Set the depth index for v to the smallest unused index v0:=v[0]; v0[INDEX]=v0[LOW_LINK]=index; index+=1; v0[ON_STACK]=True; stack.push(v);
// Consider successors of v foreach idx in (v[1][1,*]){ // links of v to other vs w,w0 := G[idx],w[0]; // well, that is pretty vile
if(w[0][INDEX]==Void){ strongConnect(w); // Successor w not yet visited; recurse on it v0[LOW_LINK]=v0[LOW_LINK].min(w0[LOW_LINK]); } else if(w0[ON_STACK]) // Successor w is in stack S and hence in the current SCC v0[LOW_LINK]=v0[LOW_LINK].min(w0[INDEX]);
} // If v is a root node, pop the stack and generate an SCC if(v0[LOW_LINK]==v0[INDEX]){ strong:=List(); // start a new strongly connected component
do{ w,w0 := stack.pop(), w[0]; w0[ON_STACK]=False; strong.append(w[1][0]); // add w to strongly connected component }while(w.id!=v.id); components.append(strong); // output strongly connected component
} }
}</lang> <lang zkl> // graph from https://en.wikipedia.org/wiki/Tarjan%27s_strongly_connected_components_algorithm
// with vertices id zero based (vs 1 based in article) // ids start at zero and are consecutive (no holes), graph is unsorted
graph:= // ( (id, links/Edges), ...)
T( T(0,1), T(2,0), T(5,2,6), T(6,5), T(1,2), T(3,1,2,4), T(4,5,3), T(7,4,7,6) );
Tarjan(graph);</lang>
- Output:
0,1,2 5,6 3,4 7