Mercurial > codeOptimizer

annotate DepGraph.py @ 10:09b39021c4af

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Make filename an attribute of file.
author Tom Fredrik Blenning Klaussen <bfg@blenning.no>
date Wed, 14 Nov 2012 21:44:53 +0100
parents 2263a283203c
children
Ignore whitespace changes - Everywhere: Within whitespace: At end of lines:
rev   line source
8
8952a4f7aa95 Fix off by one error, and simplify.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents: 4
diff changeset
1 import copy
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
10
09b39021c4af Make filename an attribute of file.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents: 9
diff changeset
36 self.rightSize()
4
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):
9
2263a283203c Clean up code, and remove unnecessary debug output.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents: 8
diff changeset
46 """Tarjan's algorithm"""
4
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:
8
8952a4f7aa95 Fix off by one error, and simplify.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents: 4
diff changeset
53 retVal.extend(DepGraph.strongconnect(deps, v, 0, vindex, lowlink, S))
4
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
9
2263a283203c Clean up code, and remove unnecessary debug output.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents: 8
diff changeset
57 def successors(deps, v):
2263a283203c Clean up code, and remove unnecessary debug output.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents: 8
diff changeset
58 retVal = []
2263a283203c Clean up code, and remove unnecessary debug output.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents: 8
diff changeset
59 for w in range(len(deps)):
2263a283203c Clean up code, and remove unnecessary debug output.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents: 8
diff changeset
60 if deps[w][v]:
2263a283203c Clean up code, and remove unnecessary debug output.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents: 8
diff changeset
61 retVal.append(w)
2263a283203c Clean up code, and remove unnecessary debug output.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents: 8
diff changeset
62 return retVal
2263a283203c Clean up code, and remove unnecessary debug output.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents: 8
diff changeset
63
2263a283203c Clean up code, and remove unnecessary debug output.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents: 8
diff changeset
64 @staticmethod
4
3a56cd936c59 Cleanup some code.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents: 1
diff changeset
65 def strongconnect(deps, v, index, vindex, lowlink, S):
3a56cd936c59 Cleanup some code.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents: 1
diff changeset
66 retVal = []
3a56cd936c59 Cleanup some code.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents: 1
diff changeset
67 # 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
68 vindex[v] = index
3a56cd936c59 Cleanup some code.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents: 1
diff changeset
69 lowlink[v] = index
3a56cd936c59 Cleanup some code.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents: 1
diff changeset
70 S.append(v)
3a56cd936c59 Cleanup some code.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents: 1
diff changeset
71
9
2263a283203c Clean up code, and remove unnecessary debug output.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents: 8
diff changeset
72 # Consider successors of v
2263a283203c Clean up code, and remove unnecessary debug output.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents: 8
diff changeset
73 for w in DepGraph.successors(deps, v):
4
3a56cd936c59 Cleanup some code.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents: 1
diff changeset
74 if not w in vindex:
3a56cd936c59 Cleanup some code.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents: 1
diff changeset
75 # Successor w has not yet been visited; recurse on it
8
8952a4f7aa95 Fix off by one error, and simplify.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents: 4
diff changeset
76 res = DepGraph.strongconnect(deps, w, index + 1, vindex, lowlink, S)
4
3a56cd936c59 Cleanup some code.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents: 1
diff changeset
77 retVal.extend(res)
3a56cd936c59 Cleanup some code.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents: 1
diff changeset
78 lowlink[v] = min(lowlink[v], lowlink[w])
3a56cd936c59 Cleanup some code.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents: 1
diff changeset
79 elif w in S:
3a56cd936c59 Cleanup some code.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents: 1
diff changeset
80 # 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
81 lowlink[v] = min(lowlink[v], vindex[w])
3a56cd936c59 Cleanup some code.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents: 1
diff changeset
82
3a56cd936c59 Cleanup some code.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents: 1
diff changeset
83 # 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
84 if lowlink[v] == vindex[v]:
3a56cd936c59 Cleanup some code.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents: 1
diff changeset
85 #start a new strongly connected component
3a56cd936c59 Cleanup some code.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents: 1
diff changeset
86 component = []
3a56cd936c59 Cleanup some code.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents: 1
diff changeset
87 w = None
3a56cd936c59 Cleanup some code.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents: 1
diff changeset
88 while w != v:
3a56cd936c59 Cleanup some code.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents: 1
diff changeset
89 w = S.pop()
3a56cd936c59 Cleanup some code.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents: 1
diff changeset
90 #add w to current strongly connected component
3a56cd936c59 Cleanup some code.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents: 1
diff changeset
91 component.append(w)
3a56cd936c59 Cleanup some code.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents: 1
diff changeset
92 retVal.append(component)
3a56cd936c59 Cleanup some code.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents: 1
diff changeset
93 return retVal
3a56cd936c59 Cleanup some code.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents: 1
diff changeset
94
3a56cd936c59 Cleanup some code.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents: 1
diff changeset
95 @staticmethod
3a56cd936c59 Cleanup some code.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents: 1
diff changeset
96 def dissolveStronglyConnectedComponents(deps):
3a56cd936c59 Cleanup some code.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents: 1
diff changeset
97 dissolved = True
3a56cd936c59 Cleanup some code.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents: 1
diff changeset
98 while dissolved:
3a56cd936c59 Cleanup some code.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents: 1
diff changeset
99 dissolved = False
3a56cd936c59 Cleanup some code.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents: 1
diff changeset
100 strong = DepGraph.identifyStronglyConnectedComponents(deps)
3a56cd936c59 Cleanup some code.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents: 1
diff changeset
101 for s in strong:
3a56cd936c59 Cleanup some code.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents: 1
diff changeset
102 if len(s) > 1:
3a56cd936c59 Cleanup some code.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents: 1
diff changeset
103 #We remove the first dependency, and see how it goes.
9
2263a283203c Clean up code, and remove unnecessary debug output.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents: 8
diff changeset
104 #FIXME: This may not be the best strategy to achieve this
4
3a56cd936c59 Cleanup some code.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents: 1
diff changeset
105 v = s[0]
3a56cd936c59 Cleanup some code.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents: 1
diff changeset
106 for w in s[1:]:
3a56cd936c59 Cleanup some code.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents: 1
diff changeset
107 if deps[w][v]:
3a56cd936c59 Cleanup some code.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents: 1
diff changeset
108 #print "Remove link %d -> %d" % (w, v)
3a56cd936c59 Cleanup some code.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents: 1
diff changeset
109 deps[w][v] = False
3a56cd936c59 Cleanup some code.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents: 1
diff changeset
110 dissolved = True
3a56cd936c59 Cleanup some code.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents: 1
diff changeset
111 break
3a56cd936c59 Cleanup some code.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents: 1
diff changeset
112 return deps
0
28b636105ed6 Working version of codeOptimizer.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
113
28b636105ed6 Working version of codeOptimizer.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
114 @staticmethod
28b636105ed6 Working version of codeOptimizer.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
115 def directedGraphInternal(deps):
28b636105ed6 Working version of codeOptimizer.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
116 dl = len(deps)
4
3a56cd936c59 Cleanup some code.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents: 1
diff changeset
117 startPoints = []
0
28b636105ed6 Working version of codeOptimizer.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
118 for i in range(dl):
28b636105ed6 Working version of codeOptimizer.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
119 if not max(deps[i]):
4
3a56cd936c59 Cleanup some code.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents: 1
diff changeset
120 startPoints.append(i)
0
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 for i in startPoints:
0
28b636105ed6 Working version of codeOptimizer.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
123 for j in range(dl):
28b636105ed6 Working version of codeOptimizer.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
124 deps[j][i] = False
28b636105ed6 Working version of codeOptimizer.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
125
4
3a56cd936c59 Cleanup some code.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents: 1
diff changeset
126 retVal = startPoints
0
28b636105ed6 Working version of codeOptimizer.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
127
4
3a56cd936c59 Cleanup some code.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents: 1
diff changeset
128 if len(deps) != len(startPoints):
3a56cd936c59 Cleanup some code.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents: 1
diff changeset
129 subVals = DepGraph.directedGraphInternal(deps)
3a56cd936c59 Cleanup some code.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents: 1
diff changeset
130 for val in startPoints:
0
28b636105ed6 Working version of codeOptimizer.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
131 if val in subVals:
28b636105ed6 Working version of codeOptimizer.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
132 ind = subVals.index(val)
28b636105ed6 Working version of codeOptimizer.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
133 del subVals[ind]
28b636105ed6 Working version of codeOptimizer.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
134
28b636105ed6 Working version of codeOptimizer.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
135 if subVals:
28b636105ed6 Working version of codeOptimizer.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
136 retVal.extend(subVals)
28b636105ed6 Working version of codeOptimizer.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
137
28b636105ed6 Working version of codeOptimizer.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
138 return retVal
28b636105ed6 Working version of codeOptimizer.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
139
28b636105ed6 Working version of codeOptimizer.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
140 @staticmethod
28b636105ed6 Working version of codeOptimizer.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
141 def printableDepgraph(deps):
28b636105ed6 Working version of codeOptimizer.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
142 res=''
28b636105ed6 Working version of codeOptimizer.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
143 for i in range(len(deps)):
28b636105ed6 Working version of codeOptimizer.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
144 if res:
28b636105ed6 Working version of codeOptimizer.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
145 res += '\n'
28b636105ed6 Working version of codeOptimizer.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
146 s = ''
28b636105ed6 Working version of codeOptimizer.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
147 for j in range(len(deps[i])):
28b636105ed6 Working version of codeOptimizer.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
148 if deps[i][j]:
28b636105ed6 Working version of codeOptimizer.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
149 s += '1'
28b636105ed6 Working version of codeOptimizer.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
150 else:
28b636105ed6 Working version of codeOptimizer.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
151 s += '0'
28b636105ed6 Working version of codeOptimizer.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
152 res += s
28b636105ed6 Working version of codeOptimizer.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
153 return res
28b636105ed6 Working version of codeOptimizer.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
154
4
3a56cd936c59 Cleanup some code.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents: 1
diff changeset
155 def depGraphRepr(self):
3a56cd936c59 Cleanup some code.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents: 1
diff changeset
156 return self.printableDepgraph(self.deps)
3a56cd936c59 Cleanup some code.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents: 1
diff changeset
157
3a56cd936c59 Cleanup some code.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents: 1
diff changeset
158 def directedGraph(self, force = True):
3a56cd936c59 Cleanup some code.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents: 1
diff changeset
159 deps = copy.deepcopy(self.deps)
3a56cd936c59 Cleanup some code.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents: 1
diff changeset
160 if force:
3a56cd936c59 Cleanup some code.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents: 1
diff changeset
161 deps = self.dissolveStronglyConnectedComponents(deps)
0
28b636105ed6 Working version of codeOptimizer.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
162 vals = self.directedGraphInternal(deps)
28b636105ed6 Working version of codeOptimizer.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
163 retVal = []
28b636105ed6 Working version of codeOptimizer.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
164 for i in vals:
28b636105ed6 Working version of codeOptimizer.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
165 retVal.append(self.values[i])
28b636105ed6 Working version of codeOptimizer.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
166 return retVal
28b636105ed6 Working version of codeOptimizer.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
167
28b636105ed6 Working version of codeOptimizer.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
168
28b636105ed6 Working version of codeOptimizer.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
169 def toplevelDependencies(self):
28b636105ed6 Working version of codeOptimizer.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
170 dl = len(self.deps)
28b636105ed6 Working version of codeOptimizer.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
171 retVal = []
28b636105ed6 Working version of codeOptimizer.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
172 for i in range(dl):
28b636105ed6 Working version of codeOptimizer.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
173 if not max(self.deps[i]):
28b636105ed6 Working version of codeOptimizer.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
174 print max(self.deps[i])
28b636105ed6 Working version of codeOptimizer.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
175 retVal.append(self.values[i])
28b636105ed6 Working version of codeOptimizer.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
176 return retVal