User Tools

Site Tools


Python Topological Sort
import functools
def toposort(data):
    """Argument is a dict mapping element to set of dependency elements."""
    data = dict((key, deps-set((key,))) for key, deps in data.iteritems()
                if not deps == set((key,)))
    gen = functools.reduce(set.union, data.itervalues()) - set(data.iterkeys())
    while True:
        yield gen
        data = dict((i, j - gen) for i, j in data.iteritems() if i not in gen)
        gen = set(i for i, j in data.iteritems() if not j)
        if not gen:
    if data:
        raise Exception("Cyclic dependencies, can't satisfy: %s" %
                        (" ".join("%r" % (i,) for i in data.keys()),))
notes/python_topological_sort.txt · Last modified: 2012/11/20 12:10 by andy