Topological sort: Difference between revisions
m
→{{header|Wren}}: Changed to Wren S/H
No edit summary |
m (→{{header|Wren}}: Changed to Wren S/H) |
||
| (181 intermediate revisions by 69 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.
The compiling of a library in the [[wp:VHDL|VHDL]] language has the constraint that a library must be compiled after any library it depends on.
A tool exists that extracts library dependencies.
;Task:
Write a function that will return a valid compile order of VHDL libraries from their dependencies.
* Assume library names are single words.
* Items mentioned as only
* Any self dependencies should be ignored.
* Any un-orderable dependencies should be flagged.
<br>
Use the following data as an example:
<pre>
Line 25 ⟶ 36:
ramlib std ieee
std_cell_lib ieee std_cell_lib
synopsys
</pre>
<br>
<small>Note: the above data would be un-orderable if, for example, <code>dw04</code> is added to the list of dependencies of <code>dw01</code>.</small>
;C.f.:
:* [[Topological sort/Extracted top item]].
<br>
There are two popular algorithms for topological sorting:
:* Kahn's 1962 topological sort <ref> [[wp: topological sorting]] </ref>
:* depth-first search <ref> [[wp: topological sorting]] </ref> <ref> Jason Sachs
[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}}==
'''Digraphs: A package for directed graphs, representing nodes as positive numbers'''
The specification:
<syntaxhighlight lang="ada">with Ada.Containers.Vectors; use Ada.Containers;
package Digraphs is
type Node_Idx_With_Null is new Natural;
subtype Node_Index is Node_Idx_With_Null range 1 .. Node_Idx_With_Null'Last;
-- a Node_Index is a number from 1, 2, 3, ... and the representative of a node
type Graph_Type is tagged private;
-- make sure Node is in Graph (possibly without connections)
procedure Add_Node
(Graph: in out Graph_Type'Class; Node: Node_Index);
-- insert an edge From->To into Graph; do nothing if already there
procedure Add_Connection
(Graph: in out Graph_Type'Class; From, To: Node_Index);
-- get the largest Node_Index used in any Add_Node or Add_Connection op.
-- iterate over all nodes of Graph: "for I in 1 .. Graph.Node_Count loop ..."
function Node_Count(Graph: Graph_Type) return Node_Idx_With_Null;
-- remove an edge From->To from Fraph; do nothing if not there
-- Graph.Node_Count is not changed
procedure Del_Connection
(Graph: in out Graph_Type'Class; From, To: Node_Index);
-- check if an edge From->to exists in Graph
function Connected
(Graph: Graph_Type; From, To: Node_Index) return Boolean;
-- data structure to store a list of nodes
package Node_Vec is new Vectors(Positive, Node_Index);
-- get a list of all nodes From->Somewhere in Graph
function All_Connections
(Graph: Graph_Type; From: Node_Index) return Node_Vec.Vector;
Graph_Is_Cyclic: exception;
-- a depth-first search to find a topological sorting of the nodes
-- raises Graph_Is_Cyclic if no topological sorting is possible
function Top_Sort
(Graph: Graph_Type) return Node_Vec.Vector;
private
package Conn_Vec is new Vectors(Node_Index, Node_Vec.Vector, Node_Vec."=");
type Graph_Type is new Conn_Vec.Vector with null record;
end Digraphs;</syntaxhighlight>
The implementation:
<syntaxhighlight lang="ada">package body Digraphs is
function Node_Count(Graph: Graph_Type) return Node_Idx_With_Null is
begin
return Node_Idx_With_Null(Graph.Length);
end Node_Count;
procedure Add_Node(Graph: in out Graph_Type'Class; Node: Node_Index) is
begin
for I in Node_Index range Graph.Node_Count+1 .. Node loop
Graph.Append(Node_Vec.Empty_Vector);
end loop;
end Add_Node;
procedure Add_Connection
(Graph: in out Graph_Type'Class; From, To: Node_Index) is
begin
Graph.Add_Node(Node_Index'Max(From, To));
declare
Connection_List: Node_Vec.Vector := Graph.Element(From);
begin
for I in Connection_List.First_Index .. Connection_List.Last_Index loop
if Connection_List.Element(I) >= To then
if Connection_List.Element(I) = To then
return; -- if To is already there, don't add it a second time
else -- I is the first index with Element(I)>To, insert To here
Connection_List.Insert(Before => I, New_Item => To);
Graph.Replace_Element(From, Connection_List);
return;
end if;
end if;
end loop;
-- there was no I with no Element(I) > To, so insert To at the end
Connection_List.Append(To);
Graph.Replace_Element(From, Connection_List);
return;
end;
end Add_Connection;
procedure Del_Connection
(Graph: in out Graph_Type'Class; From, To: Node_Index) is
Connection_List: Node_Vec.Vector := Graph.Element(From);
begin
for I in Connection_List.First_Index .. Connection_List.Last_Index loop
if Connection_List.Element(I) = To then
Connection_List.Delete(I);
Graph.Replace_Element(From, Connection_List);
return; -- we are done
end if;
end loop;
end Del_Connection;
function Connected
(Graph: Graph_Type; From, To: Node_Index) return Boolean is
Connection_List: Node_Vec.Vector renames Graph.Element(From);
begin
for I in Connection_List.First_Index .. Connection_List.Last_Index loop
if Connection_List.Element(I) = To then
return True;
end if;
end loop;
return False;
end Connected;
function All_Connections
(Graph: Graph_Type; From: Node_Index) return Node_Vec.Vector is
begin
return Graph.Element(From);
end All_Connections;
function Top_Sort
(Graph: Graph_Type) return Node_Vec.Vector is
Result: Node_Vec.Vector;
Visited: array(1 .. Graph.Node_Count) of Boolean := (others => False);
Active: array(1 .. Graph.Node_Count) of Boolean := (others => False);
procedure Visit(Node: Node_Index) is
begin
if not Visited(Node) then
Visited(Node) := True;
Active(Node) := True;
declare
Cons: Node_Vec.Vector := All_Connections(Graph, Node);
begin
for Idx in Cons.First_Index .. Cons.Last_Index loop
Visit(Cons.Element(Idx));
end loop;
end;
Active(Node) := False;
Result.Append(Node);
else
if Active(Node) then
raise Constraint_Error with "Graph is Cyclic";
end if;
end if;
end Visit;
begin
for Some_Node in Visited'Range loop
Visit(Some_Node);
end loop;
return Result;
end Top_Sort;
end Digraphs;</syntaxhighlight>
'''Set_of_Names: Translating strings into numbers and vice versa'''
The specification:
<syntaxhighlight lang="ada">private with Ada.Containers.Indefinite_Vectors;
generic
type Index_Type_With_Null is new Natural;
package Set_Of_Names is
subtype Index_Type is Index_Type_With_Null
range 1 .. Index_Type_With_Null'Last;
-- manage a set of strings;
-- each string in the set is assigned a unique index of type Index_Type
type Set is tagged private;
-- inserts Name into Names; do nothing if already there;
procedure Add(Names: in out Set; Name: String);
-- Same operation, additionally emiting Index=Names.Idx(Name)
procedure Add(Names: in out Set; Name: String; Index: out Index_Type);
-- remove Name from Names; do nothing if not found
-- the removal may change the index of other strings in Names
procedure Sub(Names: in out Set; Name: String);
-- returns the unique index of Name in Set; or 0 if Name is not there
function Idx(Names: Set; Name: String) return Index_Type_With_Null;
-- returns the unique name of Index;
function Name(Names: Set; Index: Index_Type) return String;
-- first index, last index and total number of names in set
-- to iterate over Names, use "for I in Names.Start .. Names.Stop loop ...
function Start(Names: Set) return Index_Type;
function Stop(Names: Set) return Index_Type_With_Null;
function Size(Names: Set) return Index_Type_With_Null;
private
package Vecs is new Ada.Containers.Indefinite_Vectors
(Index_Type => Index_Type, Element_Type => String);
type Set is new Vecs.Vector with null record;
end Set_Of_Names;</syntaxhighlight>
The implementation
<syntaxhighlight lang="ada">package body Set_Of_Names is
use type Ada.Containers.Count_Type, Vecs.Cursor;
function Start(Names: Set) return Index_Type is
begin
if Names.Length = 0 then
return 1;
else
return Names.First_Index;
end if;
end Start;
function Stop(Names: Set) return Index_Type_With_Null is
begin
if Names.Length=0 then
return 0;
else
return Names.Last_Index;
end if;
end Stop;
function Size(Names: Set) return Index_Type_With_Null is
begin
return Index_Type_With_Null(Names.Length);
end Size;
procedure Add(Names: in out Set; Name: String; Index: out Index_Type) is
I: Index_Type_With_Null := Names.Idx(Name);
begin
if I = 0 then -- Name is not yet in Set
Names.Append(Name);
Index := Names.Stop;
else
Index := I;
end if;
end Add;
procedure Add(Names: in out Set; Name: String) is
I: Index_Type;
begin
Names.Add(Name, I);
end Add;
procedure Sub(Names: in out Set; Name: String) is
I: Index_Type_With_Null := Names.Idx(Name);
begin
if I /= 0 then -- Name is in set
Names.Delete(I);
end if;
end Sub;
function Idx(Names: Set; Name: String) return Index_Type_With_Null is
begin
for I in Names.First_Index .. Names.Last_Index loop
if Names.Element(I) = Name then
return I;
end if;
end loop;
return 0;
end Idx;
function Name(Names: Set; Index: Index_Type) return String is
begin
return Names.Element(Index);
end Name;
end Set_Of_Names;</syntaxhighlight>
'''Toposort: Putting things together for the main program'''
<syntaxhighlight lang="ada">with Ada.Text_IO, Digraphs, Set_Of_Names, Ada.Command_Line;
procedure Toposort is
-- shortcuts for package names, intantiation of generic package
package TIO renames Ada.Text_IO;
package DG renames Digraphs;
package SN is new Set_Of_Names(DG.Node_Idx_With_Null);
-- reat the graph from the file with the given Filename
procedure Read(Filename: String; G: out DG.Graph_Type; N: out SN.Set) is
-- finds the first word in S(Start .. S'Last), delimited by spaces
procedure Find_Token(S: String; Start: Positive;
First: out Positive; Last: out Natural) is
begin
First := Start;
while First <= S'Last and then S(First)= ' ' loop
First := First + 1;
end loop;
Last := First-1;
while Last < S'Last and then S(Last+1) /= ' ' loop
Last := Last + 1;
end loop;
end Find_Token;
File: TIO.File_Type;
begin
TIO.Open(File, TIO.In_File, Filename);
TIO.Skip_Line(File, 2);
-- the first two lines contain header and "===...==="
while not TIO.End_Of_File(File) loop
declare
Line: String := TIO.Get_Line(File);
First: Positive;
Last: Natural;
To, From: DG.Node_Index;
begin
Find_Token(Line, Line'First, First, Last);
if Last >= First then
N.Add(Line(First .. Last), From);
G.Add_Node(From);
loop
Find_Token(Line, Last+1, First, Last);
exit when Last < First;
N.Add(Line(First .. Last), To);
G.Add_Connection(From, To);
end loop;
end if;
end;
end loop;
TIO.Close(File);
end Read;
Graph: DG.Graph_Type;
Names: SN.Set;
begin
Read(Ada.Command_Line.Argument(1), Graph, Names);
-- eliminat self-cycles
for Start in 1 .. Graph.Node_Count loop
Graph.Del_Connection(Start, Start);
end loop;
-- perform the topological sort and output the result
declare
Result: DG.Node_Vec.Vector;
begin
Result := Graph.Top_Sort;
for Index in Result.First_Index .. Result.Last_Index loop
TIO.Put(Names.Name(Result.Element(Index)));
if Index < Result.Last_Index then
TIO.Put(" -> ");
end if;
end loop;
TIO.New_Line;
exception
when DG.Graph_Is_Cyclic =>
TIO.Put_Line("There is no topological sorting -- the Graph is cyclic!");
end;
end Toposort;</syntaxhighlight>
{{out}}
Given the name of the file with the dependencies as the parameter,
Toposort generates the following output:
<pre>std -> synopsys -> ieee -> std_cell_lib -> dware -> dw02 -> gtech -> dw01 -> ramlib -> des_system_lib -> dw03 -> dw04 -> dw05 -> dw06 -> dw07</pre>
If the dependencies is circular, the the Toposort tells that:
<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}}==
<syntaxhighlight 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)
(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.)
(cycle-11.cycle-12)
(cycle-12.cycle-11)
(cycle-21.dw01 cycle-22 dw02 dw03)
(cycle-22.cycle-21 dw01 dw04)
: ?libdeps
& :?indeps
& ( toposort
= A Z res module dependants todo done
. !arg:(?todo.?done)
& ( areDone
=
. !arg:
| !arg
: ( %@
: [%( !module+!done+!indeps:?+(? !sjt ?)+?
| ~(!libdeps:? (!sjt.?) ?)
& !sjt !indeps:?indeps
)
)
?arg
& areDone$!arg
)
& ( !todo
: ?A
(?module.?dependants&areDone$!dependants)
( ?Z
& toposort$(!A !Z.!done !module):?res
)
& !res
| (!todo.!done)
)
)
& toposort$(!libdeps.):(?cycles.?res)
& out$("
compile order:" !indeps !res "\ncycles:" !cycles)
);</syntaxhighlight>
{{out}}
<pre>compile order:
ieee
std
dware
dw02
dw05
dw06
dw07
gtech
dw01
dw04
ramlib
std_cell_lib
synopsys
des_system_lib
dw03
cycles:
(cycle-11.cycle-12)
(cycle-12.cycle-11)
(cycle-21.dw01 cycle-22 dw02 dw03)
(cycle-22.cycle-21 dw01 dw04)</pre>
=={{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.
<syntaxhighlight lang="c">#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>
char input[] =
"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"
"dw06 dw06 ieee dware\n"
"dw07 ieee dware\n"
"dware ieee dware\n"
"gtech ieee gtech\n"
"ramlib std ieee\n"
"std_cell_lib ieee std_cell_lib\n"
"synopsys\n"
"cycle_11 cycle_12\n"
"cycle_12 cycle_11\n"
"cycle_21 dw01 cycle_22 dw02 dw03\n"
"cycle_22 cycle_21 dw01 dw04";
typedef struct item_t item_t, *item;
struct item_t { const char *name; int *deps, n_deps, idx, depth; };
int get_item(item *list, int *len, const char *name)
{
int i;
item lst = *list;
for (i = 0; i < *len; i++)
if (!strcmp(lst[i].name, name)) return i;
lst = *list = realloc(lst, ++*len * sizeof(item_t));
i = *len - 1;
memset(lst + i, 0, sizeof(item_t));
lst[i].idx = i;
lst[i].name = name;
return i;
}
void add_dep(item it, int i)
{
if (it->idx == i) return;
it->deps = realloc(it->deps, (it->n_deps + 1) * sizeof(int));
it->deps[it->n_deps++] = i;
}
int parse_input(item *ret)
{
int n_items = 0;
int i, parent, idx;
item list = 0;
char *s, *e, *word, *we;
for (s = input; ; s = 0) {
if (!(s = strtok_r(s, "\n", &e))) break;
for (i = 0, word = s; ; i++, word = 0) {
if (!(word = strtok_r(word, " \t", &we))) break;
idx = get_item(&list, &n_items, word);
if (!i) parent = idx;
else add_dep(list + parent, idx);
}
}
*ret = list;
return n_items;
}
/* recursively resolve compile order; negative means loop */
int get_depth(item list, int idx, int bad)
{
int max, i, t;
if (!list[idx].deps)
return list[idx].depth = 1;
if ((t = list[idx].depth) < 0) return t;
list[idx].depth = bad;
for (max = i = 0; i < list[idx].n_deps; i++) {
if ((t = get_depth(list, list[idx].deps[i], bad)) < 0) {
max = t;
break;
}
if (max < t + 1) max = t + 1;
}
return list[idx].depth = max;
}
int main()
{
int i, j, n, bad = -1, max, min;
item items;
n = parse_input(&items);
for (i = 0; i < n; i++)
if (!items[i].depth && get_depth(items, i, bad) < 0) bad--;
for (i = 0, max = min = 0; i < n; i++) {
if (items[i].depth > max) max = items[i].depth;
if (items[i].depth < min) min = items[i].depth;
}
printf("Compile order:\n");
for (i = min; i <= max; i++) {
if (!i) continue;
if (i < 0) printf(" [unorderable]");
else printf("%d:", i);
for (j = 0; j < n || !putchar('\n'); j++)
if (items[j].depth == i)
printf(" %s", items[j].name);
}
return 0;
}</syntaxhighlight>
{{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
1: std synopsys ieee
2: std_cell_lib ramlib dware gtech
3: dw02 dw01 dw05 dw06 dw07
4: des_system_lib dw03 dw04</syntaxhighlight>
=={{header|C sharp}}==
<syntaxhighlight lang="csharp">
namespace Algorithms
{
using System;
using System.Collections.Generic;
using System.Linq;
public class TopologicalSorter<ValueType>
{
private class Relations
{
public int Dependencies = 0;
public HashSet<ValueType> Dependents = new HashSet<ValueType>();
}
private Dictionary<ValueType, Relations> _map = new Dictionary<ValueType, Relations>();
public void Add(ValueType obj)
{
if (!_map.ContainsKey(obj)) _map.Add(obj, new Relations());
}
public void Add(ValueType obj, ValueType dependency)
{
if (dependency.Equals(obj)) return;
if (!_map.ContainsKey(dependency)) _map.Add(dependency, new Relations());
var dependents = _map[dependency].Dependents;
if (!dependents.Contains(obj))
{
dependents.Add(obj);
if (!_map.ContainsKey(obj)) _map.Add(obj, new Relations());
++_map[obj].Dependencies;
}
}
public void Add(ValueType obj, IEnumerable<ValueType> dependencies)
{
foreach (var dependency in dependencies) Add(obj, dependency);
}
public void Add(ValueType obj, params ValueType[] dependencies)
{
Add(obj, dependencies as IEnumerable<ValueType>);
}
public Tuple<IEnumerable<ValueType>, IEnumerable<ValueType>> Sort()
{
List<ValueType> sorted = new List<ValueType>(), cycled = new List<ValueType>();
var map = _map.ToDictionary(kvp => kvp.Key, kvp => kvp.Value);
sorted.AddRange(map.Where(kvp => kvp.Value.Dependencies == 0).Select(kvp => kvp.Key));
for (int idx = 0; idx < sorted.Count; ++idx) sorted.AddRange(map[sorted[idx]].Dependents.Where(k => --map[k].Dependencies == 0));
cycled.AddRange(map.Where(kvp => kvp.Value.Dependencies != 0).Select(kvp => kvp.Key));
return new Tuple<IEnumerable<ValueType>, IEnumerable<ValueType>>(sorted, cycled);
}
public void Clear()
{
_map.Clear();
}
}
}
/*
Example usage with Task object
*/
namespace ExampleApplication
{
using Algorithms;
using System;
using System.Collections.Generic;
using System.Linq;
public class Task
{
public string Message;
}
class Program
{
static void Main(string[] args)
{
List<Task> tasks = new List<Task>
{
new Task{ Message = "A - depends on B and C" }, //0
new Task{ Message = "B - depends on none" }, //1
new Task{ Message = "C - depends on D and E" }, //2
new Task{ Message = "D - depends on none" }, //3
new Task{ Message = "E - depends on F, G and H" }, //4
new Task{ Message = "F - depends on I" }, //5
new Task{ Message = "G - depends on none" }, //6
new Task{ Message = "H - depends on none" }, //7
new Task{ Message = "I - depends on none" }, //8
};
TopologicalSorter<Task> resolver = new TopologicalSorter<Task>();
// now setting relations between them as described above
resolver.Add(tasks[0], new[] { tasks[1], tasks[2] });
//resolver.Add(tasks[1]); // no need for this since the task was already mentioned as a dependency
resolver.Add(tasks[2], new[] { tasks[3], tasks[4] });
//resolver.Add(tasks[3]); // no need for this since the task was already mentioned as a dependency
resolver.Add(tasks[4], tasks[5], tasks[6], tasks[7]);
resolver.Add(tasks[5], tasks[8]);
//resolver.Add(tasks[6]); // no need for this since the task was already mentioned as a dependency
//resolver.Add(tasks[7]); // no need for this since the task was already mentioned as a dependency
//resolver.Add(tasks[3], tasks[0]); // uncomment this line to test cycled dependency
var result = resolver.Sort();
var sorted = result.Item1;
var cycled = result.Item2;
if (!cycled.Any())
{
foreach (var d in sorted) Console.WriteLine(d.Message);
}
else
{
Console.Write("Cycled dependencies detected: ");
foreach (var d in cycled) Console.Write($"{d.Message[0]} ");
Console.WriteLine();
}
Console.WriteLine("exiting...");
}
}
}
</syntaxhighlight>
{{out}}<syntaxhighlight lang="text">B - depends on none
D - depends on none
G - depends on none
H - depends on none
I - depends on none
F - depends on I
E - depends on F, G and H
C - depends on D and E
A - depends on B and C
exiting...</syntaxhighlight>
{{out}}(with cycled dependency)<syntaxhighlight lang="text">Cycled dependencies detected: A C D
exiting...</syntaxhighlight>
=={{header|C++}}==
===C++11===
<syntaxhighlight lang="cpp">#include <map>
#include <set>
template<typename Goal>
class topological_sorter {
protected:
struct relations {
std::size_t dependencies;
std::set<Goal> dependents;
};
std::map<Goal, relations> map;
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>
#include <iostream>
#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) {
if (argc == 1) {
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"
"dw06 dw06 ieee dware\n"
"dw07 ieee dware\n"
"dware ieee dware\n"
"gtech ieee gtech\n"
"ramlib std ieee\n"
"std_cell_lib ieee std_cell_lib\n"
"synopsys\n"
"cycle_11 cycle_12\n"
"cycle_12 cycle_11\n"
"cycle_21 dw01 cycle_22 dw02 dw03\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>
===C++17===
<syntaxhighlight lang="cpp">#include <unordered_map>
#include <unordered_set>
#include <vector>
template <typename ValueType>
class topological_sorter
{
public:
using value_type = ValueType;
protected:
struct relations
{
std::size_t dependencies { 0 };
std::unordered_set<value_type> dependents {};
};
std::unordered_map<value_type, relations> _map {};
public:
void add(const value_type &object)
{
_map.try_emplace(object, relations {});
}
void add(const value_type &object, const value_type &dependency)
{
if (dependency == object) return;
auto &dependents = _map[dependency].dependents;
if (dependents.find(object) == std::end(dependents))
{
dependents.insert(object);
++_map[object].dependencies;
}
}
template <typename Container>
void add(const value_type &object, const Container &dependencies)
{
for (auto const &dependency : dependencies) add(object, dependency);
}
void add(const value_type &object, const std::initializer_list<value_type> &dependencies)
{
add<std::initializer_list<value_type>>(object, dependencies);
}
template<typename... Args>
void add(const value_type &object, const Args&... dependencies)
{
(add(object, dependencies), ...);
}
auto sort()
{
std::vector<value_type> sorted, cycled;
auto map { _map };
for (const auto &[object, relations] : map) if (!relations.dependencies) sorted.emplace_back(object);
for (decltype(std::size(sorted)) idx = 0; idx < std::size(sorted); ++idx)
for (auto const& object : map[sorted[idx]].dependents)
if (!--map[object].dependencies) sorted.emplace_back(object);
for (const auto &[object, relations] : map) if (relations.dependencies) cycled.emplace_back(std::move(object));
return std::pair(std::move(sorted), std::move(cycled));
}
void clear()
{
_map.clear();
}
};
/*
Example usage with shared_ptr to class
*/
#include <iostream>
#include <memory>
int main()
{
using namespace std::string_literals;
struct task
{
std::string message;
task(const std::string &v) : message { v } {}
~task() { std::cout << message[0] << " - destroyed" << std::endl; }
};
using task_ptr = std::shared_ptr<task>;
std::vector<task_ptr> tasks
{
// defining simple tasks
std::make_shared<task>("A - depends on B and C"s), //0
std::make_shared<task>("B - depends on none"s), //1
std::make_shared<task>("C - depends on D and E"s), //2
std::make_shared<task>("D - depends on none"s), //3
std::make_shared<task>("E - depends on F, G and H"s), //4
std::make_shared<task>("F - depends on I"s), //5
std::make_shared<task>("G - depends on none"s), //6
std::make_shared<task>("H - depends on none"s), //7
std::make_shared<task>("I - depends on none"s), //8
};
topological_sorter<task_ptr> resolver;
// now setting relations between them as described above
resolver.add(tasks[0], { tasks[1], tasks[2] });
//resolver.add(tasks[1]); // no need for this since the task was already mentioned as a dependency
resolver.add(tasks[2], { tasks[3], tasks[4] });
//resolver.add(tasks[3]); // no need for this since the task was already mentioned as a dependency
resolver.add(tasks[4], tasks[5], tasks[6], tasks[7]); // using templated add with fold expression
resolver.add(tasks[5], tasks[8]);
//resolver.add(tasks[6]); // no need for this since the task was already mentioned as a dependency
//resolver.add(tasks[7]); // no need for this since the task was already mentioned as a dependency
//resolver.add(tasks[3], tasks[0]); // uncomment this line to test cycled dependency
const auto &[sorted, cycled] = resolver.sort();
if (std::empty(cycled))
{
for (auto const& d: sorted)
std::cout << d->message << std::endl;
}
else
{
std::cout << "Cycled dependencies detected: ";
for (auto const& d: cycled)
std::cout << d->message[0] << " ";
std::cout << std::endl;
}
//tasks.clear(); // uncomment this line to destroy all tasks in sorted order.
std::cout << "exiting..." << std::endl;
return 0;
}</syntaxhighlight>
{{out}}<syntaxhighlight lang="text">I - depends on none
H - depends on none
G - depends on none
D - depends on none
B - depends on none
F - depends on I
E - depends on F, G and H
C - depends on D and E
A - depends on B and C
exiting...
A - destroyed
B - destroyed
C - destroyed
D - destroyed
E - destroyed
F - destroyed
G - destroyed
H - destroyed
I - destroyed</syntaxhighlight>
{{out}}(with cycled dependency)<syntaxhighlight lang="text">Cycled dependencies detected: A D C
exiting...
A - destroyed
B - destroyed
C - destroyed
D - destroyed
E - destroyed
F - destroyed
G - destroyed
H - destroyed
I - destroyed</syntaxhighlight>
=={{header|Clojure}}==
Line 41 ⟶ 1,905:
=====Implementation=====
<
(use 'clojure.contrib.seq-utils)
Line 113 ⟶ 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 136 ⟶ 2,000:
(def bad-sample
(concat cyclic-dependence good-sample))</
=====
<
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}}==
<syntaxhighlight lang="coffeescript">
toposort = (targets) ->
# targets is hash of sets, where keys are parent nodes and
# where values are sets that contain nodes that must precede the parent
# Start by identifying obviously independent nodes
independents = []
do ->
for k of targets
if targets[k].cnt == 0
delete targets[k]
independents.push k
# Note reverse dependencies for theoretical O(M+N) efficiency.
reverse_deps = []
do ->
for k of targets
for child of targets[k].v
reverse_deps[child] ?= []
reverse_deps[child].push k
# Now be greedy--start with independent nodes, then start
# breaking dependencies, and keep going as long as we still
# have independent nodes left.
result = []
while independents.length > 0
k = independents.pop()
result.push k
for parent in reverse_deps[k] or []
set_remove targets[parent], k
if targets[parent].cnt == 0
independents.push parent
delete targets[parent]
# Show unresolvable dependencies
for k of targets
console.log "WARNING: node #{k} is part of cyclical dependency"
result
parse_deps = ->
# parse string data, remove self-deps, and fill in gaps
#
# e.g. this would transform {a: "a b c", d: "e"} to this:
# a: set(b, c)
# b: set()
# c: set()
# d: set(e)
# e: set()
targets = {}
deps = set()
for k, v of data
targets[k] = set()
children = v.split(' ')
for child in children
continue if child == ''
set_add targets[k], child unless child == k
set_add deps, child
# make sure even leaf nodes are in targets
for dep of deps.v
if dep not of targets
targets[dep] = set()
targets
set = ->
cnt: 0
v: {}
set_add = (s, e) ->
return if s.v[e]
s.cnt += 1
s.v[e] = true
set_remove = (s, e) ->
return if !s.v[e]
s.cnt -= 1
delete s.v[e]
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: ""
targets = parse_deps()
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 194 ⟶ 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 217 ⟶ 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 248 ⟶ 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}}
<syntaxhighlight lang="d">import std.stdio, std.string, std.algorithm, std.range;
final class ArgumentException : Exception {
this(string text) pure nothrow @safe /*@nogc*/ {
super(text);
}
}
alias TDependencies = string[][string];
string[][] topoSort(TDependencies d) pure /*nothrow @safe*/ {
foreach (immutable k, v; d)
d[k] = v.sort().uniq.filter!(s => s != k).array;
foreach (immutable s; d.byValue.join.sort().uniq)
if (s !in d)
d[s] = [];
string[][] sorted;
while (true) {
string[] ordered;
foreach (immutable item, const dep; d)
if (dep.empty)
ordered ~= item;
if (!ordered.empty)
sorted ~= ordered.sort().release;
else
break;
TDependencies dd;
foreach (immutable item, const dep; d)
if (!ordered.canFind(item))
dd[item] = dep.dup.filter!(s => !ordered.canFind(s)).array;
d = dd;
}
//if (!d.empty)
if (d.length > 0)
throw new ArgumentException(format(
"A cyclic dependency exists amongst:\n%s", d));
return sorted;
}
void main() {
immutable 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";
TDependencies deps;
foreach (immutable line; data.splitLines)
deps[line.split[0]] = line.split[1 .. $];
auto depw = deps.dup;
foreach (immutable idx, const subOrder; depw.topoSort)
writefln("#%d : %s", idx + 1, subOrder);
writeln;
depw = deps.dup;
depw["dw01"] ~= "dw04";
foreach (const subOrder; depw.topoSort) // Should throw.
subOrder.writeln;
}</syntaxhighlight>
{{out}}
<pre>#1 : ["ieee", "std", "synopsys"]
#2 : ["dware", "gtech", "ramlib", "std_cell_lib"]
#3 : ["dw01", "dw02", "dw05", "dw06", "dw07"]
#4 : ["des_system_lib", "dw03", "dw04"]
topo.ArgumentException@topo.d(7): A cyclic dependency exists amongst:
[dw01:[dw04],des_system_lib:[dw01],dw03:[dw01],dw04:[dw01]]
----------------
...\topo.d(71): _Dmain
----------------</pre>
=={{header|E}}==
<
def topoSort(data :Map[any, Set[any]]) {
Line 300 ⟶ 2,435:
return result
}</
<
def dataText := "\
Line 322 ⟶ 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}}
<code>["std", "synopsys", "ieee", "dware", "gtech", "ramlib", "std_cell_lib", "dw02", "dw05", "dw06", "dw07", "dw01", "des_system_lib", "dw03", "dw04"]</code>
=={{header|EchoLisp}}==
We use the low-level primitives of the 'graph' library to build the directed graph and implement the topological sort.
''' Data
<syntaxhighlight lang="lisp">
(define dependencies
'((des_system_lib std synopsys std_cell_lib des_system_lib dw02 dw01 ramlib ieee)
(dw01 ieee dw01 dware gtech) ;; bad graph add dw04
(dw02 ieee dw02 dware )
(dw03 std synopsys dware dw03 dw02 dw01 ieee gtech)
(dw04 dw04 ieee dw01 dware gtech)
(dw05 dw05 ieee dware)
(dw06 dw06 ieee dware)
(dw07 ieee dware)
(dware ieee dware)
(gtech ieee gtech)
(ramlib std ieee )
(std_cell_lib ieee std_cell_lib)
(synopsys )))
;; build dependency graph
;; a depends on b
;; add arc (arrow) a --> b
(lib 'graph.lib)
(define (a->b g a b)
(unless (equal? a b)
(graph-make-arc g (graph-make-vertex g a) (graph-make-vertex g b))))
(define (add-dependencies g dep-list)
(for* ((dep dep-list) (b (rest dep))) (a->b g b (first dep))))
</syntaxhighlight>
'''Implementation
Remove all vertices with in-degree = 0, until to one left. (in-degree = number of arrows to a vertex)
<syntaxhighlight lang="lisp">
;; topological sort
;;
;; Complexity O (# of vertices + # of edges)
(define (t-sort g)
(stack 'Z) ; vertices of d°(0)
(stack 'S) ; ordered result
;; mark all vertices with their in-degree = # of incoming arcs
;; push all vertices u such as d°(u) = 0
(for ((u g)) (mark u (graph-vertex-indegree g u))
(when (zero? (mark? u)) (push 'Z u)))
;pop a d°(0) vertex u - add it to result
;decrement in-degree of all v vertices u->v
; if d°(v) = 0, push it
(while (not (stack-empty? 'Z))
(let (( u (pop 'Z)))
(push 'S u)
(for ((v (graph-vertex-out g u)))
(mark v (1- (mark? v)))
(when (zero? (mark? v)) (push 'Z v)))))
;; finish
(writeln 't-sort (map vertex-label (stack->list 'S)))
;; check no one remaining
(for ((u g))
(unless (zero? (mark? u))
(error " ♻️ t-sort:cyclic" (map vertex-label (graph-cycle g))))))
</syntaxhighlight>
{{Out}}
<syntaxhighlight lang="lisp">
(define g (make-graph "VHDL"))
(add-dependencies g dependencies)
(graph-print g)
(t-sort g)
→ t-sort (std synopsys ieee dware dw02 dw05 dw06 dw07 gtech dw01 dw03 dw04 ramlib
std_cell_lib des_system_lib)
;; Error case
;; add dw01 -> dw04
(t-sort g)
t-sort (std synopsys ieee dware dw02 dw05 dw06 dw07 gtech ramlib std_cell_lib)
⛔️ error: ♻️ t-sort:cyclic (dw04 dw01)
</syntaxhighlight>
=={{header|Elixir}}==
{{trans|Erlang}}
<syntaxhighlight lang="elixir">defmodule Topological do
def sort(library) do
g = :digraph.new
Enum.each(library, fn {l,deps} ->
:digraph.add_vertex(g,l) # noop if library already added
Enum.each(deps, fn d -> add_dependency(g,l,d) end)
end)
if t = :digraph_utils.topsort(g) do
print_path(t)
else
IO.puts "Unsortable contains circular dependencies:"
Enum.each(:digraph.vertices(g), fn v ->
if vs = :digraph.get_short_cycle(g,v), do: print_path(vs)
end)
end
end
defp print_path(l), do: IO.puts Enum.join(l, " -> ")
defp add_dependency(_g,l,l), do: :ok
defp add_dependency(g,l,d) do
:digraph.add_vertex(g,d) # noop if dependency already added
:digraph.add_edge(g,d,l) # Dependencies represented as an edge d -> l
end
end
libraries = [
des_system_lib: ~w[std synopsys std_cell_lib des_system_lib dw02 dw01 ramlib ieee]a,
dw01: ~w[ieee dw01 dware gtech]a,
dw02: ~w[ieee dw02 dware]a,
dw03: ~w[std synopsys dware dw03 dw02 dw01 ieee gtech]a,
dw04: ~w[dw04 ieee dw01 dware gtech]a,
dw05: ~w[dw05 ieee dware]a,
dw06: ~w[dw06 ieee dware]a,
dw07: ~w[ieee dware]a,
dware: ~w[ieee dware]a,
gtech: ~w[ieee gtech]a,
ramlib: ~w[std ieee]a,
std_cell_lib: ~w[ieee std_cell_lib]a,
synopsys: []
]
Topological.sort(libraries)
IO.puts ""
bad_libraries = Keyword.update!(libraries, :dw01, &[:dw04 | &1])
Topological.sort(bad_libraries)</syntaxhighlight>
{{out}}
<pre>
std -> synopsys -> ieee -> dware -> dw02 -> dw05 -> gtech -> dw01 -> dw03 -> dw04 -> ramlib -> std_cell_lib -> des_system_lib -> dw06 -> dw07
Unsortable contains circular dependencies:
dw04 -> dw01 -> dw04
dw01 -> dw04 -> dw01
</pre>
=={{header|Erlang}}==
<syntaxhighlight lang="erlang">
-module(topological_sort).
-compile(export_all).
-define(LIBRARIES,
[{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, []}]).
-define(BAD_LIBRARIES,
[{des_system_lib, [std, synopsys, std_cell_lib, des_system_lib, dw02, dw01, ramlib, ieee]},
{dw01, [ieee, dw01, dw04, 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, []}]).
main() ->
top_sort(?LIBRARIES),
top_sort(?BAD_LIBRARIES).
top_sort(Library) ->
G = digraph:new(),
lists:foreach(fun ({L,Deps}) ->
digraph:add_vertex(G,L), % noop if library already added
lists:foreach(fun (D) ->
add_dependency(G,L,D)
end, Deps)
end, Library),
T = digraph_utils:topsort(G),
case T of
false ->
io:format("Unsortable contains circular dependencies:~n",[]),
lists:foreach(fun (V) ->
case digraph:get_short_cycle(G,V) of
false ->
ok;
Vs ->
print_path(Vs)
end
end, digraph:vertices(G));
_ ->
print_path(T)
end.
print_path(L) ->
lists:foreach(fun (V) -> io:format("~s -> ",[V]) end,
lists:sublist(L,length(L)-1)),
io:format("~s~n",[lists:last(L)]).
add_dependency(_G,_L,_L) ->
ok;
add_dependency(G,L,D) ->
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}}
<syntaxhighlight 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
Unsortable contains circular dependencies:
dw04 -> dw01 -> dw04
dw01 -> dw04 -> dw01
ok</syntaxhighlight>
Erlang has a built in digraph library and datastructure. ''digraph_utils'' contains the ''top_sort'' function which provides a topological sort of the vertices or returns false if it's not possible (due to circular references).
The ''digraph'' module contains ''get_short_cycle'' which returns the shortest cycle involving a vertex.
=={{header|Forth}}==
Provides syntactical sugar for inputting the data in a way similar to the way given in the task description.
Implementation: Each node (with dependencies) goes through three
states: At the start, it contains an execution token (xt, similar to a function pointer) that calls all before-nodes.
At the start of that, the xt called by the node changes to
PROCESSING; if that is ever called, there is a cycle (or
self-reference), and if it is not a self-reference, the cycle is
printed. When the processing of the before-nodes is complete, the
present node is printed, and the xt changes to DROP, so any further
processing of the node does nothing.
This implements depth-first search with PROCESSING being the temporary mark, and DROP being the permanent
mark.
The cool thing about this implementation is that we don't need a
single conditional branch for topologically sorting the dependencies
of a single node; there are a few for deciding what to output on a
cycle, but if we are happy with more primitive output, we can get rid
of that; we do have EXECUTE instead, so we don't get rid of branch
mispredictions, but given our representation of the dependencies, we
need the indirect branch anyway.
A Forth-specific (although unidiomatic) feature is that we can recognize self-references and print
cycles without building an extra data structure, because the chain
of nodes we are looking at is on the data stack.
Another Forth feature is that we use the dictionary as symbol table
for input processing: Each node is turned into a Forth word. Also,
the list of dependencies is turned into an anonymous colon
definition rather than some list or array.
This code uses a number of Gforth extensions, some just as minor
conveniences, some more substantial (although nothing that could not
be replaced with a few lines of standard code).
{{works with|Gforth}}
<syntaxhighlight lang="forth">variable nodes 0 nodes ! \ linked list of nodes
: node. ( body -- )
body> >name name>string type ;
: nodeps ( body -- )
\ the word referenced by body has no (more) dependencies to resolve
['] drop over ! node. space ;
: processing ( body1 ... bodyn body -- body1 ... bodyn )
\ the word referenced by body is in the middle of resolving dependencies
2dup <> if \ unless it is a self-reference (see task description)
['] drop over !
." (cycle: " dup node. >r 1 begin \ print the cycle
dup pick dup r@ <> while
space node. 1+ repeat
." ) " 2drop r>
then drop ;
: >processing ( body -- body )
['] processing over ! ;
: node ( "name" -- )
\ define node "name" and initialize it to having no dependences
create
['] nodeps , \ on definition, a node has no dependencies
nodes @ , lastxt nodes ! \ linked list of nodes
does> ( -- )
dup @ execute ; \ perform xt associated with node
: define-nodes ( "names" <newline> -- )
\ define all the names that don't exist yet as nodes
begin
parse-name dup while
2dup find-name 0= if
2dup nextname node then
2drop repeat
2drop ;
: deps ( "name" "deps" <newline> -- )
\ name is after deps. Implementation: Define missing nodes, then
\ define a colon definition for
>in @ define-nodes >in !
' :noname ]] >processing [[ source >in @ /string evaluate ]] nodeps ; [[
swap >body ! 0 parse 2drop ;
: all-nodes ( -- )
\ call all nodes, and they then print their dependences and themselves
nodes begin
@ dup while
dup execute
>body cell+ repeat
drop ;
deps des_system_lib std synopsys std_cell_lib des_system_lib dw02 dw01 ramlib ieee
deps dw01 ieee dw01 dware gtech
deps dw02 ieee dw02 dware
deps dw03 std synopsys dware dw03 dw02 dw01 ieee gtech
deps dw04 dw04 ieee dw01 dware gtech
deps dw05 dw05 ieee dware
deps dw06 dw06 ieee dware
deps dw07 ieee dware
deps dware ieee dware
deps gtech ieee gtech
deps ramlib std ieee
deps std_cell_lib ieee std_cell_lib
deps synopsys
\ to test the cycle recognition (overwrites dependences for dw1 above)
deps dw01 ieee dw01 dware gtech dw04
all-nodes</syntaxhighlight>
{{out}}
<pre>ieee dware dw07 dw06 dw05 gtech (cycle: dw04 dw01) dw01 dw04 std synopsys dw02 dw03 ramlib std_cell_lib des_system_lib</pre>
=={{header|Fortran}}==
===FORTRAN 77===
Main routine for topological sort.
''Input'' : IDEP is an array ND x 2 of dependencies, with IDEP(I,1) depending on IDEP(I,2).
NL is the number of libraries to sort, ND the number of dependencies, one for each pair of ordered libraries.
Array IPOS is used internally by the routine, to maintain a list of positions of libraries in IORD.
''Output'' : IORD(1:NO) is the compile order, and IORD(NO+1:NL) contains unordered libraries.
This implementation is not optimal: for each ''level'' of dependency (for example A -> B -> C counts as three levels), there is a loop through all dependencies in IDEP.
It would be possible to optimize a bit, without changing the main idea, by first sorting IDEP according to first column, and using more temporary space, keeping track of where is located data in IDEP for each library (all dependencies of a same library being grouped).
<syntaxhighlight 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
DO 10 I=1,NL
IORD(I)=I
10 IPOS(I)=I
K=1
20 J=K
K=NL+1
DO 30 I=1,ND
IL=IDEP(I,1)
IR=IDEP(I,2)
IPL=IPOS(IL)
IPR=IPOS(IR)
IF(IL.EQ.IR .OR. IPL.GE.K .OR. IPL.LT.J .OR. IPR.LT.J) GO TO 30
K=K-1
IPOS(IORD(K))=IPL
IPOS(IL)=K
IORD(IPL)=IORD(K)
IORD(K)=IL
30 CONTINUE
IF(K.GT.J) GO TO 20
NO=J-1
END</syntaxhighlight>
An example. Dependencies are encoded to make program shorter (in array ICODE).
<syntaxhighlight lang="fortran"> PROGRAM EX_TSORT
IMPLICIT NONE
INTEGER NL,ND,NC,NO,IDEP,IORD,IPOS,ICODE,I,J,IL,IR
PARAMETER(NL=15,ND=44,NC=69)
CHARACTER*(20) LABEL
DIMENSION IDEP(ND,2),LABEL(NL),IORD(NL),IPOS(NL),ICODE(NC)
DATA LABEL/'DES_SYSTEM_LIB','DW01','DW02','DW03','DW04','DW05',
1 'DW06','DW07','DWARE','GTECH','RAMLIB','STD_CELL_LIB','SYNOPSYS',
2 'STD','IEEE'/
DATA ICODE/1,14,13,12,1,3,2,11,15,0,2,15,2,9,10,0,3,15,3,9,0,4,14,
213,9,4,3,2,15,10,0,5,5,15,2,9,10,0,6,6,15,9,0,7,7,15,9,0,8,15,9,0,
39,15,9,0,10,15,10,0,11,14,15,0,12,15,12,0,0/
C DECODE DEPENDENCIES AND BUILD IDEP ARRAY
I=0
J=0
10 I=I+1
IL=ICODE(I)
IF(IL.EQ.0) GO TO 30
20 I=I+1
IR=ICODE(I)
IF(IR.EQ.0) GO TO 10
J=J+1
IDEP(J,1)=IL
IDEP(J,2)=IR
GO TO 20
30 CONTINUE
C SORT LIBRARIES ACCORDING TO DEPENDENCIES (TOPOLOGICAL SORT)
CALL TSORT(NL,ND,IDEP,IORD,IPOS,NO)
PRINT*,'COMPILE ORDER'
DO 40 I=1,NO
40 PRINT*,LABEL(IORD(I))
PRINT*,'UNORDERED LIBRARIES'
DO 50 I=NO+1,NL
50 PRINT*,LABEL(IORD(I))
END</syntaxhighlight>
{{out}}
<pre>
COMPILE ORDER
IEEE
STD
SYNOPSYS
STD_CELL_LIB
RAMLIB
GTECH
DWARE
DW07
DW06
DW05
DW02
DW01
DW04
DW03
DES_SYSTEM_LIB
UNORDERED LIBRARIES
</pre>
{{out}} with alternate input (DW01 depends also on DW04):
<pre>
COMPILE ORDER
IEEE
STD
SYNOPSYS
STD_CELL_LIB
RAMLIB
GTECH
DWARE
DW07
DW06
DW05
DW02
UNORDERED LIBRARIES
DW04
DW03
DW01
DES_SYSTEM_LIB
</pre>
===Modern Fortran===
A modern Fortran (95-2008) version of the TSORT subroutine is shown here (note that the IPOS array is not an input).
<syntaxhighlight lang="fortran">subroutine tsort(nl,nd,idep,iord,no)
implicit none
integer,intent(in) :: nl
integer,intent(in) :: nd
integer,dimension(nd,2),intent(in) :: idep
integer,dimension(nl),intent(out) :: iord
integer,intent(out) :: no
integer :: i,j,k,il,ir,ipl,ipr,ipos(nl)
do i=1,nl
iord(i)=i
ipos(i)=i
end do
k=1
do
j=k
k=nl+1
do i=1,nd
il=idep(i,1)
ir=idep(i,2)
ipl=ipos(il)
ipr=ipos(ir)
if (il==ir .or. ipl>=k .or. ipl<j .or. ipr<j) cycle
k=k-1
ipos(iord(k))=ipl
ipos(il)=k
iord(ipl)=iord(k)
iord(k)=il
end do
if (k<=j) exit
end do
no=j-1
end subroutine tsort
</syntaxhighlight>
=={{header|FunL}}==
<syntaxhighlight lang="funl">def topsort( graph ) =
val L = seq()
val S = seq()
val g = dict( graph )
for (v, es) <- g
g(v) = seq( es )
for (v, es) <- g if es.isEmpty()
S.append( v )
while not S.isEmpty()
val n = S.remove( 0 )
L.append( n )
for (m, es) <- g if n in es
if (es -= n).isEmpty()
S.append( m )
for (v, es) <- g
if not es.isEmpty()
return None
Some( L.toList() )
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
'''
// convert dependencies data into a directed graph
graph = dict()
deps = set()
for l <- WrappedString( dependencies ).lines() if l.trim() != ''
case list(l.trim().split('\\s+')) of
[a] -> graph(a) = []
h:t ->
d = set( t )
d -= h // remove self dependencies
graph(h) = d
deps ++= t
// add graph vertices for dependencies not appearing in left column
for e <- deps if e not in graph
graph(e) = []
case topsort( graph ) of
None -> println( 'un-orderable' )
Some( ordering ) -> println( ordering )</syntaxhighlight>
{{out}}
<pre>
[synopsys, ieee, std, dware, std_cell_lib, gtech, ramlib, dw06, dw05, dw02, dw07, dw01, dw03, dw04, des_system_lib]
</pre>
=={{header|Go}}==
===Kahn===
<syntaxhighlight lang="go">package main
import (
"fmt"
"strings"
)
var data = `
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 `
func main() {
g, in, err := parseLibComp(data)
if err != nil {
fmt.Println(err)
return
}
order, cyclic := topSortKahn(g, in)
if cyclic != nil {
fmt.Println("Cyclic:", cyclic)
return
}
fmt.Println("Order:", order)
}
type graph map[string][]string
type inDegree map[string]int
// parseLibComp parses the text format of the task and returns a graph
// representation and a list of the in-degrees of each node. The returned graph
// represents compile order rather than dependency order. That is, for each map
// map key n, the map elements are libraries that depend on n being compiled
// first.
func parseLibComp(data string) (g graph, in inDegree, err error) {
// small sanity check on input
lines := strings.Split(data, "\n")
if len(lines) < 3 || !strings.HasPrefix(lines[2], "=") {
return nil, nil, fmt.Errorf("data format")
}
// toss header lines
lines = lines[3:]
// scan and interpret input, build graph
g = graph{}
in = inDegree{}
for _, line := range lines {
libs := strings.Fields(line)
if len(libs) == 0 {
continue // allow blank lines
}
lib := libs[0]
g[lib] = g[lib]
for _, dep := range libs[1:] {
in[dep] = in[dep]
if dep == lib {
continue // ignore self dependencies
}
successors := g[dep]
for i := 0; ; i++ {
if i == len(successors) {
g[dep] = append(successors, lib)
in[lib]++
break
}
if dep == successors[i] {
break // ignore duplicate dependencies
}
}
}
}
return g, in, nil
}
// General purpose topological sort, not specific to the application of
// library dependencies. Adapted from Wikipedia pseudo code, one main
// difference here is that this function does not consume the input graph.
// WP refers to incoming edges, but does not really need them fully represented.
// A count of incoming edges, or the in-degree of each node is enough. Also,
// WP stops at cycle detection and doesn't output information about the cycle.
// A little extra code at the end of this function recovers the cyclic nodes.
func topSortKahn(g graph, in inDegree) (order, cyclic []string) {
var L, S []string
// rem for "remaining edges," this function makes a local copy of the
// in-degrees and consumes that instead of consuming an input.
rem := inDegree{}
for n, d := range in {
if d == 0 {
// accumulate "set of all nodes with no incoming edges"
S = append(S, n)
} else {
// initialize rem from in-degree
rem[n] = d
}
}
for len(S) > 0 {
last := len(S) - 1 // "remove a node n from S"
n := S[last]
S = S[:last]
L = append(L, n) // "add n to tail of L"
for _, m := range g[n] {
// WP pseudo code reads "for each node m..." but it means for each
// node m *remaining in the graph.* We consume rem rather than
// the graph, so "remaining in the graph" for us means rem[m] > 0.
if rem[m] > 0 {
rem[m]-- // "remove edge from the graph"
if rem[m] == 0 { // if "m has no other incoming edges"
S = append(S, m) // "insert m into S"
}
}
}
}
// "If graph has edges," for us means a value in rem is > 0.
for c, in := range rem {
if in > 0 {
// recover cyclic nodes
for _, nb := range g[c] {
if rem[nb] > 0 {
cyclic = append(cyclic, c)
break
}
}
}
}
if len(cyclic) > 0 {
return nil, cyclic
}
return L, nil
}</syntaxhighlight>
{{out}}
<pre>
Order: [std ieee std_cell_lib ramlib gtech dware dw07 dw06 dw05 dw02 dw01 dw04 synopsys dw03 des_system_lib]
</pre>
Cycle detection demonstrated with the example in the task description:
<pre>
Cyclic: [dw01 dw04]
</pre>
===Depth First===
Topological sort only, this function can replace topSortKahn in above program. The
in-degree list is not needed.
<syntaxhighlight 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) {
L := make([]string, len(g))
i := len(L)
temp := map[string]bool{}
perm := map[string]bool{}
var cycleFound bool
var cycleStart string
var visit func(string)
visit = func(n string) {
switch {
case temp[n]:
cycleFound = true
cycleStart = n
return
case perm[n]:
return
}
temp[n] = true
for _, m := range g[n] {
visit(m)
if cycleFound {
if cycleStart > "" {
cyclic = append(cyclic, n)
if n == cycleStart {
cycleStart = ""
}
}
return
}
}
delete(temp, n)
perm[n] = true
i--
L[i] = n
}
for n := range g {
if perm[n] {
continue
}
visit(n)
if cycleFound {
return nil, cyclic
}
}
return L, nil
}</syntaxhighlight>
{{out}}
(when used in program of Kahn example.)
<pre>
Order: [ieee gtech synopsys dware dw07 dw06 dw02 dw01 dw04 std_cell_lib dw05 std ramlib dw03 des_system_lib]
</pre>
And with the cycle added,
<pre>
Cyclic: [dw04 dw01]
</pre>
=={{header|Haskell}}==
<
import Data.
combs 0 _ = [[]]
combs _ [] = []
combs k (x:xs) =
depLibs :: [(String, String)]
depLibs =
[ ( "des_system_lib"
, "std synopsys std_cell_lib des_system_lib
, ("dw03", "std synopsys dware dw03 dw02
, ("std_cell_lib", "ieee std_cell_lib")
, ("synopsys", [])
]
toposort :: [(String, String)] -> [String]
toposort xs
error $ "Dependency cycle detected for libs " ++ show cycleDetect
| otherwise = foldl makePrecede [] dB
where
dB = (\(x, y) -> (x, y \\ x)) . bimap return words <$> xs
makePrecede ts ([x], xs) =
nub $
case elemIndex x ts of
Just i -> uncurry (++) $ first (++ xs) $ splitAt i ts
_ -> ts ++ xs ++ [x]
cycleDetect =
filter ((> 1) . length) $
(\[(a, as), (b, bs)] -> (a `intersect` bs) ++ (b `intersect` as)) <$>
combs 2 dB
main :: IO ()
main = print $ toposort depLibs</syntaxhighlight>
{{out}}
<syntaxhighlight 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"]]</
=={{header|Huginn}}==
<syntaxhighlight lang="huginn">import Algorithms as algo;
import Text as text;
class DirectedGraph {
_adjecentVertices = {};
add_vertex( vertex_ ) {
_adjecentVertices[vertex_] = [];
}
add_edge( from_, to_ ) {
_adjecentVertices[from_].push( to_ );
}
adjecent_vertices( vertex_ ) {
return ( vertex_ ∈ _adjecentVertices ? _adjecentVertices.get( vertex_ ) : [] );
}
}
class DepthFirstSearch {
_visited = set();
_postOrder = [];
_cycleDetector = set();
run( graph_, start_ ) {
_cycleDetector.insert( start_ );
_visited.insert( start_ );
for ( vertex : graph_.adjecent_vertices( start_ ) ) {
if ( vertex == start_ ) {
continue;
}
if ( vertex ∈ _cycleDetector ) {
throw Exception( "A cycle involving vertices {} found!".format( _cycleDetector ) );
}
if ( vertex ∉ _visited ) {
run( graph_, vertex );
}
}
_postOrder.push( start_ );
_cycleDetector.erase( start_ );
}
topological_sort( graph_ ) {
for ( vertex : graph_._adjecentVertices ) {
if ( vertex ∉ _visited ) {
run( graph_, vertex );
}
}
return ( _postOrder );
}
}
main() {
rawdata =
"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"
"dw06 | dw06 ieee dware\n"
"dw07 | ieee dware\n"
"dware | ieee dware\n"
"gtech | ieee gtech\n"
"ramlib | std ieee\n"
"std_cell_lib | ieee std_cell_lib\n"
"synopsys |\n";
dg = DirectedGraph();
for ( l : algo.filter( text.split( rawdata, "\n" ), @( x ) { size( x ) > 0; } ) ) {
def = algo.materialize( algo.map( text.split( l, "|" ), string.strip ), list );
dg.add_vertex( def[0] );
for ( n : algo.filter( algo.map( text.split( def[1], " " ), string.strip ), @( x ) { size( x ) > 0; } ) ) {
dg.add_edge( def[0], n );
}
}
dfs = DepthFirstSearch();
print( "{}\n".format( dfs.topological_sort( dg ) ) );
}</syntaxhighlight>
==Icon and Unicon==
Line 384 ⟶ 3,382:
elements have been built.
<
global ex_name, in_name
Line 498 ⟶ 3,496:
g.arcs ? while arc := move(2) do if arc[1] == f then t ++:= arc[2]
return t
end</
{{out}}
<pre>->tsort <tsort.data
Line 526 ⟶ 3,523:
in parallel once the elements in the preceding lines have been built.
<
procedure main()
Line 612 ⟶ 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 623 ⟶ 3,622:
assert.-.1 e. (<0 1)|:depends
(-.&names ~.;parsed),names /: +/"1 depends
)</
With the sample data set:
Line 645 ⟶ 3,644:
We would get:
<syntaxhighlight lang="j"> >dependencySort dependencies
std
ieee
Line 660 ⟶ 3,659:
dw04
dw03
des_system_lib</syntaxhighlight>
If we tried to also make dw01 depend on dw04, the sort would fail because of the circular dependency:
<syntaxhighlight lang="j"> dependencySort dependencies,'dw01 dw04',LF
|assertion failure: dependencySort
| -.1 e.(<0 1)|:depends</syntaxhighlight>
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):
<syntaxhighlight lang="j">depSort=: monad define
parsed=. <@;:;._2 y
names=. {.&>parsed
Line 671 ⟶ 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.
=={{header|Java}}==
{{works with|Java|7}}
<syntaxhighlight lang="java">import java.util.*;
public class TopologicalSort {
public static void main(String[] args) {
String s = "std, ieee, des_system_lib, dw01, dw02, dw03, dw04, dw05,"
+ "dw06, dw07, dware, gtech, ramlib, std_cell_lib, synopsys";
Graph g = new Graph(s, new int[][]{
{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}
});
System.out.println("Topologically sorted order: ");
System.out.println(g.topoSort());
}
}
class Graph {
String[] vertices;
boolean[][] adjacency;
int numVertices;
public Graph(String s, int[][] edges) {
vertices = s.split(",");
numVertices = vertices.length;
adjacency = new boolean[numVertices][numVertices];
for (int[] edge : edges)
adjacency[edge[0]][edge[1]] = true;
}
List<String> topoSort() {
List<String> result = new ArrayList<>();
List<Integer> todo = new LinkedList<>();
for (int i = 0; i < numVertices; i++)
todo.add(i);
try {
outer:
while (!todo.isEmpty()) {
for (Integer r : todo) {
if (!hasDependency(r, todo)) {
todo.remove(r);
result.add(vertices[r]);
// no need to worry about concurrent modification
continue outer;
}
}
throw new Exception("Graph has cycles");
}
} catch (Exception e) {
System.out.println(e);
return null;
}
return result;
}
boolean hasDependency(Integer r, List<Integer> todo) {
for (Integer c : todo) {
if (adjacency[r][c])
return true;
}
return false;
}
}</syntaxhighlight>
<pre>[std, ieee, dware, dw02, dw05, dw06, dw07, gtech, dw01, dw04, ramlib, std_cell_lib, synopsys, des_system_lib, dw03]</pre>
=={{header|JavaScript}}==
====ES6====
<syntaxhighlight lang="javascript">const 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`;
// A map of the input data, with the keys as the packages, and the values as
// and array of packages on which it depends.
const D = libs
.split('\n')
.map(e => e.split(' ').filter(e => e != ''))
.reduce((p, c) =>
p.set(c[0], c.filter((e, i) => i > 0 && e !== c[0] ? e : null)), new Map());
[].concat(...D.values()).forEach(e => {
D.set(e, D.get(e) || [])
});
// The above map rotated so that it represents a DAG of the form
// Map {
// A => [ A, B, C],
// B => [C],
// C => []
// }
// where each key represents a node, and the array contains the edges.
const G = [...D.keys()].reduce((p, c) =>
p.set(
c,
[...D.keys()].filter(e => D.get(e).includes(c))),
new Map()
);
// An array of leaf nodes; nodes with 0 in degrees.
const Q = [...D.keys()].filter(e => D.get(e).length == 0);
// The result array.
const S = [];
while (Q.length) {
const u = Q.pop();
S.push(u);
G.get(u).forEach(v => {
D.set(v, D.get(v).filter(e => e !== u));
if (D.get(v).length == 0) {
Q.push(v);
}
});
}
console.log('Solution:', S);
</syntaxhighlight>
Output:
<syntaxhighlight lang="javascript">
Solution: [
'ieee',
'std_cell_lib',
'gtech',
'dware',
'dw07',
'dw06',
'dw05',
'dw02',
'dw01',
'dw04',
'std',
'ramlib',
'synopsys',
'dw03',
'des_system_lib' ]
</syntaxhighlight>
=={{header|jq}}==
In the following, the graph of dependencies is represented as a JSON
object with keys being the dependent entities, and each
corresponding value being a list of its dependencies. For example:
{"x": ["y", "z"] } means: x depends on y and z.
The tsort filter will accept a dependency graph with self-dependencies.
'''Implementation Notes''':
Notice that the main function, tsort, has an inner function which itself has an inner function.
The normalize filter eliminates self-dependencies from a dependency graph.
'''Efficiency''':
The implementation of tsort uses a tail-recursive helper function, _tsort/0, which incurs no overhead due to recursion as jq optimizes arity-0 tail-recursive functions.
Since the dependency graph is represented as a jq object, which acts like a hash, access to the dependencies of a particular dependent is fast.
To solve and print the solution to the given problem on a 1GHz machine takes about 5ms.
<syntaxhighlight lang="jq"># independent/0 emits an array of the dependencies that have no dependencies
# Input: an object representing a normalized dependency graph
def independent:
. as $G
| reduce keys[] as $key
([];
. + ((reduce $G[$key][] as $node
([];
if ($G[$node] == null or ($G[$node]|length)==0) then . + [$node]
else .
end ))))
| unique;
# normalize/0 eliminates self-dependencies in the input dependency graph.
# Input: an object representing a dependency graph.
def normalize:
. as $G
| reduce keys[] as $key
($G;
.[$key] as $nodes
| if $nodes and ($nodes|index($key)) then .[$key] = $nodes - [$key] else . end);
# minus/1 removes all the items in ary from each of the values in the input object
# Input: an object representing a dependency graph
def minus(ary):
. as $G | with_entries(.value -= ary);
# tsort/0 emits the topologically sorted nodes of the input,
# in ">" order.
# Input is assumed to be an object representing a dependency
# graph and need not be normalized.
def tsort:
# _sort: input: [L, Graph], where L is the tsort so far
def _tsort:
def done: [.[]] | all( length==0 );
.[0] as $L | .[1] as $G
| if ($G|done) then $L + (($G|keys) - $L)
else
($G|independent) as $I
| if (($I|length) == 0)
then error("the dependency graph is cyclic: \($G)")
else [ ($L + $I), ($G|minus($I))] | _tsort
end
end;
normalize | [[], .] | _tsort ;
tsort</syntaxhighlight>
Data:
<syntaxhighlight 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"],
"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}}
<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}}==
{{works with|Julia|0.6}}
{{trans|Python}}
<syntaxhighlight lang="julia">function toposort(data::Dict{T,Set{T}}) where T
data = copy(data)
for (k, v) in data
delete!(v, k)
end
extraitems = setdiff(reduce(∪, values(data)), keys(data))
for item in extraitems
data[item] = Set{T}()
end
rst = Vector{T}()
while true
ordered = Set(item for (item, dep) in data if isempty(dep))
if isempty(ordered) break end
append!(rst, ordered)
data = Dict{T,Set{T}}(item => setdiff(dep, ordered) for (item, dep) in data if item ∉ ordered)
end
@assert isempty(data) "a cyclic dependency exists amongst $(keys(data))"
return rst
end
data = Dict{String,Set{String}}(
"des_system_lib" => Set(split("std synopsys std_cell_lib des_system_lib dw02 dw01 ramlib ieee")),
"dw01" => Set(split("ieee dw01 dware gtech")),
"dw02" => Set(split("ieee dw02 dware")),
"dw03" => Set(split("std synopsys dware dw03 dw02 dw01 ieee gtech")),
"dw04" => Set(split("dw04 ieee dw01 dware gtech")),
"dw05" => Set(split("dw05 ieee dware")),
"dw06" => Set(split("dw06 ieee dware")),
"dw07" => Set(split("ieee dware")),
"dware" => Set(split("ieee dware")),
"gtech" => Set(split("ieee gtech")),
"ramlib" => Set(split("std ieee")),
"std_cell_lib" => Set(split("ieee std_cell_lib")),
"synopsys" => Set(),
)
println("# Topologically sorted:\n - ", join(toposort(data), "\n - "))</syntaxhighlight>
{{out}}
<pre># Topologically sorted:
- synopsys
- ieee
- std
- ramlib
- dware
- gtech
- std_cell_lib
- dw07
- dw05
- dw02
- dw01
- dw06
- des_system_lib
- dw03
- dw04</pre>
=={{header|Kotlin}}==
{{trans|Java}}
<syntaxhighlight lang="scala">// version 1.1.51
val s = "std, ieee, des_system_lib, dw01, dw02, dw03, dw04, dw05, " +
"dw06, dw07, dware, gtech, ramlib, std_cell_lib, synopsys"
val deps = mutableListOf(
2 to 0, 2 to 14, 2 to 13, 2 to 4, 2 to 3, 2 to 12, 2 to 1,
3 to 1, 3 to 10, 3 to 11,
4 to 1, 4 to 10,
5 to 0, 5 to 14, 5 to 10, 5 to 4, 5 to 3, 5 to 1, 5 to 11,
6 to 1, 6 to 3, 6 to 10, 6 to 11,
7 to 1, 7 to 10,
8 to 1, 8 to 10,
9 to 1, 9 to 10,
10 to 1,
11 to 1,
12 to 0, 12 to 1,
13 to 1
)
class Graph(s: String, edges: List<Pair<Int,Int>>) {
val vertices = s.split(", ")
val numVertices = vertices.size
val adjacency = List(numVertices) { BooleanArray(numVertices) }
init {
for (edge in edges) adjacency[edge.first][edge.second] = true
}
fun hasDependency(r: Int, todo: List<Int>): Boolean {
return todo.any { adjacency[r][it] }
}
fun topoSort(): List<String>? {
val result = mutableListOf<String>()
val todo = MutableList<Int>(numVertices) { it }
try {
outer@ while(!todo.isEmpty()) {
for ((i, r) in todo.withIndex()) {
if (!hasDependency(r, todo)) {
todo.removeAt(i)
result.add(vertices[r])
continue@outer
}
}
throw Exception("Graph has cycles")
}
}
catch (e: Exception) {
println(e)
return null
}
return result
}
}
fun main(args: Array<String>) {
val g = Graph(s, deps)
println("Topologically sorted order:")
println(g.topoSort())
println()
// now insert 3 to 6 at index 10 of deps
deps.add(10, 3 to 6)
val g2 = Graph(s, deps)
println("Following the addition of dw04 to the dependencies of dw01:")
println(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:
java.lang.Exception: Graph has cycles
null
</pre>
{{trans|Python}}
<pre>
This version follows python implementation and returns List of Lists which is useful for parallel execution for example
</pre>
<syntaxhighlight lang="scala">
val graph = mapOf(
"des_system_lib" to "std synopsys std_cell_lib des_system_lib dw02 dw01 ramlib ieee".split(" ").toSet(),
"dw01" to "ieee dw01 dware gtech".split(" ").toSet(),
"dw02" to "ieee dw02 dware".split(" ").toSet(),
"dw03" to "std synopsys dware dw03 dw02 dw01 ieee gtech".split(" ").toSet(),
"dw04" to "dw04 ieee dw01 dware gtech".split(" ").toSet(),
"dw05" to "dw05 ieee dware".split(" ").toSet(),
"dw06" to "dw06 ieee dware".split(" ").toSet(),
"dw07" to "ieee dware".split(" ").toSet(),
"dware" to "ieee dware".split(" ").toSet(),
"gtech" to "ieee gtech".split(" ").toSet(),
"ramlib" to "std ieee".split(" ").toSet(),
"std_cell_lib" to "ieee std_cell_lib".split(" ").toSet(),
"synopsys" to setOf()
)
fun toposort( graph: Map<String,Set<String>> ): List<List<String>> {
var data = graph.map { (k,v) -> k to v.toMutableSet() }.toMap().toMutableMap()
// ignore self dependancies
data = data.map { (k,v) -> v.remove(k); k to v }.toMap().toMutableMap()
val extraItemsInDeps = data.values.reduce { a,b -> a.union( b ).toMutableSet() } - data.keys.toSet()
data.putAll( extraItemsInDeps.map { it to mutableSetOf<String>() }.toMap() )
val res = mutableListOf<List<String>>()
mainloop@ while( true ) {
innerloop@ while( true ) {
val ordered = data.filter{ (_,v) -> v.isEmpty() }.map { (k,_) -> k }
if( ordered.isEmpty() )
break@innerloop
res.add( ordered )
data = data.filter { (k,_) -> !ordered.contains(k) }.map { (k,v) -> v.removeAll(ordered); k to v }.toMap().toMutableMap()
}
if( data.isNotEmpty() )
throw Exception( "A cyclic dependency exists amongst: ${data.toList().joinToString { "," }}" )
else
break@mainloop
}
return res
}
fun main( args: Array<String> ) {
val result = toposort( graph )
println( "sorted dependencies:[\n${result.joinToString( ",\n")}\n]" )
}
</syntaxhighlight>
{{out}}
<pre>
sorted dependencies:[
[synopsys, std, ieee],
[dware, gtech, ramlib, std_cell_lib],
[dw01, dw02, dw05, dw06, dw07],
[des_system_lib, dw03, dw04]
]
</pre>
=={{header|M2000 Interpreter}}==
<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.
<syntaxhighlight lang="mathematica">TopologicalSort[
Graph[Flatten[# /. {l_, ld_} :>
Map[# -> l &,
DeleteCases[ld, l]]]]] /. {_TopologicalSort -> $Failed} &@
{{"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>{"ieee", "std_cell_lib", "gtech", "dware", "dw07", "dw06", "dw05", \
"dw02", "dw01", "dw04", "std", "ramlib", "synopsys", "dw03", \
"des_system_lib"}</pre>
If the data is un-orderable, it will return $Failed.
=={{header|Mercury}}==
<syntaxhighlight lang="mercury">
:- module topological_sort.
:- interface.
:- import_module io.
:- pred main(io::di,io::uo) is det.
:- implementation.
:- import_module string, solutions, list, set, require.
:- pred min_element(set(T),pred(T,T),T).
:- mode min_element(in,pred(in,in) is semidet,out) is nondet.
min_element(_,_,_):-fail.
min_element(S,P,X):-
member(X,S),
filter((pred(Y::in) is semidet :- P(Y,X)),S,LowerThanX),
is_empty(LowerThanX).
:- pred topological_sort(set(T),pred(T,T),list(T),list(T)).
:- mode topological_sort(in,(pred((ground >> ground), (ground >> ground)) is semidet),in,out) is nondet.
:- pred topological_sort(set(T),pred(T,T),list(T)).
:- mode topological_sort(in,(pred((ground >> ground), (ground >> ground)) is semidet),out) is nondet.
topological_sort(S,P,Ac,L) :-
(
is_empty(S) -> L is Ac
; solutions(
pred(X::out) is nondet:-
min_element(S,P,X)
, Solutions
),
(
is_empty(Solutions) -> error("No solution detected.\n")
; delete_list(Solutions,S,Sprime),
append(Solutions,Ac,AcPrime),
topological_sort(Sprime,P,AcPrime,L)
)
).
topological_sort(S,P,L) :- topological_sort(S,P,[],L).
:- pred distribute(list(T)::in,{T,list(T)}::out) is det.
distribute([],_):-error("Error in distribute").
distribute([H|T],Z) :- Z = {H,T}.
:- pred db_compare({string,list(string)}::in,{string,list(string)}::in) is semidet.
db_compare({X1,L1},{X2,_}) :- not(X1=X2),list.member(X2,L1).
main(!IO) :-
Input = [
"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"],
Words=list.map(string.words,Input),
list.map(distribute,Words,Db),
solutions(pred(X::out) is nondet :- topological_sort(set.from_list(Db),db_compare,X),SortedWordLists),
list.map(
pred({X,Y}::in,Z::out) is det:- X=Z,
list.det_head(SortedWordLists),
CompileOrder),
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;
{*
Topological sorter to parse e.g. dependencies.
Written for FreePascal 2.4.x/2.5.1. Probably works in Delphi, but you'd have to
change some units.
*}
{$IFDEF FPC}
// FreePascal-specific setup
{$mode objfpc}
uses {$IFDEF UNIX}
cwstring, {* widestring support for unix *} {$IFDEF UseCThreads}
cthreads, {$ENDIF UseCThreads} {$ENDIF UNIX}
Classes,
SysUtils;
{$ENDIF}
type
RNodeIndex = record
NodeName: WideString; //Name of the node
//Index: integer; //Index number used in DepGraph. For now, we can distill the index from the array index. If we want to use a TList or similar, we'd need an index property
Order: integer; //Order when sorted
end;
RDepGraph = record
Node: integer; //Refers to Index in NodeIndex
DependsOn: integer; //The Node depends on this other Node.
end;
{ TTopologicalSort }
TTopologicalSort = class(TObject)
private
Nodes: array of RNodeIndex;
DependencyGraph: array of RDepGraph;
FCanBeSorted: boolean;
function SearchNode(NodeName: WideString): integer;
function SearchIndex(NodeID: integer): WideString;
function DepFromNodeID(NodeID: integer): integer;
function DepFromDepID(DepID: integer): integer;
function DepFromNodeIDDepID(NodeID, DepID: integer): integer;
procedure DelDependency(const Index: integer);
public
constructor Create;
destructor Destroy; override;
procedure SortOrder(var Output: TStringList);
procedure AddNode(NodeName: WideString);
procedure AddDependency(NodeName, DependsOn: WideString);
procedure AddNodeDependencies(NodeAndDependencies: TStringList);
//Each string has node, and the nodes it depends on. This allows insertion of an entire dependency graph at once
//procedure DelNode(NodeName: Widestring);
procedure DelDependency(NodeName, DependsOn: WideString);
property CanBeSorted: boolean read FCanBeSorted;
end;
const
INVALID = -1;
// index not found for index search functions, no sort order defined, or record invalid/deleted
function TTopologicalSort.SearchNode(NodeName: WideString): integer;
var
Counter: integer;
begin
// Return -1 if node not found. If node found, return index in array
Result := INVALID;
for Counter := 0 to High(Nodes) do
begin
if Nodes[Counter].NodeName = NodeName then
begin
Result := Counter;
break;
end;
end;
end;
function TTopologicalSort.SearchIndex(NodeID: integer): WideString;
//Look up name for the index
begin
if (NodeID > 0) and (NodeID <= High(Nodes)) then
begin
Result := Nodes[NodeID].NodeName;
end
else
begin
Result := 'ERROR'; //something's fishy, this shouldn't happen
end;
end;
function TTopologicalSort.DepFromNodeID(NodeID: integer): integer;
// Look for Node index number in the dependency graph
// and return the first node found. If nothing found, return -1
var
Counter: integer;
begin
Result := INVALID;
for Counter := 0 to High(DependencyGraph) do
begin
if DependencyGraph[Counter].Node = NodeID then
begin
Result := Counter;
break;
end;
end;
end;
function TTopologicalSort.DepFromDepID(DepID: integer): integer;
// Look for dependency index number in the dependency graph
// and return the index for the first one found. If nothing found, return -1
var
Counter: integer;
begin
Result := INVALID;
for Counter := 0 to High(DependencyGraph) do
begin
if DependencyGraph[Counter].DependsOn = DepID then
begin
Result := Counter;
break;
end;
end;
end;
function TTopologicalSort.DepFromNodeIDDepID(NodeID, DepID: integer): integer;
// Shows index for the dependency from NodeID on DepID, or INVALID if not found
var
Counter: integer;
begin
Result := INVALID;
for Counter := 0 to High(DependencyGraph) do
begin
if DependencyGraph[Counter].Node = NodeID then
if DependencyGraph[Counter].DependsOn = DepID then
begin
Result := Counter;
break;
end;
end;
end;
procedure TTopologicalSort.DelDependency(const Index: integer);
// Removes dependency from array.
// Is fastest when the dependency is near the top of the array
// as we're copying the remaining elements.
var
Counter: integer;
OriginalLength: integer;
begin
OriginalLength := Length(DependencyGraph);
if Index = OriginalLength - 1 then
begin
SetLength(DependencyGraph, OriginalLength - 1);
end;
if Index < OriginalLength - 1 then
begin
for Counter := Index to OriginalLength - 2 do
begin
DependencyGraph[Counter] := DependencyGraph[Counter + 1];
end;
SetLength(DependencyGraph, OriginalLength - 1);
end;
if Index > OriginalLength - 1 then
begin
// This could happen when deleting on an empty array:
raise Exception.Create('Tried to delete index ' + IntToStr(Index) +
' while the maximum index was ' + IntToStr(OriginalLength - 1));
end;
end;
constructor TTopologicalSort.Create;
begin
inherited Create;
end;
destructor TTopologicalSort.Destroy;
begin
// Clear up data just to make sure:
Finalize(DependencyGraph);
Finalize(Nodes);
inherited;
end;
procedure TTopologicalSort.SortOrder(var Output: TStringList);
var
Counter: integer;
NodeCounter: integer;
OutputSortOrder: integer;
DidSomething: boolean; //used to detect cycles (circular references)
Node: integer;
begin
OutputSortOrder := 0;
DidSomething := True; // prime the loop below
FCanBeSorted := True; //hope for the best.
while (DidSomething = True) do
begin
// 1. Find all nodes (now) without dependencies, output them first and remove the dependencies:
// 1.1 Nodes that are not present in the dependency graph at all:
for Counter := 0 to High(Nodes) do
begin
if DepFromNodeID(Counter) = INVALID then
begin
if DepFromDepID(Counter) = INVALID then
begin
// Node doesn't occur in either side of the dependency graph, so it has sort order 0:
DidSomething := True;
if (Nodes[Counter].Order = INVALID) or
(Nodes[Counter].Order > OutputSortOrder) then
begin
// Enter sort order if the node doesn't have a lower valid order already.
Nodes[Counter].Order := OutputSortOrder;
end;
end; //Invalid Dep
end; //Invalid Node
end; //Count
// Done with the first batch, so we can increase the sort order:
OutputSortOrder := OutputSortOrder + 1;
// 1.2 Nodes that are only present on the right hand side of the dep graph:
DidSomething := False;
// reverse order so we can delete dependencies without passing upper array
for Counter := High(DependencyGraph) downto 0 do
begin
Node := DependencyGraph[Counter].DependsOn; //the depended node
if (DepFromNodeID(Node) = INVALID) then
begin
DidSomething := True;
//Delete dependency so we don't hit it again:
DelDependency(Counter);
if (Nodes[Node].Order = INVALID) or (Nodes[Node].Order > OutputSortOrder) then
begin
// Enter sort order if the node doesn't have a lower valid order already.
Nodes[Node].Order := OutputSortOrder;
end;
end;
OutputSortOrder := OutputSortOrder + 1; //next iteration
end;
// 2. Go back to 1 until we can't do more work, and do some bookkeeping:
OutputSortOrder := OutputSortOrder + 1;
end; //outer loop for 1 to 2
OutputSortOrder := OutputSortOrder - 1; //fix unused last loop.
// 2. If we have dependencies left, we have a cycle; exit.
if (High(DependencyGraph) > 0) then
begin
FCanBeSorted := False; //indicate we have a cycle
Output.Add('Cycle (circular dependency) detected, cannot sort further. Dependencies left:');
for Counter := 0 to High(DependencyGraph) do
begin
Output.Add(SearchIndex(DependencyGraph[Counter].Node) +
' depends on: ' + SearchIndex(DependencyGraph[Counter].DependsOn));
end;
end
else
begin
// No cycle:
// Now parse results, if we have them
for Counter := 0 to OutputSortOrder do
begin
for NodeCounter := 0 to High(Nodes) do
begin
if Nodes[NodeCounter].Order = Counter then
begin
Output.Add(Nodes[NodeCounter].NodeName);
end;
end; //output each result
end; //order iteration
end; //cycle detection
end;
procedure TTopologicalSort.AddNode(NodeName: WideString);
var
NodesNewLength: integer;
begin
// Adds node; make sure we don't add duplicate entries
if SearchNode(NodeName) = INVALID then
begin
NodesNewLength := Length(Nodes) + 1;
SetLength(Nodes, NodesNewLength);
Nodes[NodesNewLength - 1].NodeName := NodeName; //Arrays are 0 based
//Nodes[NodesNewLength -1].Index := //If we change the object to a tlist or something, we already have an index property
Nodes[NodesNewLength - 1].Order := INVALID; //default value
end;
end;
procedure TTopologicalSort.AddDependency(NodeName, DependsOn: WideString);
begin
// Make sure both nodes in the dependency exist as a node
if SearchNode(NodeName) = INVALID then
begin
Self.AddNode(NodeName);
end;
if SearchNode(DependsOn) = INVALID then
begin
Self.AddNode(DependsOn);
end;
// Add the dependency, only if we don't depend on ourselves:
if NodeName <> DependsOn then
begin
SetLength(DependencyGraph, Length(DependencyGraph) + 1);
DependencyGraph[High(DependencyGraph)].Node := SearchNode(NodeName);
DependencyGraph[High(DependencyGraph)].DependsOn := SearchNode(DependsOn);
end;
end;
procedure TTopologicalSort.AddNodeDependencies(NodeAndDependencies: TStringList);
// Takes a stringlist containing a list of strings. Each string contains node names
// separated by spaces. The first node depends on the others. It is permissible to have
// only one node name, which doesn't depend on anything.
// This procedure will add the dependencies and the nodes in one go.
var
Deplist: TStringList;
StringCounter: integer;
NodeCounter: integer;
begin
if Assigned(NodeAndDependencies) then
begin
DepList := TStringList.Create;
try
for StringCounter := 0 to NodeAndDependencies.Count - 1 do
begin
// For each string in the argument: split into names, and process:
DepList.Delimiter := ' '; //use space to separate the entries
DepList.StrictDelimiter := False; //allows us to ignore double spaces in input.
DepList.DelimitedText := NodeAndDependencies[StringCounter];
for NodeCounter := 0 to DepList.Count - 1 do
begin
if NodeCounter = 0 then
begin
// Add the first node, which might be the only one.
Self.AddNode(Deplist[0]);
end;
if NodeCounter > 0 then
begin
// Only add dependency from the second item onwards
// The AddDependency code will automatically add Deplist[0] to the Nodes, if required
Self.AddDependency(DepList[0], DepList[NodeCounter]);
end;
end;
end;
finally
DepList.Free;
end;
end;
end;
procedure TTopologicalSort.DelDependency(NodeName, DependsOn: WideString);
// Delete the record.
var
NodeID: integer;
DependsID: integer;
Dependency: integer;
begin
NodeID := Self.SearchNode(NodeName);
DependsID := Self.SearchNode(DependsOn);
if (NodeID <> INVALID) and (DependsID <> INVALID) then
begin
// Look up dependency and delete it.
Dependency := Self.DepFromNodeIDDepID(NodeID, DependsID);
if (Dependency <> INVALID) then
begin
Self.DelDependency(Dependency);
end;
end;
end;
// Main program:
var
InputList: TStringList; //Lines of dependencies
TopSort: TTopologicalSort; //Topological sort object
OutputList: TStringList; //Sorted dependencies
Counter: integer;
begin
//Actual sort
InputList := TStringList.Create;
// Add rosetta code sample input separated by at least one space in the lines
InputList.Add(
'des_system_lib std synopsys std_cell_lib des_system_lib dw02 dw01 ramlib ieee');
InputList.Add('dw01 ieee dw01 dware gtech');
InputList.Add('dw02 ieee dw02 dware');
InputList.Add('dw03 std synopsys dware dw03 dw02 dw01 ieee gtech');
InputList.Add('dw04 dw04 ieee dw01 dware gtech');
InputList.Add('dw05 dw05 ieee dware');
InputList.Add('dw06 dw06 ieee dware');
InputList.Add('dw07 ieee dware');
InputList.Add('dware ieee dware');
InputList.Add('gtech ieee gtech');
InputList.Add('ramlib std ieee');
InputList.Add('std_cell_lib ieee std_cell_lib');
InputList.Add('synopsys');
TopSort := TTopologicalSort.Create;
OutputList := TStringList.Create;
try
TopSort.AddNodeDependencies(InputList); //read in nodes
TopSort.SortOrder(OutputList); //perform the sort
for Counter := 0 to OutputList.Count - 1 do
begin
writeln(OutputList[Counter]);
end;
except
on E: Exception do
begin
Writeln(stderr, 'Error: ', DateTimeToStr(Now),
': Error sorting. Technical details: ',
E.ClassName, '/', E.Message);
end;
end; //try
OutputList.Free;
TopSort.Free;
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 698 ⟶ 4,888:
List.filter (fun d -> d <> lib) deps) in
List.map f dep_libs
let rev_unique =
List.fold_left (fun acc x -> if List.mem x acc then acc else x::acc) []
let libs = (* list items, each being unique *)
rev_unique (List.flatten(List.map (fun (lib, deps) -> lib::deps) dep_libs))
let get_deps lib =
Line 731 ⟶ 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 823 ⟶ 5,233:
{System.showInfo "\nBONUS - grouped by parallelizable compile jobs:"}
{PrintSolution Sol}
end</
Output:
Line 850 ⟶ 5,260:
des_system_lib dw03 dw04
</pre>
=={{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}}==
In July 2002, [http://perlgolf.sourceforge.net/TPR/0/4b/ Topological Sort] was the monthly [http://perlgolf.sourceforge.net/ Perl Golf] course. The [http://perlgolf.sourceforge.net/cgi-bin/PGAS/post_mortem.cgi?id=6 post-mortem] contains many solutions. This code was adapted from the solution that scored 144.39.
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.
<syntaxhighlight lang="perl">sub print_topo_sort {
my %deps = @_;
my %ba;
while ( my ( $before, $afters_aref ) = each %deps ) {
for my $after ( @{ $afters_aref } ) {
$ba{$before}{$after} = 1 if $before ne $after;
$ba{$after} ||= {};
}
}
while ( my @afters = sort grep { ! %{ $ba{$_} } } keys %ba ) {
print "@afters\n";
delete @ba{@afters};
delete @{$_}{@afters} for values %ba;
}
print !!%ba ? "Cycle found! ". join( ' ', sort keys %ba ). "\n" : "---\n";
}
my %deps = (
des_system_lib => [qw( std synopsys std_cell_lib des_system_lib dw02
dw01 ramlib ieee )],
dw01 => [qw( ieee dw01 dware gtech )],
dw02 => [qw( ieee dw02 dware )],
dw03 => [qw( std synopsys dware dw03 dw02 dw01 ieee gtech )],
dw04 => [qw( dw04 ieee dw01 dware gtech )],
dw05 => [qw( dw05 ieee dware )],
dw06 => [qw( dw06 ieee dware )],
dw07 => [qw( ieee dware )],
dware => [qw( ieee dware )],
gtech => [qw( ieee gtech )],
ramlib => [qw( std ieee )],
std_cell_lib => [qw( ieee std_cell_lib )],
synopsys => [qw( )],
);
print_topo_sort(%deps);
push @{ $deps{'dw01'} }, 'dw04'; # Add unresolvable dependency
print_topo_sort(%deps);</syntaxhighlight>
Output:<pre>ieee std synopsys
dware gtech ramlib std_cell_lib
dw01 dw02 dw05 dw06 dw07
des_system_lib dw03 dw04
---
ieee std synopsys
dware gtech ramlib std_cell_lib
dw02 dw05 dw06 dw07
Cycle found! des_system_lib dw01 dw03 dw04</pre>
=={{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: #000080;font-style:italic;">-- not yet compiled, or same pass</span>
<span style="color: #000000;">ok</span> <span style="color: #0000FF;">=</span> <span style="color: #004600;">false</span>
<span style="color: #008080;">exit</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
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"""</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.
<pre>
ieee std synopsys
dware gtech ramlib std_cell_lib
dw01 dw02 dw05 dw06 dw07
des_system_lib dw03 dw04
bad input:
** CYCLIC **:des_system_lib dw01 dw03 dw04
ieee std synopsys
dware gtech ramlib std_cell_lib
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 866 ⟶ 5,886:
(del (link @) 'Lst) # Yes: Store in result
(for This Lst # and remove from 'dep's
(=: dep (delete @ (: dep))) ) ) ) ) )</
Output:
<pre>: (sortDependencies
Line 884 ⟶ 5,904:
(synopsys) ) )
-> (std synopsys ieee std-cell-lib ramlib dware dw02 gtech dw01 des-system-lib dw03 dw04 dw05 dw06 dw07)</pre>
=={{header|PowerShell}}==
<
$a=@"
des_system_lib std synopsys std_cell_lib des_system_lib dw02 dw01 ramlib ieee
Line 935 ⟶ 5,956:
1
}
}
##Modify Dependency Value, perform check for incorrect dependency
##Dep Value is determined by a parent child relationship, if a library is a parent, all libraries dependant on it are children
Line 983 ⟶ 6,004:
"{0,-14} $($_."Library Dependencies")" -f $_.Library
}
}</
=={{header|PureBasic}}==
<
DataSection
;"LIBRARY: [LIBRARY_DEPENDENCY_1 LIBRARY_DEPENDENCY_2 ... LIBRARY_DEPENDENCY_N]
Line 1,103 ⟶ 6,125:
Print(#CRLF$ + #CRLF$ + "Press ENTER to exit")
Input()
CloseConsole()</
Sample output for no dependencies:
<pre>Compile order:
Line 1,132 ⟶ 6,154:
=={{header|Python}}==
===Python 3===
<syntaxhighlight lang="python">try:
from functools import reduce
except:
pass
data = {
Line 1,157 ⟶ 6,176:
}
def
for k, v in data.items():
v.discard(k) # Ignore self dependencies
extra_items_in_deps = reduce(set.union, data.values()) - set(data.keys())
while True:
ordered = set(item for item,dep in data.items() if not dep)
if not ordered:
break
yield ' '.join(sorted(ordered))
data
if item not in ordered}
assert not data, "A cyclic dependency exists amongst %r" % data
print ('\n'.join( toposort2(data) ))</syntaxhighlight>
'''Ordered output'''<br>
items on a line could be processed in any sub-order or, indeed, in parallel:
<pre>ieee std synopsys
dware gtech ramlib std_cell_lib
dw01 dw02 dw05 dw06 dw07
des_system_lib dw03 dw04</pre>
If dw04 is added to the set of dependencies of dw01 to make the data un-orderable, an exception is raised:
<pre>Traceback (most recent call last):
File "C:\Documents and Settings\All Users\Documents\Paddys\topological_sort.py", line 115, in <module>
print ('\n'.join( toposort2(data) ))
File "C:\Documents and Settings\All Users\Documents\Paddys\topological_sort.py", line 113, in toposort2
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 1,222 ⟶ 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 1,258 ⟶ 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 1,276 ⟶ 6,308:
dw04
dw03
</syntaxhighlight>
=={{header|Racket}}==
<syntaxhighlight lang="racket">
#lang racket
(define G
(make-hash
'((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 . ()))))
(define (clean G)
(define G* (hash-copy G))
(for ([(from tos) G])
; remove self dependencies
(hash-set! G* from (remove from tos))
; make sure all nodes are present in the ht
(for ([to tos]) (hash-update! G* to (λ(_)_) '())))
G*)
(define (incoming G)
(define in (make-hash))
(for* ([(from tos) G] [to tos])
(hash-update! in to (λ(fs) (cons from fs)) '()))
in)
(define (nodes G) (hash-keys G))
(define (out G n) (hash-ref G n '()))
(define (remove! G n m) (hash-set! G n (remove m (out G n))))
(define (topo-sort G)
(define n (length (nodes G)))
(define in (incoming G))
(define (no-incoming? n) (empty? (hash-ref in n '())))
(let loop ([L '()] [S (list->set (filter no-incoming? (nodes G)))])
(cond [(set-empty? S)
(if (= (length L) n)
L
(error 'topo-sort (~a "cycle detected" G)))]
[else
(define n (set-first S))
(define S\n (set-rest S))
(for ([m (out G n)])
(remove! G n m)
(remove! in m n)
(when (no-incoming? m)
(set! S\n (set-add S\n m))))
(loop (cons n L) S\n)])))
(topo-sort (clean G))
</syntaxhighlight>
Output:
<syntaxhighlight lang="racket">
'(synopsys ieee dware gtech std_cell_lib std ramlib dw07 dw06 dw05 dw01 dw04 dw02 dw03 des_system_lib)
</syntaxhighlight>
=={{header|Raku}}==
(formerly Perl 6)
{{trans|Perl}}
{{Works with|rakudo|2016.01}}
<syntaxhighlight lang="raku" line>sub print_topo_sort ( %deps ) {
my %ba;
for %deps.kv -> $before, @afters {
for @afters -> $after {
%ba{$before}{$after} = 1 if $before ne $after;
%ba{$after} //= {};
}
}
while %ba.grep( not *.value )».key -> @afters {
say ~@afters.sort;
%ba{@afters}:delete;
for %ba.values { .{@afters}:delete }
}
say %ba ?? "Cycle found! {%ba.keys.sort}" !! '---';
}
my %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 => < >;
print_topo_sort(%deps);
%deps<dw01> = <ieee dw01 dware gtech dw04>; # Add unresolvable dependency
print_topo_sort(%deps);</syntaxhighlight>
Output:<pre>ieee std synopsys
dware gtech ramlib std_cell_lib
dw01 dw02 dw05 dw06 dw07
des_system_lib dw03 dw04
---
ieee std synopsys
dware gtech ramlib std_cell_lib
dw02 dw05 dw06 dw07
Cycle found! des_system_lib dw01 dw03 dw04</pre>
Some differences from the Perl 5 version include use of
formal parameters; use of <tt>»</tt> as a "hyper" operator, that is, a parallelizable implicit loop; and use of normal lambda-like notation to bind loop parameters, so we can have multiple loop parameters bound on each iteration. Also,
since <tt>=></tt> is now a real pair composer rather than a synonym for comma, the data can be represented with real pair notation that points to quoted word lists delimited by angle brackets rather than <tt>[qw(...)]</tt>.
=={{header|REXX}}==
{{trans|FORTRAN 77}}
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>.
<syntaxhighlight 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.*/
label= 'DES_SYSTEM_LIB DW01 DW02 DW03 DW04 DW05 DW06 DW07' ,
'DWARE GTECH RAMLIB STD_CELL_LIB SYNOPSYS STD IEEE'
iCode= 1 14 13 12 1 3 2 11 15 0 2 15 2 9 10 0 3 15 3 9 0 4 14 213 9 4 3 2 15 10 0 5 5 15 ,
2 9 10 0 6 6 15 9 0 7 7 15 9 0 8 15 9 0 39 15 9 0 10 15 10 0 11 14 15 0 12 15 12 0 0
j= 0
do i=1
iL= word(iCode, i); if iL==0 then leave
do forever; i= i+1
iR= word(iCode, i); if iR==0 then leave
j= j+1; iDep.j.1= iL
iDep.j.2= iR
end /*forever*/
end /*i*/
call tSort
say '═══compile order═══'
@= 'libraries found.)'
#=0; do o=nO by -1 for nO; #= #+1; say word(label, iOrd.o)
end /*o*/; if #==0 then #= 'no'
say ' ('# @; say
say '═══unordered libraries═══'
#=0; do u=nO+1 to nL; #= #+1; say word(label, iOrd.u)
end /*u*/; if #==0 then #= 'no'
say ' ('# "unordered" @
exit /*stick a fork in it, we're all done. */
/*──────────────────────────────────────────────────────────────────────────────────────*/
tSort: procedure expose iDep. iOrd. iPos. nd nL nO
do i=1 for nL; iOrd.i= i; iPos.i= i
end /*i*/
k= 1
do until k<=j; j = k; k= nL+1
do i=1 for nd; iL = iDep.i.1; iR= iPos.iL
ipL= iPos.iL; ipR= iPos.iR
if iL==iR | ipL>.k | ipL<j | ipR<j then iterate
k= k-1
_= iOrd.k; iPos._ = ipL
iPos.iL= k
iOrd.ipL= iOrd.k; iOrd.k = iL
end /*i*/
end /*until*/
nO= j-1; return</syntaxhighlight>
{{out|output}}
<pre>
═══compile order═══
IEEE
STD
SYNOPSYS
STD_CELL_LIB
RAMLIB
GTECH
DWARE
DW07
DW06
DW05
DW04
DW03
DW02
DW01
DES_SYSTEM_LIB
(15 libraries found.)
═══unordered libraries═══
(no unordered libraries found.)
</pre>
=={{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 1,291 ⟶ 6,516:
depends = {}
DATA.each do |line|
key, *libs = line.split
depends[key] = libs
libs.each {|lib| depends[lib] ||= []}
Line 1,302 ⟶ 6,526:
p depends.tsort
rescue TSort::Cyclic => e
puts "
end
Line 1,318 ⟶ 6,542:
ramlib std ieee
std_cell_lib ieee std_cell_lib
synopsys</
{{out}}
<pre>
["std", "synopsys", "ieee", "std_cell_lib", "dware", "dw02", "gtech", "dw01", "ramlib", "des_system_lib", "dw03", "dw04", "dw05", "dw06", "dw07"]
cycle detected: topological sort failed: ["dw01", "dw04"]
</pre>
=={{header|Rust}}==
<syntaxhighlight lang="rust">use std::boxed::Box;
use std::collections::{HashMap, HashSet};
#[derive(Debug, PartialEq, Eq, Hash)]
struct Library<'a> {
name: &'a str,
children: Vec<&'a str>,
num_parents: usize,
}
fn build_libraries(input: Vec<&str>) -> HashMap<&str, Box<Library>> {
let mut libraries: HashMap<&str, Box<Library>> = HashMap::new();
for input_line in input {
let line_split = input_line.split_whitespace().collect::<Vec<&str>>();
let name = line_split.get(0).unwrap();
let mut num_parents: usize = 0;
for parent in line_split.iter().skip(1) {
if parent == name {
continue;
}
if !libraries.contains_key(parent) {
libraries.insert(
parent,
Box::new(Library {
name: parent,
children: vec![name],
num_parents: 0,
}),
);
} else {
libraries.get_mut(parent).unwrap().children.push(name);
}
num_parents += 1;
}
if !libraries.contains_key(name) {
libraries.insert(
name,
Box::new(Library {
name,
children: Vec::new(),
num_parents,
}),
);
} else {
libraries.get_mut(name).unwrap().num_parents = num_parents;
}
}
libraries
}
fn topological_sort<'a>(
mut libraries: HashMap<&'a str, Box<Library<'a>>>,
) -> Result<Vec<&'a str>, String> {
let mut needs_processing = libraries
.iter()
.map(|(k, _v)| k.clone())
.collect::<HashSet<&str>>();
let mut options: Vec<&str> = libraries
.iter()
.filter(|(_k, v)| v.num_parents == 0)
.map(|(k, _v)| *k)
.collect();
let mut sorted: Vec<&str> = Vec::new();
while !options.is_empty() {
let cur = options.pop().unwrap();
for children in libraries
.get_mut(cur)
.unwrap()
.children
.drain(0..)
.collect::<Vec<&str>>()
{
let child = libraries.get_mut(children).unwrap();
child.num_parents -= 1;
if child.num_parents == 0 {
options.push(child.name)
}
}
sorted.push(cur);
needs_processing.remove(cur);
}
match needs_processing.is_empty() {
true => Ok(sorted),
false => Err(format!("Cycle detected among {:?}", needs_processing)),
}
}
fn main() {
let input: Vec<&str> = vec![
"des_system_lib std synopsys std_cell_lib des_system_lib dw02 dw01 ramlib ieee\n",
"dw01 ieee dw01 dware gtech dw04\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",
"dw06 dw06 ieee dware\n",
"dw07 ieee dware\n",
"dware ieee dware\n",
"gtech ieee gtech\n",
"ramlib std ieee\n",
"std_cell_lib ieee std_cell_lib\n",
"synopsys\n",
];
let libraries = build_libraries(input);
match topological_sort(libraries) {
Ok(sorted) => println!("{:?}", sorted),
Err(msg) => println!("{:?}", msg),
}
}
</syntaxhighlight>
Output:
<pre>
["std", "synopsys", "ieee", "std_cell_lib", "ramlib", "gtech", "dware", "dw07", "dw06", "dw05", "dw02", "dw01", "dw04", "dw03", "des_system_lib"]
</pre>
Output if we make dw01 depend on dw04 by changing input to
<pre>
"des_system_lib std synopsys std_cell_lib des_system_lib dw02 dw01 ramlib ieee\n",
"dw01 ieee dw01 dware gtech dw04\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",
"dw06 dw06 ieee dware\n",
"dw07 ieee dware\n",
"dware ieee dware\n",
"gtech ieee gtech\n",
"ramlib std ieee\n",
"std_cell_lib ieee std_cell_lib\n",
"synopsys\n",
</pre>
<pre>
"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}}
<syntaxhighlight lang="ruby">func print_topo_sort (deps) {
var ba = Hash.new;
deps.each { |before, afters|
afters.each { |after|
if (before != after) {
ba{before}{after} = 1;
};
ba{after} \\= Hash.new;
}
};
loop {
var afters = ba.keys.grep {|k| ba{k}.values.len == 0 }.sort;
afters.len || break;
say afters.join(" ");
ba.delete(afters...);
ba.values.each { |v| v.delete(afters...) };
};
say (ba.len ? "Cicle found! #{ba.keys.sort}" : "---");
}
var deps = Hash.new(
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 => < >
);
print_topo_sort(deps);
deps{:dw01}.append('dw04'); # Add unresolvable dependency
print_topo_sort(deps);</syntaxhighlight>
{{out}}
<pre>
ieee std synopsys
dware gtech ramlib std_cell_lib
dw01 dw02 dw05 dw06 dw07
des_system_lib dw03 dw04
---
ieee std synopsys
dware gtech ramlib std_cell_lib
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 1,361 ⟶ 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 1,382 ⟶ 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 1,389 ⟶ 7,032:
=={{header|UNIX Shell}}==
The Unix [http://www.openbsd.org/cgi-bin/man.cgi?query=tsort&apropos=0&sektion=1&manpath=OpenBSD+Current&arch=i386&format=html tsort(1)] utility does a topological sort. Each line of input must have two items in order, like 'std des_system_lib'.<ref>
[[wp: tsort]]
</ref>
{{works with|Bourne Shell}}
<syntaxhighlight 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
>
> 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
>
>
>
> std_cell_lib ieee std_cell_lib
> synopsys
> !
ieee
dware
dw02
dw05
dw06
dw07
gtech
dw01
dw04
std_cell_lib
synopsys
std
dw03
ramlib
des_system_lib</syntaxhighlight>
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.
<pre>ieee
dware
dw02
dw05
dw06
dw07
gtech
std_cell_lib
synopsys
std
ramlib
tsort: cycle in data
tsort: dw01
tsort: dw04
dw01
des_system_lib
dw03
dw04</pre>
=={{header|Ursala}}==
The tsort function takes a list of pairs
Line 1,459 ⟶ 7,095:
unorderable libraries, if any, on the right. Self-dependences are
ignored and unlisted libraries are presumed independent.
<
test program:
<
dependence_table = -[
Line 1,485 ⟶ 7,121:
#show+
main = <.~&l,@r ~&i&& 'unorderable: '--> mat` ~~ tsort parse dependence_table</
With the given table, the output is
<pre>
Line 1,498 ⟶ 7,134:
=={{header|VBScript}}==
=====Implementation=====
<syntaxhighlight lang="vb">
class topological
dim dictDependencies
Line 1,578 ⟶ 7,214:
end property
end class
</syntaxhighlight>
=====Invocation=====
<syntaxhighlight lang="vb">
dim toposort
set toposort = new topological
Line 1,605 ⟶ 7,241:
toposort.reset
next
</syntaxhighlight>
=====Output=====
Line 1,684 ⟶ 7,320:
synopsys
-----
</pre>
=={{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.
<syntaxhighlight lang="vbnet">' Adapted from:
' http://tawani.blogspot.com/2009/02/topological-sorting-and-cyclic.html
' added/changed:
' - conversion to VB.Net (.Net 2 framework)
' - added Rosetta Code dependency format parsing
' - check & removal of self-dependencies before sorting
Module Program
Sub Main()
Dim Fields As New List(Of Field)()
' You can also add Dependson using code like:
' .DependsOn = New String() {"ieee", "dw01", "dware"} _
fields.Add(New Field() With { _
.Name = "des_system_lib", _
.DependsOn = Split("std synopsys std_cell_lib des_system_lib dw02 dw01 ramlib ieee", " ") _
})
fields.Add(New Field() With { _
.Name = "dw01", _
.DependsOn = Split("ieee dw01 dware gtech", " ") _
})
fields.Add(New Field() With { _
.Name = "dw02", _
.DependsOn = Split("ieee dw02 dware", " ") _
})
fields.Add(New Field() With { _
.Name = "dw03", _
.DependsOn = Split("std synopsys dware dw03 dw02 dw01 ieee gtech", " ") _
})
fields.Add(New Field() With { _
.Name = "dw04", _
.DependsOn = Split("dw04 ieee dw01 dware gtech", " ") _
})
fields.Add(New Field() With { _
.Name = "dw05", _
.DependsOn = Split("dw05 ieee dware", " ") _
})
fields.Add(New Field() With { _
.Name = "dw06", _
.DependsOn = Split("dw06 ieee dware", " ") _
})
fields.Add(New Field() With { _
.Name = "dw07", _
.DependsOn = Split("ieee dware", " ") _
})
fields.Add(New Field() With { _
.Name = "dware", _
.DependsOn = Split("ieee dware", " ") _
})
fields.Add(New Field() With { _
.Name = "gtech", _
.DependsOn = Split("ieee gtech", " ") _
})
fields.Add(New Field() With { _
.Name = "ramlib", _
.DependsOn = Split("std ieee", " ") _
})
fields.Add(New Field() With { _
.Name = "std_cell_lib", _
.DependsOn = Split("ieee std_cell_lib", " ") _
})
fields.Add(New Field() With { _
.Name = "synopsys" _
})
Console.WriteLine("Input:")
For Each ThisField As field In fields
Console.WriteLine(ThisField.Name)
If ThisField.DependsOn IsNot Nothing Then
For Each item As String In ThisField.DependsOn
Console.WriteLine(" -{0}", item)
Next
End If
Next
Console.WriteLine(vbLf & "...Sorting..." & vbLf)
Dim sortOrder As Integer() = getTopologicalSortOrder(fields)
For i As Integer = 0 To sortOrder.Length - 1
Dim field = fields(sortOrder(i))
Console.WriteLine(field.Name)
' Write up dependencies, too:
'If field.DependsOn IsNot Nothing Then
' For Each item As String In field.DependsOn
' Console.WriteLine(" -{0}", item)
' Next
'End If
Next
Console.Write("Press any key to continue . . . ")
Console.ReadKey(True)
End Sub
Private Sub CheckDependencies (ByRef Fields As List(Of Field))
' Make sure all objects we depend on are part of the field list
' themselves, as there may be dependencies that are not specified as fields themselves.
' Remove dependencies on fields themselves.Y
Dim AField As Field, ADependency As String
For i As Integer = Fields.Count - 1 To 0 Step -1
AField=fields(i)
If AField.DependsOn IsNot Nothing then
For j As Integer = 0 To Ubound(AField.DependsOn)
ADependency = Afield.DependsOn(j)
' We ignore fields that depends on themselves:
If AField.Name <> ADependency then
If ListContainsVertex(fields, ADependency) = False Then
' Add the dependent object to the field list, as it
' needs to be there, without any dependencies
Fields.Add(New Field() With { _
.Name = ADependency _
})
End If
End If
Next j
End If
Next i
End Sub
Private Sub RemoveSelfDependencies (ByRef Fields As List(Of Field))
' Make sure our fields don't depend on themselves.
' If they do, remove the dependency.
Dim InitialUbound as Integer
For Each AField As Field In Fields
If AField.DependsOn IsNot Nothing Then
InitialUbound = Ubound(AField.DependsOn)
For i As Integer = InitialUbound to 0 Step - 1
If Afield.DependsOn(i) = Afield.Name Then
' This field depends on itself, so remove
For j as Integer = i To UBound(AField.DependsOn)-1
Afield.DependsOn(j)=Afield.DependsOn(j+1)
Next
ReDim Preserve Afield.DependsOn(UBound(Afield.DependsOn)-1)
End If
Next
End If
Next
End Sub
Private Function ListContainsVertex(Fields As List(Of Field), VertexName As String) As Boolean
' Check to see if the list of Fields already contains a vertext called VertexName
Dim Found As Boolean = False
For i As Integer = 0 To fields.Count - 1
If Fields(i).Name = VertexName Then
Found = True
Exit For
End If
Next
Return Found
End Function
Private Function getTopologicalSortOrder(ByRef Fields As List(Of Field)) As Integer()
' Gets sort order. Will also add required dependencies to
' Fields.
' Make sure we don't have dependencies on ourselves.
' We'll just get rid of them.
RemoveSelfDependencies(Fields)
'First check depencies, add them to Fields if required:
CheckDependencies(Fields)
' Now we have the correct Fields list, so we can proceed:
Dim g As New TopologicalSorter(fields.Count)
Dim _indexes As New Dictionary(Of String, Integer)(fields.count)
'add vertex names to our lookup dictionaey
For i As Integer = 0 To fields.Count - 1
_indexes(fields(i).Name.ToLower()) = g.AddVertex(i)
Next
'add edges
For i As Integer = 0 To fields.Count - 1
If fields(i).DependsOn IsNot Nothing Then
For j As Integer = 0 To fields(i).DependsOn.Length - 1
g.AddEdge(i, _indexes(fields(i).DependsOn(j).ToLower()))
Next
End If
Next
Dim result As Integer() = g.Sort()
Return result
End Function
Private Class Field
Public Property Name() As String
Get
Return m_Name
End Get
Set
m_Name = Value
End Set
End Property
Private m_Name As String
Public Property DependsOn() As String()
Get
Return m_DependsOn
End Get
Set
m_DependsOn = Value
End Set
End Property
Private m_DependsOn As String()
End Class
End Module
Class TopologicalSorter
''source adapted from:
''http://tawani.blogspot.com/2009/02/topological-sorting-and-cyclic.html
''which was adapted from:
''http://www.java2s.com/Code/Java/Collections-Data-Structure/Topologicalsorting.htm
#Region "- Private Members -"
Private ReadOnly _vertices As Integer()
' list of vertices
Private ReadOnly _matrix As Integer(,)
' adjacency matrix
Private _numVerts As Integer
' current number of vertices
Private ReadOnly _sortedArray As Integer()
' Sorted vertex labels
#End Region
#Region "- CTors -"
Public Sub New(size As Integer)
_vertices = New Integer(size - 1) {}
_matrix = New Integer(size - 1, size - 1) {}
_numVerts = 0
For i As Integer = 0 To size - 1
For j As Integer = 0 To size - 1
_matrix(i, j) = 0
Next
Next
' sorted vert labels
_sortedArray = New Integer(size - 1) {}
End Sub
#End Region
#Region "- Public Methods -"
Public Function AddVertex(vertex As Integer) As Integer
_vertices(System.Threading.Interlocked.Increment(_numVerts)-1) = vertex
Return _numVerts - 1
End Function
Public Sub AddEdge(start As Integer, [end] As Integer)
_matrix(start, [end]) = 1
End Sub
Public Function Sort() As Integer()
' Topological sort
While _numVerts > 0
' while vertices remain,
' get a vertex with no successors, or -1
Dim currentVertex As Integer = noSuccessors()
If currentVertex = -1 Then
' must be a cycle
Throw New Exception("Graph has cycles")
End If
' insert vertex label in sorted array (start at end)
_sortedArray(_numVerts - 1) = _vertices(currentVertex)
' delete vertex
deleteVertex(currentVertex)
End While
' vertices all gone; return sortedArray
Return _sortedArray
End Function
#End Region
#Region "- Private Helper Methods -"
' returns vert with no successors (or -1 if no such verts)
Private Function noSuccessors() As Integer
For row As Integer = 0 To _numVerts - 1
Dim isEdge As Boolean = False
' edge from row to column in adjMat
For col As Integer = 0 To _numVerts - 1
If _matrix(row, col) > 0 Then
' if edge to another,
isEdge = True
' this vertex has a successor try another
Exit For
End If
Next
If Not isEdge Then
' if no edges, has no successors
Return row
End If
Next
Return -1
' no
End Function
Private Sub deleteVertex(delVert As Integer)
' if not last vertex, delete from vertexList
If delVert <> _numVerts - 1 Then
For j As Integer = delVert To _numVerts - 2
_vertices(j) = _vertices(j + 1)
Next
For row As Integer = delVert To _numVerts - 2
moveRowUp(row, _numVerts)
Next
For col As Integer = delVert To _numVerts - 2
moveColLeft(col, _numVerts - 1)
Next
End If
_numVerts -= 1
' one less vertex
End Sub
Private Sub moveRowUp(row As Integer, length As Integer)
For col As Integer = 0 To length - 1
_matrix(row, col) = _matrix(row + 1, col)
Next
End Sub
Private Sub moveColLeft(col As Integer, length As Integer)
For row As Integer = 0 To length - 1
_matrix(row, col) = _matrix(row, col + 1)
Next
End Sub
#End Region
End Class
</syntaxhighlight>
=====Output=====
<pre>
Input:
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
...Sorting...
des_system_lib
ramlib
dw03
std
std_cell_lib
dw04
dw01
gtech
dw07
dw06
dw05
dw02
dware
ieee
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>
=={{header|zkl}}==
{{trans|Wikipedia}}
Input data is munged
<syntaxhighlight 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
L:=List();
S:=data.pump(List,'wrap([(r,_)]){ if(allDs.holds(r)) Void.Skip else r }).copy();
while(S){ //while S is non-empty do
(n:=S.pop()) : L.append(_); //remove a node n from S, add n to tail of L
foreach m in (ds:=roots.find(n,List)){ //node m with an edge e from n to m
allDs.del(allDs.index(m));
if (Void==allDs.find(m)) S.append(m); //m has no other incoming edges
} roots.del(n); // remove edge e from the graph
}
if(roots) throw(Exception.ValueError("Cycle: "+roots.keys));
L
}</syntaxhighlight>
<syntaxhighlight lang="zkl">data:=T(
"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", "",
);
data=data.pump(List,Void.Read,fcn(r,ds){
T( r, ds.replace(r,"").strip().split().copy() ) // leaves writable 'cause they will be
});
topoSort(data).println();</syntaxhighlight>
{{out}}
<pre>
L("dw07","dw06","dw05","dw04","dw03","des_system_lib","ramlib",
"std","dw01","gtech","dw02","dware","std_cell_lib","ieee","synopsys")
</pre>
Adding dw04 to dw01 ("dw01", "ieee dw01 dware gtech dw04") and running:
{{out}}
<pre>
ValueError : Cycle: L("dw01","dw04","dware","gtech")
</pre>
| |||