Anonymous user
Topological sort: Difference between revisions
m
{{out}}
(Updated D entry) |
m ({{out}}) |
||
Line 2:
Given a mapping between items, and items they depend on, a [[wp:Topological sorting|topological sort]] orders items so that no item precedes an item it depends upon.
The compiling of a library in the [[wp:VHDL|VHDL]] language has the constraint that a library must be compiled after any library it depends on.
A tool exists that extracts library dependencies.
The task is to '''write a function that will return a valid compile order of VHDL libraries from their dependencies.'''
* Assume library names are single words.
Line 403 ⟶ 405:
end Toposort;</lang>
{{out}}
Given the name of the file with the dependencies as the parameter,
<pre>std -> synopsys -> ieee -> std_cell_lib -> dware -> dw02 -> gtech -> dw01 -> ramlib -> des_system_lib -> dw03 -> dw04 -> dw05 -> dw06 -> dw07</pre>
Line 463 ⟶ 464:
compile order:" !indeps !res "\ncycles:" !cycles)
);</lang>
{{out}}
<pre>compile order:
ieee
Line 610 ⟶ 611:
return 0;
}</lang>
{{out}}
[unorderable] cycle_21 cycle_22
[unorderable] cycle_11 cycle_12
Line 727 ⟶ 729:
(concat cyclic-dependence good-sample))</lang>
=====
<lang clojure>Clojure 1.1.0
1:1 user=> #<Namespace topo>
Line 1,100 ⟶ 1,102:
println(topoSort(data))</lang>
{{out}}
=={{header|Erlang}}==
<lang erlang>
Line 1,176 ⟶ 1,179:
</lang>
{{out}}
<lang erlang>
62> topological_sort:main().
Line 1,185 ⟶ 1,188:
ok</lang>
Erlang has a built in digraph library and datastructure. ''digraph_utils'' contains the ''top_sort'' function which provides a topological sort of the vertices or returns false if it's not possible (due to circular references).
The ''digraph'' module contains ''get_short_cycle'' which returns the shortest cycle involving a vertex.
=={{header|Fortran}}==
Line 1,195 ⟶ 1,199:
''Output'' : IORD(1:NO) is the compile order, and IORD(NO+1:NL) contains unordered libraries.
This implementation is not optimal: for each ''level'' of dependency (for example A -> B -> C counts as three levels), there is a loop through all dependencies in IDEP.
It would be possible to optimize a bit, without changing the main idea, by first sorting IDEP according to first column, and using more temporary space, keeping track of where is located data in IDEP for each library (all dependencies of a same library being grouped).
<lang fortran> SUBROUTINE TSORT(NL,ND,IDEP,IORD,IPOS,NO)
IMPLICIT NONE
Line 1,262 ⟶ 1,267:
END</lang>
{{out}}
<pre>
COMPILE ORDER
Line 1,283 ⟶ 1,288:
</pre>
<pre>
COMPILE ORDER
Line 1,624 ⟶ 1,629:
$ map (\[(a,as), (b,bs)] -> (a `intersect` bs) ++ (b `intersect`as))
$ combs 2 dB</lang>
{{out}}
<lang haskell>*Main> toposort depLibs
["std","synopsys","ieee","std_cell_lib","dware","dw02","gtech","dw01","ramlib","des_system_lib","dw03","dw04","dw05","dw06","dw07"]
Line 1,758 ⟶ 1,763:
end</lang>
{{out}}
<pre>->tsort <tsort.data
Line 1,964 ⟶ 1,968:
}</lang>
{{out}}
<pre>
[std, synopsys, ieee, dware, gtech, ramlib, std_cell_lib, dw02, dw05, dw06, dw07, dw01, des_system_lib, dw03, dw04]
| |||