50 lines
1.9 KiB
Text
50 lines
1.9 KiB
Text
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){
|
|
var index=0, stack=List(), components=List(),
|
|
G=List.createLong(graph.len(),0);
|
|
|
|
// 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) }
|
|
|
|
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
|
|
}
|
|
}
|
|
}
|