Mercurial > codeOptimizer

annotate 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
Ignore whitespace changes - Everywhere: Within whitespace: At end of lines:
rev   line source
4
3a56cd936c59 Cleanup some code.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents: 1
diff changeset
1 import copy, sys
0
28b636105ed6 Working version of codeOptimizer.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
2 from types import *
28b636105ed6 Working version of codeOptimizer.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
3
28b636105ed6 Working version of codeOptimizer.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
4 class DepGraph:
28b636105ed6 Working version of codeOptimizer.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
5 def __init__(self):
28b636105ed6 Working version of codeOptimizer.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
6 self.deps = []
28b636105ed6 Working version of codeOptimizer.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
7 self.values = []
28b636105ed6 Working version of codeOptimizer.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
8
28b636105ed6 Working version of codeOptimizer.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
9 def add(self, value):
28b636105ed6 Working version of codeOptimizer.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
10 if value in self.values:
28b636105ed6 Working version of codeOptimizer.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
11 raise ValueError
28b636105ed6 Working version of codeOptimizer.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
12 self.values.append(value)
28b636105ed6 Working version of codeOptimizer.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
13
28b636105ed6 Working version of codeOptimizer.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
14
4
3a56cd936c59 Cleanup some code.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents: 1
diff changeset
15 def rightSize(self):
0
28b636105ed6 Working version of codeOptimizer.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
16 vl = len(self.values)
28b636105ed6 Working version of codeOptimizer.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
17 dl = len(self.deps)
28b636105ed6 Working version of codeOptimizer.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
18
28b636105ed6 Working version of codeOptimizer.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
19 if dl != vl:
28b636105ed6 Working version of codeOptimizer.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
20 full = []
28b636105ed6 Working version of codeOptimizer.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
21 for i in range(0, vl):
28b636105ed6 Working version of codeOptimizer.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
22 full.append(False)
28b636105ed6 Working version of codeOptimizer.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
23
28b636105ed6 Working version of codeOptimizer.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
24 exp = []
28b636105ed6 Working version of codeOptimizer.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
25 for i in range(dl, vl):
28b636105ed6 Working version of codeOptimizer.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
26 exp.append(False)
28b636105ed6 Working version of codeOptimizer.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
27 self.deps.append(full[:])
28b636105ed6 Working version of codeOptimizer.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
28
28b636105ed6 Working version of codeOptimizer.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
29 for i in range(0, dl):
28b636105ed6 Working version of codeOptimizer.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
30 self.deps[i].append(exp[:])
4
3a56cd936c59 Cleanup some code.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents: 1
diff changeset
31
3a56cd936c59 Cleanup some code.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents: 1
diff changeset
32 def addDependency(self, src, dst):
3a56cd936c59 Cleanup some code.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents: 1
diff changeset
33 if not type(dst) is ListType:
3a56cd936c59 Cleanup some code.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents: 1
diff changeset
34 dst = [ dst ]
3a56cd936c59 Cleanup some code.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents: 1
diff changeset
35
3a56cd936c59 Cleanup some code.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents: 1
diff changeset
36 self.rightSize()
3a56cd936c59 Cleanup some code.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents: 1
diff changeset
37
3a56cd936c59 Cleanup some code.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents: 1
diff changeset
38 si = self.values.index(src)
0
28b636105ed6 Working version of codeOptimizer.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
39 for d in dst:
28b636105ed6 Working version of codeOptimizer.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
40 if d in self.values:
28b636105ed6 Working version of codeOptimizer.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
41 di = self.values.index(d)
28b636105ed6 Working version of codeOptimizer.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
42 self.deps[si][di] = True
28b636105ed6 Working version of codeOptimizer.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
43
4
3a56cd936c59 Cleanup some code.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents: 1
diff changeset
44 @staticmethod
3a56cd936c59 Cleanup some code.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents: 1
diff changeset
45 def identifyStronglyConnectedComponents(deps):
3a56cd936c59 Cleanup some code.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents: 1
diff changeset
46 index=0
3a56cd936c59 Cleanup some code.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents: 1
diff changeset
47 S=[]
3a56cd936c59 Cleanup some code.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents: 1
diff changeset
48 vindex={}
3a56cd936c59 Cleanup some code.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents: 1
diff changeset
49 lowlink={}
3a56cd936c59 Cleanup some code.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents: 1
diff changeset
50 retVal=[]
3a56cd936c59 Cleanup some code.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents: 1
diff changeset
51 for v in range(len(deps)):
3a56cd936c59 Cleanup some code.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents: 1
diff changeset
52 if not v in vindex:
3a56cd936c59 Cleanup some code.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents: 1
diff changeset
53 retVal.extend(DepGraph.strongconnect(deps, v, index, vindex, lowlink, S))
3a56cd936c59 Cleanup some code.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents: 1
diff changeset
54 return retVal
3a56cd936c59 Cleanup some code.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents: 1
diff changeset
55
3a56cd936c59 Cleanup some code.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents: 1
diff changeset
56 @staticmethod
3a56cd936c59 Cleanup some code.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents: 1
diff changeset
57 def strongconnect(deps, v, index, vindex, lowlink, S):
3a56cd936c59 Cleanup some code.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents: 1
diff changeset
58 retVal = []
3a56cd936c59 Cleanup some code.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents: 1
diff changeset
59 # Set the depth index for v to the smallest unused index
3a56cd936c59 Cleanup some code.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents: 1
diff changeset
60 vindex[v] = index
3a56cd936c59 Cleanup some code.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents: 1
diff changeset
61 lowlink[v] = index
3a56cd936c59 Cleanup some code.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents: 1
diff changeset
62 #print index
3a56cd936c59 Cleanup some code.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents: 1
diff changeset
63 index += 1
3a56cd936c59 Cleanup some code.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents: 1
diff changeset
64 S.append(v)
3a56cd936c59 Cleanup some code.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents: 1
diff changeset
65
3a56cd936c59 Cleanup some code.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents: 1
diff changeset
66 # Consider successors of v
3a56cd936c59 Cleanup some code.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents: 1
diff changeset
67 for w in range(len(deps)):
3a56cd936c59 Cleanup some code.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents: 1
diff changeset
68 if not deps[w][v]:
3a56cd936c59 Cleanup some code.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents: 1
diff changeset
69 continue
3a56cd936c59 Cleanup some code.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents: 1
diff changeset
70 if not w in vindex:
3a56cd936c59 Cleanup some code.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents: 1
diff changeset
71 # Successor w has not yet been visited; recurse on it
3a56cd936c59 Cleanup some code.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents: 1
diff changeset
72 res = DepGraph.strongconnect(deps, w, index, vindex, lowlink, S)
3a56cd936c59 Cleanup some code.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents: 1
diff changeset
73 retVal.extend(res)
3a56cd936c59 Cleanup some code.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents: 1
diff changeset
74 lowlink[v] = min(lowlink[v], lowlink[w])
3a56cd936c59 Cleanup some code.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents: 1
diff changeset
75 elif w in S:
3a56cd936c59 Cleanup some code.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents: 1
diff changeset
76 # Successor w is in stack S and hence in the current SCC
3a56cd936c59 Cleanup some code.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents: 1
diff changeset
77 lowlink[v] = min(lowlink[v], vindex[w])
3a56cd936c59 Cleanup some code.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents: 1
diff changeset
78
3a56cd936c59 Cleanup some code.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents: 1
diff changeset
79 # If v is a root node, pop the stack and generate an SCC
3a56cd936c59 Cleanup some code.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents: 1
diff changeset
80 if lowlink[v] == vindex[v]:
3a56cd936c59 Cleanup some code.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents: 1
diff changeset
81 #start a new strongly connected component
3a56cd936c59 Cleanup some code.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents: 1
diff changeset
82 component = []
3a56cd936c59 Cleanup some code.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents: 1
diff changeset
83 w = None
3a56cd936c59 Cleanup some code.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents: 1
diff changeset
84 while w != v:
3a56cd936c59 Cleanup some code.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents: 1
diff changeset
85 w = S.pop()
3a56cd936c59 Cleanup some code.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents: 1
diff changeset
86 #add w to current strongly connected component
3a56cd936c59 Cleanup some code.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents: 1
diff changeset
87 component.append(w)
3a56cd936c59 Cleanup some code.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents: 1
diff changeset
88 retVal.append(component)
3a56cd936c59 Cleanup some code.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents: 1
diff changeset
89 return retVal
3a56cd936c59 Cleanup some code.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents: 1
diff changeset
90
3a56cd936c59 Cleanup some code.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents: 1
diff changeset
91 @staticmethod
3a56cd936c59 Cleanup some code.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents: 1
diff changeset
92 def dissolveStronglyConnectedComponents(deps):
3a56cd936c59 Cleanup some code.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents: 1
diff changeset
93 dissolved = True
3a56cd936c59 Cleanup some code.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents: 1
diff changeset
94 while dissolved:
3a56cd936c59 Cleanup some code.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents: 1
diff changeset
95 dissolved = False
3a56cd936c59 Cleanup some code.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents: 1
diff changeset
96 strong = DepGraph.identifyStronglyConnectedComponents(deps)
3a56cd936c59 Cleanup some code.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents: 1
diff changeset
97 for s in strong:
3a56cd936c59 Cleanup some code.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents: 1
diff changeset
98 if len(s) > 1:
3a56cd936c59 Cleanup some code.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents: 1
diff changeset
99 #We remove the first dependency, and see how it goes.
3a56cd936c59 Cleanup some code.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents: 1
diff changeset
100 v = s[0]
3a56cd936c59 Cleanup some code.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents: 1
diff changeset
101 for w in s[1:]:
3a56cd936c59 Cleanup some code.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents: 1
diff changeset
102 if deps[w][v]:
3a56cd936c59 Cleanup some code.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents: 1
diff changeset
103 #print "Remove link %d -> %d" % (w, v)
3a56cd936c59 Cleanup some code.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents: 1
diff changeset
104 deps[w][v] = False
3a56cd936c59 Cleanup some code.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents: 1
diff changeset
105 dissolved = True
3a56cd936c59 Cleanup some code.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents: 1
diff changeset
106 break
3a56cd936c59 Cleanup some code.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents: 1
diff changeset
107 return deps
3a56cd936c59 Cleanup some code.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents: 1
diff changeset
108 sys.exit(1)
0
28b636105ed6 Working version of codeOptimizer.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
109
28b636105ed6 Working version of codeOptimizer.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
110 @staticmethod
28b636105ed6 Working version of codeOptimizer.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
111 def directedGraphInternal(deps):
28b636105ed6 Working version of codeOptimizer.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
112 dl = len(deps)
4
3a56cd936c59 Cleanup some code.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents: 1
diff changeset
113 startPoints = []
0
28b636105ed6 Working version of codeOptimizer.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
114 for i in range(dl):
28b636105ed6 Working version of codeOptimizer.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
115 if not max(deps[i]):
4
3a56cd936c59 Cleanup some code.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents: 1
diff changeset
116 startPoints.append(i)
0
28b636105ed6 Working version of codeOptimizer.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
117
4
3a56cd936c59 Cleanup some code.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents: 1
diff changeset
118 for i in startPoints:
0
28b636105ed6 Working version of codeOptimizer.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
119 for j in range(dl):
28b636105ed6 Working version of codeOptimizer.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
120 deps[j][i] = False
28b636105ed6 Working version of codeOptimizer.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
121
4
3a56cd936c59 Cleanup some code.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents: 1
diff changeset
122 retVal = startPoints
0
28b636105ed6 Working version of codeOptimizer.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
123
4
3a56cd936c59 Cleanup some code.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents: 1
diff changeset
124 if len(deps) != len(startPoints):
3a56cd936c59 Cleanup some code.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents: 1
diff changeset
125 subVals = DepGraph.directedGraphInternal(deps)
3a56cd936c59 Cleanup some code.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents: 1
diff changeset
126 for val in startPoints:
0
28b636105ed6 Working version of codeOptimizer.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
127 if val in subVals:
28b636105ed6 Working version of codeOptimizer.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
128 ind = subVals.index(val)
28b636105ed6 Working version of codeOptimizer.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
129 del subVals[ind]
28b636105ed6 Working version of codeOptimizer.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
130
28b636105ed6 Working version of codeOptimizer.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
131 if subVals:
28b636105ed6 Working version of codeOptimizer.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
132 retVal.extend(subVals)
28b636105ed6 Working version of codeOptimizer.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
133
28b636105ed6 Working version of codeOptimizer.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
134 return retVal
28b636105ed6 Working version of codeOptimizer.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
135
28b636105ed6 Working version of codeOptimizer.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
136 @staticmethod
28b636105ed6 Working version of codeOptimizer.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
137 def printableDepgraph(deps):
28b636105ed6 Working version of codeOptimizer.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
138 res=''
28b636105ed6 Working version of codeOptimizer.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
139 for i in range(len(deps)):
28b636105ed6 Working version of codeOptimizer.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
140 if res:
28b636105ed6 Working version of codeOptimizer.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
141 res += '\n'
28b636105ed6 Working version of codeOptimizer.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
142 s = ''
28b636105ed6 Working version of codeOptimizer.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
143 for j in range(len(deps[i])):
28b636105ed6 Working version of codeOptimizer.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
144 if deps[i][j]:
28b636105ed6 Working version of codeOptimizer.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
145 s += '1'
28b636105ed6 Working version of codeOptimizer.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
146 else:
28b636105ed6 Working version of codeOptimizer.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
147 s += '0'
28b636105ed6 Working version of codeOptimizer.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
148 res += s
28b636105ed6 Working version of codeOptimizer.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
149 return res
28b636105ed6 Working version of codeOptimizer.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
150
4
3a56cd936c59 Cleanup some code.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents: 1
diff changeset
151 def depGraphRepr(self):
3a56cd936c59 Cleanup some code.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents: 1
diff changeset
152 return self.printableDepgraph(self.deps)
3a56cd936c59 Cleanup some code.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents: 1
diff changeset
153
3a56cd936c59 Cleanup some code.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents: 1
diff changeset
154 def directedGraph(self, force = True):
3a56cd936c59 Cleanup some code.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents: 1
diff changeset
155 deps = copy.deepcopy(self.deps)
3a56cd936c59 Cleanup some code.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents: 1
diff changeset
156 if force:
3a56cd936c59 Cleanup some code.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents: 1
diff changeset
157 deps = self.dissolveStronglyConnectedComponents(deps)
0
28b636105ed6 Working version of codeOptimizer.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
158 vals = self.directedGraphInternal(deps)
28b636105ed6 Working version of codeOptimizer.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
159 retVal = []
28b636105ed6 Working version of codeOptimizer.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
160 for i in vals:
28b636105ed6 Working version of codeOptimizer.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
161 retVal.append(self.values[i])
28b636105ed6 Working version of codeOptimizer.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
162 return retVal
28b636105ed6 Working version of codeOptimizer.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
163
28b636105ed6 Working version of codeOptimizer.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
164
28b636105ed6 Working version of codeOptimizer.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
165 def toplevelDependencies(self):
28b636105ed6 Working version of codeOptimizer.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
166 dl = len(self.deps)
28b636105ed6 Working version of codeOptimizer.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
167 retVal = []
28b636105ed6 Working version of codeOptimizer.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
168 for i in range(dl):
28b636105ed6 Working version of codeOptimizer.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
169 if not max(self.deps[i]):
28b636105ed6 Working version of codeOptimizer.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
170 print max(self.deps[i])
28b636105ed6 Working version of codeOptimizer.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
171 retVal.append(self.values[i])
28b636105ed6 Working version of codeOptimizer.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
172 return retVal