Repository: keon/algorithms
Pull request #295 (2018-06-01 13:41:26)

Zhengli0817 patch 1 - 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'.

coveralls: ## Pull Request Test Coverage Report for [Build 307](https://coveralls.io/builds/17271503)

* **0** of **0**   changed or added relevant lines in **0** files are covered.
* No unchanged relevant lines lost coverage.
* Overall coverage remained the same at **91.31%**

---



|  Totals | [![Coverage Status](https://coveralls.io/builds/17271503/badge)](https://coveralls.io/builds/17271503) |
| :-- | --: |
| Change from base [Build 304](https://coveralls.io/builds/17266764): |  0.0% |
| Covered Lines: | 2669 |
| Relevant Lines: | 2923 |

---
##### 💛  - [Coveralls](https://coveralls.io)

zhengli0817: @goswami-rahul I made the changes according to your comments, please review 
zhengli0817: @goswami-rahul I made the changes again according to your comments, please review

Patch:
diff --git a/algorithms/sort/__init__.py b/algorithms/sort/__init__.py
index 39eb147..d86e2bc 100644
--- a/algorithms/sort/__init__.py
+++ b/algorithms/sort/__init__.py
@@ -6,6 +6,7 @@ from .insertion_sort import *
 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
new file mode 100644
index 0000000..b9188bb
--- /dev/null
+++ 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
deleted file mode 100644
index 8341ce9..0000000
--- a/algorithms/sort/topsort.py
+++ /dev/null
@@ -1,60 +0,0 @@
-"""
-Given a list of system packages,
-some packages cannot be installed until the other packages are installed.
-Provide a valid sequence to install all of the packages.
-
-e.g.
-a relies on b
-b relies on c
-
-then a valid sequence is [c, b, a]
-"""
-
-depGraph = {
-
-    "a": ["b"],
-    "b": ["c"],
-    "c": ['e'],
-    'e': [],
-    "d": [],
-    "f": ["e", "d"]
-}
-
-given = ["b", "c", "a", "d", "e", "f"]
-
-
-def ret_deps(visited, start):
-    queue = []
-    out = []
-    queue.append(start)
-    while queue:
-        new_node = queue.pop(0)
-        if new_node not in visited:
-            visited.add(new_node)
-        for child in depGraph[new_node]:
-            queue.append(child)
-            out.append(child)
-    out.append(start)
-    return out
-
-
-def ret_dep_graph():
-    visited = set()
-    out = []
-    # visited.add(given[0])
-    for pac in given:
-        if pac in visited:
-            continue
-        visited.add(pac)
-        # out.append(pac)
-        if pac in depGraph:
-            # find all children
-            for child in depGraph[pac]:
-                if child in visited:
-                    continue
-                out.extend(ret_deps(visited, child))
-        out.append(pac)
-    print(out)
-
-
-ret_dep_graph()


Test patch:
diff --git a/tests/graph/__init__.py b/tests/graph/__init__.py
new file mode 100644
index 0000000..8b13789
--- /dev/null
+++ b/tests/graph/__init__.py
@@ -0,0 +1,1 @@
+
diff --git a/tests/graph/test_topsort.py b/tests/graph/test_topsort.py
new file mode 100644
index 0000000..a308ed3
--- /dev/null
+++ 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()