Tarjan: Difference between revisions
Content deleted Content added
→{{header|zkl}}: added code |
m →{{header|zkl}}: tweak |
||
Line 90: | Line 90: | ||
const INDEX=0, LOW_LINK=1, ON_STACK=2; |
const INDEX=0, LOW_LINK=1, ON_STACK=2; |
||
fcn init(graph){ |
fcn init(graph){ |
||
⚫ | |||
graph=graph.copy().sort(fcn(a,b){ a[0]<b[0] }); // sort to make id index |
|||
⚫ | |||
⚫ | |||
// convert graph to ( (index,lowlink,onStack),(id,links)), ...) |
// 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) } |
foreach v in (G){ if(v[0][INDEX]==Void) strongConnect(v) } |
||
Line 137: | Line 136: | ||
<lang zkl> // graph from https://en.wikipedia.org/wiki/Tarjan%27s_strongly_connected_components_algorithm |
<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) |
// 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), ...) |
graph:= // ( (id, links/Edges), ...) |
||
T( T(0,1), T(2,0), T(5,2,6), T(6,5), |
T( T(0,1), T(2,0), T(5,2,6), T(6,5), |