Tarjan: Difference between revisions

Content added Content deleted

Inline

@@ Line 90: / 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
+          G=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()),
-         fcn(v){ T( L(Void,Void,False),v) });
+      foreach v in (graph){ G[v[0]]=T( L(Void,Void,False),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
    // 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),