Source Code for Module park.modelling.deps

 1  # This program is public domain 
 2  # Author: Paul Kienzle 
 3  """ 
 4  Functions for manipulating dependencies. 
 5   
 6  Parameter values must be updated in the correct order.  If parameter A 
 7  depends on parameter B, then parameter B must be evaluated first. 
 8  """ 
 9   
10 -def order_dependencies(pairs): 
11      """ 
12      Order elements from pairs so that b comes before a in the 
13      ordered list for all pairs (a,b). 
14      """ 
15      #print "order_dependencies",pairs 
16      emptyset = set() 
17      order = [] 
18   
19      # Break pairs into left set and right set 
20      left,right = [set(s) for s in zip(*pairs)] if pairs != [] else ([],[]) 
21      while pairs != []: 
22          #print "within",pairs 
23          # Find which items only occur on the right 
24          independent = right - left 
25          if independent == emptyset: 
26              cycleset = ", ".join(str(s) for s in left) 
27              raise ValueError,"Cyclic dependencies amongst %s"%cycleset 
28   
29          # The possibly resolvable items are those that depend on the independents 
30          dependent = set([a for a,b in pairs if b in independent]) 
31          pairs = [(a,b) for a,b in pairs if b not in independent] 
32          if pairs == []: 
33              resolved = dependent 
34          else: 
35              left,right = [set(s) for s in zip(*pairs)] 
36              resolved = dependent - left 
37          #print "independent",independent,"dependent",dependent,"resolvable",resolved 
38          order += resolved 
39          #print "new order",order 
40      order.reverse() 
41      return order 
42   
43  # ========= Test code ======== 
44 -def _check(msg,pairs): 
45      """ 
46      Verify that the list n contains the given items, and that the list 
47      satisfies the partial ordering given by the pairs in partial order. 
48      """ 
49      left,right = zip(*pairs) if pairs != [] else ([],[]) 
50      items = set(left) 
51      n = order_dependencies(pairs) 
52      if set(n) != items or len(n) != len(items): 
53          n.sort() 
54          items = list(items); items.sort() 
55          raise Exception,"%s expect %s to contain %s for %s"%(msg,n,items,pairs) 
56      for lo,hi in pairs: 
57          if lo in n and hi in n and n.index(lo) >= n.index(hi): 
58              raise Exception,"%s expect %s before %s in %s for %s"%(msg,lo,hi,n,pairs) 
59   
60 -def test(): 
61      import numpy 
62   
63      # Null case 
64      _check("test empty",[]) 
65   
66      # Some dependencies 
67      _check("test1",[(2,7),(1,5),(1,4),(2,1),(3,1),(5,6)]) 
68      _check("test1 renumbered",[(6,1),(7,3),(7,4),(6,7),(5,7),(3,2)]) 
69      _check("test1 numpy",numpy.array([(2,7),(1,5),(1,4),(2,1),(3,1),(5,6)])) 
70   
71      # No dependencies 
72      _check("test2",[(4,1),(3,2),(8,4)]) 
73   
74      # Cycle test 
75      pairs = [(1,4),(4,3),(4,5),(5,1)] 
76      try: n = order_dependencies(pairs) 
77      except ValueError: pass 
78      else: raise Exception,"test3 expect ValueError exception for %s"%(pairs,) 
79   
80      # large test for gross speed check 
81      A = numpy.random.randint(4000,size=(1000,2)) 
82      A[:,1] += 4000  # Avoid cycles 
83      _check("test-large",A) 
84   
85      # depth tests 
86      k = 200 
87      A = numpy.array([range(0,k),range(1,k+1)]).T 
88      _check("depth-1",A) 
89   
90      A = numpy.array([range(1,k+1),range(0,k)]).T 
91      _check("depth-2",A) 
92   
93  if __name__ == "__main__": 
94      test() 
95