find "generations" of based on a dependency graph

topogen.py

from relativity import M2M

def generations(m2m):
    """
    m2m is {dependent: dependes-on}
    returns [{item, item, ...}, {item, item, ...}, ...] in topologically sorted order
    """
    m2m = m2m.copy()
    generations = []
    # first generation is things that have no dependencies
    cur_gen = set(m2m.inv.keys()) - set(m2m.keys())

    while cur_gen:
        generations.append(cur_gen)
        less_deps = set()  # items that have fewer dependencies once cur_gen are satisfied
        for item in cur_gen & set(m2m.inv.keys()):
            less_deps |= m2m.inv.pop(item)
        # next generation is things with less dependencies
        # that no longer have any dependencies
        cur_gen = less_deps - set(m2m.keys())

    if m2m:
        raise ValueError('circular dependency')

    return generations