30 lines
844 B
Text
30 lines
844 B
Text
topological_sort(Precedences, Sorted) =>
|
|
|
|
Edges = [K=V : [K,V] in Precedences],
|
|
Nodes = (domain(Edges) ++ range(Edges)).remove_dups(),
|
|
Sorted1 = [],
|
|
while (member(X,Nodes), not membchk(X,range(Edges)))
|
|
Sorted1 := Sorted1 ++ [X],
|
|
Nodes := Nodes.delete(X),
|
|
Edges := Edges.delete_key(X)
|
|
end,
|
|
% detect and remove a cycle
|
|
if Nodes.length > 0 then
|
|
println("\nThe graph is cyclic. Here's the detected cycle."),
|
|
println(nodes_in_cycle=Nodes),
|
|
println(edges_in_cycle=Edges),
|
|
Sorted = [without_cycle=Sorted1,cycle=Nodes]
|
|
else
|
|
Sorted = Sorted1
|
|
end,
|
|
nl.
|
|
|
|
% domain are the keys in L
|
|
domain(L) = [K : K=_V in L].
|
|
|
|
% range are the values of L
|
|
range(L) = [V : _K=V in L].
|
|
|
|
% deletes all pairs in L where a key is X
|
|
% (this is lessf on a multi-map in GNU SETL)
|
|
delete_key(L,X) = [K=V : K=V in L, K!=X].
|