Rosetta Code

Topological sort: Difference between revisions

Page Discussion

Topological sort (view source)

Revision as of 18:52, 28 August 2022

2,963 bytes added ,  1 year ago
m
syntax highlighting fixup automation
m (→‎{{header|Object Pascal}}: changed highlighter from "Object Pascal" to pascal)
m (syntax highlighting fixup automation)
Line 56:
{{trans|Python}}
 
<langsyntaxhighlight lang="11l">V data = [
‘des_system_lib’ = Set(‘std synopsys std_cell_lib des_system_lib dw02 dw01 ramlib ieee’.split(‘ ’)),
‘dw01’ = Set(‘ieee dw01 dware gtech’.split(‘ ’)),
Line 104:
R r
 
print(toposort2(&data).join("\n"))</langsyntaxhighlight>
 
{{out}}
Line 120:
The specification:
 
<langsyntaxhighlight Adalang="ada">with Ada.Containers.Vectors; use Ada.Containers;
 
package Digraphs is
Line 171:
type Graph_Type is new Conn_Vec.Vector with null record;
 
end Digraphs;</langsyntaxhighlight>
 
The implementation:
 
<langsyntaxhighlight Adalang="ada">package body Digraphs is
 
function Node_Count(Graph: Graph_Type) return Node_Idx_With_Null is
Line 280:
end Top_Sort;
 
end Digraphs;</langsyntaxhighlight>
 
'''Set_of_Names: Translating strings into numbers and vice versa'''
Line 286:
The specification:
 
<langsyntaxhighlight Adalang="ada">private with Ada.Containers.Indefinite_Vectors;
 
generic
Line 327:
type Set is new Vecs.Vector with null record;
 
end Set_Of_Names;</langsyntaxhighlight>
 
The implementation
 
<langsyntaxhighlight Adalang="ada">package body Set_Of_Names is
 
use type Ada.Containers.Count_Type, Vecs.Cursor;
Line 398:
end Name;
 
end Set_Of_Names;</langsyntaxhighlight>
 
'''Toposort: Putting things together for the main program'''
 
<langsyntaxhighlight Adalang="ada">with Ada.Text_IO, Digraphs, Set_Of_Names, Ada.Command_Line;
 
procedure Toposort is
Line 484:
TIO.Put_Line("There is no topological sorting -- the Graph is cyclic!");
end;
end Toposort;</langsyntaxhighlight>
 
{{out}}
Line 496:
 
=={{header|Bracmat}}==
<langsyntaxhighlight lang="bracmat">( ("des_system_lib".std synopsys "std_cell_lib" "des_system_lib" dw02 dw01 ramlib ieee)
(dw01.ieee dw01 dware gtech)
(dw02.ieee dw02 dware)
Line 544:
& out$("
compile order:" !indeps !res "\ncycles:" !cycles)
);</langsyntaxhighlight>
{{out}}
<pre>compile order:
Line 571:
=={{header|C}}==
Parses a multiline string and show the compile order. Note that four lines were added to the example input to form two separate cycles. Code is a little ugly.
<langsyntaxhighlight lang="c">#include <stdio.h>
#include <stdlib.h>
#include <string.h>
Line 692:
 
return 0;
}</langsyntaxhighlight>
{{out}} (items on the same row can be compiled together)<syntaxhighlight lang="text">Compile order:
[unorderable] cycle_21 cycle_22
[unorderable] cycle_11 cycle_12
Line 699:
2: std_cell_lib ramlib dware gtech
3: dw02 dw01 dw05 dw06 dw07
4: des_system_lib dw03 dw04</langsyntaxhighlight>
 
=={{header|C sharp}}==
<langsyntaxhighlight lang="csharp">
namespace Algorithms
{
Line 843:
}
 
</syntaxhighlight>
</lang>
 
{{out}}<syntaxhighlight lang="text">B - depends on none
D - depends on none
G - depends on none
Line 854:
C - depends on D and E
A - depends on B and C
exiting...</langsyntaxhighlight>
{{out}}(with cycled dependency)<syntaxhighlight lang="text">Cycled dependencies detected: A C D
exiting...</langsyntaxhighlight>
 
=={{header|C++}}==
===C++11===
<langsyntaxhighlight lang="cpp">#include <map>
#include <set>
 
Line 996:
display_results(string(iterator(file), iterator()));
}
}</langsyntaxhighlight>
 
===C++17===
<langsyntaxhighlight lang="cpp">#include <unordered_map>
#include <unordered_set>
#include <vector>
Line 1,147:
 
return 0;
}</langsyntaxhighlight>
 
{{out}}<syntaxhighlight lang="text">I - depends on none
H - depends on none
G - depends on none
Line 1,167:
G - destroyed
H - destroyed
I - destroyed</langsyntaxhighlight>
{{out}}(with cycled dependency)<syntaxhighlight lang="text">Cycled dependencies detected: A D C
exiting...
A - destroyed
Line 1,178:
G - destroyed
H - destroyed
I - destroyed</langsyntaxhighlight>
 
=={{header|Clojure}}==
Line 1,192:
 
=====Implementation=====
<langsyntaxhighlight lang="clojure">(use 'clojure.set)
(use 'clojure.contrib.seq-utils)
 
Line 1,264:
[items]
(topo-sort-deps (deps items)))
</syntaxhighlight>
</lang>
 
Examples of sortable and non-sortable data:
 
<langsyntaxhighlight lang="clojure">(def good-sample
'(:des_system_lib (:std :synopsys :std_cell_lib :des_system_lib :dw02 :dw01 :ramlib :ieee)
:dw01 (:ieee :dw01 :dware :gtech)
Line 1,287:
 
(def bad-sample
(concat cyclic-dependence good-sample))</langsyntaxhighlight>
 
====={{out}}=====
<langsyntaxhighlight lang="clojure">Clojure 1.1.0
1:1 user=> #<Namespace topo>
1:2 topo=> (topo-sort good-sample)
(:std :synopsys :ieee :gtech :ramlib :dware :std_cell_lib :dw07 :dw06 :dw05 :dw01 :dw02 :des_system_lib :dw03 :dw04)
1:3 topo=> (topo-sort bad-sample)
"ERROR: cycles remain among (:dw01 :dw04 :dw03 :des_system_lib)"</langsyntaxhighlight>
 
=={{header|CoffeeScript}}==
<langsyntaxhighlight lang="coffeescript">
toposort = (targets) ->
# targets is hash of sets, where keys are parent nodes and
Line 1,395:
console.log toposort targets
</syntaxhighlight>
</lang>
 
=={{header|Common Lisp}}==
 
<langsyntaxhighlight lang="lisp">(defun topological-sort (graph &key (test 'eql))
"Graph is an association list whose keys are objects and whose
values are lists of objects on which the corresponding key depends.
Line 1,445:
all-sorted-p
(unless all-sorted-p
entries)))))))</langsyntaxhighlight>
 
Provided example in which all items can be sorted:
 
<langsyntaxhighlight lang="lisp">> (defparameter *dependency-graph*
'((des-system-lib std synopsys std-cell-lib des-system-lib dw02 dw01 ramlib ieee)
(dw01 ieee dw01 dware gtech)
Line 1,468:
(IEEE DWARE DW02 DW05 DW06 DW07 GTECH DW01 DW04 STD-CELL-LIB SYNOPSYS STD DW03 RAMLIB DES-SYSTEM-LIB)
T
NIL</langsyntaxhighlight>
 
Provided example with <code>dw04</code> added to the dependencies of <code>dw01</code>. Some vertices are ordered, but the second return is <code>nil</code>, indicating that not all vertices could be sorted. The third return value is the hash table containing entries for the four vertices that couldn't be sorted. (The variable <code>[http://www.lispworks.com/documentation/HyperSpec/Body/v_sl_sls.htm /]</code> stores the list of values produced by the last form, and <code>[http://www.lispworks.com/documentation/HyperSpec/Body/f_descri.htm describe]</code> prints information about an object.)
 
<langsyntaxhighlight lang="lisp">> (defparameter *dependency-graph*
'((des-system-lib std synopsys std-cell-lib des-system-lib dw02 dw01 ramlib ieee)
(dw01 ieee dw01 dw04 dware gtech)
Line 1,499:
DW04 (1 DW01)
DW03 (1)
DES-SYSTEM-LIB (1)</langsyntaxhighlight>
 
=={{header|Crystal}}==
<langsyntaxhighlight lang="crystal">def dfs_topo_visit(n, g, tmp, permanent, l)
if permanent.includes?(n)
return
Line 1,576:
puts ""
puts dfs_topo_sort(build_graph(data + circular_deps)).join(" -> ")
</syntaxhighlight>
</lang>
 
{{out}}
Line 1,587:
=={{header|D}}==
{{trans|Python}}
<langsyntaxhighlight lang="d">import std.stdio, std.string, std.algorithm, std.range;
 
final class ArgumentException : Exception {
Line 1,660:
foreach (const subOrder; depw.topoSort) // Should throw.
subOrder.writeln;
}</langsyntaxhighlight>
{{out}}
<pre>#1 : ["ieee", "std", "synopsys"]
Line 1,674:
=={{header|E}}==
 
<langsyntaxhighlight lang="e">def makeQueue := <elib:vat.makeQueue>
 
def topoSort(data :Map[any, Set[any]]) {
Line 1,722:
return result
}</langsyntaxhighlight>
 
<langsyntaxhighlight lang="e">pragma.enable("accumulator")
 
def dataText := "\
Line 1,744:
def data := accum [].asMap() for rx`(@item.{17})(@deps.*)` in dataText.split("\n") { _.with(item.trim(), deps.split(" ").asSet()) }
 
println(topoSort(data))</langsyntaxhighlight>
 
{{out}}
Line 1,754:
''' Data
 
<langsyntaxhighlight lang="lisp">
(define dependencies
'((des_system_lib std synopsys std_cell_lib des_system_lib dw02 dw01 ramlib ieee)
Line 1,781:
(define (add-dependencies g dep-list)
(for* ((dep dep-list) (b (rest dep))) (a->b g b (first dep))))
</syntaxhighlight>
</lang>
'''Implementation
 
Remove all vertices with in-degree = 0, until to one left. (in-degree = number of arrows to a vertex)
<langsyntaxhighlight lang="lisp">
;; topological sort
;;
Line 1,818:
(error " ♻️ t-sort:cyclic" (map vertex-label (graph-cycle g))))))
 
</syntaxhighlight>
</lang>
{{Out}}
<langsyntaxhighlight lang="lisp">
(define g (make-graph "VHDL"))
(add-dependencies g dependencies)
Line 1,834:
t-sort (std synopsys ieee dware dw02 dw05 dw06 dw07 gtech ramlib std_cell_lib)
⛔️ error: ♻️ t-sort:cyclic (dw04 dw01)
</syntaxhighlight>
</lang>
 
=={{header|Elixir}}==
{{trans|Erlang}}
<langsyntaxhighlight lang="elixir">defmodule Topological do
def sort(library) do
g = :digraph.new
Line 1,883:
IO.puts ""
bad_libraries = Keyword.update!(libraries, :dw01, &[:dw04 | &1])
Topological.sort(bad_libraries)</langsyntaxhighlight>
 
{{out}}
Line 1,895:
 
=={{header|Erlang}}==
<langsyntaxhighlight lang="erlang">
-module(topological_sort).
-compile(export_all).
Line 1,967:
digraph:add_vertex(G,D), % noop if dependency already added
digraph:add_edge(G,D,L). % Dependencies represented as an edge D -> L
</syntaxhighlight>
</lang>
 
{{out}}
<langsyntaxhighlight lang="erlang">
62> topological_sort:main().
synopsys -> std -> ieee -> dware -> dw02 -> dw05 -> ramlib -> std_cell_lib -> dw06 -> dw07 -> gtech -> dw01 -> des_system_lib -> dw03 -> dw04
Line 1,976:
dw04 -> dw01 -> dw04
dw01 -> dw04 -> dw01
ok</langsyntaxhighlight>
 
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).
Line 2,018:
 
{{works with|Gforth}}
<langsyntaxhighlight lang="forth">variable nodes 0 nodes ! \ linked list of nodes
 
: node. ( body -- )
Line 2,088:
deps dw01 ieee dw01 dware gtech dw04
 
all-nodes</langsyntaxhighlight>
 
{{out}}
Line 2,103:
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).
<langsyntaxhighlight lang="fortran"> SUBROUTINE TSORT(NL,ND,IDEP,IORD,IPOS,NO)
IMPLICIT NONE
INTEGER NL,ND,NO,IDEP(ND,2),IORD(NL),IPOS(NL),I,J,K,IL,IR,IPL,IPR
Line 2,126:
IF(K.GT.J) GO TO 20
NO=J-1
END</langsyntaxhighlight>
 
An example. Dependencies are encoded to make program shorter (in array ICODE).
 
<langsyntaxhighlight lang="fortran"> PROGRAM EX_TSORT
IMPLICIT NONE
INTEGER NL,ND,NC,NO,IDEP,IORD,IPOS,ICODE,I,J,IL,IR
Line 2,167:
DO 50 I=NO+1,NL
50 PRINT*,LABEL(IORD(I))
END</langsyntaxhighlight>
 
{{out}}
Line 2,212:
===Modern Fortran===
A modern Fortran (95-2008) version of the TSORT subroutine is shown here (note that the IPOS array is not an input).
<langsyntaxhighlight lang="fortran">subroutine tsort(nl,nd,idep,iord,no)
 
implicit none
Line 2,249:
 
end subroutine tsort
</syntaxhighlight>
</lang>
 
=={{header|FunL}}==
<langsyntaxhighlight lang="funl">def topsort( graph ) =
val L = seq()
val S = seq()
Line 2,312:
case topsort( graph ) of
None -> println( 'un-orderable' )
Some( ordering ) -> println( ordering )</langsyntaxhighlight>
 
{{out}}
Line 2,322:
=={{header|Go}}==
===Kahn===
<langsyntaxhighlight lang="go">package main
 
import (
Line 2,461:
}
return L, nil
}</langsyntaxhighlight>
{{out}}
<pre>
Line 2,473:
Topological sort only, this function can replace topSortKahn in above program. The
in-degree list is not needed.
<langsyntaxhighlight lang="go">// General purpose topological sort, not specific to the application of
// library dependencies. Also adapted from Wikipedia pseudo code.
func topSortDFS(g graph) (order, cyclic []string) {
Line 2,520:
}
return L, nil
}</langsyntaxhighlight>
{{out}}
(when used in program of Kahn example.)
Line 2,532:
 
=={{header|Haskell}}==
<langsyntaxhighlight lang="haskell">import Data.List ((\\), elemIndex, intersect, nub)
import Data.Bifunctor (bimap, first)
 
Line 2,575:
 
main :: IO ()
main = print $ toposort depLibs</langsyntaxhighlight>
{{out}}
<langsyntaxhighlight lang="haskell">*Main> toposort depLibs
["std","synopsys","ieee","std_cell_lib","dware","dw02","gtech","dw01","ramlib","des_system_lib","dw03","dw04","dw05","dw06","dw07"]
 
*Main> toposort $ (\(xs,(k,ks):ys) -> xs++ (k,ks++" dw04"):ys) $ splitAt 1 depLibs
*** Exception: Dependency cycle detected for libs [["dw01","dw04"]]</langsyntaxhighlight>
 
=={{header|Huginn}}==
<langsyntaxhighlight lang="huginn">import Algorithms as algo;
import Text as text;
 
Line 2,656:
dfs = DepthFirstSearch();
print( "{}\n".format( dfs.topological_sort( dg ) ) );
}</langsyntaxhighlight>
 
==Icon and Unicon==
Line 2,669:
elements have been built.
 
<langsyntaxhighlight lang="icon">record graph(nodes,arcs)
global ex_name, in_name
 
Line 2,783:
g.arcs ? while arc := move(2) do if arc[1] == f then t ++:= arc[2]
return t
end</langsyntaxhighlight>
 
{{out}}
Line 2,810:
in parallel once the elements in the preceding lines have been built.
 
<langsyntaxhighlight lang="icon">record graph(nodes,arcs)
 
procedure main()
Line 2,896:
while (af := @cp, at := @cp) do if af == f then insert(t, at)
return t
end</langsyntaxhighlight>
 
=={{header|J}}==
 
<langsyntaxhighlight Jlang="j">dependencySort=: monad define
parsed=. <@;:;._2 y
names=. {.&>parsed
Line 2,907:
assert.-.1 e. (<0 1)|:depends
(-.&names ~.;parsed),names /: +/"1 depends
)</langsyntaxhighlight>
 
With the sample data set:
Line 2,929:
We would get:
 
<langsyntaxhighlight Jlang="j"> >dependencySort dependencies
std
ieee
Line 2,944:
dw04
dw03
des_system_lib</langsyntaxhighlight>
 
If we tried to also make dw01 depend on dw04, the sort would fail because of the circular dependency:
 
<langsyntaxhighlight Jlang="j"> dependencySort dependencies,'dw01 dw04',LF
|assertion failure: dependencySort
| -.1 e.(<0 1)|:depends</langsyntaxhighlight>
 
Here is an alternate implementation which uses a slightly different representation for the dependencies (instead of a boolean connection matrix to represent connections, we use a list of lists of indices to represent connections):
 
<langsyntaxhighlight Jlang="j">depSort=: monad define
parsed=. <@;:;._2 y
names=. {.&>parsed
Line 2,961:
assert.-.1 e. (i.@# e.S:0"0 ])depends
(-.&names ~.;parsed),names /: #@> depends
)</langsyntaxhighlight>
 
It's results are identical to the first implementation, but this might be more efficient in typical cases.
Line 2,967:
=={{header|Java}}==
{{works with|Java|7}}
<langsyntaxhighlight lang="java">import java.util.*;
 
public class TopologicalSort {
Line 3,043:
return false;
}
}</langsyntaxhighlight>
 
<pre>[std, ieee, dware, dw02, dw05, dw06, dw07, gtech, dw01, dw04, ramlib, std_cell_lib, synopsys, des_system_lib, dw03]</pre>
Line 3,051:
====ES6====
 
<langsyntaxhighlight JavaScriptlang="javascript">const libs =
`des_system_lib std synopsys std_cell_lib des_system_lib dw02 dw01 ramlib ieee
dw01 ieee dw01 dware gtech
Line 3,108:
 
console.log('Solution:', S);
</langsyntaxhighlight>
 
Output:
<syntaxhighlight lang="javascript">
<lang JavaScript>
Solution: [
'ieee',
Line 3,128:
'dw03',
'des_system_lib' ]
</syntaxhighlight>
</lang>
 
=={{header|jq}}==
Line 3,149:
 
To solve and print the solution to the given problem on a 1GHz machine takes about 5ms.
<langsyntaxhighlight lang="jq"># independent/0 emits an array of the dependencies that have no dependencies
# Input: an object representing a normalized dependency graph
def independent:
Line 3,199:
normalize | [[], .] | _tsort ;
 
tsort</langsyntaxhighlight>
Data:
<langsyntaxhighlight lang="json">{"des_system_lib": [ "std", "synopsys", "std_cell_lib", "des_system_lib", "dw02", "dw01", "ramlib", "ieee"],
"dw01": [ "ieee", "dw01", "dware", "gtech"],
"dw02": [ "ieee", "dw02", "dware"],
Line 3,215:
"synopsys": []
}
</syntaxhighlight>
</lang>
{{Out}}
<syntaxhighlight lang="jq">
<lang jq>
$ jq -c -f tsort.jq tsort.json
["ieee","std","synopsys","dware","gtech","ramlib","std_cell_lib","dw01","dw02","des_system_lib","dw03","dw04","dw05","dw06","dw07"]
</syntaxhighlight>
</lang>
 
=={{header|Julia}}==
Line 3,226:
{{trans|Python}}
 
<langsyntaxhighlight lang="julia">function toposort(data::Dict{T,Set{T}}) where T
data = copy(data)
for (k, v) in data
Line 3,262:
)
 
println("# Topologically sorted:\n - ", join(toposort(data), "\n - "))</langsyntaxhighlight>
 
{{out}}
Line 3,284:
=={{header|Kotlin}}==
{{trans|Java}}
<langsyntaxhighlight lang="scala">// version 1.1.51
 
val s = "std, ieee, des_system_lib, dw01, dw02, dw03, dw04, dw05, " +
Line 3,351:
println("Following the addition of dw04 to the dependencies of dw01:")
println(g2.topoSort())
}</langsyntaxhighlight>
 
{{out}}
Line 3,367:
This version follows python implementation and returns List of Lists which is useful for parallel execution for example
</pre>
<langsyntaxhighlight lang="scala">
val graph = mapOf(
"des_system_lib" to "std synopsys std_cell_lib des_system_lib dw02 dw01 ramlib ieee".split(" ").toSet(),
Line 3,420:
}
 
</syntaxhighlight>
</lang>
{{out}}
<pre>
Line 3,432:
 
=={{header|M2000 Interpreter}}==
<langsyntaxhighlight M2000lang="m2000 Interpreterinterpreter">Module testthis {
\\ empty stack
Flush
Line 3,529:
}
testthis
</syntaxhighlight>
</lang>
{{out}}
<pre>
Line 3,541:
=={{header|Mathematica}}/{{header|Wolfram Language}}==
Work in Mathematica 8 or higher versions.
<langsyntaxhighlight lang="mathematica">TopologicalSort[
Graph[Flatten[# /. {l_, ld_} :>
Map[# -> l &,
Line 3,559:
{"ramlib", {"std", "ieee"}},
{"std_cell_lib", {"ieee", "std_cell_lib"}},
{"synopsys", {}}}</langsyntaxhighlight>
{{Out}}
<pre>{"ieee", "std_cell_lib", "gtech", "dware", "dw07", "dw06", "dw05", \
Line 3,567:
 
=={{header|Mercury}}==
<syntaxhighlight lang="mercury">
<lang Mercury>
:- module topological_sort.
 
Line 3,645:
print(CompileOrder,!IO).
 
</syntaxhighlight>
</lang>
 
=={{header|Nim}}==
 
<langsyntaxhighlight Nimlang="nim">import sequtils, strutils, sets, tables, sugar
 
type StringSet = HashSet[string]
Line 3,731:
for key in data.keys: echo key
except ValueError:
echo getCurrentExceptionMsg()</langsyntaxhighlight>
 
=={{header|Object Pascal}}==
Written for Free Pascal, but will probably work in Delphi if you change the required units.
<langsyntaxhighlight lang="pascal">
program topologicalsortrosetta;
 
Line 4,148:
InputList.Free;
end.
</syntaxhighlight>
</lang>
 
=={{header|OCaml}}==
 
<langsyntaxhighlight lang="ocaml">let dep_libs = [
("des_system_lib", ["std"; "synopsys"; "std_cell_lib"; "des_system_lib"; "dw02"; "dw01"; "ramlib"; "ieee"]);
("dw01", (*"dw04"::*)["ieee"; "dw01"; "dware"; "gtech"]);
Line 4,205:
print_string "result: \n ";
print_endline (String.concat ", " res);
;;</langsyntaxhighlight>
 
If dw04 is added to the set of dependencies of dw01 to make the data un-orderable (uncomment it), an exception is raised:
Line 4,211:
 
=={{header|OxygenBasic}}==
<syntaxhighlight lang="text">
'TOPOLOGICAL SORT
 
Line 4,428:
next
ret
</syntaxhighlight>
</lang>
 
 
=={{header|Oz}}==
Using constraint propagation and search:
<langsyntaxhighlight lang="oz">declare
Deps = unit(
des_system_lib: [std synopsys std_cell_lib des_system_lib
Line 4,518:
{System.showInfo "\nBONUS - grouped by parallelizable compile jobs:"}
{PrintSolution Sol}
end</langsyntaxhighlight>
 
Output:
Line 4,554:
The algorithm used allows the output to be clustered; libraries on the same line are all independent (given the building of any previous lines of libraries), and so could be built in parallel.
 
<langsyntaxhighlight lang="perl">sub print_topo_sort {
my %deps = @_;
 
Line 4,592:
print_topo_sort(%deps);
push @{ $deps{'dw01'} }, 'dw04'; # Add unresolvable dependency
print_topo_sort(%deps);</langsyntaxhighlight>
 
Output:<pre>ieee std synopsys
Line 4,606:
=={{header|Phix}}==
Implemented as a trivial normal sort.
<!--<langsyntaxhighlight Phixlang="phix">(phixonline)-->
<span style="color: #004080;">sequence</span> <span style="color: #000000;">names</span>
<span style="color: #008080;">enum</span> <span style="color: #000000;">RANK</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">NAME</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">DEP</span> <span style="color: #000080;font-style:italic;">-- content of names
Line 4,697:
<span style="color: #7060A8;">puts</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"\nbad input:\n"</span><span style="color: #0000FF;">)</span>
<span style="color: #000000;">topsort</span><span style="color: #0000FF;">(</span><span style="color: #000000;">input</span><span style="color: #0000FF;">&</span><span style="color: #008000;">"\ndw01 dw04"</span><span style="color: #0000FF;">)</span>
<!--</langsyntaxhighlight>-->
{{out}}
Items on the same line can be compiled at the same time, and each line is alphabetic.
Line 4,714:
 
=={{header|Picat}}==
<langsyntaxhighlight Picatlang="picat">topological_sort(Precedences, Sorted) =>
 
Edges = [K=V : [K,V] in Precedences],
Line 4,743:
% 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].</langsyntaxhighlight>
 
The approach was inspired by a SETL snippet:
Line 4,756:
===Test without cycles===
Identify and remove the cycles.
<langsyntaxhighlight Picatlang="picat">main =>
deps(1,Deps),
Prec=[],
Line 4,782:
std_cell_lib=[ieee,std_cell_lib],
synopsys=[]
].</langsyntaxhighlight>
 
{{out}}
Line 4,788:
 
===Test with cycles===
<langsyntaxhighlight Picatlang="picat">main =>
deps(with_cycle,Deps),
Prec=[],
Line 4,819:
cycle_3=[dw01,cycle_4,dw02,daw03],
cycle_4=[cycle_3,dw01,dw04]
].</langsyntaxhighlight>
 
{{out}}
Line 4,830:
 
=={{header|PicoLisp}}==
<langsyntaxhighlight PicoLisplang="picolisp">(de sortDependencies (Lst)
(setq Lst # Build a flat list
(uniq
Line 4,844:
(del (link @) 'Lst) # Yes: Store in result
(for This Lst # and remove from 'dep's
(=: dep (delete @ (: dep))) ) ) ) ) )</langsyntaxhighlight>
Output:
<pre>: (sortDependencies
Line 4,864:
 
=={{header|PowerShell}}==
<langsyntaxhighlight PowerShelllang="powershell">#Input Data
$a=@"
des_system_lib std synopsys std_cell_lib des_system_lib dw02 dw01 ramlib ieee
Line 4,962:
"{0,-14} $($_."Library Dependencies")" -f $_.Library
}
}</langsyntaxhighlight>
 
=={{header|PureBasic}}==
<langsyntaxhighlight PureBasiclang="purebasic">#EndOfDataMarker$ = "::EndOfData::"
DataSection
;"LIBRARY: [LIBRARY_DEPENDENCY_1 LIBRARY_DEPENDENCY_2 ... LIBRARY_DEPENDENCY_N]
Line 5,083:
Print(#CRLF$ + #CRLF$ + "Press ENTER to exit")
Input()
CloseConsole()</langsyntaxhighlight>
Sample output for no dependencies:
<pre>Compile order:
Line 5,113:
 
===Python 3===
<langsyntaxhighlight lang="python">try:
from functools import reduce
except:
Line 5,148:
assert not data, "A cyclic dependency exists amongst %r" % data
 
print ('\n'.join( toposort2(data) ))</langsyntaxhighlight>
 
'''Ordered output'''<br>
Line 5,166:
 
===Python 3.9 graphlib===
<langsyntaxhighlight lang="python">from graphlib import TopologicalSorter
 
# LIBRARY mapped_to LIBRARY DEPENDENCIES
Line 5,189:
 
ts = TopologicalSorter(data)
print(tuple(ts.static_order()))</langsyntaxhighlight>
 
{{out}}
Line 5,197:
 
First make the list
<syntaxhighlight lang="r">
<lang R>
deps <- list(
"des_system_lib" = c("std", "synopsys", "std_cell_lib", "des_system_lib", "dw02", "dw01", "ramlib", "ieee"),
Line 5,212:
"std_cell_lib" = c("ieee", "std_cell_lib"),
"synopsys" = c())
</syntaxhighlight>
</lang>
 
Topological sort function. It will throw an error if it cannot complete, printing the list of items which cannot be ordered.
If it succeeds, returns the list of items in topological order.
<syntaxhighlight lang="r">
<lang R>
tsort <- function(deps) {
nm <- names(deps)
Line 5,248:
s
}
</syntaxhighlight>
</lang>
 
On the given example :
<syntaxhighlight lang="r">
<lang R>
tsort(deps)
# [1] "std" "ieee" "dware" "gtech" "ramlib"
# [6] "std_cell_lib" "synopsys" "dw01" "dw02" "dw03"
#[11] "dw04" "dw05" "dw06" "dw07" "des_system_lib"
</syntaxhighlight>
</lang>
 
If dw01 depends on dw04 as well :
 
<syntaxhighlight lang="r">
<lang R>
Unorderable items :
des_system_lib
Line 5,266:
dw04
dw03
</syntaxhighlight>
</lang>
 
=={{header|Racket}}==
<langsyntaxhighlight lang="racket">
#lang racket
 
Line 5,328:
 
(topo-sort (clean G))
</syntaxhighlight>
</lang>
Output:
<langsyntaxhighlight lang="racket">
'(synopsys ieee dware gtech std_cell_lib std ramlib dw07 dw06 dw05 dw01 dw04 dw02 dw03 des_system_lib)
</syntaxhighlight>
</lang>
 
=={{header|Raku}}==
Line 5,338:
{{trans|Perl}}
{{Works with|rakudo|2016.01}}
<syntaxhighlight lang="raku" perl6line>sub print_topo_sort ( %deps ) {
my %ba;
for %deps.kv -> $before, @afters {
Line 5,374:
print_topo_sort(%deps);
%deps<dw01> = <ieee dw01 dware gtech dw04>; # Add unresolvable dependency
print_topo_sort(%deps);</langsyntaxhighlight>
 
Output:<pre>ieee std synopsys
Line 5,394:
Some of the FORTRAN 77 statements were converted to &nbsp; '''do''' &nbsp; loops (or &nbsp; '''do''' &nbsp; structures), &nbsp; and
<br>some variables were &nbsp; [https://en.wikipedia.org/wiki/Camel_case <u>''camel capitalized]''</u>.
<langsyntaxhighlight lang="rexx">/*REXX pgm does a topological sort (orders such that no item precedes a dependent item).*/
iDep.= 0; iPos.= 0; iOrd.= 0 /*initialize some stemmed arrays to 0.*/
nL= 15; nd= 44; nc= 69 /* " " "parms" and indices.*/
Line 5,436:
end /*i*/
end /*until*/
nO= j-1; return</langsyntaxhighlight>
{{out|output}}
<pre>
Line 5,463:
=={{header|Ruby}}==
Uses the [http://www.ruby-doc.org/stdlib/libdoc/tsort/rdoc/classes/TSort.html TSort] module from the Ruby stdlib.
<langsyntaxhighlight lang="ruby">require 'tsort'
class Hash
include TSort
Line 5,500:
ramlib std ieee
std_cell_lib ieee std_cell_lib
synopsys</langsyntaxhighlight>
{{out}}
<pre>
Line 5,509:
 
=={{header|Rust}}==
<langsyntaxhighlight lang="rust">use std::boxed::Box;
use std::collections::{HashMap, HashSet};
 
Line 5,621:
}
}
</syntaxhighlight>
</lang>
Output:
<pre>
Line 5,648:
=={{header|Scheme}}==
{{trans|Python}}
<langsyntaxhighlight lang="scheme">
(import (chezscheme))
(import (srfi srfi-1))
Line 5,734:
(newline)
(write (topological-sort unsortable))
</syntaxhighlight>
</lang>
 
=={{header|Sidef}}==
{{trans|Perl}}
<langsyntaxhighlight lang="ruby">func print_topo_sort (deps) {
var ba = Hash.new;
deps.each { |before, afters|
Line 5,779:
print_topo_sort(deps);
deps{:dw01}.append('dw04'); # Add unresolvable dependency
print_topo_sort(deps);</langsyntaxhighlight>
{{out}}
<pre>
Line 5,797:
{{trans|Rust}}
 
<langsyntaxhighlight lang="swift">let libs = [
("des_system_lib", ["std", "synopsys", "std_cell_lib", "des_system_lib", "dw02", "dw01", "ramlib", "ieee"]),
("dw01", ["ieee", "dw01", "dware", "gtech"]),
Line 5,865:
}
 
print(topologicalSort(libs: buildLibraries(libs))!)</langsyntaxhighlight>
 
{{out}}
Line 5,872:
 
=={{header|Tailspin}}==
<langsyntaxhighlight lang="tailspin">
data node <'.+'>, from <node>, to <node>
 
Line 5,917:
synopsys
' -> lines -> collectDeps -> topologicalSort -> !OUT::write
</syntaxhighlight>
</lang>
 
{{out}}
Line 5,926:
=={{header|Tcl}}==
{{works with|Tcl|8.5}}
<langsyntaxhighlight lang="tcl">package require Tcl 8.5
proc topsort {data} {
# Clean the data
Line 5,962:
}
}
}</langsyntaxhighlight>
Demonstration code (which parses it from the format that the puzzle was posed in):
<langsyntaxhighlight lang="tcl">set inputData {
des_system_lib std synopsys std_cell_lib des_system_lib dw02 dw01 ramlib ieee
dw01 ieee dw01 dware gtech
Line 5,983:
dict set parsedData [lindex $line 0] [lrange $line 1 end]
}
puts [topsort $parsedData]</langsyntaxhighlight>
Sample output:
<pre>ieee std synopsys dware gtech ramlib std_cell_lib dw01 dw02 dw05 dw06 dw07 des_system_lib dw03 dw04</pre>
Line 5,995:
 
{{works with|Bourne Shell}}
<langsyntaxhighlight lang="bash">$ awk '{ for (i = 1; i <= NF; i++) print $i, $1 }' <<! | tsort
> des_system_lib std synopsys std_cell_lib des_system_lib dw02 dw01 ramlib ieee
> dw01 ieee dw01 dware gtech
Line 6,024:
dw03
ramlib
des_system_lib</langsyntaxhighlight>
 
If the graph of dependencies contains a cycle, [[BSD]]'s tsort(1) will print messages to standard error, break the cycle (by deleting one of the dependencies), continue the sort, and exit 0. So if dw04 becomes a dependency of dw01, then tsort(1) finds the cycle between dw01 and dw04.
Line 6,053:
unorderable libraries, if any, on the right. Self-dependences are
ignored and unlisted libraries are presumed independent.
<langsyntaxhighlight Ursalalang="ursala">tsort = ~&nmnNCjA*imSLs2nSjiNCSPT; @NiX ^=lxPrnSPX ^(~&rlPlT,~&rnPrmPljA*D@r)^|/~& ~&m!=rnSPlX</langsyntaxhighlight>
test program:
<langsyntaxhighlight Ursalalang="ursala">#import std
dependence_table = -[
Line 6,079:
#show+
 
main = <.~&l,@r ~&i&& 'unorderable: '--> mat` ~~ tsort parse dependence_table</langsyntaxhighlight>
With the given table, the output is
<pre>
Line 6,092:
=={{header|VBScript}}==
=====Implementation=====
<syntaxhighlight lang="vb">
<lang vb>
class topological
dim dictDependencies
Line 6,172:
end property
end class
</syntaxhighlight>
</lang>
 
=====Invocation=====
<syntaxhighlight lang="vb">
<lang vb>
dim toposort
set toposort = new topological
Line 6,199:
toposort.reset
next
</syntaxhighlight>
</lang>
 
=====Output=====
Line 6,282:
=={{header|Visual Basic .NET}}==
Adapted from http://tawani.blogspot.com/2009/02/topological-sorting-and-cyclic.html which was itself an adaptation of Java code. I added the Rosetta code specific format of dependencies, as well as checks for references to self.
<langsyntaxhighlight lang="vbnet">' Adapted from:
' http://tawani.blogspot.com/2009/02/topological-sorting-and-cyclic.html
' added/changed:
Line 6,611:
#End Region
End Class
</syntaxhighlight>
</lang>
=====Output=====
<pre>
Line 6,695:
=={{header|Wren}}==
{{trans|Kotlin}}
<langsyntaxhighlight lang="ecmascript">class Graph {
construct new(s, edges) {
_vertices = s.split(", ")
Line 6,760:
var g2 = Graph.new(s, deps)
System.print("Following the addition of dw04 to the dependencies of dw01:")
System.print(g2.topoSort())</langsyntaxhighlight>
 
{{out}}
Line 6,774:
{{trans|Wikipedia}}
Input data is munged
<langsyntaxhighlight lang="zkl">fcn topoSort(data){ // data is L( L(root,L(leaves)),...)
allDs:=data.pump(List,fcn(rds){ T(Void.Write,Void.Write,rds[1]) }).copy();
roots:=Dictionary(data); // dictionary of root:leaves
Line 6,788:
if(roots) throw(Exception.ValueError("Cycle: "+roots.keys));
L
}</langsyntaxhighlight>
<langsyntaxhighlight lang="zkl">data:=T(
"des_system_lib", "std synopsys std_cell_lib des_system_lib dw02 dw01 ramlib ieee",
"dw01", "ieee dw01 dware gtech",
Line 6,807:
T( r, ds.replace(r,"").strip().split().copy() ) // leaves writable 'cause they will be
});
topoSort(data).println();</langsyntaxhighlight>
{{out}}
<pre>
Thundergnat
10,333

edits

Retrieved from "https://rosettacode.org/wiki/Special:MobileDiff/328614"