Zhengli0817 patch 1 - update topsort.py (#295) · wxpython/algorithms@97e5e85 · GitHub
Skip to content

Commit 97e5e85

Browse files
zhengli0817keon
zhengli0817
authored and
keon
committed
Zhengli0817 patch 1 - update topsort.py (keon#295)
* 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
1 parent 4a3cbb7 commit 97e5e85

5 files changed

Lines changed: 95 additions & 60 deletions

File tree

‎algorithms/sort/__init__.py‎

Lines changed: 1 addition & 0 deletions

‎algorithms/sort/top_sort.py‎

Lines changed: 66 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,66 @@
1+
GRAY, BLACK = 0, 1
2+
3+
def top_sort_recursive(graph):
4+
""" Time complexity is the same as DFS, which is O(V + E)
5+
Space complexity: O(V)
6+
"""
7+
order, enter, state = [], set(graph), {}
8+
9+
def dfs(node):
10+
state[node] = GRAY
11+
#print(node)
12+
for k in graph.get(node, ()):
13+
sk = state.get(k, None)
14+
if sk == GRAY:
15+
raise ValueError("cycle")
16+
if sk == BLACK:
17+
continue
18+
enter.discard(k)
19+
dfs(k)
20+
order.append(node)
21+
state[node] = BLACK
22+
23+
while enter: dfs(enter.pop())
24+
return order
25+
26+
def top_sort(graph):
27+
""" Time complexity is the same as DFS, which is O(V + E)
28+
Space complexity: O(V)
29+
"""
30+
order, enter, state = [], set(graph), {}
31+
32+
def is_ready(node):
33+
lst = graph.get(node, ())
34+
if len(lst) == 0:
35+
return True
36+
for k in lst:
37+
sk = state.get(k, None)
38+
if sk == GRAY:
39+
raise ValueError("cycle")
40+
if sk != BLACK:
41+
return False
42+
return True
43+
44+
while enter:
45+
node = enter.pop()
46+
stack = []
47+
while True:
48+
state[node] = GRAY
49+
stack.append(node)
50+
for k in graph.get(node, ()):
51+
sk = state.get(k, None)
52+
if sk == GRAY:
53+
raise ValueError("cycle")
54+
if sk == BLACK:
55+
continue
56+
enter.discard(k)
57+
stack.append(k)
58+
while stack and is_ready(stack[-1]):
59+
node = stack.pop()
60+
order.append(node)
61+
state[node] = BLACK
62+
if len(stack) == 0:
63+
break
64+
node = stack.pop()
65+
66+
return order

‎algorithms/sort/topsort.py‎

Lines changed: 0 additions & 60 deletions
This file was deleted.

‎tests/graph/__init__.py‎

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1 @@
1+

‎tests/graph/test_topsort.py‎

Lines changed: 27 additions & 0 deletions

0 commit comments

Comments
 (0)