Generic topological sort in python

tsort.py

#!/usr/bin/env python3
from collections import defaultdict


def tsorted(pairs, reverse=False):
    incoming = defaultdict(set)
    outgoing = defaultdict(set)
    for src, dst in pairs:
        incoming[dst].add(src)
        outgoing[src].add(dst)
    if reverse:
        incoming, outgoing = outgoing, incoming
    leaves = list(outgoing.keys() - incoming.keys())
    while leaves:
        leaf = leaves.pop()
        yield leaf
        for dst in outgoing[leaf].copy():
            incoming[dst].remove(leaf)
            if not incoming[dst]:
                leaves.append(dst)
                del incoming[dst]
            outgoing[leaf].remove(dst)
    if incoming:
        raise Exception("Cycles detected")


if __name__ == "__main__":
    def edges():
        yield from [('title_bar', 'safe'),
                    ('title_text', 'title_bar'),
                    ('title_text', 'title_icon'),
                    ('bg', 12007),
                    ('safe', 'bg'),
                    ('bottom_bar', 'bg'),
                    ('title_icon', 'title_bar'),
                    ('copyright', 'bottom_bar')]

    for item in tsorted(edges(), reverse=True):
        print(repr(item))