Zhengli0817 patch 1 - update topsort.py (keon#295)

zhengli0817 · keon · commit 97e5e85cedd1 · 2018-06-05T00:07:56.000-04:00
* Update bst.py

* Update topsort.py

The original algo is wrong because it is using BFS, it should use DFS instead.

A counter-example is provided below:

depGraph = {
    "a" : [ "b" ],
    "b" : [ "c" ],
    "c" :  [ 'e'],
    'e' : [ 'g' ],
    "d" : [ ],
    "f" : ["e" , "d"],
    "g" : [ ]
}

given = [ "b", "c", "a", "d", "e", "f", "g" ]

The output of ret_dep_graph() is: ['e', 'g', 'c', 'b', 'a', 'd', 'f']

Clearly, 'g' has to be done before 'e'.

* Update topsort.py

* Update topsort.py

The original algo in topsort.py is wrong because it is using BFS, it should use DFS instead.

A counter-example is provided below:

depGraph = {
"a" : [ "b" ],
"b" : [ "c" ],
"c" : [ 'e'],
'e' : [ 'g' ],
"d" : [ ],
"f" : ["e" , "d"],
"g" : [ ]
}

given = [ "b", "c", "a", "d", "e", "f", "g" ]

The output of ret_dep_graph() is: ['e', 'g', 'c', 'b', 'a', 'd', 'f']

Clearly, 'g' has to be done before 'e'.

* Update topsort.py

* Create __init__.py

* Update __init__.py

* Update __init__.py

* Create test_topsort.py

* Update topsort.py

* Update test_topsort.py

* Update __init__.py

* Update and rename topsort.py to top_sort.py

* Update top_sort.py

* Update __init__.py

* Update test_topsort.py
diff --git a/algorithms/sort/__init__.py b/algorithms/sort/__init__.py
@@ -6,6 +6,7 @@
 from .merge_sort import *
 from .quick_sort import *
 from .selection_sort import *
+from .top_sort import *
 from .bucket_sort import *
 from .shell_sort import *
 from .radix_sort import *
diff --git a/algorithms/sort/top_sort.py b/algorithms/sort/top_sort.py
@@ -0,0 +1,66 @@
+GRAY, BLACK = 0, 1
+
+def top_sort_recursive(graph):
+    """ Time complexity is the same as DFS, which is O(V + E)
+        Space complexity: O(V)
+    """
+    order, enter, state = [], set(graph), {}
+    
+    def dfs(node):
+        state[node] = GRAY
+        #print(node)
+        for k in graph.get(node, ()):
+            sk = state.get(k, None)
+            if sk == GRAY:
+                raise ValueError("cycle")
+            if sk == BLACK:
+                continue
+            enter.discard(k)
+            dfs(k)
+        order.append(node)
+        state[node] = BLACK
+        
+    while enter: dfs(enter.pop())
+    return order
+
+def top_sort(graph):
+    """ Time complexity is the same as DFS, which is O(V + E)
+        Space complexity: O(V)
+    """
+    order, enter, state = [], set(graph), {}
+    
+    def is_ready(node):
+        lst = graph.get(node, ())
+        if len(lst) == 0:
+            return True
+        for k in lst:
+            sk = state.get(k, None)
+            if sk == GRAY: 
+                raise ValueError("cycle")
+            if sk != BLACK:
+                return False
+        return True
+        
+    while enter:
+        node = enter.pop()
+        stack = []
+        while True:
+            state[node] = GRAY
+            stack.append(node)
+            for k in graph.get(node, ()):
+                sk = state.get(k, None)
+                if sk == GRAY: 
+                    raise ValueError("cycle")
+                if sk == BLACK: 
+                    continue
+                enter.discard(k)
+                stack.append(k)
+            while stack and is_ready(stack[-1]):
+                node = stack.pop()
+                order.append(node)
+                state[node] = BLACK
+            if len(stack) == 0:
+                break
+            node = stack.pop()
+        
+    return order
diff --git a/algorithms/sort/topsort.py b/algorithms/sort/topsort.py
diff --git a/tests/graph/__init__.py b/tests/graph/__init__.py
@@ -0,0 +1 @@
+
diff --git a/tests/graph/test_topsort.py b/tests/graph/test_topsort.py
@@ -0,0 +1,27 @@
+from algorithms.sort import (
+    top_sort, top_sort_recursive
+)
+
+import unittest
+
+class TestSuite(unittest.TestCase):
+    def setUp(self):
+        self.depGraph = {
+                            "a" : [ "b" ],
+                            "b" : [ "c" ],
+                            "c" :  [ 'e'],
+                            'e' : [ 'g' ],
+                            "d" : [ ],
+                            "f" : ["e" , "d"],
+                            "g" : [ ]
+                        }
+        
+    def test_topsort(self):
+        res = top_sort_recursive(self.depGraph)
+        #print(res)
+        self.assertTrue(res.index('g') < res.index('e'))
+        res = top_sort(self.depGraph)
+        self.assertTrue(res.index('g') < res.index('e'))
+
+if __name__ == '__main__':
+    unittest.main()
