Mercurial > codeOptimizer
changeset 9:2263a283203c
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 |
| files | DepGraph.py |
| diffstat | 1 files changed, 12 insertions(+), 6 deletions(-) [+] |
line wrap: on
line diff
--- a/DepGraph.py Mon Sep 24 10:36:03 2012 +0200 +++ b/DepGraph.py Mon Sep 24 10:48:28 2012 +0200 @@ -43,6 +43,7 @@ @staticmethod def identifyStronglyConnectedComponents(deps): + """Tarjan's algorithm""" S=[] vindex={} lowlink={} @@ -53,18 +54,23 @@ return retVal @staticmethod + def successors(deps, v): + retVal = [] + for w in range(len(deps)): + if deps[w][v]: + retVal.append(w) + return retVal + + @staticmethod def strongconnect(deps, v, index, vindex, lowlink, S): retVal = [] # Set the depth index for v to the smallest unused index vindex[v] = index lowlink[v] = index - #print index S.append(v) - # Consider successors of v - for w in range(len(deps)): - if not deps[w][v]: - continue + # Consider successors of v + for w in DepGraph.successors(deps, v): if not w in vindex: # Successor w has not yet been visited; recurse on it res = DepGraph.strongconnect(deps, w, index + 1, vindex, lowlink, S) @@ -92,10 +98,10 @@ while dissolved: dissolved = False strong = DepGraph.identifyStronglyConnectedComponents(deps) - print strong for s in strong: if len(s) > 1: #We remove the first dependency, and see how it goes. + #FIXME: This may not be the best strategy to achieve this v = s[0] for w in s[1:]: if deps[w][v]: