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

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)

### Required Modules

• (none specified)