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
Download
Copy to clipboard1 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)
|
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.