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

This recipe shows how to take a list of objects, each with their own list of dependencies, and resolve them to proper order. It includes some poor mans circular dependency detection (very poor mans).

Python, 53 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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
#!/usr/bin/env python

class P(object):
    def __init__(self, pkg, requires):
        self.requires = requires
        self.pkg      = pkg
        self.Required = 0

    def __str__(self):
        return self.pkg

    def __repr__(self):
        return self.__str__()

    def Require(self, pkg):
        if str(pkg) in self.requires:
            return True
        return False


objs = []
# The proper dependancy order is:
# e f b g d c a
objs.append(P('a', ['b', 'c', 'd']))
objs.append(P('b', ['f']))
objs.append(P('c', ['d', 'e']))
objs.append(P('d', ['g']))
objs.append(P('e', []))
objs.append(P('f', ['e']))
objs.append(P('g', []))

print(objs)
changes = True
iters   = 0
while changes:
    changes = False
    if iters >= 5000:
        print('Poor man\'s circular dependancy detection triggered!')
        break
    else:
        iters += 1
    for a in range(0, len(objs)):
        for b in range(0, len(objs)):
            if objs[b].Require(objs[a]):
                if b < a:
                    objs.insert(a, objs.pop(b))
                    changes = True
                    break
        if changes:
            break
    if not changes:
        break
print(objs)

1 comment

Mike 'Fuzzy' Partin (author) 5 years, 7 months ago  # | flag

So that it's clearly stated, this is a slight variation of a basic bubble sort. Large data sets would benefit from a different solution.

Created by Mike 'Fuzzy' Partin on Thu, 14 Apr 2016 (BSD)
Python recipes (4591)
Mike 'Fuzzy' Partin's recipes (12)

Required Modules

  • (none specified)

Other Information and Tasks