Topological sort

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. The task is to 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 dependants, (sic), have no dependants 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.

Common Lisp

<lang lisp>(defun topological-sort (graph &key (test 'eql))

 "Graph is an association list whose keys are objects and whose

values are lists of objects on which the corresponding key depends. 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)))))))</lang>

Provided example in which all items can be sorted:

<lang lisp>> (defparameter *dependency-graph*

 '((des-system-lib   std synopsys std-cell-lib des-system-lib dw02 dw01 ramlib ieee)
   (dw01             ieee dw01 dware gtech)
   (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</lang>

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

<lang lisp>> (defparameter *dependency-graph*

 '((des-system-lib   std synopsys std-cell-lib des-system-lib dw02 dw01 ramlib ieee)
   (dw01             ieee dw01 dw04 dware gtech)
   (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

1. <EQL Hash Table{4} 200C9023>

> (describe (third /))

1. <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)</lang>

E

<lang e>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

}</lang>

<lang e>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))</lang>

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

Haskell

<lang haskell>import Data.List import Data.Maybe import Control.Arrow import System.Random import Control.Monad

combs 0 _ = [[]] combs _ [] = [] combs k (x:xs) = map (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 xs

     | (not.null) cycleDetect = error $ "Dependency cycle detected for libs " ++ show cycleDetect 
     | otherwise              = foldl makePrecede [] dB

  where dB = map ((\(x,y) -> (x,y \\ x)). (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)
                      $ map (\[(a,as), (b,bs)] -> (a `intersect` bs) ++ (b `intersect`as))
                      $ combs 2 dB</lang>

output: <lang haskell>*Main> toposort depLibs ["std","synopsys","ieee","std_cell_lib","dware","dw02","gtech","dw01","ramlib","des_system_lib","dw03","dw04","dw05","dw06","dw07"]

• Main> toposort $ (\(xs,(k,ks):ys) -> xs++ (k,ks++" dw04"):ys) $ splitAt 1 depLibs
  • • Exception: Dependency cycle detected for libs "dw01","dw04"</lang>

J

<lang J>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

)</lang>

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

Here is an alternate implementation which uses a slightly different representation for the dependencies:

<lang J>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

)</lang>

It's results are identical to the first implementation, but this might be more efficient in typical cases.

OCaml

<lang ocaml>let dep_libs = [

 ("des_system_lib", ["std"; "synopsys"; "std_cell_lib"; "des_system_lib"; "dw02"; "dw01"; "ramlib"; "ieee"]);
 ("dw01",           (*"dw04"::*)["ieee"; "dw01"; "dware"; "gtech"]);
 ("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 libs = (* list items, each being unique *)

 let rec aux acc = function
 | [] -> (acc)
 | x::xs -> aux (if List.mem x acc then acc else x::acc) xs
 in
 aux [] (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);

</lang>

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

Python

<lang python>try:

   from functools import reduce

except:

   pass

from pprint import pprint as pp from copy import deepcopy

class CyclicDependencyError(Exception): 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 toposort(dependencies):

   givenchildren = set(dependencies.keys())
   givenparents = reduce(set.union,
                         ( set(p for p in parents) 
                           for child, parents in dependencies.items() )
                        )
   data = deepcopy(dependencies)
   # Every parent is also a child, sometimes of nothing.
   originalchildren = givenparents - givenchildren
   for child in originalchildren:
       data[child] = set() # No parents
   # Self dependencies are no dependencies
   for child, parents in data.items():
       parents.discard(child)

   order = list()

   while data:
       nocurrentdependencies = [child 
                                for child, parents in data.items()
                                if not parents]
       if not nocurrentdependencies and data:
           #raise CyclicDependencyError, "Does not involve items: %s" % order
           raise CyclicDependencyError("Involving items from: %s" % data.keys())
       order += sorted(nocurrentdependencies)
       nocurrentdependencies = set(nocurrentdependencies)
       for child, parents in data.items():
           parents.difference_update(nocurrentdependencies)
       for child in nocurrentdependencies:
           del data[child]

   return order

print (', '.join( toposort(data) ))</lang>

Ordered output:

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 77, in <module>
    print (', '.join( toposort(data) ))
  File "C:\Documents and Settings\All Users\Documents\Paddys\topological_sort.py", line 67, in toposort
    raise CyclicDependencyError("Involving items from: %s" % data.keys())
CyclicDependencyError: Involving items from: ['des_system_lib', 'dw04', 'dw03', 'dw01']

Ruby

Uses the TSort module from the Ruby stdlib. <lang ruby>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|

 libs = line.split(' ')
 key = libs.shift
 depends[key] = libs
 libs.each {|lib| depends[lib] ||= []}

end

begin

 p depends.tsort
 depends["dw01"] << "dw04"
 p depends.tsort

rescue TSort::Cyclic => e

 puts "cycle 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</lang> Produces:

["ieee", "dware", "gtech", "dw01", "dw02", "std", "synopsys", "dw03", "dw04", "dw05", "std_cell_lib", "ramlib", "des_system_lib", "dw06", "dw07"]
cycle detected: topological sort failed: ["dw01", "dw04"]

Tcl

Works with: Tcl version 8.5

<lang tcl>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 }

   }

}</lang> Demonstration code (which parses it from the format that the puzzle was posed in): <lang tcl>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]</lang> 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

The unix tsort utility does a topological sort where dependencies on multiple items must be reformatted as multiple lines of dependencies of an item and only one dependant.

<lang bash>bash$ tsort <<! > des_system_lib des_system_lib > des_system_lib dw01 > des_system_lib dw02 > des_system_lib ieee > des_system_lib ramlib > des_system_lib std > des_system_lib std_cell_lib > des_system_lib synopsys > dw01 dw01 > dw01 dware > dw01 gtech > dw01 ieee > dw02 dw02 > dw02 dware > dw02 ieee > dw03 dw01 > dw03 dw02 > dw03 dw03 > dw03 dware > dw03 gtech > dw03 ieee > dw03 std > dw03 synopsys > dw04 dw01 > dw04 dw04 > dw04 dware > dw04 gtech > dw04 ieee > dw05 dw05 > dw05 dware > dw05 ieee > dw06 dw06 > dw06 dware > dw06 ieee > dw07 dware > dw07 ieee > dware dware > dware ieee > gtech gtech > gtech ieee > ramlib ieee > ramlib std > std_cell_lib ieee > std_cell_lib std_cell_lib ! des_system_lib dw03 dw04 dw05 dw06 dw07 std_cell_lib ramlib synopsys dw02 dw01 std gtech dware ieee bash$</lang>

Ursala

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. <lang Ursala>tsort = ~&nmnNCjA*imSLs2nSjiNCSPT; @NiX ^=lxPrnSPX ^(~&rlPlT,~&rnPrmPljA*D@r)^|/~& ~&m!=rnSPlX</lang> test program: <lang Ursala>#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

1. show+

main = <.~&l,@r ~&i&& 'unorderable: '--> mat` ~~ tsort parse dependence_table</lang> 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