--- a/DepGraph.py	Sun Sep 16 21:31:41 2012 +0200
+++ b/DepGraph.py	Mon Sep 24 01:16:43 2012 +0200
@@ -1,3 +1,4 @@
+import copy, sys
 from types import *
 
 class DepGraph:
@@ -11,14 +12,9 @@
         self.values.append(value)
 
 
-    def addDependency(self, src, dst):
-        if not type(dst) is ListType:
-            dst = [ dst ]
-
+    def rightSize(self):
         vl = len(self.values)
         dl = len(self.deps)
-        si = self.values.index(src)
-        
 
         if dl != vl:
             full = []
@@ -32,30 +28,102 @@
 
             for i in range(0, dl):
                 self.deps[i].append(exp[:])
-                
+
+    def addDependency(self, src, dst):
+        if not type(dst) is ListType:
+            dst = [ dst ]
+
+        self.rightSize()                
+
+        si = self.values.index(src)
         for d in dst:
             if d in self.values:
                 di = self.values.index(d)
                 self.deps[si][di] = True
 
+    @staticmethod
+    def identifyStronglyConnectedComponents(deps):
+        index=0
+        S=[]
+        vindex={}
+        lowlink={}
+        retVal=[]
+        for v in range(len(deps)):
+            if not v in vindex:
+                retVal.extend(DepGraph.strongconnect(deps, v, index, vindex, lowlink, S))
+        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
+        index += 1
+        S.append(v)
+
+        # Consider successors of v        
+        for w in range(len(deps)):
+            if not deps[w][v]:
+                continue
+            if not w in vindex:
+                # Successor w has not yet been visited; recurse on it
+                res = DepGraph.strongconnect(deps, w, index, vindex, lowlink, S)
+                retVal.extend(res)
+                lowlink[v] = min(lowlink[v], lowlink[w])
+            elif w in S:
+                # Successor w is in stack S and hence in the current SCC
+                lowlink[v] = min(lowlink[v], vindex[w])
+
+        # If v is a root node, pop the stack and generate an SCC
+        if lowlink[v] == vindex[v]:
+            #start a new strongly connected component
+            component = []
+            w = None
+            while w != v:
+                w = S.pop()
+                #add w to current strongly connected component
+                component.append(w)
+            retVal.append(component)
+        return retVal
+
+    @staticmethod
+    def dissolveStronglyConnectedComponents(deps):
+        dissolved = True
+        while dissolved:
+            dissolved = False
+            strong = DepGraph.identifyStronglyConnectedComponents(deps)
+            for s in strong:
+                if len(s) > 1:
+                    #We remove the first dependency, and see how it goes.
+                    v = s[0]
+                    for w in s[1:]:
+                        if deps[w][v]:
+                            #print "Remove link %d -> %d" % (w, v)
+                            deps[w][v] = False
+                            dissolved = True
+                            break
+        return deps
+        sys.exit(1)
 
     @staticmethod
     def directedGraphInternal(deps):
         dl = len(deps)
-        myVals = []
+        startPoints = []
         for i in range(dl):
             if not max(deps[i]):
-                myVals.append(i)
+                startPoints.append(i)
 
-        for i in myVals:
+        for i in startPoints:
             for j in range(dl):
                 deps[j][i] = False
 
-        retVal = myVals
+        retVal = startPoints
 
-        if len(deps) != len(myVals):
-            subVals = self.directedGraphInternal(deps)
-            for val in myVals:
+        if len(deps) != len(startPoints):
+            subVals = DepGraph.directedGraphInternal(deps)
+            for val in startPoints:
                 if val in subVals:
                     ind = subVals.index(val)
                     del subVals[ind]
@@ -80,8 +148,13 @@
             res += s
         return res
 
-    def directedGraph(self):
-        deps = self.deps[:][:]
+    def depGraphRepr(self):
+        return self.printableDepgraph(self.deps)
+
+    def directedGraph(self, force = True):
+        deps = copy.deepcopy(self.deps)
+        if force:
+            deps = self.dissolveStronglyConnectedComponents(deps)
         vals = self.directedGraphInternal(deps)
         retVal = []
         for i in vals: