| 20 | } |
| 21 | |
| 22 | def toposort2(data): |
| 23 | for k, v in data.items(): |
| 24 | v.discard(k) # Ignore self dependencies |
| 25 | extra_items_in_deps = reduce(set.union, data.values()) - set(data.keys()) |
| 26 | data.update({item:set() for item in extra_items_in_deps}) |
| 27 | while True: |
| 28 | ordered = set(item for item,dep in data.items() if not dep) |
| 29 | if not ordered: |
| 30 | break |
| 31 | yield ' '.join(sorted(ordered)) |
| 32 | data = {item: (dep - ordered) for item,dep in data.items() |
| 33 | if item not in ordered} |
| 34 | assert not data, "A cyclic dependency exists amongst %r" % data |
| 35 | |
| 36 | print ('\n'.join( toposort2(data) )) |