Anonymous user
Topological sort: Difference between revisions
→{{header|Python}}: Works with Python 2.6.1 aand 3.1 (tested)
(→{{header|Python}}: Works with Python 2.6.1 aand 3.1 (tested)) |
|||
Line 31:
=={{header|Python}}==
<lang python>
from functools import reduce
except:
pass
from pprint import pprint as pp
from copy import deepcopy
class CyclicDependencyError(Exception): pass
'''
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 = {
Line 52 ⟶ 75:
def toposort(dependencies):
givenchildren = set(dependencies.
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.
Line 60 ⟶ 86:
data[child] = set() # No parents
# Self dependencies are no dependencies
for child, parents in data.
parents.discard(child)
order =
while data:
nocurrentdependencies = [child
for child, parents in data.
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.
parents
for child in nocurrentdependencies:
del data[child]
Line 80 ⟶ 107:
return order
print (', '.join( toposort(data) ))
</lang>
Ordered output:
Line 88 ⟶ 116:
<pre>
Traceback (most recent call last):
File "C:\Documents and Settings\All Users\Documents\Paddys\topological_sort.py", line
print (', '.join( toposort(data) ))
File "C:\Documents and Settings\All Users\Documents\Paddys\topological_sort.py", line
raise CyclicDependencyError
CyclicDependencyError:
=={{header|Ruby}}==
| |||