Tarjan: Difference between revisions

Content added Content deleted
(→‎{{header|zkl}}: added code)
Line 90:
const INDEX=0, LOW_LINK=1, ON_STACK=2;
fcn init(graph){
var index=0, stack=List(), components=List();, ▼
graph=graph.copy().sort(fcn(a,b){ a[0]<b[0] }); // sort to make id index
var G=graph.pump(List.createLong(graph.len()),0);▼
 
▲ var index=0, stack=List(), components=List();
 
// convert graph to ( (index,lowlink,onStack),(id,links)), ...)
// sorted by id
▲ var G=graph.pump(List.createLong(graph.len()),
foreach v in fcn(vgraph){ G[v[0]]=T( L(Void,Void,False),v) });
 
foreach v in (G){ if(v[0][INDEX]==Void) strongConnect(v) }
Line 137 ⟶ 136:
<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),
Retrieved from "https://rosettacode.org/wiki/Tarjan"