codeOptimizer: DepGraph.py annotate

annotate DepGraph.py @ 8:8952a4f7aa95

Fix off by one error, and simplify.

author	Tom Fredrik Blenning Klaussen <bfg@blenning.no>
date	Mon, 24 Sep 2012 10:36:03 +0200
parents	3a56cd936c59
children	2263a283203c

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
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 S=[]
3a56cd936c59 Cleanup some code. Tom Fredrik Blenning Klaussen <bfg@blenning.no> parents: 1 diff changeset	47 vindex={}
3a56cd936c59 Cleanup some code. Tom Fredrik Blenning Klaussen <bfg@blenning.no> parents: 1 diff changeset	48 lowlink={}
3a56cd936c59 Cleanup some code. Tom Fredrik Blenning Klaussen <bfg@blenning.no> parents: 1 diff changeset	49 retVal=[]
3a56cd936c59 Cleanup some code. Tom Fredrik Blenning Klaussen <bfg@blenning.no> parents: 1 diff changeset	50 for v in range(len(deps)):
3a56cd936c59 Cleanup some code. Tom Fredrik Blenning Klaussen <bfg@blenning.no> parents: 1 diff changeset	51 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	52 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	53 return retVal
3a56cd936c59 Cleanup some code. Tom Fredrik Blenning Klaussen <bfg@blenning.no> parents: 1 diff changeset	54
3a56cd936c59 Cleanup some code. Tom Fredrik Blenning Klaussen <bfg@blenning.no> parents: 1 diff changeset	55 @staticmethod
3a56cd936c59 Cleanup some code. Tom Fredrik Blenning Klaussen <bfg@blenning.no> parents: 1 diff changeset	56 def strongconnect(deps, v, index, vindex, lowlink, S):
3a56cd936c59 Cleanup some code. Tom Fredrik Blenning Klaussen <bfg@blenning.no> parents: 1 diff changeset	57 retVal = []
3a56cd936c59 Cleanup some code. Tom Fredrik Blenning Klaussen <bfg@blenning.no> parents: 1 diff changeset	58 # 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	59 vindex[v] = index
3a56cd936c59 Cleanup some code. Tom Fredrik Blenning Klaussen <bfg@blenning.no> parents: 1 diff changeset	60 lowlink[v] = index
3a56cd936c59 Cleanup some code. Tom Fredrik Blenning Klaussen <bfg@blenning.no> parents: 1 diff changeset	61 #print index
3a56cd936c59 Cleanup some code. Tom Fredrik Blenning Klaussen <bfg@blenning.no> parents: 1 diff changeset	62 S.append(v)
3a56cd936c59 Cleanup some code. Tom Fredrik Blenning Klaussen <bfg@blenning.no> parents: 1 diff changeset	63
3a56cd936c59 Cleanup some code. Tom Fredrik Blenning Klaussen <bfg@blenning.no> parents: 1 diff changeset	64 # Consider successors of v
3a56cd936c59 Cleanup some code. Tom Fredrik Blenning Klaussen <bfg@blenning.no> parents: 1 diff changeset	65 for w in range(len(deps)):
3a56cd936c59 Cleanup some code. Tom Fredrik Blenning Klaussen <bfg@blenning.no> parents: 1 diff changeset	66 if not deps[w][v]:
3a56cd936c59 Cleanup some code. Tom Fredrik Blenning Klaussen <bfg@blenning.no> parents: 1 diff changeset	67 continue
3a56cd936c59 Cleanup some code. Tom Fredrik Blenning Klaussen <bfg@blenning.no> parents: 1 diff changeset	68 if not w in vindex:
3a56cd936c59 Cleanup some code. Tom Fredrik Blenning Klaussen <bfg@blenning.no> parents: 1 diff changeset	69 # 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	70 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	71 retVal.extend(res)
3a56cd936c59 Cleanup some code. Tom Fredrik Blenning Klaussen <bfg@blenning.no> parents: 1 diff changeset	72 lowlink[v] = min(lowlink[v], lowlink[w])
3a56cd936c59 Cleanup some code. Tom Fredrik Blenning Klaussen <bfg@blenning.no> parents: 1 diff changeset	73 elif w in S:
3a56cd936c59 Cleanup some code. Tom Fredrik Blenning Klaussen <bfg@blenning.no> parents: 1 diff changeset	74 # 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	75 lowlink[v] = min(lowlink[v], vindex[w])
3a56cd936c59 Cleanup some code. Tom Fredrik Blenning Klaussen <bfg@blenning.no> parents: 1 diff changeset	76
3a56cd936c59 Cleanup some code. Tom Fredrik Blenning Klaussen <bfg@blenning.no> parents: 1 diff changeset	77 # 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	78 if lowlink[v] == vindex[v]:
3a56cd936c59 Cleanup some code. Tom Fredrik Blenning Klaussen <bfg@blenning.no> parents: 1 diff changeset	79 #start a new strongly connected component
3a56cd936c59 Cleanup some code. Tom Fredrik Blenning Klaussen <bfg@blenning.no> parents: 1 diff changeset	80 component = []
3a56cd936c59 Cleanup some code. Tom Fredrik Blenning Klaussen <bfg@blenning.no> parents: 1 diff changeset	81 w = None
3a56cd936c59 Cleanup some code. Tom Fredrik Blenning Klaussen <bfg@blenning.no> parents: 1 diff changeset	82 while w != v:
3a56cd936c59 Cleanup some code. Tom Fredrik Blenning Klaussen <bfg@blenning.no> parents: 1 diff changeset	83 w = S.pop()
3a56cd936c59 Cleanup some code. Tom Fredrik Blenning Klaussen <bfg@blenning.no> parents: 1 diff changeset	84 #add w to current strongly connected component
3a56cd936c59 Cleanup some code. Tom Fredrik Blenning Klaussen <bfg@blenning.no> parents: 1 diff changeset	85 component.append(w)
3a56cd936c59 Cleanup some code. Tom Fredrik Blenning Klaussen <bfg@blenning.no> parents: 1 diff changeset	86 retVal.append(component)
3a56cd936c59 Cleanup some code. Tom Fredrik Blenning Klaussen <bfg@blenning.no> parents: 1 diff changeset	87 return retVal
3a56cd936c59 Cleanup some code. Tom Fredrik Blenning Klaussen <bfg@blenning.no> parents: 1 diff changeset	88
3a56cd936c59 Cleanup some code. Tom Fredrik Blenning Klaussen <bfg@blenning.no> parents: 1 diff changeset	89 @staticmethod
3a56cd936c59 Cleanup some code. Tom Fredrik Blenning Klaussen <bfg@blenning.no> parents: 1 diff changeset	90 def dissolveStronglyConnectedComponents(deps):
3a56cd936c59 Cleanup some code. Tom Fredrik Blenning Klaussen <bfg@blenning.no> parents: 1 diff changeset	91 dissolved = True
3a56cd936c59 Cleanup some code. Tom Fredrik Blenning Klaussen <bfg@blenning.no> parents: 1 diff changeset	92 while dissolved:
3a56cd936c59 Cleanup some code. Tom Fredrik Blenning Klaussen <bfg@blenning.no> parents: 1 diff changeset	93 dissolved = False
3a56cd936c59 Cleanup some code. Tom Fredrik Blenning Klaussen <bfg@blenning.no> parents: 1 diff changeset	94 strong = DepGraph.identifyStronglyConnectedComponents(deps)
8 8952a4f7aa95 Fix off by one error, and simplify. Tom Fredrik Blenning Klaussen <bfg@blenning.no> parents: 4 diff changeset	95 print strong
4 3a56cd936c59 Cleanup some code. Tom Fredrik Blenning Klaussen <bfg@blenning.no> parents: 1 diff changeset	96 for s in strong:
3a56cd936c59 Cleanup some code. Tom Fredrik Blenning Klaussen <bfg@blenning.no> parents: 1 diff changeset	97 if len(s) > 1:
3a56cd936c59 Cleanup some code. Tom Fredrik Blenning Klaussen <bfg@blenning.no> parents: 1 diff changeset	98 #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	99 v = s[0]
3a56cd936c59 Cleanup some code. Tom Fredrik Blenning Klaussen <bfg@blenning.no> parents: 1 diff changeset	100 for w in s[1:]:
3a56cd936c59 Cleanup some code. Tom Fredrik Blenning Klaussen <bfg@blenning.no> parents: 1 diff changeset	101 if deps[w][v]:
3a56cd936c59 Cleanup some code. Tom Fredrik Blenning Klaussen <bfg@blenning.no> parents: 1 diff changeset	102 #print "Remove link %d -> %d" % (w, v)
3a56cd936c59 Cleanup some code. Tom Fredrik Blenning Klaussen <bfg@blenning.no> parents: 1 diff changeset	103 deps[w][v] = False
3a56cd936c59 Cleanup some code. Tom Fredrik Blenning Klaussen <bfg@blenning.no> parents: 1 diff changeset	104 dissolved = True
3a56cd936c59 Cleanup some code. Tom Fredrik Blenning Klaussen <bfg@blenning.no> parents: 1 diff changeset	105 break
3a56cd936c59 Cleanup some code. Tom Fredrik Blenning Klaussen <bfg@blenning.no> parents: 1 diff changeset	106 return deps
0 28b636105ed6 Working version of codeOptimizer. Tom Fredrik Blenning Klaussen <bfg@blenning.no> parents: diff changeset	107
28b636105ed6 Working version of codeOptimizer. Tom Fredrik Blenning Klaussen <bfg@blenning.no> parents: diff changeset	108 @staticmethod
28b636105ed6 Working version of codeOptimizer. Tom Fredrik Blenning Klaussen <bfg@blenning.no> parents: diff changeset	109 def directedGraphInternal(deps):
28b636105ed6 Working version of codeOptimizer. Tom Fredrik Blenning Klaussen <bfg@blenning.no> parents: diff changeset	110 dl = len(deps)
4 3a56cd936c59 Cleanup some code. Tom Fredrik Blenning Klaussen <bfg@blenning.no> parents: 1 diff changeset	111 startPoints = []
0 28b636105ed6 Working version of codeOptimizer. Tom Fredrik Blenning Klaussen <bfg@blenning.no> parents: diff changeset	112 for i in range(dl):
28b636105ed6 Working version of codeOptimizer. Tom Fredrik Blenning Klaussen <bfg@blenning.no> parents: diff changeset	113 if not max(deps[i]):
4 3a56cd936c59 Cleanup some code. Tom Fredrik Blenning Klaussen <bfg@blenning.no> parents: 1 diff changeset	114 startPoints.append(i)
0 28b636105ed6 Working version of codeOptimizer. Tom Fredrik Blenning Klaussen <bfg@blenning.no> parents: diff changeset	115
4 3a56cd936c59 Cleanup some code. Tom Fredrik Blenning Klaussen <bfg@blenning.no> parents: 1 diff changeset	116 for i in startPoints:
0 28b636105ed6 Working version of codeOptimizer. Tom Fredrik Blenning Klaussen <bfg@blenning.no> parents: diff changeset	117 for j in range(dl):
28b636105ed6 Working version of codeOptimizer. Tom Fredrik Blenning Klaussen <bfg@blenning.no> parents: diff changeset	118 deps[j][i] = False
28b636105ed6 Working version of codeOptimizer. Tom Fredrik Blenning Klaussen <bfg@blenning.no> parents: diff changeset	119
4 3a56cd936c59 Cleanup some code. Tom Fredrik Blenning Klaussen <bfg@blenning.no> parents: 1 diff changeset	120 retVal = startPoints
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 if len(deps) != len(startPoints):
3a56cd936c59 Cleanup some code. Tom Fredrik Blenning Klaussen <bfg@blenning.no> parents: 1 diff changeset	123 subVals = DepGraph.directedGraphInternal(deps)
3a56cd936c59 Cleanup some code. Tom Fredrik Blenning Klaussen <bfg@blenning.no> parents: 1 diff changeset	124 for val in startPoints:
0 28b636105ed6 Working version of codeOptimizer. Tom Fredrik Blenning Klaussen <bfg@blenning.no> parents: diff changeset	125 if val in subVals:
28b636105ed6 Working version of codeOptimizer. Tom Fredrik Blenning Klaussen <bfg@blenning.no> parents: diff changeset	126 ind = subVals.index(val)
28b636105ed6 Working version of codeOptimizer. Tom Fredrik Blenning Klaussen <bfg@blenning.no> parents: diff changeset	127 del subVals[ind]
28b636105ed6 Working version of codeOptimizer. Tom Fredrik Blenning Klaussen <bfg@blenning.no> parents: diff changeset	128
28b636105ed6 Working version of codeOptimizer. Tom Fredrik Blenning Klaussen <bfg@blenning.no> parents: diff changeset	129 if subVals:
28b636105ed6 Working version of codeOptimizer. Tom Fredrik Blenning Klaussen <bfg@blenning.no> parents: diff changeset	130 retVal.extend(subVals)
28b636105ed6 Working version of codeOptimizer. Tom Fredrik Blenning Klaussen <bfg@blenning.no> parents: diff changeset	131
28b636105ed6 Working version of codeOptimizer. Tom Fredrik Blenning Klaussen <bfg@blenning.no> parents: diff changeset	132 return retVal
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 @staticmethod
28b636105ed6 Working version of codeOptimizer. Tom Fredrik Blenning Klaussen <bfg@blenning.no> parents: diff changeset	135 def printableDepgraph(deps):
28b636105ed6 Working version of codeOptimizer. Tom Fredrik Blenning Klaussen <bfg@blenning.no> parents: diff changeset	136 res=''
28b636105ed6 Working version of codeOptimizer. Tom Fredrik Blenning Klaussen <bfg@blenning.no> parents: diff changeset	137 for i in range(len(deps)):
28b636105ed6 Working version of codeOptimizer. Tom Fredrik Blenning Klaussen <bfg@blenning.no> parents: diff changeset	138 if res:
28b636105ed6 Working version of codeOptimizer. Tom Fredrik Blenning Klaussen <bfg@blenning.no> parents: diff changeset	139 res += '\n'
28b636105ed6 Working version of codeOptimizer. Tom Fredrik Blenning Klaussen <bfg@blenning.no> parents: diff changeset	140 s = ''
28b636105ed6 Working version of codeOptimizer. Tom Fredrik Blenning Klaussen <bfg@blenning.no> parents: diff changeset	141 for j in range(len(deps[i])):
28b636105ed6 Working version of codeOptimizer. Tom Fredrik Blenning Klaussen <bfg@blenning.no> parents: diff changeset	142 if deps[i][j]:
28b636105ed6 Working version of codeOptimizer. Tom Fredrik Blenning Klaussen <bfg@blenning.no> parents: diff changeset	143 s += '1'
28b636105ed6 Working version of codeOptimizer. Tom Fredrik Blenning Klaussen <bfg@blenning.no> parents: diff changeset	144 else:
28b636105ed6 Working version of codeOptimizer. Tom Fredrik Blenning Klaussen <bfg@blenning.no> parents: diff changeset	145 s += '0'
28b636105ed6 Working version of codeOptimizer. Tom Fredrik Blenning Klaussen <bfg@blenning.no> parents: diff changeset	146 res += s
28b636105ed6 Working version of codeOptimizer. Tom Fredrik Blenning Klaussen <bfg@blenning.no> parents: diff changeset	147 return res
28b636105ed6 Working version of codeOptimizer. Tom Fredrik Blenning Klaussen <bfg@blenning.no> parents: diff changeset	148
4 3a56cd936c59 Cleanup some code. Tom Fredrik Blenning Klaussen <bfg@blenning.no> parents: 1 diff changeset	149 def depGraphRepr(self):
3a56cd936c59 Cleanup some code. Tom Fredrik Blenning Klaussen <bfg@blenning.no> parents: 1 diff changeset	150 return self.printableDepgraph(self.deps)
3a56cd936c59 Cleanup some code. Tom Fredrik Blenning Klaussen <bfg@blenning.no> parents: 1 diff changeset	151
3a56cd936c59 Cleanup some code. Tom Fredrik Blenning Klaussen <bfg@blenning.no> parents: 1 diff changeset	152 def directedGraph(self, force = True):
3a56cd936c59 Cleanup some code. Tom Fredrik Blenning Klaussen <bfg@blenning.no> parents: 1 diff changeset	153 deps = copy.deepcopy(self.deps)
3a56cd936c59 Cleanup some code. Tom Fredrik Blenning Klaussen <bfg@blenning.no> parents: 1 diff changeset	154 if force:
3a56cd936c59 Cleanup some code. Tom Fredrik Blenning Klaussen <bfg@blenning.no> parents: 1 diff changeset	155 deps = self.dissolveStronglyConnectedComponents(deps)
0 28b636105ed6 Working version of codeOptimizer. Tom Fredrik Blenning Klaussen <bfg@blenning.no> parents: diff changeset	156 vals = self.directedGraphInternal(deps)
28b636105ed6 Working version of codeOptimizer. Tom Fredrik Blenning Klaussen <bfg@blenning.no> parents: diff changeset	157 retVal = []
28b636105ed6 Working version of codeOptimizer. Tom Fredrik Blenning Klaussen <bfg@blenning.no> parents: diff changeset	158 for i in vals:
28b636105ed6 Working version of codeOptimizer. Tom Fredrik Blenning Klaussen <bfg@blenning.no> parents: diff changeset	159 retVal.append(self.values[i])
28b636105ed6 Working version of codeOptimizer. Tom Fredrik Blenning Klaussen <bfg@blenning.no> parents: diff changeset	160 return retVal
28b636105ed6 Working version of codeOptimizer. Tom Fredrik Blenning Klaussen <bfg@blenning.no> parents: diff changeset	161
28b636105ed6 Working version of codeOptimizer. Tom Fredrik Blenning Klaussen <bfg@blenning.no> parents: diff changeset	162
28b636105ed6 Working version of codeOptimizer. Tom Fredrik Blenning Klaussen <bfg@blenning.no> parents: diff changeset	163 def toplevelDependencies(self):
28b636105ed6 Working version of codeOptimizer. Tom Fredrik Blenning Klaussen <bfg@blenning.no> parents: diff changeset	164 dl = len(self.deps)
28b636105ed6 Working version of codeOptimizer. Tom Fredrik Blenning Klaussen <bfg@blenning.no> parents: diff changeset	165 retVal = []
28b636105ed6 Working version of codeOptimizer. Tom Fredrik Blenning Klaussen <bfg@blenning.no> parents: diff changeset	166 for i in range(dl):
28b636105ed6 Working version of codeOptimizer. Tom Fredrik Blenning Klaussen <bfg@blenning.no> parents: diff changeset	167 if not max(self.deps[i]):
28b636105ed6 Working version of codeOptimizer. Tom Fredrik Blenning Klaussen <bfg@blenning.no> parents: diff changeset	168 print max(self.deps[i])
28b636105ed6 Working version of codeOptimizer. Tom Fredrik Blenning Klaussen <bfg@blenning.no> parents: diff changeset	169 retVal.append(self.values[i])
28b636105ed6 Working version of codeOptimizer. Tom Fredrik Blenning Klaussen <bfg@blenning.no> parents: diff changeset	170 return retVal

Mercurial > codeOptimizer

annotate DepGraph.py @ 8:8952a4f7aa95