15 lines
728 B
Text
15 lines
728 B
Text
fcn topoSort(data){ // data is L( L(root,L(leaves)),...)
|
|
allDs:=data.pump(List,fcn(rds){ T(Void.Write,Void.Write,rds[1]) }).copy();
|
|
roots:=Dictionary(data); // dictionary of root:leaves
|
|
L:=List();
|
|
S:=data.pump(List,'wrap([(r,_)]){ if(allDs.holds(r)) Void.Skip else r }).copy();
|
|
while(S){ //while S is non-empty do
|
|
(n:=S.pop()) : L.append(_); //remove a node n from S, add n to tail of L
|
|
foreach m in (ds:=roots.find(n,List)){ //node m with an edge e from n to m
|
|
allDs.del(allDs.index(m));
|
|
if (Void==allDs.find(m)) S.append(m); //m has no other incoming edges
|
|
} roots.del(n); // remove edge e from the graph
|
|
}
|
|
if(roots) throw(Exception.ValueError("Cycle: "+roots.keys));
|
|
L
|
|
}
|