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.

Python

<lang python>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
       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:\Paddys\topological_sort.py", line 73, in <module>
    print (', '.join( toposort(data) ))
  File "C:\Paddys\topological_sort.py", line 63, in toposort
    raise CyclicDependencyError, "Does not involve items: %s" % order
CyclicDependencyError: Does not involve items: ['ieee', 'std', 'synopsys', 'dware', 'gtech', 'ramlib', 'std_cell_lib', 'dw02', 'dw05', 'dw06', 'dw07']

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

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.

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$