gistfile1.py

from collections import deque

def dependency_sort(initial, dependency_func):
    """
    Generic dependency sorting algorithm; supply an initial list of IDs as
    "initial", and a callable that takes an ID and returns a list of IDs as
    "dependencies".

    The resultant list is in order from leaf nodes (no dependencies) to stems.
    """
    # Turn the dependencies into a mapping of all nodes to their deps
    dependencies = list(initial)
    pending = deque(initial)
    mapping = {}
    while pending:
        current = pending.popleft()
        mapping[current] = [x for x in dependency_func(current) if x is not None]
        for dependency in mapping[current]:
            if dependency not in pending and dependency not in mapping:
                pending.append(dependency)
    # Build a sorted list based on that
    result = []
    while mapping:
        len_before = len(mapping)
        for node, dependencies in sorted(mapping.items()):
            if not dependencies or all((dependency in result) for dependency in dependencies):
                result.append(node)
                del mapping[node]
        if len(mapping) == len_before:
            raise ValueError("Circular dependency: %s" % mapping.keys())
    return result