Tarjan: Difference between revisions
Content added Content deleted
m (→{{header|C sharp|C#}}: added zkl header) |
(→{{header|zkl}}: added code) |
||
Line 84: | Line 84: | ||
=={{header|zkl}}== |
=={{header|zkl}}== |
||
<lang 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){ |
|||
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}} |
{{out}} |
||
<pre> |
<pre> |
||
0,1,2 |
|||
5,6 |
|||
3,4 |
|||
7 |
|||
</pre> |
</pre> |