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>
Oredered 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']