Given items that depend on other items, a topological sort arranges items in order that no one item precedes an item it depends on. In this example items are strings and dependencies are expressed in a dictionary whose keys are items and whose values are a set of dependent items. Note that the dict may contain self-dependencies (which are ignored), and dependent items that are not also dict keys, such as the item 'ieee'.
Python, 36 lines
Download
Copy to clipboard1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 | 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) ))
|
The output is line based where the topological order is between the lines. Many items may appear on one line which shows that there is no necessary ordering between those items of one line. The output:
ieee std synopsys
dware gtech ramlib std_cell_lib
dw01 dw02 dw05 dw06 dw07
des_system_lib dw03 dw04
This shows that 'ieee' and 'std' can be in any relative order, but both must precede 'dware'.
Your code assumes that (a) the input data consists of strings and (b) the lists of equal values need to be sorted. I'd replace the yield with:
and change the print to:
I state in the first paragraph, second sentence, that the items are strings. Thanks for reading that. The lists of equal values need not be further sorted so long as the topological order is preserved. The topological sort order is what the routine is about. Any further partial ordering detracts from the main function of topological sorting.
Maybe you have extra needs?
Yes, I do have extra needs. I've put an (IMHO) improved version of the program here. Inputs can be any hashable object, not just strings; the results are not sorted (the caller can do that if required); there's a doc-string explaining the format of the input and result; and the (simpler) example is in a doctest. The result is code that can be dropped into a program without any editing by the programmer.