Mercurial > codeOptimizer

comparison DepGraph.py @ 4:3a56cd936c59

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Cleanup some code. Add code for breaking loops in the dependency tree.
author Tom Fredrik Blenning Klaussen <bfg@blenning.no>
date Mon, 24 Sep 2012 01:16:43 +0200
parents a1224150b8f6
children 8952a4f7aa95
comparison
equal deleted inserted replaced
3:f65c2d63ab66 4:3a56cd936c59
1 import copy, sys
1 from types import * 2 from types import *
2 3
3 class DepGraph: 4 class DepGraph:
4 def __init__(self): 5 def __init__(self):
5 self.deps = [] 6 self.deps = []
9 if value in self.values: 10 if value in self.values:
10 raise ValueError 11 raise ValueError
11 self.values.append(value) 12 self.values.append(value)
12 13
13 14
14 def addDependency(self, src, dst): 15 def rightSize(self):
15 if not type(dst) is ListType:
16 dst = [ dst ]
17
18 vl = len(self.values) 16 vl = len(self.values)
19 dl = len(self.deps) 17 dl = len(self.deps)
20 si = self.values.index(src)
21
22 18
23 if dl != vl: 19 if dl != vl:
24 full = [] 20 full = []
25 for i in range(0, vl): 21 for i in range(0, vl):
26 full.append(False) 22 full.append(False)
30 exp.append(False) 26 exp.append(False)
31 self.deps.append(full[:]) 27 self.deps.append(full[:])
32 28
33 for i in range(0, dl): 29 for i in range(0, dl):
34 self.deps[i].append(exp[:]) 30 self.deps[i].append(exp[:])
35 31
32 def addDependency(self, src, dst):
33 if not type(dst) is ListType:
34 dst = [ dst ]
35
36 self.rightSize()
37
38 si = self.values.index(src)
36 for d in dst: 39 for d in dst:
37 if d in self.values: 40 if d in self.values:
38 di = self.values.index(d) 41 di = self.values.index(d)
39 self.deps[si][di] = True 42 self.deps[si][di] = True
40 43
44 @staticmethod
45 def identifyStronglyConnectedComponents(deps):
46 index=0
47 S=[]
48 vindex={}
49 lowlink={}
50 retVal=[]
51 for v in range(len(deps)):
52 if not v in vindex:
53 retVal.extend(DepGraph.strongconnect(deps, v, index, vindex, lowlink, S))
54 return retVal
55
56 @staticmethod
57 def strongconnect(deps, v, index, vindex, lowlink, S):
58 retVal = []
59 # Set the depth index for v to the smallest unused index
60 vindex[v] = index
61 lowlink[v] = index
62 #print index
63 index += 1
64 S.append(v)
65
66 # Consider successors of v
67 for w in range(len(deps)):
68 if not deps[w][v]:
69 continue
70 if not w in vindex:
71 # Successor w has not yet been visited; recurse on it
72 res = DepGraph.strongconnect(deps, w, index, vindex, lowlink, S)
73 retVal.extend(res)
74 lowlink[v] = min(lowlink[v], lowlink[w])
75 elif w in S:
76 # Successor w is in stack S and hence in the current SCC
77 lowlink[v] = min(lowlink[v], vindex[w])
78
79 # If v is a root node, pop the stack and generate an SCC
80 if lowlink[v] == vindex[v]:
81 #start a new strongly connected component
82 component = []
83 w = None
84 while w != v:
85 w = S.pop()
86 #add w to current strongly connected component
87 component.append(w)
88 retVal.append(component)
89 return retVal
90
91 @staticmethod
92 def dissolveStronglyConnectedComponents(deps):
93 dissolved = True
94 while dissolved:
95 dissolved = False
96 strong = DepGraph.identifyStronglyConnectedComponents(deps)
97 for s in strong:
98 if len(s) > 1:
99 #We remove the first dependency, and see how it goes.
100 v = s[0]
101 for w in s[1:]:
102 if deps[w][v]:
103 #print "Remove link %d -> %d" % (w, v)
104 deps[w][v] = False
105 dissolved = True
106 break
107 return deps
108 sys.exit(1)
41 109
42 @staticmethod 110 @staticmethod
43 def directedGraphInternal(deps): 111 def directedGraphInternal(deps):
44 dl = len(deps) 112 dl = len(deps)
45 myVals = [] 113 startPoints = []
46 for i in range(dl): 114 for i in range(dl):
47 if not max(deps[i]): 115 if not max(deps[i]):
48 myVals.append(i) 116 startPoints.append(i)
49 117
50 for i in myVals: 118 for i in startPoints:
51 for j in range(dl): 119 for j in range(dl):
52 deps[j][i] = False 120 deps[j][i] = False
53 121
54 retVal = myVals 122 retVal = startPoints
55 123
56 if len(deps) != len(myVals): 124 if len(deps) != len(startPoints):
57 subVals = self.directedGraphInternal(deps) 125 subVals = DepGraph.directedGraphInternal(deps)
58 for val in myVals: 126 for val in startPoints:
59 if val in subVals: 127 if val in subVals:
60 ind = subVals.index(val) 128 ind = subVals.index(val)
61 del subVals[ind] 129 del subVals[ind]
62 130
63 if subVals: 131 if subVals:
78 else: 146 else:
79 s += '0' 147 s += '0'
80 res += s 148 res += s
81 return res 149 return res
82 150
83 def directedGraph(self): 151 def depGraphRepr(self):
84 deps = self.deps[:][:] 152 return self.printableDepgraph(self.deps)
153
154 def directedGraph(self, force = True):
155 deps = copy.deepcopy(self.deps)
156 if force:
157 deps = self.dissolveStronglyConnectedComponents(deps)
85 vals = self.directedGraphInternal(deps) 158 vals = self.directedGraphInternal(deps)
86 retVal = [] 159 retVal = []
87 for i in vals: 160 for i in vals:
88 retVal.append(self.values[i]) 161 retVal.append(self.values[i])
89 return retVal 162 return retVal