jit_toposort.py

def jit_toposort(dep_map):
    "expects a dict of {item: set([deps])}"
    ret, orig_dep_map, dep_map = [], dep_map, dict(dep_map)
    if not dep_map:
        return []
    extras = set.union(*dep_map.values()) - set(dep_map)
    dep_map.update([(k, set()) for k in extras])
    remaining = dict(dep_map)
    ready = set()
    while remaining:
        cur = set([item for item, deps in remaining.items() if not deps])
        if not cur:
            break
        ready.update(cur)
        cur_used = set([r for r in ready
                        if any([r in orig_dep_map[c] for c in cur])])
        ret.append(cur_used)
        ready = ready - cur_used
        remaining = dict([(item, deps - cur) for item, deps
                          in remaining.items() if item not in cur])
    if ready:
        ret.append(ready)
    if remaining:
        raise ValueError('unresolvable dependencies: %r' % remaining)
    return ret[1:]  # nothing's every used before the first thing, so snip snip