Message333806
Here is an implementation that I've used for years. It is somewhat shorter than the one in PR 11583:
class CycleError(LogicalError, ValueError):
"""dependencies cycle detected
"""
def tsort(pairs):
"""topological sort
Just like unix tsort(1)
>>> tsort([(1, 2), (7, 8), (8, 10), (7, 4), (2, 3), (4, 10)])
[1, 7, 2, 8, 4, 3, 10]
>>> try:
... tsort([(1,2), (2,1)])
... except CycleError as e:
... print(e)
([], Counter({1: 1, 2: 1}), {1: [2], 2: [1]})
"""
# inspired by http://mail.python.org/pipermail/python-list/1999-July/002831.html
successors = {}
predecessor_counts = collections.Counter()
for x, y in pairs:
successors.setdefault(x, []).append(y)
predecessor_counts.setdefault(x, 0)
predecessor_counts[y] += 1
ordered = [x for x in predecessor_counts
if predecessor_counts[x] == 0]
for x in ordered:
del predecessor_counts[x]
for y in successors.get(x, ()):
predecessor_counts[y] -= 1
if predecessor_counts[y] == 0:
ordered.append(y)
if predecessor_counts:
raise CycleError(ordered, predecessor_counts, successors)
return ordered |
|
Date |
User |
Action |
Args |
2019-01-17 00:43:57 | belopolsky | set | recipients:
+ belopolsky, rhettinger, terry.reedy, eric.smith, christian.heimes, tshepang, martin.panter |
2019-01-17 00:43:56 | belopolsky | set | messageid: <1547685836.53.0.0918508657671.issue17005@roundup.psfhosted.org> |
2019-01-17 00:43:56 | belopolsky | link | issue17005 messages |
2019-01-17 00:43:56 | belopolsky | create | |
|