Welcome, guest | Sign In | My Account | Store | Cart

Shows the order in which "tasks" can be "done".
Groups tasks that can be done simultaneously.

Python, 30 lines
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
def dep(arg):
    '''
        Dependency resolver

    "arg" is a dependency dictionary in which
    the values are the dependencies of their respective keys.
    '''
    d=dict((k, set(arg[k])) for k in arg)
    r=[]
    while d:
        # values not in keys (items without dep)
        t=set(i for v in d.values() for i in v)-set(d.keys())
        # and keys without value (items without dep)
        t.update(k for k, v in d.items() if not v)
        # can be done right away
        r.append(t)
        # and cleaned up
        d=dict(((k, v-t) for k, v in d.items() if v))
    return r

if __name__=='__main__':
    d=dict(
        a=('b','c'),
        b=('c','d'),
        e=(),
        f=('c','e'),
        g=('h','f'),
        i=('f',)
    )
    print dep(d)

Inspired by Recipe 576569

1 comment

Alice Bevan-McGregor 9 years, 1 month ago  # | flag

How would you go about extending this <strike>obfuscated</strike> "space efficient" algorithm to deal with pathological cases, specifically circular dependencies?

Created by Louis RIVIERE on Sun, 23 Nov 2008 (MIT)
Python recipes (4591)
Louis RIVIERE's recipes (13)

Required Modules

  • (none specified)

Other Information and Tasks