# HG changeset patch
# User Scott Chacon <schacon@gmail.com>
# Date 1241934750 25200
# Node ID 3127001779791b4654577b862e0e9d04c27aa32b
# Parent  6305f274fc63850dd07587b7a27aa5f771bdb69e
modified topological sort to be non-recursive

diff --git a/toposort.py b/toposort.py
--- a/toposort.py
+++ b/toposort.py
@@ -53,6 +53,64 @@
 
         return result
 
+    def strongly_connected_components_non(self, G):
+        """Returns a list of strongly connected components in G.
+
+         Uses Tarjan's algorithm with Nuutila's modifications.
+         Nonrecursive version of algorithm.
+
+         References:
+
+          R. Tarjan (1972). Depth-first search and linear graph algorithms.
+          SIAM Journal of Computing 1(2):146-160.
+
+          E. Nuutila and E. Soisalon-Soinen (1994).
+          On finding the strongly connected components in a directed graph.
+          Information Processing Letters 49(1): 9-14.
+
+         """
+        preorder={}
+        lowlink={}
+        scc_found={}
+        scc_queue = []
+        scc_list=[]
+        i=0     # Preorder counter
+        for source in G:
+            if source not in scc_found:
+                queue=[source]
+                while queue:
+                    v=queue[-1]
+                    if v not in preorder:
+                        i=i+1
+                        preorder[v]=i
+                    done=1
+                    v_nbrs=G[v]
+                    for w in v_nbrs.parents:
+                        if w not in preorder:
+                            queue.append(w)
+                            done=0
+                            break
+                    if done==1:
+                        lowlink[v]=preorder[v]
+                        for w in v_nbrs.parents:
+                            if w not in scc_found:
+                                if preorder[w]>preorder[v]:
+                                    lowlink[v]=min([lowlink[v],lowlink[w]])
+                                else:
+                                    lowlink[v]=min([lowlink[v],preorder[w]])
+                        queue.pop()
+                        if lowlink[v]==preorder[v]:
+                            scc_found[v]=True
+                            scc=(v,)
+                            while scc_queue and preorder[scc_queue[-1]]>preorder[v]:
+                                k=scc_queue.pop()
+                                scc_found[k]=True
+                                scc.append(k)
+                            scc_list.append(scc)
+                        else:
+                            scc_queue.append(v)
+        scc_list.sort(lambda x, y: cmp(len(y),len(x)))
+        return scc_list
 
     def topological_sort(self, graph):
         count = { }
@@ -76,13 +134,12 @@
 
         return result
 
-
     def robust_topological_sort(self, graph):
         """ First identify strongly connected components,
             then perform a topological sort on these components. """
 
-        components = self.strongly_connected_components(graph)
-
+        components = self.strongly_connected_components_non(graph)
+        
         node_component = { }
         for component in components:
             for node in component:
diff --git a/unit-tests/topo-test.py b/unit-tests/topo-test.py
new file mode 100644
--- /dev/null
+++ b/unit-tests/topo-test.py
@@ -0,0 +1,46 @@
+import random, sys
+import unittest
+
+sys.path.append('../')
+
+import toposort
+
+class Ob:
+    def __init__(self, eyedee, parents):
+        self._id = eyedee
+        self.parents = parents
+        
+    def id(self):
+        return self._id
+
+#   f
+#  /\
+# e  \
+# |\  \
+# | g |
+# |/  |
+# c   d
+# |\ /
+# h b 
+# |/
+# a 
+
+class TestTopoSorting(unittest.TestCase):
+
+    def testsort(self):
+        data = {
+         'f' : Ob('f', ['d', 'e']),
+         'd' : Ob('d', ['b']),
+         'e' : Ob('e', ['c', 'g']),
+         'g' : Ob('g', ['c']),
+         'c' : Ob('c', ['b', 'h']),
+         'b' : Ob('b', ['a']),
+         'h' : Ob('h', ['a']),
+         'a' : Ob('a', []),
+        }
+        d = toposort.TopoSort(data).items()
+        sort = ['a', 'b', 'd', 'h', 'c', 'g', 'e', 'f']
+        self.assertEquals(d, sort)
+
+if __name__ == '__main__':
+    unittest.main()