This snippet demonstrates a function to implement a simple topological sort in Python. This could be used to resolve a set of targets with dependencies between them, for example.

python_topological_sort.py

import functools

def toposort(data):
    """Argument is a dict mapping element to set of dependency elements.

    Generator yields sets of elements in an appropriate order to satisfy
    dependencies. Each element in the set from a single iteration may be
    processed in parallel (i.e. they have no dependencies between them).
    """

    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:
            break
    if data:
        raise Exception("Cyclic dependencies, can't satisfy: %s" %
                        (" ".join("%r" % (i,) for i in data.keys()),))


acyclic_deps = { "A": set(("B", "D", "E")),
                 "B": set(("C", "D")),
                 "D": set(("C",)),
                 "E": set(("E",)) }

print ", ".join(repr(i) for i in toposort(acyclic_deps))

cyclic_deps = { "A": set(("B",)),
                "B": set(("C", "D")),
                "D": set(("C", "A")) }

try:
    print ", ".join(toposort(cyclic_deps))
except Exception, e:
    print "Error: %s" % (e,)