Topological sort

From Rosetta Code
Task
Topological sort
You are encouraged to solve this task according to the task description, using any language you may know.


Given a mapping between items, and items they depend on, a topological sort orders items so that no item precedes an item it depends upon.

The compiling of a library in the 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 dependents, (sic), have no dependents of their own, but their order of compiling must be given.
  • Any self dependencies should be ignored.
  • Any un-orderable dependencies should be flagged.


Use the following data as an example:

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


Note: the above data would be un-orderable if, for example, dw04 is added to the list of dependencies of dw01.


C.f.


There are two popular algorithms for topological sorting:

  •   Kahn's 1962 topological sort [1]
  •   depth-first search [2] [3]



11l[edit]

Translation of: Python
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"))
Output:
ieee std synopsys
dware gtech ramlib std_cell_lib
dw01 dw02 dw05 dw06 dw07
des_system_lib dw03 dw04

Ada[edit]

Digraphs: A package for directed graphs, representing nodes as positive numbers

The specification:

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;

The implementation:

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;

Set_of_Names: Translating strings into numbers and vice versa

The specification:

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;

The implementation

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;

Toposort: Putting things together for the main program

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;
Output:

Given the name of the file with the dependencies as the parameter, Toposort generates the following output:

std -> synopsys -> ieee -> std_cell_lib -> dware -> dw02 -> gtech -> dw01 -> ramlib ->  des_system_lib -> dw03 -> dw04 -> dw05 -> dw06 -> dw07

If the dependencies is circular, the the Toposort tells that:

There is no topological sorting -- the Graph is cyclic!

ATS[edit]

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")

(*------------------------------------------------------------------*)
(* 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

(*------------------------------------------------------------------*)
Output:

Data fed to standard 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;

Data from standard output:

ieee, dware, dw05, dw06, dw07, gtech, dw01, dw04, dw02, std_cell_lib, synopsys, std, dw03, ramlib, des_system_lib

AND ...

Data fed to standard input:

a b; b d; d a e; e a;

Data from standard output:

COMPILATION CYCLE: a, e, d, b, a

Bracmat[edit]

(     ("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)
);
Output:
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)

C[edit]

Parses a multiline string and show the compile order. Note that four lines were added to the example input to form two separate cycles. Code is a little ugly.

#include <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;
}
Output:
(items on the same row can be compiled together)
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

C#[edit]

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...");
        }
    }
}
Output:
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...
Output:
(with cycled dependency)
Cycled dependencies detected: A C D
exiting...

C++[edit]

C++11[edit]

#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()));
        }
}

C++17[edit]

#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;
}
Output:
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
Output:
(with cycled dependency)
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

Clojure[edit]

Here is a quick implementation in Clojure, developed at Java Posse Roundup 2010 in collaboration with Fred Simon, with a bit of subsequent simplification by Joel Neely.

Dependencies are represented by a map from each item to the set of items on which it depends. The first function (dep), builds a dependency map for a single item.

The next few functions (empty-dep, pair-dep, default-deps, declared-deps, and deps) are used to construct the map from a list that alternates items with lists of their dependencies.

The next three functions (no-dep-items, remove-items, and topo-sort-deps) are the core of the topological sort algorithm, which iteratively removes items with no remaining dependencies from the map and "stacks" them onto the result. When the map becomes empty the reversed result is returned. If no dependency-free items can be found, then any non-empty remainder of the map contains cycles.

The last function (topo-sort) is simply a helper which applies topo-sort-deps to a dependency map constructed from the item-and-list-of-dependencies input list.

Implementation[edit]
(use 'clojure.set)
(use 'clojure.contrib.seq-utils)

(defn dep
  "Constructs a single-key dependence, represented as a map from
   item to a set of items, ensuring that item is not in the set."
  [item items]
  {item (difference (set items) (list item))})

(defn empty-dep
  "Constructs a single-key dependence from item to an empty set."
  [item]
  (dep item '()))

(defn pair-dep
  "Invokes dep after destructuring item and items from the argument."
  [[item items]]
  (dep item items))

(defn default-deps
  "Constructs a default dependence map taking every item
   in the argument to an empty set"
  [items]
  (apply merge-with union (map empty-dep (flatten items))))

(defn declared-deps
  "Constructs a dependence map from a list containaining
   alternating items and list of their predecessor items."
  [items]
  (apply merge-with union (map pair-dep (partition 2 items))))

(defn deps
  "Constructs a full dependence map containing both explicitly
   represented dependences and default empty dependences for
   items without explicit predecessors."
  [items]
  (merge (default-deps items) (declared-deps items)))

(defn no-dep-items
  "Returns all keys from the argument which have no (i.e. empty) dependences."
  [deps]
  (filter #(empty? (deps %)) (keys deps)))

(defn remove-items
  "Returns a dependence map with the specified items removed from keys
   and from all dependence sets of remaining keys."
  [deps items]
  (let [items-to-remove (set items)
        remaining-keys  (difference (set (keys deps)) items-to-remove)
        remaining-deps  (fn [x] (dep x (difference (deps x) items-to-remove)))]
    (apply merge (map remaining-deps remaining-keys))))

(defn topo-sort-deps
  "Given a dependence map, returns either a list of items in which each item
   follows all of its predecessors, or a string showing the items among which
   there is a cyclic dependence preventing a linear order."
  [deps]
  (loop [remaining-deps deps
         result         '()]
    (if (empty? remaining-deps)
        (reverse result)
        (let [ready-items (no-dep-items remaining-deps)]
          (if (empty? ready-items)
              (str "ERROR: cycles remain among " (keys remaining-deps))
              (recur (remove-items remaining-deps ready-items)
                     (concat ready-items result)))))))

(defn topo-sort
  "Given a list of alternating items and predecessor lists, constructs a
   full dependence map and then applies topo-sort-deps to that map."
  [items]
  (topo-sort-deps (deps items)))

Examples of sortable and non-sortable data:

(def good-sample
  '(: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         ()))

(def cyclic-dependence
  '(:dw01 (:dw04)))

(def bad-sample
  (concat cyclic-dependence good-sample))
=====
Output:
=====
Clojure 1.1.0
1:1 user=> #<Namespace topo>
1:2 topo=> (topo-sort good-sample)
(:std :synopsys :ieee :gtech :ramlib :dware :std_cell_lib :dw07 :dw06 :dw05 :dw01 :dw02 :des_system_lib :dw03 :dw04)
1:3 topo=> (topo-sort bad-sample)
"ERROR: cycles remain among (:dw01 :dw04 :dw03 :des_system_lib)"

CoffeeScript[edit]

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

Common Lisp[edit]

(defun topological-sort (graph &key (test 'eql))
  "Graph is an association list whose keys are objects and whose
values are lists of objects on which the corresponding key depends.
Test is used to compare elements, and should be a suitable test for
hash-tables.  Topological-sort returns two values.  The first is a
list of objects sorted toplogically.  The second is a boolean
indicating whether all of the objects in the input graph are present
in the topological ordering (i.e., the first value)."
  (let ((entries (make-hash-table :test test)))
    (flet ((entry (vertex)
             "Return the entry for vertex.  Each entry is a cons whose
              car is the number of outstanding dependencies of vertex
              and whose cdr is a list of dependants of vertex."
             (multiple-value-bind (entry presentp) (gethash vertex entries)
               (if presentp entry
                 (setf (gethash vertex entries) (cons 0 '()))))))
      ;; populate entries initially
      (dolist (vertex graph)
        (destructuring-bind (vertex &rest dependencies) vertex
          (let ((ventry (entry vertex)))
            (dolist (dependency dependencies)
              (let ((dentry (entry dependency)))
                (unless (funcall test dependency vertex)
                  (incf (car ventry))
                  (push vertex (cdr dentry))))))))
      ;; L is the list of sorted elements, and S the set of vertices
      ;; with no outstanding dependencies.
      (let ((L '())
            (S (loop for entry being each hash-value of entries
                     using (hash-key vertex)
                     when (zerop (car entry)) collect vertex)))
        ;; Until there are no vertices with no outstanding dependencies,
        ;; process vertices from S, adding them to L.
        (do* () ((endp S))
          (let* ((v (pop S)) (ventry (entry v)))
            (remhash v entries)
            (dolist (dependant (cdr ventry) (push v L))
              (when (zerop (decf (car (entry dependant))))
                (push dependant S)))))
        ;; return (1) the list of sorted items, (2) whether all items
        ;; were sorted, and (3) if there were unsorted vertices, the
        ;; hash table mapping these vertices to their dependants
        (let ((all-sorted-p (zerop (hash-table-count entries))))
          (values (nreverse L)
                  all-sorted-p
                  (unless all-sorted-p
                    entries)))))))

Provided example in which all items can be sorted:

> (defparameter *dependency-graph*
  '((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)))
*DEPENDENCY-GRAPH*

> (topological-sort *dependency-graph*)
(IEEE DWARE DW02 DW05 DW06 DW07 GTECH DW01 DW04 STD-CELL-LIB SYNOPSYS STD DW03 RAMLIB DES-SYSTEM-LIB)
T
NIL

Provided example with dw04 added to the dependencies of dw01. Some vertices are ordered, but the second return is nil, 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 / stores the list of values produced by the last form, and describe prints information about an object.)

> (defparameter *dependency-graph*
  '((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)))
*DEPENDENCY-GRAPH*

> (topological-sort *dependency-graph*)
(IEEE DWARE DW02 DW05 DW06 DW07 GTECH STD-CELL-LIB SYNOPSYS STD RAMLIB)
NIL
#<EQL Hash Table{4} 200C9023>

> (describe (third /))

#<EQL Hash Table{4} 200C9023> is a HASH-TABLE
DW01                (1 DW04 DW03 DES-SYSTEM-LIB)
DW04                (1 DW01)
DW03                (1)
DES-SYSTEM-LIB      (1)

Crystal[edit]

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(" -> ")
Output:
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)

D[edit]

Translation of: Python
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;
}
Output:
#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
----------------

E[edit]

def makeQueue := <elib:vat.makeQueue>

def topoSort(data :Map[any, Set[any]]) {
    # Tables of nodes and edges
    def forwardEdges := [].asMap().diverge()
    def reverseCount := [].asMap().diverge()
    
    def init(node) {
      reverseCount[node] := 0
      forwardEdges[node] := [].asSet().diverge()
    }
    for node => deps in data {
        init(node)
        for dep in deps { init(dep) }
    }
  
    # 'data' holds the dependencies. Compute the other direction.
    for node => deps in data {
        for dep ? (dep != node) in deps {
            forwardEdges[dep].addElement(node)
            reverseCount[node] += 1
        }
    }

    # Queue containing all elements that have no (initial or remaining) incoming edges
    def ready := makeQueue()
    for node => ==0 in reverseCount {
      ready.enqueue(node)
    }
    
    var result := []
    
    while (ready.optDequeue() =~ node :notNull) {
        result with= node
        for next in forwardEdges[node] {
            # Decrease count of incoming edges and enqueue if none
            if ((reverseCount[next] -= 1).isZero()) {
                ready.enqueue(next)
            }
        }
        forwardEdges.removeKey(node)
    }
  
    if (forwardEdges.size().aboveZero()) {
        throw(`Topological sort failed: $forwardEdges remains`)
    }
    
    return result
}
pragma.enable("accumulator")

def dataText := "\
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\
"

def data := accum [].asMap() for rx`(@item.{17})(@deps.*)` in dataText.split("\n") { _.with(item.trim(), deps.split(" ").asSet()) }

println(topoSort(data))
Output:

["std", "synopsys", "ieee", "dware", "gtech", "ramlib", "std_cell_lib", "dw02", "dw05", "dw06", "dw07", "dw01", "des_system_lib", "dw03", "dw04"]

EchoLisp[edit]

We use the low-level primitives of the 'graph' library to build the directed graph and implement the topological sort.

Data

(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))))

Implementation

Remove all vertices with in-degree = 0, until to one left. (in-degree = number of arrows to a vertex)

;; 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))))))
Output:
(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)

Elixir[edit]

Translation of: Erlang
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)
Output:
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

Erlang[edit]

-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
Output:
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

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.

Forth[edit]

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
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
Output:
ieee dware dw07 dw06 dw05 gtech (cycle: dw04 dw01) dw01 dw04 std synopsys dw02 dw03 ramlib std_cell_lib des_system_lib

Fortran[edit]

FORTRAN 77[edit]

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).

      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

An example. Dependencies are encoded to make program shorter (in array ICODE).

      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
Output:
 COMPILE ORDER
 IEEE
 STD
 SYNOPSYS
 STD_CELL_LIB
 RAMLIB
 GTECH
 DWARE
 DW07
 DW06
 DW05
 DW02
 DW01
 DW04
 DW03
 DES_SYSTEM_LIB
 UNORDERED LIBRARIES
Output:
with alternate input (DW01 depends also on DW04)
 COMPILE ORDER
 IEEE                
 STD                 
 SYNOPSYS            
 STD_CELL_LIB        
 RAMLIB              
 GTECH               
 DWARE               
 DW07                
 DW06                
 DW05                
 DW02                
 UNORDERED LIBRARIES
 DW04                
 DW03                
 DW01                
 DES_SYSTEM_LIB      

Modern Fortran[edit]

A modern Fortran (95-2008) version of the TSORT subroutine is shown here (note that the IPOS array is not an input).

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

FunL[edit]

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 )
Output:
[synopsys, ieee, std, dware, std_cell_lib, gtech, ramlib, dw06, dw05, dw02, dw07, dw01, dw03, dw04, des_system_lib]

Go[edit]

Kahn[edit]

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
}
Output:
Order: [std ieee std_cell_lib ramlib gtech dware dw07 dw06 dw05 dw02 dw01 dw04 synopsys dw03 des_system_lib]

Cycle detection demonstrated with the example in the task description:

Cyclic: [dw01 dw04]

Depth First[edit]

Topological sort only, this function can replace topSortKahn in above program. The in-degree list is not needed.

// 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
}
Output:

(when used in program of Kahn example.)

Order: [ieee gtech synopsys dware dw07 dw06 dw02 dw01 dw04 std_cell_lib dw05 std ramlib dw03 des_system_lib]

And with the cycle added,

Cyclic: [dw04 dw01]

Haskell[edit]

import Data.List ((\\), elemIndex, intersect, nub)
import Data.Bifunctor (bimap, first)

combs 0 _ = [[]]
combs _ [] = []
combs k (x:xs) = ((x :) <$> combs (k - 1) xs) ++ combs k xs

depLibs :: [(String, String)]
depLibs =
  [ ( "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", [])
  ]

toposort :: [(String, String)] -> [String]
toposort xs
  | (not . null) cycleDetect =
    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
Output:
*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"]]

Huginn[edit]

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 ) ) );
}

Icon and Unicon[edit]

Icon[edit]

This solution uses an efficient internal representation for a graph that limits the number of nodes to no more than 256.

The resulting topological ordering is displayed so elements on each line are independent and so can be built in parallel once the preceding lines of elements have been built.

record graph(nodes,arcs)
global ex_name, in_name

procedure main()
   show(tsort(getgraph()))
end

procedure tsort(g)
   t := ""
   while (n := g.nodes -- pnodes(g)) ~== "" do {
      t ||:= "("||n||")"
      g := delete(g,n)
      }
   if g.nodes == '' then return t
   write("graph contains the cycle:")
   write("\t",genpath(fn := !g.nodes,fn,g))
end

## pnodes(g) -- return the predecessor nodes of g
#     (those that have an arc from them)
procedure pnodes(g)
   static labels, fromnodes
   initial {
           labels := &ucase
           fromnodes := 'ACEGIKMOQSUWY'
           }
   return cset(select(g.arcs,labels, fromnodes))
end

## select(s,image,object) - efficient node selection
procedure select(s,image,object)
   slen := *s
   ilen := *image
   return if slen <= ilen then map(object[1+:slen/2],image[1+:slen],s)
          else map(object,image,s[1+:ilen]) || select(s[1+ilen:0],image,object)
end

## delete(g,x) -- deletes all nodes in x from graph g
#     note that arcs must be deleted as well
procedure delete(g,x)
   t := ""
   g.arcs ? while arc := move(2) do if not upto(x,arc) then t ||:= arc
   return graph(g.nodes--x,t)
end


## getgraph() -- read and construct a graph
#      graph is described via sets of arcs, as in:
#
#           from to1 to2 to3
#
# external names are converted to single character names for efficiency
# self-referential arcs are ignored
procedure getgraph()
   static labels
   initial labels := &cset
   ex_name := table()
   in_name := table()
   count := 0
   arcstr := ""
   nodes := ''
   every line := !&input do {
       nextWord := create genWords(line)
       if nfrom := @nextWord then {
           /in_name[nfrom] := &cset[count +:= 1]
           /ex_name[in_name[nfrom]] := nfrom
           nodes ++:= in_name[nfrom]
           while nto := @nextWord do {
               if nfrom ~== nto then {
                   /in_name[nto] := &cset[count +:= 1]
                   /ex_name[in_name[nto]] := nto
                   nodes ++:= in_name[nto]
                   arcstr ||:= in_name[nfrom] || in_name[nto]
                   }
               }
           }
       }
   return graph(nodes,arcstr)
end

# generate all 'words' in string
procedure genWords(s)
    static wchars
    initial wchars := &cset -- ' \t'
    s ?  while tab(upto(wchars))\1 do suspend tab(many(wchars))\1
end

## show(t) - return the external names (in order) for the nodes in t
#  Each output line contains names that are independent of each other
procedure show(t)
   line := ""
   every n := !t do
      case n of {
         "(" : line ||:= "\n\t("
         ")" : line[-1] := ")"
         default : line ||:= ex_name[n] || " "
      }
   write(line)
end

## genpath(f,t,g) -- generate paths from f to t in g
procedure genpath(f,t,g, seen)
   /seen := ''
   seen ++:= f
   sn := nnodes(f,g)
   if t ** sn == t then return ex_name[f] || " -> " || ex_name[t]
   suspend ex_name[f] || " -> " || genpath(!(sn --seen),t,g,seen)
end

## nnodes(f,g) -- compute all nodes that could follow f in g
procedure nnodes(f,g)
   t := ''
   g.arcs ? while arc := move(2) do if arc[1] == f then t ++:= arc[2]
   return t
end
Output:
->tsort <tsort.data

	(std synopsys ieee)
	(std_cell_lib ramlib dware gtech)
	(dw02 dw01 dw05 dw06 dw07)
	(des_system_lib dw03 dw04)
->

When run with the cycle suggested in the problem statement:

->tsort <tsort.data
graph contains the cycle:
        dw01 -> dw04 -> dw01
->

Unicon[edit]

The Icon solution also works in Unicon, but the following variant removes the 256-node limit by using sets instead of csets with the same algorithm that produces output so each line gives the elements that can be built in parallel once the elements in the preceding lines have been built.

record graph(nodes,arcs)

procedure main()
   show(tsort(getgraph()))
end

procedure tsort(g)
   t := []
   while *(n := g.nodes -- pnodes(g)) > 0 do {
      every put(p := [], !n)
      put(t, p)
      g := delete(g,n)
      }
   if *g.nodes = 0 then return t
   write("graph contains the cycle:")
   write("\t",genpath(fn := !g.nodes,fn,g))
end

procedure pnodes(g)
   cp := create !g.arcs
   every insert(p := set(), |1(@cp,@cp))
   return p
end

procedure delete(g,x)
   arcs := []
   cp := create !g.arcs
   while (f := @cp, t := @cp) do {
        if !x == (f|t) then next
        every put(arcs,f|t)
        }
   return graph(g.nodes--x, arcs)
end

procedure getgraph()
   arcs := []
   nodes := set()
   every line := !&input do {
       nextWord := create genWords(line)
       if nfrom := @nextWord then {
           insert(nodes, nfrom)
           while nto := @nextWord do {
               if nfrom ~== nto then {
                   insert(nodes, nto)
                   every put(arcs, nfrom | nto)
                   }
               }
           }
       }
   return graph(nodes,arcs)
end

procedure genWords(s)
    static wchars
    initial wchars := &cset -- ' \t'
    s ?  while tab(upto(wchars))\1 do suspend tab(many(wchars))\1
end

procedure show(t)
   line := ""
   every n := !t do
      case type(n) of {
         "list" : line ||:= "\n\t("||toString(n)||")"
         default : line ||:= " "||n
         }
   write(line)
end

procedure toString(n)
   every (s := "") ||:= !n || " "
   return s[1:-1] | s
end

procedure genpath(f,t,g, seen)
   /seen := set()
   insert(seen, f)
   sn := nnodes(f,g)
   if member(sn, t) then return f || " -> " || t
   suspend f || " -> " || genpath(!(sn--seen),t,g,seen)
end

procedure nnodes(f,g)
   t := set()
   cp := create !g.arcs
   while (af := @cp, at := @cp) do if af == f then insert(t, at)
   return t
end

J[edit]

dependencySort=: monad define
  parsed=. <@;:;._2 y
  names=. {.&>parsed
  depends=. (> =@i.@#) names e.S:1 parsed
  depends=. (+. +./ .*.~)^:_ depends
  assert.-.1 e. (<0 1)|:depends
  (-.&names ~.;parsed),names /: +/"1 depends
)

With the sample data set:

dependencies=: noun define
  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 
)

We would get:

    >dependencySort dependencies
 std           
 ieee          
 dware         
 gtech         
 ramlib        
 std_cell_lib  
 synopsys      
 dw02          
 dw05          
 dw06          
 dw07          
 dw01          
 dw04          
 dw03          
 des_system_lib

If we tried to also make dw01 depend on dw04, the sort would fail because of the circular dependency:

   dependencySort dependencies,'dw01 dw04',LF
|assertion failure: dependencySort
|   -.1 e.(<0 1)|:depends

Here is an alternate implementation which uses a slightly different representation for the dependencies (instead of a boolean connection matrix to represent connections, we use a list of lists of indices to represent connections):

depSort=: monad define
  parsed=. <@;:;._2 y
  names=. {.&>parsed
  depends=. (-.L:0"_1 #,.i.@#) names i.L:1 parsed
  depends=. (~.@,&.> ;@:{L:0 1~)^:_ depends
  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.

Java[edit]

Works with: Java version 7
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;
    }
}
[std,  ieee,  dware,  dw02,  dw05, dw06,  dw07,  gtech,  dw01,  dw04,  ramlib,  std_cell_lib,  synopsys,  des_system_lib,  dw03]

JavaScript[edit]

ES6[edit]

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);

Output:

Solution: [
  'ieee',
  'std_cell_lib',
  'gtech',
  'dware',
  'dw07',
  'dw06',
  'dw05',
  'dw02',
  'dw01',
  'dw04',
  'std',
  'ramlib',
  'synopsys',
  'dw03',
  'des_system_lib' ]

jq[edit]

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.

# 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

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": []
}
Output:
$ 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"]

Julia[edit]

Works with: Julia version 0.6
Translation of: Python
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 - "))
Output:
# Topologically sorted:
 - synopsys
 - ieee
 - std
 - ramlib
 - dware
 - gtech
 - std_cell_lib
 - dw07
 - dw05
 - dw02
 - dw01
 - dw06
 - des_system_lib
 - dw03
 - dw04

Kotlin[edit]

Translation of: Java
// 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())
}
Output:
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
Translation of: Python
This version follows python implementation and returns List of Lists which is useful for parallel execution for example
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]" )
}
Output:
sorted dependencies:[
[synopsys, std, ieee],
[dware, gtech, ramlib, std_cell_lib],
[dw01, dw02, dw05, dw06, dw07],
[des_system_lib, dw03, dw04]
]

M2000 Interpreter[edit]

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
Output:
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

Mathematica/Wolfram Language[edit]

Work in Mathematica 8 or higher versions.

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", {}}}
Output:
{"ieee", "std_cell_lib", "gtech", "dware", "dw07", "dw06", "dw05", \
"dw02", "dw01", "dw04", "std", "ramlib", "synopsys", "dw03", \
"des_system_lib"}

If the data is un-orderable, it will return $Failed.

Mercury[edit]

:- 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).

Nim[edit]

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()

Object Pascal[edit]

Written for Free Pascal, but will probably work in Delphi if you change the required units.

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.

OCaml[edit]

let dep_libs = [
  ("des_system_lib", ["std"; "synopsys"; "std_cell_lib"; "des_system_lib"; "dw02"; "dw01"; "ramlib"; "ieee"]);
  ("dw01",           (*"dw04"::*)["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",       []);
]

let dep_libs =
  let f (lib, deps) =  (* remove self dependency *)
    (lib,
     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 =
  try (List.assoc lib dep_libs)
  with Not_found -> []

let res =
  let rec aux acc later todo progress =
  match todo, later with
  | [], [] -> (List.rev acc)
  | [], _ ->
      if progress
      then aux acc [] later false
      else invalid_arg "un-orderable data"
  | x::xs, _ ->
      let deps = get_deps x in
      let ok = List.for_all (fun dep -> List.mem dep acc) deps in
      if ok
      then aux (x::acc) later xs true
      else aux acc (x::later) xs progress
  in
  let starts, todo = List.partition (fun lib -> get_deps lib = []) libs in
  aux starts [] todo false

let () =
  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".

OxygenBasic[edit]

'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


Oz[edit]

Using constraint propagation and search:

declare
  Deps = unit(
            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:nil
            )

  %% Describe possible solutions
  proc {TopologicalOrder Solution}
     FullDeps = {Complete Deps}
  in
     %% The solution is a record that maps library names
     %% to finite domain variables.
     %% The smaller the value, the earlier it must be compiled
     Solution = {FD.record sol {Arity FullDeps} 1#{Width FullDeps}}
     %% for every lib on the left side
     {Record.forAllInd FullDeps
      proc {$ LibName Dependants}
         %% ... and every dependant on the right side
         for Dependant in Dependants do
            %% propagate compilation order
            if Dependant \= LibName then
               Solution.LibName >: Solution.Dependant
            end
         end
      end
     }
     %% enumerate solutions
     {FD.distribute naive Solution}
  end

  %% adds empty list of dependencies for libs that only occur on the right side
  fun {Complete Dep}
     AllLibs = {Nub {Record.foldL Dep Append nil}}
  in
     {Adjoin
      {List.toRecord unit {Map AllLibs fun {$ L} L#nil end}}
      Dep}
  end

  %% removes duplicates
  fun {Nub Xs}
     D = {Dictionary.new}
  in
     for X in Xs do D.X := unit end
     {Dictionary.keys D}
  end

  %% print grouped by parallelizable jobs
  proc {PrintSolution Sol}
     for I in 1..{Record.foldL Sol Value.max 1} do
        for Lib in {Arity {Record.filter Sol fun {$ X} X == I end}} do
           {System.printInfo Lib#" "}
        end
        {System.printInfo "\n"}
     end
  end

  fun {GetOrderedLibs Sol}
     {Map
      {Sort {Record.toListInd Sol} CompareSecond}
      SelectFirst}
  end
  fun {CompareSecond A B} A.2 < B.2 end
  fun {SelectFirst X} X.1 end
in
  case {SearchOne TopologicalOrder}
  of nil then {System.showInfo "Un-orderable."}
  [] [Sol] then
     {System.showInfo "A possible topological ordering: "}
     {ForAll {GetOrderedLibs Sol} System.showInfo}
  
     {System.showInfo "\nBONUS - grouped by parallelizable compile jobs:"}
     {PrintSolution Sol}
  end

Output:

A possible topological ordering: 
synopsys
std
ieee
std_cell_lib
ramlib
gtech
dware
dw07
dw06
dw05
dw02
dw01
dw04
dw03
des_system_lib

BONUS - grouped by parallelizable compile jobs:
ieee std synopsys 
dware gtech ramlib std_cell_lib 
dw01 dw02 dw05 dw06 dw07 
des_system_lib dw03 dw04 

Pascal[edit]

Kahn's algorithm[edit]

This solution uses Kahn's algorithm, requires FPC version at least 3.2.0.

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.
Output:
success:
ieee, dware, gtech, std, dw01, dw02, synopsys, std_cell_lib, ramlib, dw04, dw05,
 dw07, dw03, dw06, des_system_lib

circular dependency detected
Depth-first search[edit]

Another solution uses DFS and can extract the found cycle; requires FPC version at least 3.2.0.

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.
Output:
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

Perl[edit]

In July 2002, Topological Sort was the monthly Perl Golf course. The 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.

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);
Output:
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

Phix[edit]

Implemented as a trivial normal sort.

sequence names
enum RANK, NAME, DEP    -- 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)
 
function add_dependency(string name)
    integer k = find(name,vslice(names,NAME))
    if k=0 then
        names = append(names,{0,name,{}})
        k = length(names)
    end if
    return k
end function
 
procedure topsort(string input)
    names = {}
    sequence lines = split(input,'\n')
    for i=1 to length(lines) do
        sequence line = split(lines[i]),
                 dependencies = {}
        integer k = add_dependency(line[1])
        for j=2 to length(line) do
            integer l = add_dependency(line[j])
            if l!=k then -- ignore self-references
                dependencies &= l
            end if
        end for
        names[k][DEP] = dependencies
    end for
 
    -- Now populate names[RANK] iteratively:
    bool more = true
    integer rank = 0
    while more do
        more = false 
        rank += 1
        for i=1 to length(names) do
            if names[i][RANK]=0 then
                bool ok = true
                for j=1 to length(names[i][DEP]) do
                    integer ji = names[i][DEP][j],
                            nr = names[ji][RANK]
                    if nr=0 or nr=rank then
                        -- not yet compiled, or same pass
                        ok = false
                        exit
                    end if
                end for
                if ok then
                    names[i][RANK] = rank
                    more = true
                end if
            end if
        end for
    end while
 
    names = sort(names) -- (ie by [RANK=1] then [NAME=2])
    integer prank = names[1][RANK]
    if prank=0 then puts(1,"** CYCLIC **:") end if
    for i=1 to length(names) do
        rank = names[i][RANK]
        if i>1 then
            puts(1,iff(rank=prank?" ":"\n"))
        end if
        puts(1,names[i][NAME])
        prank = rank
    end for
    puts(1,"\n")
end procedure
 
constant 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"""
 
topsort(input)
puts(1,"\nbad input:\n")
topsort(input&"\ndw01 dw04")
Output:

Items on the same line can be compiled at the same time, and each line is alphabetic.

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

Picat[edit]

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].

The approach was inspired by a SETL snippet:

(while exists x in nodes | x notin range edges)
  print(x);
  nodes less:= x;
  edges lessf:= x;
end;

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[edit]

Identify and remove the cycles.

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=[]
    ].
Output:
[std,synopsys,ieee,std_cell_lib,ramlib,dware,dw02,gtech,dw01,des_system_lib,dw03,dw04,dw05,dw06,dw07]

Test with cycles[edit]

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]
    ].
Output:
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]]


PicoLisp[edit]

(de sortDependencies (Lst)
   (setq Lst                              # Build a flat list
      (uniq
         (mapcan
            '((L)
               (put (car L) 'dep (cdr L)) # Store dependencies in 'dep' properties
               (copy L) )
            (mapcar uniq Lst) ) ) )       # without self-dependencies
   (make
      (while Lst
         (ifn (find '((This) (not (: dep))) Lst)   # Found non-depending lib?
            (quit "Can't resolve dependencies" Lst)
            (del (link @) 'Lst)                    # Yes: Store in result
            (for This Lst                          # and remove from 'dep's
               (=: dep (delete @ (: dep))) ) ) ) ) )

Output:

: (sortDependencies
   (quote
      (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) ) )
-> (std synopsys ieee std-cell-lib ramlib dware dw02 gtech dw01 des-system-lib dw03 dw04 dw05 dw06 dw07)

PowerShell[edit]

#Input Data
$a=@"
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 to Object[]
$c = switch ( $a.split([char] 10) ) { 
    $_ {
        $b=$_.split(' ')
        New-Object PSObject -Property @{
            Library = $b[0]
            "Library Dependencies" = @( $( $b[1..($b.length-1)] | Where-Object { $_ -match '\w' } ) )
        } 
    }
}
#Add pure dependencies
$c | ForEach-Object {
    $_."Library Dependencies" | Where-Object {
        $d=$_
        $(:andl foreach($i in $c) {
            if($d -match $i.Library) {
                $false
                break andl
            }
        }) -eq $null
    } | ForEach-Object {
        $c+=New-Object PSObject -Property @{
            Library=$_
            "Library Dependencies"=@()
        }
    }
}
#Associate with a dependency value
##Initial Dependency Value
$d = $c | Sort Library | Select-Object Library,"Library Dependencies",@{
    Name="Dep Value"
    Expression={
        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
for( $i=0; $i -lt $d.count; $i++ ) {
    $errmsg=""
    foreach( $j in ( 0..( $d.count - 1 ) | Where-Object { $_ -ne $i } ) ) {
        #Foreach other Child Library where this is a dependency, increase the Dep Value of the Child
        if( $( :orl foreach( $k in $d[$j]."Library Dependencies" ) {
            if( $k -match $d[$i].Library ) {
                foreach( $n in $d[$i]."Library Dependencies" ) {
                    if( $n -match $d[$j].Library ) {
                        $errmsg="Error Cyclic Dependency {0}<->{1}" -f $d[$i].Library, $d[$j].Library
                        break
                    }
                }
                $true
                break orl
            }
        } ) ) {
            #If the child has already been processed, increase the Dep Value of its children
            if( $j -lt $i ) {
                foreach( $l in ( 0..( $d.count - 1 ) | Where-Object { $_ -ne $j } ) ) {
                    if( $( :orl2 foreach( $m in $d[$l]."Library Dependencies" ) {
                        if( $m -match $d[$j].Library ) {
                            $true
                            break orl2
                        }
                    } ) ) {
                        $d[$l]."Dep Value"+=$d[$i]."Dep Value"
                    }
                }
            }
            $d[$j]."Dep Value"+=$d[$i]."Dep Value"
        }
        if( $errmsg -ne "" ) {
            $errmsg
            $d=$null
            break
        }
    }
}
#Sort and Display
if( $d ) {
    $d | Sort "Dep Value",Library | ForEach-Object { 
        "{0,-14} LIBRARY DEPENDENCIES`n{1,-14} ====================" -f "LIBRARY", "======="
    } {
        "{0,-14} $($_."Library Dependencies")" -f $_.Library
    }
}

PureBasic[edit]

#EndOfDataMarker$ = "::EndOfData::"
DataSection
  ;"LIBRARY: [LIBRARY_DEPENDENCY_1 LIBRARY_DEPENDENCY_2 ... LIBRARY_DEPENDENCY_N]
  Data.s "des_system_lib: [std synopsys std_cell_lib des_system_lib dw02 dw01 ramlib ieee]"
  Data.s "dw01: [ieee dw01 dware gtech]"
  ;Data.s "dw01: [ieee dw01 dware gtech dw04]" ;comment the previous line and uncomment this one for cyclic dependency
  Data.s "dw02: [ieee dw02 dware]"
  Data.s "dw03: [std synopsys dware dw03 dw02 dw01 ieee gtech]"
  Data.s "dw04: [dw04 ieee dw01 dware gtech]"
  Data.s "dw05: [dw05 ieee dware]"
  Data.s "dw06: [dw06 ieee dware]"
  Data.s "dw07: [ieee dware]"
  Data.s "dware: [ieee dware]"
  Data.s "gtech: [ieee gtech]"
  Data.s "ramlib: [std ieee]"
  Data.s "std_cell_lib: [ieee std_cell_lib]"
  Data.s "synopsys: nil"
  Data.s #EndOfDataMarker$
EndDataSection

Structure DAG_node
  Value.s
  forRemoval.i ;flag marks elements that should be removed the next time they are accessed
  List dependencies.s()
EndStructure

If Not OpenConsole()
  MessageRequester("Error","Unable to open console")
  End
EndIf

;// initialize Directed Acyclic Graph //
Define i, itemData.s, firstBracketPos
NewList DAG.DAG_node()
Repeat
  Read.s itemData
  itemData = Trim(itemData)
  If itemData <> #EndOfDataMarker$
    AddElement(DAG())
    ;add library
    DAG()\Value = Trim(Left(itemData, FindString(itemData, ":", 1) - 1))
    ;parse library dependencies
    firstBracketPos = FindString(itemData, "[", 1)
    If firstBracketPos
      itemData = Trim(Mid(itemData, firstBracketPos + 1, FindString(itemData, "]", 1) - firstBracketPos - 1))
      For i = (CountString(itemData, " ") + 1) To 1 Step -1
        AddElement(DAG()\dependencies())
        DAG()\dependencies() = StringField(itemData, i, " ")
      Next 
    EndIf 
  EndIf 
Until itemData = #EndOfDataMarker$

;// process DAG //
;create DAG entry for nodes listed in dependencies but without their own entry
NewMap libraries()
ForEach DAG()
  ForEach DAG()\dependencies()
    libraries(DAG()\dependencies()) = #True
    If DAG()\dependencies() = DAG()\Value
      DeleteElement(DAG()\dependencies()) ;remove self-dependencies
    EndIf 
  Next
Next

ForEach DAG()
  If FindMapElement(libraries(),DAG()\Value)
    DeleteMapElement(libraries(),DAG()\Value)
  EndIf 
Next

ResetList(DAG())
ForEach libraries()
  AddElement(DAG())
  DAG()\Value = MapKey(libraries())
Next
ClearMap(libraries())

;process DAG() repeatedly until no changes occur
NewList compileOrder.s()
Repeat 
  noChangesMade = #True
  ForEach DAG()
    If DAG()\forRemoval
      DeleteElement(DAG())
    Else
      ;remove dependencies that have been placed in the compileOrder
      ForEach DAG()\dependencies()
        If FindMapElement(libraries(),DAG()\dependencies())
          DeleteElement(DAG()\dependencies())
        EndIf 
      Next
      ;add DAG() entry to compileOrder if it has no more dependencies
      If ListSize(DAG()\dependencies()) = 0
        AddElement(compileOrder())
        compileOrder() = DAG()\Value
        libraries(DAG()\Value) = #True ;mark the library for removal as a dependency
        DAG()\forRemoval = #True
        noChangesMade = #False
      EndIf 
    EndIf 
  Next 
Until noChangesMade

If ListSize(DAG())
  PrintN("Cyclic dependencies detected in:" + #CRLF$)
  ForEach DAG()
    PrintN(" " + DAG()\Value)
  Next
Else
  PrintN("Compile order:" + #CRLF$)
  ForEach compileOrder()
    PrintN(" " + compileOrder())
  Next
EndIf 

Print(#CRLF$ + #CRLF$ + "Press ENTER to exit")
Input()
CloseConsole()

Sample output for no dependencies:

Compile order:

 ieee
 std
 dware
 gtech
 ramlib
 std_cell_lib
 synopsys
 dw01
 dw02
 dw03
 dw04
 dw05
 dw06
 dw07
 des_system_lib

Sample output when cyclic dependencies are present:

Cyclic dependencies detected in:

 des_system_lib
 dw01
 dw03
 dw04

Python[edit]

Python 3[edit]

try:
    from functools import reduce
except:
    pass

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(),
    }

def toposort2(data):
    for k, v in data.items():
        v.discard(k) # Ignore self dependencies
    extra_items_in_deps = reduce(set.union, data.values()) - set(data.keys())
    data.update({item:set() for item in extra_items_in_deps})
    while True:
        ordered = set(item for item,dep in data.items() if not dep)
        if not ordered:
            break
        yield ' '.join(sorted(ordered))
        data = {item: (dep - ordered) for item,dep in data.items()
                if item not in ordered}
    assert not data, "A cyclic dependency exists amongst %r" % data

print ('\n'.join( toposort2(data) ))

Ordered output
items on a line could be processed in any sub-order or, indeed, in parallel:

ieee std synopsys
dware gtech ramlib std_cell_lib
dw01 dw02 dw05 dw06 dw07
des_system_lib dw03 dw04

If dw04 is added to the set of dependencies of dw01 to make the data un-orderable, an exception is raised:

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'}}

Python 3.9 graphlib[edit]

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()))
Output:
('synopsys', 'std', 'ieee', 'dware', 'gtech', 'ramlib', 'std_cell_lib', 'dw02', 'dw05', 'dw06', 'dw07', 'dw01', 'des_system_lib', 'dw03', 'dw04')

R[edit]

First make the list

deps <- list(
"des_system_lib" = c("std", "synopsys", "std_cell_lib", "des_system_lib", "dw02", "dw01", "ramlib", "ieee"),
"dw01" = c("ieee", "dw01", "dware", "gtech", "dw04"),
"dw02" = c("ieee", "dw02", "dware"),
"dw03" = c("std", "synopsys", "dware", "dw03", "dw02", "dw01", "ieee", "gtech"),
"dw04" = c("dw04", "ieee", "dw01", "dware", "gtech"),
"dw05" = c("dw05", "ieee", "dware"),
"dw06" = c("dw06", "ieee", "dware"),
"dw07" = c("ieee", "dware"),
"dware" = c("ieee", "dware"),
"gtech" = c("ieee", "gtech"),
"ramlib" = c("std", "ieee"),
"std_cell_lib" = c("ieee", "std_cell_lib"),
"synopsys" = c())

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.

tsort <- function(deps) {
	nm <- names(deps)
	libs <- union(as.vector(unlist(deps)), nm)
	
	s <- c()
	# first libs that depend on nothing
	for(x in libs) {
		if(!(x %in% nm)) {
			s <- c(s, x)
		}
	}
	
	k <- 1
	while(k > 0) {
		k <- 0
		for(x in setdiff(nm, s)) {
			r <- c(s, x)
			if(length(setdiff(deps[[x]], r)) == 0) {
				s <- r
				k <- 1
			}
		}
	}
	
	if(length(s) < length(libs)) {
		v <- setdiff(libs, s)
		stop(sprintf("Unorderable items :\n%s", paste("", v, sep="", collapse="\n")))
	}
	
	s
}

On the given example :

tsort(deps)
# [1] "std"            "ieee"           "dware"          "gtech"          "ramlib"        
# [6] "std_cell_lib"   "synopsys"       "dw01"           "dw02"           "dw03"          
#[11] "dw04"           "dw05"           "dw06"           "dw07"           "des_system_lib"

If dw01 depends on dw04 as well :

Unorderable items :
des_system_lib
dw01
dw04
dw03

Racket[edit]

#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))

Output:

'(synopsys ieee dware gtech std_cell_lib std ramlib dw07 dw06 dw05 dw01 dw04 dw02 dw03 des_system_lib)

Raku[edit]

(formerly Perl 6)

Translation of: Perl
Works with: rakudo version 2016.01
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);
Output:
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

Some differences from the Perl 5 version include use of formal parameters; use of » 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 => 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 [qw(...)].

REXX[edit]

Translation of: FORTRAN 77

Some of the FORTRAN 77 statements were converted to   do   loops (or   do   structures),   and
some variables were   camel capitalized.

/*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
output:
═══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.)

Ruby[edit]

Uses the TSort module from the Ruby stdlib.

require 'tsort'
class Hash
  include TSort
  alias tsort_each_node each_key
  def tsort_each_child(node, &block)
    fetch(node).each(&block)
  end
end

depends = {}
DATA.each do |line|
  key, *libs = line.split
  depends[key] = libs
  libs.each {|lib| depends[lib] ||= []}
end

begin
  p depends.tsort
  depends["dw01"] << "dw04"
  p depends.tsort
rescue TSort::Cyclic => e
  puts "\ncycle detected: #{e}"
end

__END__
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
Output:
["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"]

Rust[edit]

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),
    }
}

Output:

["std", "synopsys", "ieee", "std_cell_lib", "ramlib", "gtech", "dware", "dw07", "dw06", "dw05", "dw02", "dw01", "dw04", "dw03", "des_system_lib"]

Output if we make dw01 depend on dw04 by changing input to

"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",
"Cycle detected among {\"dw03\", \"des_system_lib\", \"dw04\", \"dw01\"}"

Scheme[edit]

Translation of: Python
(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))

Sidef[edit]

Translation of: Perl
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);
Output:
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

Swift[edit]

Translation of: Rust
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))!)
Output:
["ieee", "std_cell_lib", "gtech", "dware", "dw07", "dw06", "dw05", "dw02", "dw01", "dw04", "std", "ramlib", "synopsys", "dw03", "des_system_lib"]

Tailspin[edit]

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, to: $}; <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
Output:
[[std, synopsys, ieee], [ramlib, dware, std_cell_lib, gtech], [dw01, dw02, dw05, dw06, dw07], [dw03, dw04, des_system_lib]]

Tcl[edit]

Works with: Tcl version 8.5
package require Tcl 8.5
proc topsort {data} {
    # Clean the data
    dict for {node depends} $data {
	if {[set i [lsearch -exact $depends $node]] >= 0} {
	    set depends [lreplace $depends $i $i]
	    dict set data $node $depends
	}
	foreach node $depends {dict lappend data $node}
    }
    # Do the sort
    set sorted {}
    while 1 {
	# Find available nodes
	set avail [dict keys [dict filter $data value {}]]
	if {![llength $avail]} {
	    if {[dict size $data]} {
		error "graph is cyclic, possibly involving nodes \"[dict keys $data]\""
	    }
	    return $sorted
	}
	# Note that the lsort is only necessary for making the results more like other langs
	lappend sorted {*}[lsort $avail]
        # Remove from working copy of graph
	dict for {node depends} $data {
	    foreach n $avail {
		if {[set i [lsearch -exact $depends $n]] >= 0} {
		    set depends [lreplace $depends $i $i]
		    dict set data $node $depends
		}
	    }
	}
	foreach node $avail {
	    dict unset data $node
	}
    }
}

Demonstration code (which parses it from the format that the puzzle was posed in):

set inputData {
    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
}
foreach line [split $inputData \n] {
    if {[string trim $line] eq ""} continue
    dict set parsedData [lindex $line 0] [lrange $line 1 end]
}
puts [topsort $parsedData]

Sample output:

ieee std synopsys dware gtech ramlib std_cell_lib dw01 dw02 dw05 dw06 dw07 des_system_lib dw03 dw04

If the suggested extra arc is added, this is the error output:

graph is cyclic, possibly involving nodes "des_system_lib dw01 dw03 dw04"

UNIX Shell[edit]

The Unix tsort(1) utility does a topological sort. Each line of input must have two items in order, like 'std des_system_lib'.[4]

Works with: Bourne Shell
$ 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
> 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         
> !
ieee
dware
dw02
dw05
dw06
dw07
gtech
dw01
dw04
std_cell_lib
synopsys
std
dw03
ramlib
des_system_lib

If the graph of dependencies contains a cycle, BSD's tsort(1) will print messages to standard error, break the cycle (by deleting one of the dependencies), continue the sort, and exit 0. So if dw04 becomes a dependency of dw01, then tsort(1) finds the cycle between dw01 and dw04.

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

Ursala[edit]

The tsort function takes a list of pairs <(lib: <dep...>)...> and returns a pair of lists (<lib...>,<lib...>) with the topologically sorted libraries on the left and the unorderable libraries, if any, on the right. Self-dependences are ignored and unlisted libraries are presumed independent.

tsort = ~&nmnNCjA*imSLs2nSjiNCSPT; @NiX ^=lxPrnSPX ^(~&rlPlT,~&rnPrmPljA*D@r)^|/~& ~&m!=rnSPlX

test program:

#import std                     
                                
dependence_table = -[           
                                
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         ]-

parse = ~&htA*FS+ sep` *tttt

#show+

main = <.~&l,@r ~&i&& 'unorderable: '--> mat` ~~ tsort parse dependence_table

With the given table, the output is

std ieee synopsys std_cell_lib ramlib gtech dware dw07 dw06 dw05 dw02 dw01 dw04 dw03 des_system_lib

When the suggested dependence is added, the output becomes

std ieee synopsys std_cell_lib ramlib gtech dware dw07 dw06 dw05 dw02
unorderable: des_system_lib dw01 dw03 dw04

VBScript[edit]

Implementation[edit]
class topological
	dim dictDependencies
	dim dictReported
	dim depth
	
	sub class_initialize
		set dictDependencies = createobject("Scripting.Dictionary")
		set dictReported = createobject("Scripting.Dictionary")
		depth = 0
	end sub
	
	sub reset
		dictReported.removeall
	end sub
	
	property let dependencies( s )
		'assuming token tab token-list newline
		dim i, j ,k
		dim aList
		dim dep
		dim a1
		aList = Split( s, vbNewLine )
		'~ remove empty lines at end
		do while aList( UBound( aList ) ) = vbnullstring
			redim preserve aList( UBound( aList ) - 1 )
		loop

		for i = lbound( aList ) to ubound( aList )
			aList( i ) = Split( aList( i ), vbTab, 2 )
			a1 = Split( aList( i )( 1 ), " " )
			k = 0
			for j = lbound( a1) to ubound(a1)
				if a1(j) <> aList(i)(0) then
					a1(k) = a1(j)
					k = k + 1
				end if
			next
			redim preserve a1(k-1)
			aList(i)(1) = a1
		next
		for i = lbound( aList ) to ubound( aList )
			dep = aList(i)(0)
			if not dictDependencies.Exists( dep ) then
				dictDependencies.add dep, aList(i)(1)
			end if
		next
		
	end property
	
	sub resolve( s )
		dim i 
		dim deps
		'~ wscript.echo string(depth,"!"),s
		depth = depth + 1
		if dictDependencies.Exists(s) then
			deps = dictDependencies(s)
			for i = lbound(deps) to ubound(deps)
				resolve deps(i)
			next
		end if
		if not seen(s) then
			wscript.echo s
			see s
		end if
		depth = depth - 1
	end sub

	function seen( key )
		seen = dictReported.Exists( key )
	end function
	
	sub see( key )
		dictReported.add key, ""
	end sub
	
	property get keys
		keys = dictDependencies.keys
	end property
end class
Invocation[edit]
dim toposort
set toposort = new topological
toposort.dependencies = "des_system_lib	std synopsys std_cell_lib des_system_lib dw02 dw01 ramlib ieee" & vbNewLine & _
	"dw01	ieee dw01 dware gtech" & vbNewLine & _
	"dw02	ieee dw02 dware" & vbNewLine & _
	"dw03	std synopsys dware dw03 dw02 dw01 ieee gtech" & vbNewLine & _
	"dw04	dw04 ieee dw01 dware gtech" & vbNewLine & _
	"dw05	dw05 ieee dware" & vbNewLine & _
	"dw06	dw06 ieee dware" & vbNewLine & _
	"dw07	ieee dware" & vbNewLine & _
	"dware	ieee dware" & vbNewLine & _
	"gtech	ieee gtech" & vbNewLine & _
	"ramlib	std ieee" & vbNewLine & _
	"std_cell_lib	ieee std_cell_lib" & vbNewLine & _
	"synopsys	"

dim k
for each k in toposort.keys
	wscript.echo "----- " & k
	toposort.resolve k
	wscript.echo "-----"
	toposort.reset
next
Output[edit]
----- des_system_lib
std
synopsys
ieee
std_cell_lib
dware
dw02
gtech
dw01
ramlib
des_system_lib
-----
----- dw01
ieee
dware
gtech
dw01
-----
----- dw02
ieee
dware
dw02
-----
----- dw03
std
synopsys
ieee
dware
dw02
gtech
dw01
dw03
-----
----- dw04
ieee
dware
gtech
dw01
dw04
-----
----- dw05
ieee
dware
dw05
-----
----- dw06
ieee
dware
dw06
-----
----- dw07
ieee
dware
dw07
-----
----- dware
ieee
dware
-----
----- gtech
ieee
gtech
-----
----- ramlib
std
ieee
ramlib
-----
----- std_cell_lib
ieee
std_cell_lib
-----
----- synopsys
synopsys
-----

Visual Basic .NET[edit]

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.

' 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) {}