Topological sort: Difference between revisions
Content added Content deleted
m (→{{header|zkl}}: add space) |
(Added EchoLisp) |
||
| Line 1,200: | Line 1,200: | ||
{{out}} |
{{out}} |
||
<code>["std", "synopsys", "ieee", "dware", "gtech", "ramlib", "std_cell_lib", "dw02", "dw05", "dw06", "dw07", "dw01", "des_system_lib", "dw03", "dw04"]</code> |
<code>["std", "synopsys", "ieee", "dware", "gtech", "ramlib", "std_cell_lib", "dw02", "dw05", "dw06", "dw07", "dw01", "des_system_lib", "dw03", "dw04"]</code> |
||
=={{header|Echolisp}}== |
|||
We use the low-level primitives of the 'graph' library to build the directed graph and implement the topological sort. |
|||
''' Data |
|||
<lang lisp> |
|||
(define dependencies |
|||
'((des_system_lib std synopsys std_cell_lib des_system_lib dw02 dw01 ramlib ieee) |
|||
(dw01 ieee dw01 dware gtech) ;; bad graph add dw04 |
|||
(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 ))) |
|||
;; build dependency graph |
|||
;; a depends on b |
|||
;; add arc (arrow) a --> b |
|||
(lib 'graph.lib) |
|||
(define (a->b g a b) |
|||
(unless (equal? a b) |
|||
(graph-make-arc g (graph-make-vertex g a) (graph-make-vertex g b)))) |
|||
(define (add-dependencies g dep-list) |
|||
(for* ((dep dep-list) (b (rest dep))) (a->b g b (first dep)))) |
|||
</lang> |
|||
'''Implementation |
|||
Remove all vertices with in-degree = 0, until to one left. (in-degree = number of arrows to a vertex) |
|||
<lang lisp> |
|||
;; topological sort |
|||
;; |
|||
;; Complexity O (# of vertices + # of edges) |
|||
(define (t-sort g) |
|||
(stack 'Z) ; vertices of d°(0) |
|||
(stack 'S) ; ordered result |
|||
;; mark all vertices with their in-degree = # of incoming arcs |
|||
;; push all vertices u such as d°(u) = 0 |
|||
(for ((u g)) (mark u (graph-vertex-indegree g u)) |
|||
(when (zero? (mark? u)) (push 'Z u))) |
|||
;pop a d°(0) vertex u - add it to result |
|||
;decrement in-degree of all v vertices u->v |
|||
; if d°(v) = 0, push it |
|||
(while (not (stack-empty? 'Z)) |
|||
(let (( u (pop 'Z))) |
|||
(push 'S u) |
|||
(for ((v (graph-vertex-out g u))) |
|||
(mark v (1- (mark? v))) |
|||
(when (zero? (mark? v)) (push 'Z v))))) |
|||
;; finish |
|||
(writeln 't-sort (map vertex-label (stack->list 'S))) |
|||
;; check no one remaining |
|||
(for ((u g)) |
|||
(unless (zero? (mark? u)) |
|||
(error " ♻️ t-sort:cyclic" (map vertex-label (graph-cycle g)))))) |
|||
</lang> |
|||
{{Out}} |
|||
<lang lisp> |
|||
(define g (make-graph "VHDL")) |
|||
(add-dependencies g dependencies) |
|||
(graph-print g) |
|||
(t-sort g) |
|||
→ t-sort (std synopsys ieee dware dw02 dw05 dw06 dw07 gtech dw01 dw03 dw04 ramlib std_cell_lib |
|||
;; Error case |
|||
;; add dw01 -> dw04 |
|||
(t-sort g) |
|||
t-sort (std synopsys ieee dware dw02 dw05 dw06 dw07 gtech ramlib std_cell_lib) |
|||
⛔️ error: ♻️ t-sort:cyclic (dw04 dw01) |
|||
</lang> |
|||
=={{header|Erlang}}== |
=={{header|Erlang}}== |
||
<lang erlang> |
<lang erlang> |
||