Topological sort: Difference between revisions
m
→{{header|Wren}}: Changed to Wren S/H
Thundergnat (talk | contribs) (Rename Perl 6 -> Raku, alphabetize, minor clean-up) |
m (→{{header|Wren}}: Changed to Wren S/H) |
||
| (48 intermediate revisions by 23 users not shown) | |||
Line 1:
{{task|Sorting Algorithms}}
[[Category:Sorting]]
{{Sorting Algorithm}}
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.
Line 48 ⟶ 52:
[http://www.embeddedrelated.com/showarticle/799.php "Ten little algorithms, part 4: topological sort"] </ref>
<br><br>
=={{header|11l}}==
{{trans|Python}}
<syntaxhighlight 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(‘ ’)),
‘dw02’ = Set(‘ieee dw02 dware’.split(‘ ’)),
‘dw03’ = Set(‘std synopsys dware dw03 dw02 dw01 ieee gtech’.split(‘ ’)),
‘dw04’ = Set(‘dw04 ieee dw01 dware gtech’.split(‘ ’)),
‘dw05’ = Set(‘dw05 ieee dware’.split(‘ ’)),
‘dw06’ = Set(‘dw06 ieee dware’.split(‘ ’)),
‘dw07’ = Set(‘ieee dware’.split(‘ ’)),
‘dware’ = Set(‘ieee dware’.split(‘ ’)),
‘gtech’ = Set(‘ieee gtech’.split(‘ ’)),
‘ramlib’ = Set(‘std ieee’.split(‘ ’)),
‘std_cell_lib’ = Set(‘ieee std_cell_lib’.split(‘ ’)),
‘synopsys’ = Set[String]()
]
F toposort2(&data)
L(k, v) data
v.discard(k)
Set[String] extra_items_in_deps
L(v) data.values()
extra_items_in_deps.update(v)
extra_items_in_deps = extra_items_in_deps - Set(data.keys())
L(item) extra_items_in_deps
data[item] = Set[String]()
[String] r
L
Set[String] ordered
L(item, dep) data
I dep.empty
ordered.add(item)
I ordered.empty
L.break
r.append(sorted(Array(ordered)).join(‘ ’))
[String = Set[String]] new_data
L(item, dep) data
I item !C ordered
new_data[item] = dep - ordered
data = move(new_data)
assert(data.empty, ‘A cyclic dependency exists’)
R r
print(toposort2(&data).join("\n"))</syntaxhighlight>
{{out}}
<pre>
ieee std synopsys
dware gtech ramlib std_cell_lib
dw01 dw02 dw05 dw06 dw07
des_system_lib dw03 dw04
</pre>
=={{header|Ada}}==
Line 55 ⟶ 120:
The specification:
<
package Digraphs is
Line 106 ⟶ 171:
type Graph_Type is new Conn_Vec.Vector with null record;
end Digraphs;</
The implementation:
<
function Node_Count(Graph: Graph_Type) return Node_Idx_With_Null is
Line 215 ⟶ 280:
end Top_Sort;
end Digraphs;</
'''Set_of_Names: Translating strings into numbers and vice versa'''
Line 221 ⟶ 286:
The specification:
<
generic
Line 262 ⟶ 327:
type Set is new Vecs.Vector with null record;
end Set_Of_Names;</
The implementation
<
use type Ada.Containers.Count_Type, Vecs.Cursor;
Line 333 ⟶ 398:
end Name;
end Set_Of_Names;</
'''Toposort: Putting things together for the main program'''
<
procedure Toposort is
Line 419 ⟶ 484:
TIO.Put_Line("There is no topological sorting -- the Graph is cyclic!");
end;
end Toposort;</
{{out}}
Line 429 ⟶ 494:
<pre>There is no topological sorting -- the Graph is cyclic!</pre>
=={{header|ATS}}==
For ATS2 (patsopt/patscc) and a garbage collector (Boehm GC). The algorithm used is depth-first search.
You can compile this program with something like
"patscc -o topo -DATS_MEMALLOC_GCBDW topo.dats -lgc"
(Or you can use the libc malloc and just let the memory leak: "patscc -o topo -DATS_MEMALLOC_LIBC topo.dats")
<syntaxhighlight lang="ATS">
(*------------------------------------------------------------------*)
(* The Rosetta Code topological sort task. *)
(*------------------------------------------------------------------*)
#include "share/atspre_staload.hats"
staload UN = "prelude/SATS/unsafe.sats"
(* Macros for list construction. *)
#define NIL list_nil ()
#define :: list_cons
(*------------------------------------------------------------------*)
(* A shorthand for list reversal. This could also have been written as
a macro. *)
fn {a : t@ype}
rev {n : int}
(lst : list (INV(a), n))
:<!wrt> list (a, n) =
(* The list_reverse template function returns a linear list. Convert
that result to a "regular" list. *)
list_vt2t (list_reverse<a> lst)
(*------------------------------------------------------------------*)
(* Some shorthands for string operations. These are written as
macros. *)
macdef substr (s, i, n) =
(* string_make_substring returns a linear strnptr, but we want a
"regular" string. *)
strnptr2string (string_make_substring (,(s), ,(i), ,(n)))
macdef copystr (s) =
(* string0 copy returns a linear strptr, but we want a "regular"
string. *)
strptr2string (string0_copy (,(s)))
(*------------------------------------------------------------------*)
local
(* A boolean type for setting marks, and a vector of those. *)
typedef _mark_t = [b : nat | b <= 1] uint8 b
typedef _marksvec_t (n : int) = arrayref (_mark_t, n)
(* Some type casts that seem not to be implemented in the
prelude. *)
implement g1int2uint<intknd, uint8knd> i = $UN.cast i
implement g1uint2int<uint8knd, intknd> i = $UN.cast i
in
abstype marks (n : int)
assume marks n = _marksvec_t n
fn marks_make_elt
{n : nat}
{b : int | b == 0 || b == 1}
(n : size_t n,
b : int b)
:<!wrt> _marksvec_t n =
arrayref_make_elt (n, g1i2u b)
fn
marks_set_at
{n : int}
{i : nat | i < n}
{b : int | b == 0 || b == 1}
(vec : _marksvec_t n,
i : size_t i,
b : int b)
:<!refwrt> void =
vec[i] := g1i2u b
fn
marks_get_at
{n : int}
{i : nat | i < n}
(vec : _marksvec_t n,
i : size_t i)
:<!ref> [b : int | b == 0 || b == 1]
int b =
g1u2i vec[i]
fn
marks_setall
{n : int}
{b : int | b == 0 || b == 1}
(vec : _marksvec_t n,
n : size_t n,
b : int b)
:<!refwrt> void =
let
prval () = lemma_arrayref_param vec
var i : [i : nat | i <= n] size_t i
in
for* {i : nat | i <= n}
.<n - i>.
(i : size_t i) =>
(i := i2sz 0; i <> n; i := succ i)
vec[i] := g1i2u b
end
overload [] with marks_set_at of 100
overload [] with marks_get_at of 100
overload setall with marks_setall of 100
end
(*------------------------------------------------------------------*)
(* Reading dependencies from a file. The format is kept very simple,
because this is not a task about parsing. (Though I have written
an S-expression parser in ATS, and there is JSON support in the
ATS contributions package.) *)
(* The format of a dependencies description. The second and later
entries of each sublist forms the list of dependencies of the first
entry. Thus this is a kind of association list. *)
typedef depdesc (n : int) = list (List1 String1, n)
typedef depdesc = [n : nat] depdesc n
typedef char_skipper =
{n : int}
{i : nat | i <= n}
(string n,
size_t n,
size_t i) -<cloref> (* A closure. *)
[j : int | i <= j; j <= n]
size_t j
fn
make_char_skipper
(match : char -<> bool)
:<> char_skipper =
let
fun
skipper {n : int}
{i : nat | i <= n}
.<n - i>.
(s : string n,
n : size_t n,
i : size_t i)
:<cloref> [j : int | i <= j; j <= n]
size_t j =
if i = n then
i
else if ~match s[i] then
i
else
skipper (s, n, succ i)
in
skipper (* Return a closure. *)
end
val skip_spaces = make_char_skipper (lam c => isspace c)
val skip_ident =
make_char_skipper (lam c => (~isspace c) * (c <> ';'))
fn is_end_of_list (c : char) :<> bool = (c = ';')
fn
read_row {n : int}
{i : nat | i <= n}
(text : string n,
n : size_t n,
i : size_t i)
:<!wrt> [j : int | i <= j; j <= n]
@(List0 String1, size_t j) =
let
fun
loop {i : nat | i <= n}
.<n - i>.
(row : List0 String1,
i : size_t i)
:<!wrt> [j : int | i <= j; j <= n]
@(List0 String1, size_t j) =
let
val i = skip_spaces (text, n, i)
in
if i = n then
@(rev row, i)
else if is_end_of_list text[i] then
@(rev row, succ i)
else
let
val j = skip_ident (text, n, i)
val () = $effmask_exn assertloc (i < j)
val nodename = substr (text, i, j - i)
in
loop (nodename :: row, j)
end
end
in
loop (NIL, i)
end
fn
read_desc {n : int}
{i : nat | i <= n}
(text : string n,
n : size_t n,
i : size_t i)
:<!wrt> [j : int | i <= j; j <= n]
@(depdesc, size_t j) =
let
fun
loop {i : nat | i <= n}
.<n - i>.
(desc : depdesc,
i : size_t i)
:<!wrt> [j : int | i <= j; j <= n]
@(depdesc, size_t j) =
let
val i = skip_spaces (text, n, i)
in
if i = n then
@(rev desc, i)
else if is_end_of_list text[i] then
@(rev desc, succ i)
else
let
val @(row, j) = read_row (text, n, i)
val () = $effmask_exn assertloc (i < j)
in
if length row = 0 then
loop (desc, j)
else
loop (row :: desc, j)
end
end
in
loop (NIL, i)
end
fn
read_to_string ()
: String =
(* This simple implementation reads input only up to a certain
size. *)
let
#define BUFSIZE 8296
var buf = @[char][BUFSIZE] ('\0')
var c : int = $extfcall (int, "getchar")
var i : Size_t = i2sz 0
in
while ((0 <= c) * (i < pred (i2sz BUFSIZE)))
begin
buf[i] := int2char0 c;
i := succ i;
c := $extfcall (int, "getchar")
end;
copystr ($UN.cast{string} (addr@ buf))
end
fn
read_depdesc ()
: depdesc =
let
val text = read_to_string ()
prval () = lemma_string_param text
val n = strlen text
val @(desc, _) = read_desc (text, n, i2sz 0)
in
desc
end
(*------------------------------------------------------------------*)
(* Conversion of a dependencies description to the internal
representation for a topological sort. *)
(* An ordered list of the node names. *)
typedef nodenames (n : int) = list (String1, n)
(* A more efficient representation for nodes: integers in 0..n-1. *)
typedef nodenum (n : int) = [num : nat | num <= n - 1] size_t num
(* A collection of directed edges. Edges go from the nodenum that is
represented by the array index, to each of the nodenums listed in
the corresponding array entry. *)
typedef edges (n : int) = arrayref (List0 (nodenum n), n)
(* An internal representation of data for a topological sort. *)
typedef topodata (n : int) =
'{
n = size_t n, (* The number of nodes. *)
edges = edges n, (* Directed edges. *)
tempmarks = marks n, (* Temporary marks. *)
permmarks = marks n (* Permanent marks. *)
}
fn
collect_nodenames
(desc : depdesc)
:<!wrt> [n : nat]
@(nodenames n,
size_t n) =
let
fun
collect_row
{m : nat}
{n0 : nat}
.<m>.
(row : list (String1, m),
names : &nodenames n0 >> nodenames n1,
n : &size_t n0 >> size_t n1)
:<!wrt> #[n1 : int | n0 <= n1]
void =
case+ row of
| NIL => ()
| head :: tail =>
let
implement list_find$pred<String1> s = (s = head)
in
case+ list_find_opt<String1> names of
| ~ None_vt () =>
begin
names := head :: names;
n := succ n;
collect_row (tail, names, n)
end
| ~ Some_vt _ => collect_row (tail, names, n)
end
fun
collect {m : nat}
{n0 : nat}
.<m>.
(desc : list (List1 String1, m),
names : &nodenames n0 >> nodenames n1,
n : &size_t n0 >> size_t n1)
:<!wrt> #[n1 : int | n0 <= n1]
void =
case+ desc of
| NIL => ()
| head :: tail =>
begin
collect_row (head, names, n);
collect (tail, names, n)
end
var names : List0 String1 = NIL
var n : Size_t = i2sz 0
in
collect (desc, names, n);
@(rev names, n)
end
fn
nodename_number
{n : int}
(nodenames : nodenames n,
name : String1)
:<> Option (nodenum n) =
let
fun
loop {i : nat | i <= n}
.<n - i>.
(names : nodenames (n - i),
i : size_t i)
:<> Option (nodenum n) =
case+ names of
| NIL => None ()
| head :: tail =>
if head = name then
Some i
else
loop (tail, succ i)
prval () = lemma_list_param nodenames
in
loop (nodenames, i2sz 0)
end
fn
add_edge {n : int}
(edges : edges n,
from : nodenum n,
to : nodenum n)
:<!refwrt> void =
(* This implementation does not store duplicate edges. *)
let
val old_edges = edges[from]
implement list_find$pred<nodenum n> s = (s = to)
in
case+ list_find_opt<nodenum n> old_edges of
| ~ None_vt () => edges[from] := to :: old_edges
| ~ Some_vt _ => ()
end
fn
fill_edges
{n : int}
{m : int}
(edges : edges n,
n : size_t n,
desc : depdesc m,
nodenames : nodenames n)
:<!refwrt> void =
let
prval () = lemma_list_param desc
prval () = lemma_list_param nodenames
fn
clear_edges ()
:<!refwrt> void =
let
var i : [i : nat | i <= n] size_t i
in
for* {i : nat | i <= n}
.<n - i>.
(i : size_t i) =>
(i := i2sz 0; i <> n; i := succ i)
edges[i] := NIL
end
fun
fill_from_desc_entry
{m1 : nat}
.<m1>.
(headnum : nodenum n,
lst : list (String1, m1))
:<!refwrt> void =
case+ lst of
| NIL => ()
| name :: tail =>
let
val- Some num = nodename_number (nodenames, name)
in
if num <> headnum then
add_edge {n} (edges, num, headnum);
fill_from_desc_entry (headnum, tail)
end
fun
fill_from_desc
{m2 : nat}
.<m2>.
(lst : list (List1 String1, m2))
:<!refwrt> void =
case+ lst of
| NIL => ()
| list_entry :: tail =>
let
val+ headname :: desc_entry = list_entry
val- Some headnum = nodename_number (nodenames, headname)
in
fill_from_desc_entry (headnum, desc_entry);
fill_from_desc tail
end
in
clear_edges ();
fill_from_desc desc
end
fn
topodata_make
(desc : depdesc)
:<!refwrt> [n : nat]
@(topodata n,
nodenames n) =
let
val @(nodenames, n) = collect_nodenames desc
prval () = lemma_g1uint_param n
prval [n : int] EQINT () = eqint_make_guint n
val edges = arrayref_make_elt<List0 (nodenum n)> (n, NIL)
val () = fill_edges {n} (edges, n, desc, nodenames)
val tempmarks = marks_make_elt (n, 0)
and permmarks = marks_make_elt (n, 0)
val topo =
'{
n = n,
edges = edges,
tempmarks = tempmarks,
permmarks = permmarks
}
in
@(topo, nodenames)
end
(*------------------------------------------------------------------*)
(*
Topological sort by depth-first search. See
https://en.wikipedia.org/w/index.php?title=Topological_sorting&oldid=1092588874#Depth-first_search
*)
(* What return values are made from. *)
datatype toporesult (a : t@ype, n : int) =
| {0 <= n}
Topo_SUCCESS (a, n) of list (a, n)
| Topo_CYCLE (a, n) of List1 a
typedef toporesult (a : t@ype) = [n : int] toporesult (a, n)
fn
find_unmarked_node
{n : int}
(topo : topodata n)
:<!ref> Option (nodenum n) =
let
val n = topo.n
and permmarks = topo.permmarks
prval () = lemma_g1uint_param n
fun
loop {i : nat | i <= n}
.<n - i>.
(i : size_t i)
:<!ref> Option (nodenum n) =
if i = n then
None ()
else if permmarks[i] = 0 then
Some i
else
loop (succ i)
in
loop (i2sz 0)
end
fun
visit {n : int}
(topo : topodata n,
nodenum : nodenum n,
accum : List0 (nodenum n),
path : List0 (nodenum n))
: toporesult (nodenum n) =
(* Probably it is cumbersome to include a proof this routine
terminates. Thus I will not try to write one. *)
let
val n = topo.n
and edges = topo.edges
and tempmarks = topo.tempmarks
and permmarks = topo.permmarks
in
if permmarks[nodenum] = 1 then
Topo_SUCCESS accum
else if tempmarks[nodenum] = 1 then
let
val () = assertloc (isneqz path)
in
Topo_CYCLE path
end
else
let
fun
recursive_visits
{k : nat}
.<k>.
(topo : topodata n,
to_visit : list (nodenum n, k),
accum : List0 (nodenum n),
path : List0 (nodenum n))
: toporesult (nodenum n) =
case+ to_visit of
| NIL => Topo_SUCCESS accum
| node_to_visit :: tail =>
begin
case+ visit (topo, node_to_visit, accum, path) of
| Topo_SUCCESS accum1 =>
recursive_visits (topo, tail, accum1, path)
| other => other
end
in
tempmarks[nodenum] := 1;
case+ recursive_visits (topo, edges[nodenum], accum,
nodenum :: path) of
| Topo_SUCCESS accum1 =>
begin
tempmarks[nodenum] := 0;
permmarks[nodenum] := 1;
Topo_SUCCESS (nodenum :: accum1)
end
| other => other
end
end
fn
topological_sort
{n : int}
(topo : topodata n)
: toporesult (nodenum n, n) =
let
prval () = lemma_arrayref_param (topo.edges)
fun
sort (accum : List0 (nodenum n))
: toporesult (nodenum n, n) =
case+ find_unmarked_node topo of
| None () =>
let
prval () = lemma_list_param accum
val () = assertloc (i2sz (length accum) = topo.n)
in
Topo_SUCCESS accum
end
| Some nodenum =>
begin
case+ visit (topo, nodenum, accum, NIL) of
| Topo_SUCCESS accum1 => sort accum1
| Topo_CYCLE cycle => Topo_CYCLE cycle
end
val () = setall (topo.tempmarks, topo.n, 0)
and () = setall (topo.permmarks, topo.n, 0)
val accum = sort NIL
val () = setall (topo.tempmarks, topo.n, 0)
and () = setall (topo.permmarks, topo.n, 0)
in
accum
end
(*------------------------------------------------------------------*)
(* The function asked for in the task. *)
fn
find_a_valid_order
(desc : depdesc)
: toporesult String1 =
let
val @(topo, nodenames) = topodata_make desc
prval [n : int] EQINT () = eqint_make_guint (topo.n)
val nodenames_array =
arrayref_make_list<String1> (sz2i (topo.n), nodenames)
implement
list_map$fopr<nodenum n><String1> i =
nodenames_array[i]
(* A shorthand for mapping from nodenum to string. *)
macdef map (lst) =
list_vt2t (list_map<nodenum n><String1> ,(lst))
in
case+ topological_sort topo of
| Topo_SUCCESS valid_order => Topo_SUCCESS (map valid_order)
| Topo_CYCLE cycle => Topo_CYCLE (map cycle)
end
(*------------------------------------------------------------------*)
implement
main0 (argc, argv) =
let
val desc = read_depdesc ()
in
case+ find_a_valid_order desc of
| Topo_SUCCESS valid_order =>
println! (valid_order : List0 string)
| Topo_CYCLE cycle =>
let
val last = list_last cycle
val cycl = rev (last :: cycle)
in
println! ("COMPILATION CYCLE: ", cycl : List0 string)
end
end
(*------------------------------------------------------------------*)
</syntaxhighlight>
{{out}}
Data fed to standard input:
<pre>
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;
</pre>
Data from standard output:
<pre>
ieee, dware, dw05, dw06, dw07, gtech, dw01, dw04, dw02, std_cell_lib, synopsys, std, dw03, ramlib, des_system_lib
</pre>
AND ...
Data fed to standard input:
<pre>
a b; b d; d a e; e a;
</pre>
Data from standard output:
<pre>
COMPILATION CYCLE: a, e, d, b, a
</pre>
=={{header|Bracmat}}==
<
(dw01.ieee dw01 dware gtech)
(dw02.ieee dw02 dware)
Line 479 ⟶ 1,257:
& out$("
compile order:" !indeps !res "\ncycles:" !cycles)
);</
{{out}}
<pre>compile order:
Line 506 ⟶ 1,284:
=={{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.
<
#include <stdlib.h>
#include <string.h>
Line 627 ⟶ 1,405:
return 0;
}</
{{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 634 ⟶ 1,412:
2: std_cell_lib ramlib dware gtech
3: dw02 dw01 dw05 dw06 dw07
4: des_system_lib dw03 dw04</
=={{header|C sharp}}==
<
namespace Algorithms
{
Line 778 ⟶ 1,556:
}
</syntaxhighlight>
{{out}}<syntaxhighlight lang="text">B - depends on none
D - depends on none
G - depends on none
Line 789 ⟶ 1,567:
C - depends on D and E
A - depends on B and C
exiting...</
{{out}}(with cycled dependency)<syntaxhighlight lang="text">Cycled dependencies detected: A C D
exiting...</
=={{header|C++}}==
===C++11===
<syntaxhighlight lang="cpp">#include <map>
#include <set>
template
class topological_sorter {
protected:
std::size_t dependencies;
std::set<Goal> dependents;
};
public:
void add_goal(Goal const &goal) {
map[goal];
}
void add_dependency(Goal const &goal, Goal const &dependency) {
if (dependency == goal)
return;
auto &dependents = map[dependency].dependents;
if (dependents.find(goal) == dependents.end()) {
dependents.insert(goal);
++map[goal].dependencies;
}
}
template<typename Container>
void add_dependencies(Goal const &goal, Container const &dependencies) {
for (auto const &dependency : dependencies)
add_dependency(goal, dependency);
}
template<typename ResultContainer, typename CyclicContainer>
void destructive_sort(ResultContainer &sorted, CyclicContainer &unsortable) {
sorted.clear();
unsortable.clear();
for (auto const &lookup : map) {
auto const &goal = lookup.first;
auto const &relations = lookup.second;
if (relations.dependencies == 0)
sorted.push_back(goal);
}
for (std::size_t index = 0; index < sorted.size(); ++index)
for (auto const &goal : map[sorted[index]].dependents)
if (--map[goal].dependencies == 0)
sorted.push_back(goal);
for (auto const &lookup : map) {
auto const &goal = lookup.first;
auto const &relations = lookup.second;
if (relations.dependencies != 0)
unsortable.push_back(goal);
}
}
template<typename ResultContainer, typename CyclicContainer>
void sort(ResultContainer &sorted, CyclicContainer &unsortable) {
topological_sorter<Goal> temporary = *this;
temporary.destructive_sort(sorted, unsortable);
}
void clear() {
map.clear();
}
};
/*
Example usage with text strings
*/
#include <fstream>
#include <sstream>
Line 890 ⟶ 1,642:
#include <string>
#include <vector>
using namespace std;
void display_heading(string const &message) {
cout << endl << "~ " << message << " ~" << endl;
}
void display_results(string const &input) {
topological_sorter<string> sorter;
vector<string> sorted, unsortable;
stringstream lines(input);
string line;
while (getline(lines, line)) {
stringstream buffer(line);
string goal, dependency;
buffer >> goal;
sorter.add_goal(goal);
while (buffer >> dependency)
sorter.add_dependency(goal, dependency);
}
sorter.destructive_sort(sorted, unsortable);
if (sorted.size() == 0)
display_heading("Error: no independent variables found!");
else {
display_heading("Result");
for (auto const &goal : sorted)
cout << goal << endl;
}
if (unsortable.size() != 0) {
display_heading("Error: cyclic dependencies detected!");
for (auto const &goal : unsortable)
cout << goal << endl;
}
}
int main(int argc, char **argv) {
string example = "des_system_lib std synopsys std_cell_lib des_system_lib dw02 dw01 ramlib ieee\n"
"dw01 ieee dw01 dware gtech\n"
"dw02 ieee dw02 dware\n"
"dw03 std synopsys dware dw03 dw02 dw01 ieee gtech\n"
"dw04 dw04 ieee dw01 dware gtech\n"
"dw05 dw05 ieee dware\n"
"cycle_22 cycle_21 dw01 dw04";
display_heading("Example: each line starts with a goal followed by it's dependencies");
cout << example << endl;
display_results(example);
display_heading("Enter lines of data (press enter when finished)");
string line, data;
while (getline(cin, line) && !line.empty())
data += line + '\n';
if (!data.empty())
display_results(data);
} else
while (*(++argv)) {
ifstream file(*argv);
typedef istreambuf_iterator<char> iterator;
display_results(string(iterator(file), iterator()));
}
}</syntaxhighlight>
==
<syntaxhighlight lang="cpp">#include <unordered_map>
#include <unordered_set>
#include <vector>
Line 1,132 ⟶ 1,855:
}
//tasks.clear(); // uncomment this line to
std::cout << "exiting..." << std::endl;
return 0;
}</syntaxhighlight>
{{out}}<syntaxhighlight lang="text">I - depends on none
H - depends on none
G - depends on none
Line 1,159 ⟶ 1,880:
G - destroyed
H - destroyed
I - destroyed</
{{out}}(with cycled dependency)<syntaxhighlight lang="text">Cycled dependencies detected: A D C
exiting...
A - destroyed
Line 1,170 ⟶ 1,891:
G - destroyed
H - destroyed
I - destroyed</
=={{header|Clojure}}==
Line 1,184 ⟶ 1,905:
=====Implementation=====
<
(use 'clojure.contrib.seq-utils)
Line 1,256 ⟶ 1,977:
[items]
(topo-sort-deps (deps items)))
</syntaxhighlight>
Examples of sortable and non-sortable data:
<
'(:des_system_lib (:std :synopsys :std_cell_lib :des_system_lib :dw02 :dw01 :ramlib :ieee)
:dw01 (:ieee :dw01 :dware :gtech)
Line 1,279 ⟶ 2,000:
(def bad-sample
(concat cyclic-dependence good-sample))</
====={{out}}=====
<
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)"</
=={{header|CoffeeScript}}==
<
toposort = (targets) ->
# targets is hash of sets, where keys are parent nodes and
Line 1,387 ⟶ 2,108:
console.log toposort targets
</syntaxhighlight>
=={{header|Common Lisp}}==
<
"Graph is an association list whose keys are objects and whose
values are lists of objects on which the corresponding key depends.
Line 1,437 ⟶ 2,158:
all-sorted-p
(unless all-sorted-p
entries)))))))</
Provided example in which all items can be sorted:
<
'((des-system-lib std synopsys std-cell-lib des-system-lib dw02 dw01 ramlib ieee)
(dw01 ieee dw01 dware gtech)
Line 1,460 ⟶ 2,181:
(IEEE DWARE DW02 DW05 DW06 DW07 GTECH DW01 DW04 STD-CELL-LIB SYNOPSYS STD DW03 RAMLIB DES-SYSTEM-LIB)
T
NIL</
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.)
<
'((des-system-lib std synopsys std-cell-lib des-system-lib dw02 dw01 ramlib ieee)
(dw01 ieee dw01 dw04 dware gtech)
Line 1,491 ⟶ 2,212:
DW04 (1 DW01)
DW03 (1)
DES-SYSTEM-LIB (1)</
=={{header|Crystal}}==
<syntaxhighlight lang="crystal">def dfs_topo_visit(n, g, tmp, permanent, l)
if permanent.includes?(n)
return
elsif tmp.includes?(n)
raise "unorderable: circular dependency detected involving '#{n}'"
end
tmp.add(n)
g[n].each { |m|
dfs_topo_visit(m, g, tmp, permanent, l)
}
tmp.delete(n)
permanent.add(n)
l.insert(0, n)
end
def dfs_topo_sort(g)
tmp = Set(String).new
permanent = Set(String).new
l = Array(String).new
while true
keys = g.keys.to_set - permanent
if keys.empty?
break
end
n = keys.first
dfs_topo_visit(n, g, tmp, permanent, l)
end
return l
end
def build_graph(deps)
g = {} of String => Set(String)
deps.split("\n").each { |line|
line_split = line.strip.split
line_split.each { |dep|
unless g.has_key?(dep)
g[dep] = Set(String).new
end
unless line_split[0] == dep
g[dep].add(line_split[0])
end
}
}
return g
end
data = "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"
circular_deps = "\ncyc01 cyc02
cyc02 cyc01"
puts dfs_topo_sort(build_graph(data)).join(" -> ")
puts ""
puts dfs_topo_sort(build_graph(data + circular_deps)).join(" -> ")
</syntaxhighlight>
{{out}}
<pre>
ieee -> gtech -> dware -> dw07 -> dw06 -> dw05 -> dw01 -> dw04 -> dw02 -> std_cell_lib -> synopsys -> std -> ramlib -> dw03 -> des_system_lib
Unhandled exception: unorderable: circular dependency detected involving 'cyc01' (Exception)
</pre>
=={{header|D}}==
{{trans|Python}}
<
final class ArgumentException : Exception {
Line 1,568 ⟶ 2,373:
foreach (const subOrder; depw.topoSort) // Should throw.
subOrder.writeln;
}</
{{out}}
<pre>#1 : ["ieee", "std", "synopsys"]
Line 1,582 ⟶ 2,387:
=={{header|E}}==
<
def topoSort(data :Map[any, Set[any]]) {
Line 1,630 ⟶ 2,435:
return result
}</
<
def dataText := "\
Line 1,652 ⟶ 2,457:
def data := accum [].asMap() for rx`(@item.{17})(@deps.*)` in dataText.split("\n") { _.with(item.trim(), deps.split(" ").asSet()) }
println(topoSort(data))</
{{out}}
Line 1,662 ⟶ 2,467:
''' Data
<
(define dependencies
'((des_system_lib std synopsys std_cell_lib des_system_lib dw02 dw01 ramlib ieee)
Line 1,689 ⟶ 2,494:
(define (add-dependencies g dep-list)
(for* ((dep dep-list) (b (rest dep))) (a->b g b (first dep))))
</syntaxhighlight>
'''Implementation
Remove all vertices with in-degree = 0, until to one left. (in-degree = number of arrows to a vertex)
<
;; topological sort
;;
Line 1,726 ⟶ 2,531:
(error " ♻️ t-sort:cyclic" (map vertex-label (graph-cycle g))))))
</syntaxhighlight>
{{Out}}
<
(define g (make-graph "VHDL"))
(add-dependencies g dependencies)
Line 1,742 ⟶ 2,547:
t-sort (std synopsys ieee dware dw02 dw05 dw06 dw07 gtech ramlib std_cell_lib)
⛔️ error: ♻️ t-sort:cyclic (dw04 dw01)
</syntaxhighlight>
=={{header|Elixir}}==
{{trans|Erlang}}
<
def sort(library) do
g = :digraph.new
Line 1,791 ⟶ 2,596:
IO.puts ""
bad_libraries = Keyword.update!(libraries, :dw01, &[:dw04 | &1])
Topological.sort(bad_libraries)</
{{out}}
Line 1,803 ⟶ 2,608:
=={{header|Erlang}}==
<
-module(topological_sort).
-compile(export_all).
Line 1,875 ⟶ 2,680:
digraph:add_vertex(G,D), % noop if dependency already added
digraph:add_edge(G,D,L). % Dependencies represented as an edge D -> L
</syntaxhighlight>
{{out}}
<
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,884 ⟶ 2,689:
dw04 -> dw01 -> dw04
dw01 -> dw04 -> dw01
ok</
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 1,926 ⟶ 2,731:
{{works with|Gforth}}
<
: node. ( body -- )
Line 1,996 ⟶ 2,801:
deps dw01 ieee dw01 dware gtech dw04
all-nodes</
{{out}}
Line 2,011 ⟶ 2,816:
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).
<
IMPLICIT NONE
INTEGER NL,ND,NO,IDEP(ND,2),IORD(NL),IPOS(NL),I,J,K,IL,IR,IPL,IPR
Line 2,034 ⟶ 2,839:
IF(K.GT.J) GO TO 20
NO=J-1
END</
An example. Dependencies are encoded to make program shorter (in array ICODE).
<
IMPLICIT NONE
INTEGER NL,ND,NC,NO,IDEP,IORD,IPOS,ICODE,I,J,IL,IR
Line 2,075 ⟶ 2,880:
DO 50 I=NO+1,NL
50 PRINT*,LABEL(IORD(I))
END</
{{out}}
Line 2,120 ⟶ 2,925:
===Modern Fortran===
A modern Fortran (95-2008) version of the TSORT subroutine is shown here (note that the IPOS array is not an input).
<
implicit none
Line 2,157 ⟶ 2,962:
end subroutine tsort
</syntaxhighlight>
=={{header|FunL}}==
<
val L = seq()
val S = seq()
Line 2,220 ⟶ 3,025:
case topsort( graph ) of
None -> println( 'un-orderable' )
Some( ordering ) -> println( ordering )</
{{out}}
Line 2,230 ⟶ 3,035:
=={{header|Go}}==
===Kahn===
<
import (
Line 2,369 ⟶ 3,174:
}
return L, nil
}</
{{out}}
<pre>
Line 2,381 ⟶ 3,186:
Topological sort only, this function can replace topSortKahn in above program. The
in-degree list is not needed.
<
// library dependencies. Also adapted from Wikipedia pseudo code.
func topSortDFS(g graph) (order, cyclic []string) {
Line 2,428 ⟶ 3,233:
}
return L, nil
}</
{{out}}
(when used in program of Kahn example.)
Line 2,440 ⟶ 3,245:
=={{header|Haskell}}==
<
import
combs 0 _ = [[]]
Line 2,471 ⟶ 3,276:
| otherwise = foldl makePrecede [] dB
where
dB =
makePrecede ts ([x], xs) =
nub $
Line 2,483 ⟶ 3,288:
main :: IO ()
main = print $ toposort depLibs</
{{out}}
<
["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"]]</
=={{header|Huginn}}==
<
import Text as text;
Line 2,564 ⟶ 3,369:
dfs = DepthFirstSearch();
print( "{}\n".format( dfs.topological_sort( dg ) ) );
}</
==Icon and Unicon==
Line 2,577 ⟶ 3,382:
elements have been built.
<
global ex_name, in_name
Line 2,691 ⟶ 3,496:
g.arcs ? while arc := move(2) do if arc[1] == f then t ++:= arc[2]
return t
end</
{{out}}
Line 2,718 ⟶ 3,523:
in parallel once the elements in the preceding lines have been built.
<
procedure main()
Line 2,804 ⟶ 3,609:
while (af := @cp, at := @cp) do if af == f then insert(t, at)
return t
end</
=={{header|J}}==
(see [[Talk:Topological_sort#J_implementation|talk page]] for some details about what happens here.)
<syntaxhighlight lang="j">dependencySort=: monad define
parsed=. <@;:;._2 y
names=. {.&>parsed
Line 2,815 ⟶ 3,622:
assert.-.1 e. (<0 1)|:depends
(-.&names ~.;parsed),names /: +/"1 depends
)</
With the sample data set:
Line 2,837 ⟶ 3,644:
We would get:
<
std
ieee
Line 2,852 ⟶ 3,659:
dw04
dw03
des_system_lib</
If we tried to also make dw01 depend on dw04, the sort would fail because of the circular dependency:
<
|assertion failure: dependencySort
| -.1 e.(<0 1)|:depends</
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):
<
parsed=. <@;:;._2 y
names=. {.&>parsed
Line 2,869 ⟶ 3,676:
assert.-.1 e. (i.@# e.S:0"0 ])depends
(-.&names ~.;parsed),names /: #@> depends
)</
It's results are identical to the first implementation, but this might be more efficient in typical cases.
Line 2,875 ⟶ 3,682:
=={{header|Java}}==
{{works with|Java|7}}
<
public class TopologicalSort {
Line 2,951 ⟶ 3,758:
return false;
}
}</
<pre>[std, ieee, dware, dw02, dw05, dw06, dw07, gtech, dw01, dw04, ramlib, std_cell_lib, synopsys, des_system_lib, dw03]</pre>
Line 2,959 ⟶ 3,766:
====ES6====
<
`des_system_lib std synopsys std_cell_lib des_system_lib dw02 dw01 ramlib ieee
dw01 ieee dw01 dware gtech
Line 3,016 ⟶ 3,823:
console.log('Solution:', S);
</
Output:
<syntaxhighlight lang="javascript">
Solution: [
'ieee',
Line 3,036 ⟶ 3,843:
'dw03',
'des_system_lib' ]
</syntaxhighlight>
=={{header|jq}}==
Line 3,057 ⟶ 3,864:
To solve and print the solution to the given problem on a 1GHz machine takes about 5ms.
<
# Input: an object representing a normalized dependency graph
def independent:
Line 3,107 ⟶ 3,914:
normalize | [[], .] | _tsort ;
tsort</
Data:
<
"dw01": [ "ieee", "dw01", "dware", "gtech"],
"dw02": [ "ieee", "dw02", "dware"],
Line 3,123 ⟶ 3,930:
"synopsys": []
}
</syntaxhighlight>
{{Out}}
<syntaxhighlight 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>
=={{header|Julia}}==
Line 3,134 ⟶ 3,941:
{{trans|Python}}
<
data = copy(data)
for (k, v) in data
Line 3,170 ⟶ 3,977:
)
println("# Topologically sorted:\n - ", join(toposort(data), "\n - "))</
{{out}}
Line 3,192 ⟶ 3,999:
=={{header|Kotlin}}==
{{trans|Java}}
<
val s = "std, ieee, des_system_lib, dw01, dw02, dw03, dw04, dw05, " +
Line 3,223 ⟶ 4,030:
fun hasDependency(r: Int, todo: List<Int>): Boolean {
}
Line 3,260 ⟶ 4,066:
println("Following the addition of dw04 to the dependencies of dw01:")
println(g2.topoSort())
}</
{{out}}
Line 3,276 ⟶ 4,082:
This version follows python implementation and returns List of Lists which is useful for parallel execution for example
</pre>
<
val graph = mapOf(
"des_system_lib" to "std synopsys std_cell_lib des_system_lib dw02 dw01 ramlib ieee".split(" ").toSet(),
Line 3,329 ⟶ 4,135:
}
</syntaxhighlight>
{{out}}
<pre>
Line 3,340 ⟶ 4,146:
</pre>
=={{header|
<syntaxhighlight lang="m2000 interpreter">Module testthis {
\\ empty stack
Flush
inventory LL
append LL, "des_system_lib":=(List:="std", "synopsys", "std_cell_lib", "des_system_lib", "dw02", "dw01", "ramlib", "ieee")
REM append LL, "dw01":=(List:="dw04","ieee", "dw01", "dware", "gtech")
append LL, "dw01":=(List:="ieee", "dw01", "dware", "gtech")
append LL, "dw02":=(List:="ieee", "dw02", "dware")
append LL, "dw03":=(List:="std", "synopsys", "dware", "dw03", "dw02", "dw01", "ieee", "gtech")
append LL, "dw04":=(List:= "ieee", "dw01", "dware", "gtech")
append LL, "dw05":=(List:="dw05", "ieee", "dware")
append LL, "dw06":=(List:="dw06", "ieee", "dware")
append LL, "dw07":=(List:="ieee", "dware")
append LL, "dware":=(List:="ieee", "dware")
append LL, "gtech":=(List:="ieee", "gtech")
append LL, "ramlib":=(List:="std", "ieee")
append LL, "std_cell_lib":=(List:="ieee", "std_cell_lib")
append LL, "synopsys":=List
\\ inventory itmes may have keys/items or keys.
\\ here we have keys so keys return as item also
\\ when we place an item in a key (an empty string) ...
\\ we mark the item to not return the key but an empty string
inventory final
mm=each(LL)
while mm
k$=eval$(mm!)
m=eval(mm)
mmm=each(m)
While mmm
k1$=eval$(mmm!)
if not exist(LL, k1$) then
if not exist(final, k1$) then append final, k1$
return m, k1$:="" \\ mark that item
else
mmmm=Eval(LL)
if len(mmmm)=0 then
if not exist(final, k1$) then append final, k1$
return m, k1$:="" \\ mark that item
end if
end if
end while
end while
mm=each(LL)
while mm
\\ using eval$(mm!) we read the key as string
k$=eval$(mm!)
if exist(final, k$) then continue
m=eval(mm)
mmm=each(m)
While mmm
\\ we read the item, if no item exist we get the key
k1$=eval$(mmm)
if k1$="" then continue
if exist(final, k1$) then continue
data k1$ \\ push to end to stack
end while
while not empty
read k1$
if exist(final, k1$) then continue
m=LL(k1$)
mmm=each(m)
delthis=0
While mmm
k2$=eval$(mmm)
if k2$="" then continue
if k1$=k2$ then continue
if exist(final, k2$) then continue
push k2$ \\ push to top of stack
return m, k2$:=""
delthis++
end while
if delthis=0 then
if not exist(final, k1$) then
mmm=each(m)
While mmm
k2$=eval$(mmm!)
if k2$=k1$ then continue
if exist(final, k2$) Else
Print "unsorted:";k1$, k2$
end if
end while
append final, k1$ : Return LL, k1$:=List
end if
end if
end while
if not exist(final, k$) then append final, k$
end while
document doc$
ret=each(final,1, -2)
while ret
doc$=eval$(ret)+" -> "
end while
doc$=final$(len(final)-1!)
Report doc$
clipboard doc$
}
testthis
</syntaxhighlight>
{{out}}
<pre>
std -> synopsys -> ieee -> std_cell_lib -> ramlib -> gtech -> dware -> dw02 -> dw01 -> des_system_lib -> dw03 -> dw04 -> dw05 -> dw06 -> dw07
if we place REM at next line we get
unsorted:dw01 dw04
std -> synopsys -> ieee -> std_cell_lib -> ramlib -> gtech -> dware -> dw01 -> dw02 -> des_system_lib -> dw03 -> dw04 -> dw05 -> dw06 -> dw07
</pre>
=={{header|Mathematica}}/{{header|Wolfram Language}}==
Work in Mathematica 8 or higher versions.
<
Graph[Flatten[# /. {l_, ld_} :>
Map[# -> l &,
Line 3,360 ⟶ 4,274:
{"ramlib", {"std", "ieee"}},
{"std_cell_lib", {"ieee", "std_cell_lib"}},
{"synopsys", {}}}</
{{Out}}
<pre>{"ieee", "std_cell_lib", "gtech", "dware", "dw07", "dw06", "dw05", \
Line 3,368 ⟶ 4,282:
=={{header|Mercury}}==
<syntaxhighlight lang="mercury">
:- module topological_sort.
Line 3,446 ⟶ 4,360:
print(CompileOrder,!IO).
</syntaxhighlight>
=={{header|Nim}}==
<syntaxhighlight lang="nim">import sequtils, strutils, sets, tables, sugar
type StringSet = HashSet[string]
proc topSort(data: var OrderedTable[string, StringSet]) =
## Topologically sort the data in place.
var ranks: Table[string, Natural] # Maps the keys to a rank.
# Remove self dependencies.
for key, values in data.mpairs:
values.excl key
# Add extra items (i.e items present in values but not in keys).
for values in toSeq(data.values):
for value in values:
if value notin data:
data[value] = initHashSet[string]()
# Find ranks.
var deps = data # Working copy of the table.
var rank = 0
while deps.len > 0:
# Find a key with an empty dependency set.
var keyToRemove: string
for key, values in deps.pairs:
if values.card == 0:
keyToRemove = key
break
if keyToRemove.len == 0:
# Not found: there is a cycle.
raise newException(ValueError, "Unorderable items found: " & toSeq(deps.keys).join(", "))
# Assign a rank to the key and remove it from keys and values.
ranks[keyToRemove] = rank
inc rank
deps.del keyToRemove
for k, v in deps.mpairs:
v.excl keyToRemove
# Sort the original data according to the ranks.
data.sort((x, y) => cmp(ranks[x[0]], ranks[y[0]]))
when isMainModule:
const Data = {"des_system_lib": ["std", "synopsys", "std_cell_lib",
"des_system_lib", "dw02", "dw01",
"ramlib", "ieee"].toHashSet,
"dw01": ["ieee", "dw01", "dware", "gtech"].toHashSet,
"dw02": ["ieee", "dw02", "dware"].toHashSet,
"dw03": ["std", "synopsys", "dware", "dw03",
"dw02", "dw01", "ieee", "gtech"].toHashSet,
"dw04": ["dw04", "ieee", "dw01", "dware", "gtech"].toHashSet,
"dw05": ["dw05", "ieee", "dware"].toHashSet,
"dw06": ["dw06", "ieee", "dware"].toHashSet,
"dw07": ["ieee", "dware"].toHashSet,
"dware": ["ieee", "dware"].toHashSet,
"gtech": ["ieee", "gtech"].toHashSet,
"ramlib": ["std", "ieee"].toHashSet,
"std_cell_lib": ["ieee", "std_cell_lib"].toHashSet,
"synopsys": initHashSet[string]()}.toOrderedTable
# Process the original data (without cycle).
echo "Data without cycle. Order after sorting:"
var data = Data
try:
data.topSort()
for key in data.keys: echo key
except ValueError:
echo getCurrentExceptionMsg()
# Process the modified data (with a cycle).
echo "\nData with a cycle:"
data = Data
data["dw01"].incl "dw04"
try:
data.topSort()
for key in data.keys: echo key
except ValueError:
echo getCurrentExceptionMsg()</syntaxhighlight>
=={{header|Object Pascal}}==
Written for Free Pascal, but will probably work in Delphi if you change the required units.
<syntaxhighlight lang="pascal">
program topologicalsortrosetta;
Line 3,863 ⟶ 4,863:
InputList.Free;
end.
</syntaxhighlight>
=={{header|OCaml}}==
<
("des_system_lib", ["std"; "synopsys"; "std_cell_lib"; "des_system_lib"; "dw02"; "dw01"; "ramlib"; "ieee"]);
("dw01", (*"dw04"::*)["ieee"; "dw01"; "dware"; "gtech"]);
Line 3,920 ⟶ 4,920:
print_string "result: \n ";
print_endline (String.concat ", " res);
;;</
If dw04 is added to the set of dependencies of dw01 to make the data un-orderable (uncomment it), an exception is raised:
Exception: Invalid_argument "un-orderable data".
=={{header|OxygenBasic}}==
<syntaxhighlight lang="text">
'TOPOLOGICAL SORT
uses parseutil 'getword() lenw
uses console
string dat="
LIBRARY LIBRARY DEPENDENCIES
======= ====================
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
"
gosub Dims
gosub CaptureData
gosub GetSystemLibs
gosub RemoveSelfReference
gosub OrderByDependency
gosub DisplayResults
end
/*RESULTS:
libraries in dependency order
-----------------------------
std
ieee
dware
gtech
ramlib
std_cell_lib
synopsys
dw01
dw02
des_system_lib
dw03
dw04
dw05
dw06
dw07
<<
remainder:
----------
<<
*/
Dims:
=====
'VARIABLES
int p 'width of first column
int h 'length of each line
int i 'iterator / counter
int j 'main iterator
int b 'table char offset
int e 'end of each line
int bd 'each offset of dependencises line
int le 'length of each lib name
int lend 'size of table
int k 'character indexer
int m 'iterator
int n 'iterator
int cw 'presence flag
int lw 'length of keyword
int a 'iinstr result
int dc 'new lib list indexer / counter
string wr 'keyword
string wn 'keyword
'--arrays--
string datl[64] 'list of lib names
string datd[64] 'lists of lib dependencies
string datn[64] 'new list in dependency ordert
ret
CaptureData:
============
dat=lcase dat
'GET HEADING POSITION
p=instr dat,"library depend"
p-=3 'crlf -1
'REMOVE HEADING
h=instr 3,dat,cr
h+=2
h=instr h,dat,cr 'to remove underlines
'print h cr
h+=2
dat=mid dat,h
'print dat "<" cr
b=1
'PREPARE DATA
lend=len dat
do
i++
datl[i]=rtrim(mid(dat,b,p))
le=len datl[i]
e=instr b+le,dat,cr
bd=b+p
datd[i]=" "+mid(dat,bd,e-bd)+" "
'print datl[i] "," datd[i] cr
b=e+2
if b>lend-2
exit do
endif
loop
ret
GetSystemLibs:
==============
'SCAN DEPENDENCIES
'GET SYSTEM LIBS NOT LISTED
for j=1 to i
k=1
do
wr=getword datd[j],k
if not wr
exit do
endif
cw=0
for m=1 to i
if wr=datl[m] 'on lib list
cw=m
endif
next
if cw=0 'lib not on library list
'add wr to new lib list
dc++ : datn[dc]=wr
'remove lib names from dependency lists
gosub BlankOutNames
endif
loop
next 'j group of dependencies
ret
RemoveSelfReference:
====================
'REMOVE SELF REFERENCE + NO DEPENDENCIES
for j=1 to i
wr=" "+datl[j]+" "
lw=len(wr)
a=instr(datd[j],wr)
if a
mid(datd[j],a,space(lw)) 'blank out self
endif
gosub RemoveLibFromLists
next
ret
'
OrderByDependency:
==================
'
for j=1 to i
if datl[j]
gosub RemoveLibFromLists
if cw then j=0 'repeat cycle
endif
next
ret
'
DisplayResults:
===============
print cr cr
print "libraries in dependency order" cr
print "-----------------------------" cr
for j=1 to dc
print datn[j] cr
next
print "<<" cr cr
print "remainder:" cr
print "----------" cr
for j=1 to i
if datl[j]
print datl[j] " , " datd[j] cr
endif
next
print "<<" cr
pause
end
RemoveLibFromLists:
===================
cw=0
k=1 : wr=getword datd[j],k
if lenw=0
dc++ : datn[dc]=datl[j] 'add to new lib list
datl[j]="" : datd[j]="" 'eliminate frecord rom further checks
gosub BlankOutNames 'eliminate all lib references from table
cw=1 'flag alteration
endif
ret
BlankOutNames:
==============
wn=" "+datn[dc]+" " 'add word boundaries
lw=len wn
for n=1 to i
if datd[n]
a=instr(datd[n],wn)
if a
mid datd[n],a,space(lw) 'blank out
endif
endif
next
ret
</syntaxhighlight>
=={{header|Oz}}==
Using constraint propagation and search:
<
Deps = unit(
des_system_lib: [std synopsys std_cell_lib des_system_lib
Line 4,012 ⟶ 5,233:
{System.showInfo "\nBONUS - grouped by parallelizable compile jobs:"}
{PrintSolution Sol}
end</
Output:
Line 4,041 ⟶ 5,262:
=={{header|Pascal}}==
======Kahn's algorithm======
This solution uses Kahn's algorithm, requires FPC version at least 3.2.0.
<syntaxhighlight lang="pascal">
program ToposortTask;
{$mode delphi}
uses
SysUtils, Generics.Collections;
type
TAdjList = class
InList, // incoming arcs
OutList: THashSet<string>; // outcoming arcs
constructor Create;
destructor Destroy; override;
end;
TDigraph = class(TObjectDictionary<string, TAdjList>)
procedure AddNode(const s: string);
procedure AddArc(const s, t: string);
function AdjList(const s: string): TAdjList;
{ returns True and the sorted sequence of nodes in aOutSeq if is acyclic,
otherwise returns False and nil; uses Kahn's algorithm }
function TryToposort(out aOutSeq: TStringArray): Boolean;
end;
constructor TAdjList.Create;
begin
InList := THashSet<string>.Create;
OutList := THashSet<string>.Create;
end;
destructor TAdjList.Destroy;
begin
InList.Free;
OutList.Free;
inherited;
end;
procedure TDigraph.AddNode(const s: string);
begin
if not ContainsKey(s) then
Add(s, TAdjList.Create);
end;
procedure TDigraph.AddArc(const s, t: string);
begin
AddNode(s);
AddNode(t);
if s <> t then begin
Items[s].OutList.Add(t);
Items[t].InList.Add(s);
end;
end;
function TDigraph.AdjList(const s: string): TAdjList;
begin
if not TryGetValue(s, Result) then
Result := nil;
end;
function TDigraph.TryToposort(out aOutSeq: TStringArray): Boolean;
var
q: TQueue<string>;
p: TPair<string, TAdjList>;
Node, ToRemove: string;
Counter: SizeInt;
begin
q := TQueue<string>.Create;
SetLength(aOutSeq, Count);
Counter := Pred(Count);
for p in Self do
if p.Value.InList.Count = 0 then
q.Enqueue(p.Key);
while q.Count > 0 do begin
ToRemove := q.Dequeue;
for Node in Items[ToRemove].OutList do
with Items[Node] do begin
InList.Remove(ToRemove);
if InList.Count = 0 then
q.Enqueue(Node);
end;
Remove(ToRemove);
aOutSeq[Counter] := ToRemove;
Dec(Counter);
end;
q.Free;
Result := Count = 0;
if not Result then
aOutSeq := nil;
end;
{ expects text separated by line breaks }
function ParseRawData(const aData: string): TDigraph;
var
Line, Curr, Node: string;
FirstTerm: Boolean;
begin
Result := TDigraph.Create([doOwnsValues]);
for Line in aData.Split([LineEnding], TStringSplitOptions.ExcludeEmpty) do begin
FirstTerm := True;
for Curr in Line.Split([' '], TStringSplitOptions.ExcludeEmpty) do
if FirstTerm then begin
Node := Curr;
Result.AddNode(Curr);
FirstTerm := False;
end else
Result.AddArc(Node, Curr);
end;
end;
procedure TrySort(const aData: string);
var
g: TDigraph;
Sorted: TStringArray;
begin
g := ParseRawData(aData);
if g.TryToposort(Sorted) then
WriteLn('success: ', LineEnding, string.Join(', ', Sorted))
else
WriteLn('circular dependency detected');
g.Free;
end;
const
ExampleData =
'des_system_lib std synopsys std_cell_lib des_system_lib dw02 dw01 ramlib ieee' + LineEnding +
'dw01 ieee dw01 dware gtech' + LineEnding +
'dw02 ieee dw02 dware' + LineEnding +
'dw03 std synopsys dware dw03 dw02 dw01 ieee gtech' + LineEnding +
'dw04 dw04 ieee dw01 dware gtech' + LineEnding +
'dw05 dw05 ieee dware' + LineEnding +
'dw06 dw06 ieee dware' + LineEnding +
'dw07 ieee dware' + LineEnding +
'dware ieee dware' + LineEnding +
'gtech ieee gtech' + LineEnding +
'ramlib std ieee' + LineEnding +
'std_cell_lib ieee std_cell_lib' + LineEnding +
'synopsys';
var
Temp: TStringArray;
begin
TrySort(ExampleData);
WriteLn;
//let's add a circular dependency
Temp := ExampleData.Split([LineEnding], TStringSplitOptions.ExcludeEmpty);
Temp[1] := Temp[1] + ' dw04';
TrySort(string.Join(LineEnding, Temp));
end.
</syntaxhighlight>
{{out}}
<pre>
success:
ieee, dware, gtech, std, dw01, dw02, synopsys, std_cell_lib, ramlib, dw04, dw05,
dw07, dw03, dw06, des_system_lib
circular dependency detected
</pre>
======Depth-first search======
Another solution uses DFS and can extract the found cycle; requires FPC version at least 3.2.0.
<syntaxhighlight lang="pascal">
program ToposortTask;
{$mode delphi}
uses
SysUtils, Generics.Collections;
type
TDigraph = class(TObjectDictionary<string, THashSet<string>>)
procedure AddNode(const s: string);
procedure AddArc(const s, t: string);
function AdjList(const s: string): THashSet<string>;
{ returns True and the sorted sequence of nodes in aOutSeq if is acyclic,
otherwise returns False and the first found cycle; uses DFS }
function TryToposort(out aOutSeq: TStringArray): Boolean;
end;
procedure TDigraph.AddNode(const s: string);
begin
if not ContainsKey(s) then
Add(s, THashSet<string>.Create);
end;
procedure TDigraph.AddArc(const s, t: string);
begin
AddNode(s);
AddNode(t);
if s <> t then
Items[s].Add(t);
end;
function TDigraph.AdjList(const s: string): THashSet<string>;
begin
if not TryGetValue(s, Result) then
Result := nil;
end;
function TDigraph.TryToposort(out aOutSeq: TStringArray): Boolean;
var
Parents: TDictionary<string, string>;// stores the traversal tree as pairs (Node, its predecessor)
procedure ExtractCycle(const BackPoint: string; Prev: string);
begin // just walk backwards through the traversal tree, starting from Prev until BackPoint is encountered
with TList<string>.Create do begin
Add(Prev);
repeat
Prev := Parents[Prev];
Add(Prev);
until Prev = BackPoint;
Add(Items[0]);
Reverse; //this is required since we moved backwards through the tree
aOutSeq := ToArray;
Free;
end
end;
var
Visited, // set of already visited nodes
Closed: THashSet<string>;// set of nodes whose subtree traversal is complete
Counter: SizeInt = 0;
function Dfs(const aNode: string): Boolean;// True means successful sorting,
var // False - found cycle
Next: string;
begin
Visited.Add(aNode);
for Next in AdjList(aNode) do
if not Visited.Contains(Next) then begin
Parents.Add(Next, aNode);
if not Dfs(Next) then exit(False);
end else
if not Closed.Contains(Next) then begin//back edge found(i.e. cycle)
ExtractCycle(Next, aNode);
exit(False);
end;
Closed.Add(aNode);
aOutSeq[Counter] := aNode;
Inc(Counter);
Result := True;
end;
var
Node: string;
begin
SetLength(aOutSeq, Count);
Visited := THashSet<string>.Create;
Closed := THashSet<string>.Create;
Parents := TDictionary<string, string>.Create;
Result := True;
for Node in Keys do
if not Visited.Contains(Node) then
if not Dfs(Node) then begin
Result := False;
break;
end;
Visited.Free;
Closed.Free;
Parents.Free;
end;
{ expects text separated by line breaks }
function ParseRawData(const aData: string): TDigraph;
var
Line, Curr, Node: string;
FirstTerm: Boolean;
begin
Result := TDigraph.Create([doOwnsValues]);
for Line in aData.Split([LineEnding], TStringSplitOptions.ExcludeEmpty) do begin
FirstTerm := True;
for Curr in Line.Split([' '], TStringSplitOptions.ExcludeEmpty) do
if FirstTerm then begin
Node := Curr;
Result.AddNode(Curr);
FirstTerm := False;
end else
Result.AddArc(Node, Curr);
end;
end;
procedure TrySort(const aData: string);
var
g: TDigraph;
Sorted: TStringArray;
begin
g := ParseRawData(aData);
if g.TryToposort(Sorted) then
WriteLn('success: ', LineEnding, string.Join(', ', Sorted))
else
WriteLn('circular dependency: ', LineEnding, string.Join('->', Sorted));
g.Free;
end;
const
ExampleData =
'des_system_lib std synopsys std_cell_lib des_system_lib dw02 dw01 ramlib ieee' + LineEnding +
'dw01 ieee dw01 dware gtech' + LineEnding +
'dw02 ieee dw02 dware' + LineEnding +
'dw03 std synopsys dware dw03 dw02 dw01 ieee gtech' + LineEnding +
'dw04 dw04 ieee dw01 dware gtech' + LineEnding +
'dw05 dw05 ieee dware' + LineEnding +
'dw06 dw06 ieee dware' + LineEnding +
'dw07 ieee dware' + LineEnding +
'dware ieee dware' + LineEnding +
'gtech ieee gtech' + LineEnding +
'ramlib std ieee' + LineEnding +
'std_cell_lib ieee std_cell_lib' + LineEnding +
'synopsys';
var
Temp: TStringArray;
begin
TrySort(ExampleData);
WriteLn;
//let's add a circular dependency
Temp := ExampleData.Split([LineEnding], TStringSplitOptions.ExcludeEmpty);
Temp[1] := Temp[1] + ' dw07';
Temp[7] := Temp[7] + ' dw03';
TrySort(string.Join(LineEnding, Temp));
end.
</syntaxhighlight>
{{out}}
<pre>
success:
ieee, dware, gtech, dw01, std, synopsys, dw02, ramlib, std_cell_lib, des_system_lib, dw06, dw03, dw07, dw05, dw04
circular dependency:
dw03->dw01->dw07->dw03
</pre>
=={{header|Perl}}==
Line 4,048 ⟶ 5,596:
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.
<
my %deps = @_;
Line 4,086 ⟶ 5,634:
print_topo_sort(%deps);
push @{ $deps{'dw01'} }, 'dw04'; # Add unresolvable dependency
print_topo_sort(%deps);</
Output:<pre>ieee std synopsys
Line 4,100 ⟶ 5,648:
=={{header|Phix}}==
Implemented as a trivial normal sort.
<!--<syntaxhighlight lang="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
-- rank is 1 for items to compile first, then 2, etc,
-- or 0 if cyclic dependencies prevent compilation.
-- name is handy, and makes the result order alphabetic!
-- dep is a list of dependencies (indexes to other names)</span>
<span style="color: #008080;">function</span> <span style="color: #000000;">add_dependency</span><span style="color: #0000FF;">(</span><span style="color: #004080;">string</span> <span style="color: #000000;">name</span><span style="color: #0000FF;">)</span>
<span style="color: #004080;">integer</span> <span style="color: #000000;">k</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">find</span><span style="color: #0000FF;">(</span><span style="color: #000000;">name</span><span style="color: #0000FF;">,</span><span style="color: #7060A8;">vslice</span><span style="color: #0000FF;">(</span><span style="color: #000000;">names</span><span style="color: #0000FF;">,</span><span style="color: #000000;">NAME</span><span style="color: #0000FF;">))</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">k</span><span style="color: #0000FF;">=</span><span style="color: #000000;">0</span> <span style="color: #008080;">then</span>
<span style="color: #000000;">names</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">append</span><span style="color: #0000FF;">(</span><span style="color: #000000;">names</span><span style="color: #0000FF;">,{</span><span style="color: #000000;">0</span><span style="color: #0000FF;">,</span><span style="color: #000000;">name</span><span style="color: #0000FF;">,{}})</span>
<span style="color: #000000;">k</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">names</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">return</span> <span style="color: #000000;">k</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
<span style="color: #008080;">procedure</span> <span style="color: #000000;">topsort</span><span style="color: #0000FF;">(</span><span style="color: #004080;">string</span> <span style="color: #000000;">input</span><span style="color: #0000FF;">)</span>
<span style="color: #000000;">names</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{}</span>
<span style="color: #004080;">sequence</span> <span style="color: #000000;">lines</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">split</span><span style="color: #0000FF;">(</span><span style="color: #000000;">input</span><span style="color: #0000FF;">,</span><span style="color: #008000;">'\n'</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">lines</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">do</span>
<span style="color: #004080;">sequence</span> <span style="color: #000000;">line</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">split</span><span style="color: #0000FF;">(</span><span style="color: #000000;">lines</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">]),</span>
<span style="color: #000000;">dependencies</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{}</span>
<span style="color: #004080;">integer</span> <span style="color: #000000;">k</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">add_dependency</span><span style="color: #0000FF;">(</span><span style="color: #000000;">line</span><span style="color: #0000FF;">[</span><span style="color: #000000;">1</span><span style="color: #0000FF;">])</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">j</span><span style="color: #0000FF;">=</span><span style="color: #000000;">2</span> <span style="color: #008080;">to</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">line</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">do</span>
<span style="color: #004080;">integer</span> <span style="color: #000000;">l</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">add_dependency</span><span style="color: #0000FF;">(</span><span style="color: #000000;">line</span><span style="color: #0000FF;">[</span><span style="color: #000000;">j</span><span style="color: #0000FF;">])</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">l</span><span style="color: #0000FF;">!=</span><span style="color: #000000;">k</span> <span style="color: #008080;">then</span> <span style="color: #000080;font-style:italic;">-- ignore self-references</span>
<span style="color: #000000;">dependencies</span> <span style="color: #0000FF;">&=</span> <span style="color: #000000;">l</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #000000;">names</span><span style="color: #0000FF;">[</span><span style="color: #000000;">k</span><span style="color: #0000FF;">][</span><span style="color: #000000;">DEP</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">dependencies</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #000080;font-style:italic;">-- Now populate names[RANK] iteratively:</span>
<span style="color: #004080;">bool</span> <span style="color: #000000;">more</span> <span style="color: #0000FF;">=</span> <span style="color: #004600;">true</span>
<span style="color: #004080;">integer</span> <span style="color: #000000;">rank</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">0</span>
<span style="color: #008080;">while</span> <span style="color: #000000;">more</span> <span style="color: #008080;">do</span>
<span style="color: #000000;">more</span> <span style="color: #0000FF;">=</span> <span style="color: #004600;">false</span>
<span style="color: #000000;">rank</span> <span style="color: #0000FF;">+=</span> <span style="color: #000000;">1</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">names</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">do</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">names</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">][</span><span style="color: #000000;">RANK</span><span style="color: #0000FF;">]=</span><span style="color: #000000;">0</span> <span style="color: #008080;">then</span>
<span style="color: #004080;">bool</span> <span style="color: #000000;">ok</span> <span style="color: #0000FF;">=</span> <span style="color: #004600;">true</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">j</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">names</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">][</span><span style="color: #000000;">DEP</span><span style="color: #0000FF;">])</span> <span style="color: #008080;">do</span>
<span style="color: #004080;">integer</span> <span style="color: #000000;">ji</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">names</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">][</span><span style="color: #000000;">DEP</span><span style="color: #0000FF;">][</span><span style="color: #000000;">j</span><span style="color: #0000FF;">],</span>
<span style="color: #000000;">nr</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">names</span><span style="color: #0000FF;">[</span><span style="color: #000000;">ji</span><span style="color: #0000FF;">][</span><span style="color: #000000;">RANK</span><span style="color: #0000FF;">]</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">nr</span><span style="color: #0000FF;">=</span><span style="color: #000000;">0</span> <span style="color: #008080;">or</span> <span style="color: #000000;">nr</span><span style="color: #0000FF;">=</span><span style="color: #000000;">rank</span> <span style="color: #008080;">then</span>
<span style="color: #000000;">ok</span> <span style="color: #0000FF;">=</span> <span style="color: #004600;">false</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">ok</span> <span style="color: #008080;">then</span>
<span style="color: #000000;">names</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">][</span><span style="color: #000000;">RANK</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">rank</span>
<span style="color: #000000;">more</span> <span style="color: #0000FF;">=</span> <span style="color: #004600;">true</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">while</span>
<span style="color: #000000;">names</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">sort</span><span style="color: #0000FF;">(</span><span style="color: #000000;">names</span><span style="color: #0000FF;">)</span> <span style="color: #000080;font-style:italic;">-- (ie by [RANK=1] then [NAME=2])</span>
<span style="color: #004080;">integer</span> <span style="color: #000000;">prank</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">names</span><span style="color: #0000FF;">[</span><span style="color: #000000;">1</span><span style="color: #0000FF;">][</span><span style="color: #000000;">RANK</span><span style="color: #0000FF;">]</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">prank</span><span style="color: #0000FF;">=</span><span style="color: #000000;">0</span> <span style="color: #008080;">then</span> <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;">"** CYCLIC **:"</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">names</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">do</span>
<span style="color: #000000;">rank</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">names</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">][</span><span style="color: #000000;">RANK</span><span style="color: #0000FF;">]</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">></span><span style="color: #000000;">1</span> <span style="color: #008080;">then</span>
<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: #008080;">iff</span><span style="color: #0000FF;">(</span><span style="color: #000000;">rank</span><span style="color: #0000FF;">=</span><span style="color: #000000;">prank</span><span style="color: #0000FF;">?</span><span style="color: #008000;">" "</span><span style="color: #0000FF;">:</span><span style="color: #008000;">"\n"</span><span style="color: #0000FF;">))</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<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: #000000;">names</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">][</span><span style="color: #000000;">NAME</span><span style="color: #0000FF;">])</span>
<span style="color: #000000;">prank</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">rank</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<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;">"\n"</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">procedure</span>
<span style="color: #008080;">constant</span> <span style="color: #000000;">input</span> <span style="color: #0000FF;">=</span> <span style="color: #008000;">"""
des_system_lib std synopsys std_cell_lib des_system_lib dw02 dw01 ramlib ieee
ramlib std ieee
std_cell_lib ieee std_cell_lib
synopsys"""</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: #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>
<!--</syntaxhighlight>-->
{{out}}
Items on the same line can be compiled at the same time, and each line is alphabetic.
Line 4,204 ⟶ 5,754:
dw02 dw05 dw06 dw07
</pre>
=={{header|Picat}}==
<syntaxhighlight 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].</syntaxhighlight>
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.
<syntaxhighlight 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=[]
].</syntaxhighlight>
{{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===
<syntaxhighlight 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]
].</syntaxhighlight>
{{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}}==
<
(setq Lst # Build a flat list
(uniq
Line 4,220 ⟶ 5,886:
(del (link @) 'Lst) # Yes: Store in result
(for This Lst # and remove from 'dep's
(=: dep (delete @ (: dep))) ) ) ) ) )</
Output:
<pre>: (sortDependencies
Line 4,240 ⟶ 5,906:
=={{header|PowerShell}}==
<
$a=@"
des_system_lib std synopsys std_cell_lib des_system_lib dw02 dw01 ramlib ieee
Line 4,338 ⟶ 6,004:
"{0,-14} $($_."Library Dependencies")" -f $_.Library
}
}</
=={{header|PureBasic}}==
<
DataSection
;"LIBRARY: [LIBRARY_DEPENDENCY_1 LIBRARY_DEPENDENCY_2 ... LIBRARY_DEPENDENCY_N]
Line 4,459 ⟶ 6,125:
Print(#CRLF$ + #CRLF$ + "Press ENTER to exit")
Input()
CloseConsole()</
Sample output for no dependencies:
<pre>Compile order:
Line 4,488 ⟶ 6,154:
=={{header|Python}}==
===Python 3===
<syntaxhighlight lang="python">try:
from functools import reduce
except:
Line 4,523 ⟶ 6,190:
assert not data, "A cyclic dependency exists amongst %r" % data
print ('\n'.join( toposort2(data) ))</
'''Ordered output'''<br>
Line 4,539 ⟶ 6,206:
assert not data, "A cyclic dependency exists amongst %r" % data
AssertionError: A cyclic dependency exists amongst {'dw04': {'dw01'}, 'dw03': {'dw01'}, 'dw01': {'dw04'}, 'des_system_lib': {'dw01'}}</pre>
===Python 3.9 graphlib===
<syntaxhighlight lang="python">from graphlib import TopologicalSorter
# LIBRARY mapped_to LIBRARY DEPENDENCIES
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()),
'dw02': set('ieee dw02 dware'.split()),
'dw03': set('std synopsys dware dw03 dw02 dw01 ieee gtech'.split()),
'dw04': set('dw04 ieee dw01 dware gtech'.split()),
'dw05': set('dw05 ieee dware'.split()),
'dw06': set('dw06 ieee dware'.split()),
'dw07': set('ieee dware'.split()),
'dware': set('ieee dware'.split()),
'gtech': set('ieee gtech'.split()),
'ramlib': set('std ieee'.split()),
'std_cell_lib': set('ieee std_cell_lib'.split()),
'synopsys': set(),
}
# Ignore self dependencies
for k, v in data.items():
v.discard(k)
ts = TopologicalSorter(data)
print(tuple(ts.static_order()))</syntaxhighlight>
{{out}}
<pre>('synopsys', 'std', 'ieee', 'dware', 'gtech', 'ramlib', 'std_cell_lib', 'dw02', 'dw05', 'dw06', 'dw07', 'dw01', 'des_system_lib', 'dw03', 'dw04')</pre>
=={{header|R}}==
First make the list
<syntaxhighlight lang="r">
deps <- list(
"des_system_lib" = c("std", "synopsys", "std_cell_lib", "des_system_lib", "dw02", "dw01", "ramlib", "ieee"),
Line 4,558 ⟶ 6,254:
"std_cell_lib" = c("ieee", "std_cell_lib"),
"synopsys" = c())
</syntaxhighlight>
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">
tsort <- function(deps) {
nm <- names(deps)
Line 4,594 ⟶ 6,290:
s
}
</syntaxhighlight>
On the given example :
<syntaxhighlight 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>
If dw01 depends on dw04 as well :
<syntaxhighlight lang="r">
Unorderable items :
des_system_lib
Line 4,612 ⟶ 6,308:
dw04
dw03
</syntaxhighlight>
=={{header|Racket}}==
<
#lang racket
Line 4,674 ⟶ 6,370:
(topo-sort (clean G))
</syntaxhighlight>
Output:
<
'(synopsys ieee dware gtech std_cell_lib std ramlib dw07 dw06 dw05 dw01 dw04 dw02 dw03 des_system_lib)
</syntaxhighlight>
=={{header|Raku}}==
Line 4,684 ⟶ 6,380:
{{trans|Perl}}
{{Works with|rakudo|2016.01}}
<syntaxhighlight lang="raku"
my %ba;
for %deps.kv -> $before, @afters {
Line 4,720 ⟶ 6,416:
print_topo_sort(%deps);
%deps<dw01> = <ieee dw01 dware gtech dw04>; # Add unresolvable dependency
print_topo_sort(%deps);</
Output:<pre>ieee std synopsys
Line 4,740 ⟶ 6,436:
Some of the FORTRAN 77 statements were converted to '''do''' loops (or '''do''' structures), and
<br>some variables were [https://en.wikipedia.org/wiki/Camel_case <u>''camel capitalized]''</u>.
<
iDep.= 0; iPos.= 0; iOrd.= 0 /*initialize some stemmed arrays to 0.*/
nL= 15; nd= 44; nc= 69 /* " " "parms" and indices.*/
Line 4,782 ⟶ 6,478:
end /*i*/
end /*until*/
nO= j-1; return</
{{out|output}}
<pre>
Line 4,809 ⟶ 6,505:
=={{header|Ruby}}==
Uses the [http://www.ruby-doc.org/stdlib/libdoc/tsort/rdoc/classes/TSort.html TSort] module from the Ruby stdlib.
<
class Hash
include TSort
Line 4,846 ⟶ 6,542:
ramlib std ieee
std_cell_lib ieee std_cell_lib
synopsys</
{{out}}
<pre>
Line 4,855 ⟶ 6,551:
=={{header|Rust}}==
<
use std::collections::{HashMap, HashSet};
Line 4,967 ⟶ 6,663:
}
}
</syntaxhighlight>
Output:
<pre>
Line 4,991 ⟶ 6,687:
"Cycle detected among {\"dw03\", \"des_system_lib\", \"dw04\", \"dw01\"}"
</pre>
=={{header|Scheme}}==
{{trans|Python}}
<syntaxhighlight lang="scheme">
(import (chezscheme))
(import (srfi srfi-1))
(define (remove-self-dependency pair)
(let ((key (car pair))
(value (cdr pair)))
(cons key (remq key value))))w
(define (remove-self-dependencies alist)
(map remove-self-dependency alist))
(define (add-missing-items dependencies)
(let loop ((items (delete-duplicates (append-map cdr dependencies) eq?))
(out dependencies))
(if (null? items)
out
(let ((item (car items)))
(if (assq item out)
(loop (cdr items) out)
(loop (cdr items) (cons (cons item '()) out)))))))
(define (lift dependencies batch)
(let loop ((dependencies dependencies)
(out '()))
(if (null? dependencies)
out
(let ((key (caar dependencies))
(value (cdar dependencies)))
(if (null? value)
(loop (cdr dependencies) out)
(loop (cdr dependencies)
(cons (cons key (lset-difference eq? value batch))
out)))))))
(define (topological-sort dependencies)
(let* ((dependencies (remove-self-dependencies dependencies))
(dependencies (add-missing-items dependencies)))
(let loop ((out '())
(dependencies dependencies))
(if (null? dependencies)
(reverse out)
(let ((batch (map car (filter (lambda (pair) (null? (cdr pair))) dependencies))))
(if (null? batch)
#f
(loop (cons batch out) (lift dependencies batch))))))))
(define example
'((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 . ())))
(write (topological-sort example))
(define unsortable
'((des_system_lib . (std synopsys std_cell_lib des_system_lib dw02
dw01 ramlib ieee))
(dw01 . (ieee dw01 dware gtech 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 . ())))
(newline)
(write (topological-sort unsortable))
</syntaxhighlight>
=={{header|Sidef}}==
{{trans|Perl}}
<
var ba = Hash.new;
deps.each { |before, afters|
Line 5,035 ⟶ 6,821:
print_topo_sort(deps);
deps{:dw01}.append('dw04'); # Add unresolvable dependency
print_topo_sort(deps);</
{{out}}
<pre>
Line 5,047 ⟶ 6,833:
dw02 dw05 dw06 dw07
Cicle found! des_system_lib dw01 dw03 dw04
</pre>
=={{header|Swift}}==
{{trans|Rust}}
<syntaxhighlight lang="swift">let libs = [
("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", [])
]
struct Library {
var name: String
var children: [String]
var numParents: Int
}
func buildLibraries(_ input: [(String, [String])]) -> [String: Library] {
var libraries = [String: Library]()
for (name, parents) in input {
var numParents = 0
for parent in parents where parent != name {
numParents += 1
libraries[parent, default: Library(name: parent, children: [], numParents: 0)].children.append(name)
}
libraries[name, default: Library(name: name, children: [], numParents: numParents)].numParents = numParents
}
return libraries
}
func topologicalSort(libs: [String: Library]) -> [String]? {
var libs = libs
var needsProcessing = Set(libs.keys)
var options = libs.compactMap({ $0.value.numParents == 0 ? $0.key : nil })
var sorted = [String]()
while let cur = options.popLast() {
for children in libs[cur]?.children ?? [] {
libs[children]?.numParents -= 1
if libs[children]?.numParents == 0 {
options.append(libs[children]!.name)
}
}
libs[cur]?.children.removeAll()
sorted.append(cur)
needsProcessing.remove(cur)
}
guard needsProcessing.isEmpty else {
return nil
}
return sorted
}
print(topologicalSort(libs: buildLibraries(libs))!)</syntaxhighlight>
{{out}}
<pre>["ieee", "std_cell_lib", "gtech", "dware", "dw07", "dw06", "dw05", "dw02", "dw01", "dw04", "std", "ramlib", "synopsys", "dw03", "des_system_lib"]</pre>
=={{header|Tailspin}}==
<syntaxhighlight lang="tailspin">
data node <'.+'>, from <node>, to <node>
templates topologicalSort
@: [];
{V: {|$.v..., $.e({node: §.to})...|} , E: {|$.e... -> \(<{from: <~=$.to>}> $! \)|}} -> #
when <{V: <?($::count <=0>)>}> $@!
otherwise
def independent: ($.V notMatching $.E({node: §.from}));
[$independent... -> $.node] -> ..|@: $;
{V: ($.V notMatching $independent), E: ($.E notMatching $independent({to: §.node}))}
-> \(<?($independent::count <1..>)> $! \) -> #
end topologicalSort
composer lines
[<line>+]
rule line: <'[^\n]*'> (<'\n'>)
end lines
templates collectDeps
@: { v: [], e: []};
composer depRecord
(<WS>? def node: <~WS>; <WS>? <dep>* <WS>? $node -> ..|@collectDeps.v: {node: $};)
rule dep: (<~WS> -> ..|@collectDeps.e: {from: node´$node, to: node´$}; <WS>?)
end depRecord
$(3..last)... -> !depRecord
$@!
end collectDeps
'LIBRARY LIBRARY DEPENDENCIES
======= ====================
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
' -> lines -> collectDeps -> topologicalSort -> !OUT::write
</syntaxhighlight>
{{out}}
<pre>
[[std, synopsys, ieee], [ramlib, dware, std_cell_lib, gtech], [dw01, dw02, dw05, dw06, dw07], [dw03, dw04, des_system_lib]]
</pre>
=={{header|Tcl}}==
{{works with|Tcl|8.5}}
<
proc topsort {data} {
# Clean the data
Line 5,087 ⟶ 7,004:
}
}
}</
Demonstration code (which parses it from the format that the puzzle was posed in):
<
des_system_lib std synopsys std_cell_lib des_system_lib dw02 dw01 ramlib ieee
dw01 ieee dw01 dware gtech
Line 5,108 ⟶ 7,025:
dict set parsedData [lindex $line 0] [lrange $line 1 end]
}
puts [topsort $parsedData]</
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,120 ⟶ 7,037:
{{works with|Bourne Shell}}
<
> des_system_lib std synopsys std_cell_lib des_system_lib dw02 dw01 ramlib ieee
> dw01 ieee dw01 dware gtech
Line 5,149 ⟶ 7,066:
dw03
ramlib
des_system_lib</
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 5,178 ⟶ 7,095:
unorderable libraries, if any, on the right. Self-dependences are
ignored and unlisted libraries are presumed independent.
<
test program:
<
dependence_table = -[
Line 5,204 ⟶ 7,121:
#show+
main = <.~&l,@r ~&i&& 'unorderable: '--> mat` ~~ tsort parse dependence_table</
With the given table, the output is
<pre>
Line 5,217 ⟶ 7,134:
=={{header|VBScript}}==
=====Implementation=====
<syntaxhighlight lang="vb">
class topological
dim dictDependencies
Line 5,297 ⟶ 7,214:
end property
end class
</syntaxhighlight>
=====Invocation=====
<syntaxhighlight lang="vb">
dim toposort
set toposort = new topological
Line 5,324 ⟶ 7,241:
toposort.reset
next
</syntaxhighlight>
=====Output=====
Line 5,407 ⟶ 7,324:
=={{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.
<
' http://tawani.blogspot.com/2009/02/topological-sorting-and-cyclic.html
' added/changed:
Line 5,736 ⟶ 7,653:
#End Region
End Class
</syntaxhighlight>
=====Output=====
<pre>
Line 5,816 ⟶ 7,733:
synopsys
Press any key to continue . . .
</pre>
=={{header|Wren}}==
{{trans|Kotlin}}
<syntaxhighlight lang="wren">class Graph {
construct new(s, edges) {
_vertices = s.split(", ")
var n = _vertices.count
_adjacency = List.filled(n, null)
for (i in 0...n) _adjacency[i] = List.filled(n, false)
for (edge in edges) _adjacency[edge[0]][edge[1]] = true
}
hasDependency(r, todo) {
for (c in todo) if (_adjacency[r][c]) return true
return false
}
topoSort() {
var res = []
var todo = List.filled(_vertices.count, 0)
for (i in 0...todo.count) todo[i] = i
while (!todo.isEmpty) {
var outer = false
var i = 0
for (r in todo) {
if (!hasDependency(r, todo)) {
todo.removeAt(i)
res.add(_vertices[r])
outer = true
break
}
i = i + 1
}
if (!outer) {
System.print("Graph has cycles")
return ""
}
}
return res
}
}
var s = "std, ieee, des_system_lib, dw01, dw02, dw03, dw04, dw05, " +
"dw06, dw07, dware, gtech, ramlib, std_cell_lib, synopsys"
var deps = [
[2, 0], [2, 14], [2, 13], [2, 4], [2, 3], [2, 12], [2, 1],
[3, 1], [3, 10], [3, 11],
[4, 1], [4, 10],
[5, 0], [5, 14], [5, 10], [5, 4], [5, 3], [5, 1], [5, 11],
[6, 1], [6, 3], [6, 10], [6, 11],
[7, 1], [7, 10],
[8, 1], [8, 10],
[9, 1], [9, 10],
[10, 1],
[11, 1],
[12, 0], [12, 1],
[13, 1]
]
var g = Graph.new(s, deps)
System.print("Topologically sorted order:")
System.print(g.topoSort())
System.print()
// now insert [3, 6] at index 10 of deps
deps.insert(10, [3, 6])
var g2 = Graph.new(s, deps)
System.print("Following the addition of dw04 to the dependencies of dw01:")
System.print(g2.topoSort())</syntaxhighlight>
{{out}}
<pre>
Topologically sorted order:
[std, ieee, dware, dw02, dw05, dw06, dw07, gtech, dw01, dw04, ramlib, std_cell_lib, synopsys, des_system_lib, dw03]
Following the addition of dw04 to the dependencies of dw01:
Graph has cycles
</pre>
Line 5,821 ⟶ 7,816:
{{trans|Wikipedia}}
Input data is munged
<
allDs:=data.pump(List,fcn(rds){ T(Void.Write,Void.Write,rds[1]) }).copy();
roots:=Dictionary(data); // dictionary of root:leaves
Line 5,835 ⟶ 7,830:
if(roots) throw(Exception.ValueError("Cycle: "+roots.keys));
L
}</
<
"des_system_lib", "std synopsys std_cell_lib des_system_lib dw02 dw01 ramlib ieee",
"dw01", "ieee dw01 dware gtech",
Line 5,854 ⟶ 7,849:
T( r, ds.replace(r,"").strip().split().copy() ) // leaves writable 'cause they will be
});
topoSort(data).println();</
{{out}}
<pre>
| |||