Anonymous user
Tarjan: Difference between revisions
→{{header|zkl}}: added code
m (→{{header|C sharp|C#}}: added zkl header) |
(→{{header|zkl}}: added code) |
||
Line 84:
=={{header|zkl}}==
<lang zkl>
// input: graph G = (V, Es)
<lang zkl></lang>▼
// 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){
graph=graph.copy().sort(fcn(a,b){ a[0]<b[0] }); // sort to make id index
var index=0, stack=List(), components=List();
// convert graph to ( (index,lowlink,onStack),(id,links)), ...)
var G=graph.pump(List.createLong(graph.len()),
fcn(v){ 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 zkl> // graph from https://en.wikipedia.org/wiki/Tarjan%27s_strongly_connected_components_algorithm
// with vertices id zero based (vs 1 based in article)
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>
{{out}}
<pre>
0,1,2
5,6
3,4
7
</pre>
| |||