Topological sort: Difference between revisions
Content added Content deleted
(Add Tailspin solution) |
|||
Line 4,712: | Line 4,712: | ||
dw02 dw05 dw06 dw07 |
dw02 dw05 dw06 dw07 |
||
</pre> |
</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}}== |
=={{header|PicoLisp}}== |