Alexander Belopolsky <alexander.belopol...@gmail.com> added the comment:
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 ---------- _______________________________________ Python tracker <rep...@bugs.python.org> <https://bugs.python.org/issue17005> _______________________________________ _______________________________________________ Python-bugs-list mailing list Unsubscribe: https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com