Topological sort: Difference between revisions
→{{header|Picat}}
(Add Tailspin solution) |
|||
Line 4,712:
dw02 dw05 dw06 dw07
</pre>
=={{header|Picat}}==
<lang Picat>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].</lang>
The approach was inspired by a SETL snippet:
<pre>(while exists x in nodes | x notin range edges)
print(x);
nodes less:= x;
edges lessf:= x;
end;</pre>
Note: In contract to SETL, Picat doesn't support multi-maps, so this version uses a list of K=V (i.e. key=value).
===Test without cycles===
Identify and remove the cycles.
<lang Picat>main =>
deps(1,Deps),
Prec=[],
foreach(Lib=Dep in Deps)
Prec := Prec ++ [[D,Lib] : D in Dep, D != Lib]
end,
topological_sort(Prec,Sort),
println(Sort),
nl.
% Dependencies
deps(1,Deps) =>
Deps = [
des_system_lib=[std,synopsys,std_cell_lib,des_system_lib,dw02,dw01,ramlib,ieee],
dw01=[ieee,dw01,dware,gtech],
dw02=[ieee,dw02,dware],
dw03=[std,synopsys,dware,dw03,dw02,dw01,ieee,gtech],
dw04=[dw04,ieee,dw01,dware,gtech],
dw05=[dw05,ieee,dware],
dw06=[dw06,ieee,dware],
dw07=[ieee,dware],
dware=[ieee,dware],
gtech=[ieee,gtech],
ramlib=[std,ieee],
std_cell_lib=[ieee,std_cell_lib],
synopsys=[]
].</lang>
{{out}}
<pre>[std,synopsys,ieee,std_cell_lib,ramlib,dware,dw02,gtech,dw01,des_system_lib,dw03,dw04,dw05,dw06,dw07]</pre>
===Test with cycles===
<lang Picat>main =>
deps(with_cycle,Deps),
Prec=[],
foreach(Lib=Dep in Deps)
Prec := Prec ++ [[D,Lib] : D in Dep, D != Lib]
end,
topological_sort(Prec,Sort),
println(Sort),
nl.
deps(with_cycle,Deps) =>
Deps = [
des_system_lib=[std,synopsys,std_cell_lib,des_system_lib,dw02,dw01,ramlib,ieee],
% dw01=[ieee,dw01,dware,gtech], % orig
dw01=[ieee,dw01,dware,gtech,dw04], % make a cycle
dw02=[ieee,dw02,dware],
dw03=[std,synopsys,dware,dw03,dw02,dw01,ieee,gtech],
dw04=[dw04,ieee,dw01,dware,gtech],
dw05=[dw05,ieee,dware],
dw06=[dw06,ieee,dware],
dw07=[ieee,dware],
dware=[ieee,dware],
gtech=[ieee,gtech],
ramlib=[std,ieee],
std_cell_lib=[ieee,std_cell_lib],
synopsys=[],
% And some other cycles
cycle_1=[cycle_2],
cycle_2=[cycle_1],
cycle_3=[dw01,cycle_4,dw02,daw03],
cycle_4=[cycle_3,dw01,dw04]
].</lang>
{{out}}
<pre>The graph is cyclic. Here's the detected cycle.
nodes_in_cycle = [dw01,dw04,cycle_2,cycle_1,cycle_4,cycle_3,des_system_lib,dw03]
edges_in_cycle = [dw01 = des_system_lib,dw04 = dw01,dw01 = dw03,dw01 = dw04,cycle_2 = cycle_1,cycle_1 = cycle_2,dw01 = cycle_3,cycle_4 = cycle_3,cycle_3 = cycle_4,dw01 = cycle_4,dw04 = cycle_4]
[without_cycle = [std,synopsys,ieee,std_cell_lib,ramlib,dware,dw02,gtech,daw03,dw05,dw06,dw07],cycle = [dw01,dw04,cycle_2,cycle_1,cycle_4,cycle_3,des_system_lib,dw03]]</pre>
=={{header|PicoLisp}}==
| |||