Author belopolsky
Recipients belopolsky, christian.heimes, eric.smith, martin.panter, rhettinger, terry.reedy, tshepang
Date 2019-01-17.00:43:56
SpamBayes Score -1.0
Marked as misclassified Yes
Message-id <1547685836.53.0.0918508657671.issue17005@roundup.psfhosted.org>
In-reply-to
Content
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
History
Date User Action Args
2019-01-17 00:43:57belopolskysetrecipients: + belopolsky, rhettinger, terry.reedy, eric.smith, christian.heimes, tshepang, martin.panter
2019-01-17 00:43:56belopolskysetmessageid: <1547685836.53.0.0918508657671.issue17005@roundup.psfhosted.org>
2019-01-17 00:43:56belopolskylinkissue17005 messages
2019-01-17 00:43:56belopolskycreate