Mercurial > codeOptimizer

comparison DepGraph.py @ 9:2263a283203c

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Clean up code, and remove unnecessary debug output.
author Tom Fredrik Blenning Klaussen <bfg@blenning.no>
date Mon, 24 Sep 2012 10:48:28 +0200
parents 8952a4f7aa95
children 09b39021c4af
comparison
equal deleted inserted replaced
8:8952a4f7aa95 9:2263a283203c
41 di = self.values.index(d) 41 di = self.values.index(d)
42 self.deps[si][di] = True 42 self.deps[si][di] = True
43 43
44 @staticmethod 44 @staticmethod
45 def identifyStronglyConnectedComponents(deps): 45 def identifyStronglyConnectedComponents(deps):
46 """Tarjan's algorithm"""
46 S=[] 47 S=[]
47 vindex={} 48 vindex={}
48 lowlink={} 49 lowlink={}
49 retVal=[] 50 retVal=[]
50 for v in range(len(deps)): 51 for v in range(len(deps)):
51 if not v in vindex: 52 if not v in vindex:
52 retVal.extend(DepGraph.strongconnect(deps, v, 0, vindex, lowlink, S)) 53 retVal.extend(DepGraph.strongconnect(deps, v, 0, vindex, lowlink, S))
53 return retVal 54 return retVal
54 55
55 @staticmethod 56 @staticmethod
57 def successors(deps, v):
58 retVal = []
59 for w in range(len(deps)):
60 if deps[w][v]:
61 retVal.append(w)
62 return retVal
63
64 @staticmethod
56 def strongconnect(deps, v, index, vindex, lowlink, S): 65 def strongconnect(deps, v, index, vindex, lowlink, S):
57 retVal = [] 66 retVal = []
58 # Set the depth index for v to the smallest unused index 67 # Set the depth index for v to the smallest unused index
59 vindex[v] = index 68 vindex[v] = index
60 lowlink[v] = index 69 lowlink[v] = index
61 #print index
62 S.append(v) 70 S.append(v)
63 71
64 # Consider successors of v 72 # Consider successors of v
65 for w in range(len(deps)): 73 for w in DepGraph.successors(deps, v):
66 if not deps[w][v]:
67 continue
68 if not w in vindex: 74 if not w in vindex:
69 # Successor w has not yet been visited; recurse on it 75 # Successor w has not yet been visited; recurse on it
70 res = DepGraph.strongconnect(deps, w, index + 1, vindex, lowlink, S) 76 res = DepGraph.strongconnect(deps, w, index + 1, vindex, lowlink, S)
71 retVal.extend(res) 77 retVal.extend(res)
72 lowlink[v] = min(lowlink[v], lowlink[w]) 78 lowlink[v] = min(lowlink[v], lowlink[w])
90 def dissolveStronglyConnectedComponents(deps): 96 def dissolveStronglyConnectedComponents(deps):
91 dissolved = True 97 dissolved = True
92 while dissolved: 98 while dissolved:
93 dissolved = False 99 dissolved = False
94 strong = DepGraph.identifyStronglyConnectedComponents(deps) 100 strong = DepGraph.identifyStronglyConnectedComponents(deps)
95 print strong
96 for s in strong: 101 for s in strong:
97 if len(s) > 1: 102 if len(s) > 1:
98 #We remove the first dependency, and see how it goes. 103 #We remove the first dependency, and see how it goes.
104 #FIXME: This may not be the best strategy to achieve this
99 v = s[0] 105 v = s[0]
100 for w in s[1:]: 106 for w in s[1:]:
101 if deps[w][v]: 107 if deps[w][v]:
102 #print "Remove link %d -> %d" % (w, v) 108 #print "Remove link %d -> %d" % (w, v)
103 deps[w][v] = False 109 deps[w][v] = False