Mercurial > codeOptimizer

comparison DepGraph.py @ 8:8952a4f7aa95

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
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
comparison
equal deleted inserted replaced
7:94b1959b0108 8:8952a4f7aa95
1 import copy, sys 1 import copy
2 from types import * 2 from types import *
3 3
4 class DepGraph: 4 class DepGraph:
5 def __init__(self): 5 def __init__(self):
6 self.deps = [] 6 self.deps = []
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 index=0
47 S=[] 46 S=[]
48 vindex={} 47 vindex={}
49 lowlink={} 48 lowlink={}
50 retVal=[] 49 retVal=[]
51 for v in range(len(deps)): 50 for v in range(len(deps)):
52 if not v in vindex: 51 if not v in vindex:
53 retVal.extend(DepGraph.strongconnect(deps, v, index, vindex, lowlink, S)) 52 retVal.extend(DepGraph.strongconnect(deps, v, 0, vindex, lowlink, S))
54 return retVal 53 return retVal
55 54
56 @staticmethod 55 @staticmethod
57 def strongconnect(deps, v, index, vindex, lowlink, S): 56 def strongconnect(deps, v, index, vindex, lowlink, S):
58 retVal = [] 57 retVal = []
59 # Set the depth index for v to the smallest unused index 58 # Set the depth index for v to the smallest unused index
60 vindex[v] = index 59 vindex[v] = index
61 lowlink[v] = index 60 lowlink[v] = index
62 #print index 61 #print index
63 index += 1
64 S.append(v) 62 S.append(v)
65 63
66 # Consider successors of v 64 # Consider successors of v
67 for w in range(len(deps)): 65 for w in range(len(deps)):
68 if not deps[w][v]: 66 if not deps[w][v]:
69 continue 67 continue
70 if not w in vindex: 68 if not w in vindex:
71 # Successor w has not yet been visited; recurse on it 69 # Successor w has not yet been visited; recurse on it
72 res = DepGraph.strongconnect(deps, w, index, vindex, lowlink, S) 70 res = DepGraph.strongconnect(deps, w, index + 1, vindex, lowlink, S)
73 retVal.extend(res) 71 retVal.extend(res)
74 lowlink[v] = min(lowlink[v], lowlink[w]) 72 lowlink[v] = min(lowlink[v], lowlink[w])
75 elif w in S: 73 elif w in S:
76 # Successor w is in stack S and hence in the current SCC 74 # Successor w is in stack S and hence in the current SCC
77 lowlink[v] = min(lowlink[v], vindex[w]) 75 lowlink[v] = min(lowlink[v], vindex[w])
92 def dissolveStronglyConnectedComponents(deps): 90 def dissolveStronglyConnectedComponents(deps):
93 dissolved = True 91 dissolved = True
94 while dissolved: 92 while dissolved:
95 dissolved = False 93 dissolved = False
96 strong = DepGraph.identifyStronglyConnectedComponents(deps) 94 strong = DepGraph.identifyStronglyConnectedComponents(deps)
95 print strong
97 for s in strong: 96 for s in strong:
98 if len(s) > 1: 97 if len(s) > 1:
99 #We remove the first dependency, and see how it goes. 98 #We remove the first dependency, and see how it goes.
100 v = s[0] 99 v = s[0]
101 for w in s[1:]: 100 for w in s[1:]:
103 #print "Remove link %d -> %d" % (w, v) 102 #print "Remove link %d -> %d" % (w, v)
104 deps[w][v] = False 103 deps[w][v] = False
105 dissolved = True 104 dissolved = True
106 break 105 break
107 return deps 106 return deps
108 sys.exit(1)
109 107
110 @staticmethod 108 @staticmethod
111 def directedGraphInternal(deps): 109 def directedGraphInternal(deps):
112 dl = len(deps) 110 dl = len(deps)
113 startPoints = [] 111 startPoints = []