1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
|
Description: Make graphlib less recursive
Fixes FTBFS on armel, mipsel, mips64el
Author: Armin Rigo <arigo@tunes.org>
Origin: upstream,
https://bitbucket.org/pypy/pypy/commits/198fd97491aa047542f85ee0069ae2d82c832df9
https://bitbucket.org/pypy/pypy/commits/c49289d2da9650a94976de2a4489d1f9d7f42940
https://bitbucket.org/pypy/pypy/commits/924339af3d65f367d2b7a6d06276dbd230c50439
https://bitbucket.org/pypy/pypy/commits/da7ce96af92c1537a3bf15f92f5f50bd6dc419a3
diff --git a/rpython/tool/algo/graphlib.py b/rpython/tool/algo/graphlib.py
--- a/rpython/tool/algo/graphlib.py
+++ b/rpython/tool/algo/graphlib.py
@@ -25,18 +25,27 @@
return edges
def depth_first_search(root, vertices, edges):
- seen = {}
+ seen = set([root])
result = []
- def visit(vertex):
- result.append(('start', vertex))
- seen[vertex] = True
- for edge in edges[vertex]:
- w = edge.target
- if w in vertices and w not in seen:
- visit(w)
- result.append(('stop', vertex))
- visit(root)
- return result
+ stack = []
+ while True:
+ result.append(('start', root))
+ stack.append((root, iter(edges[root])))
+ while True:
+ vertex, iterator = stack[-1]
+ try:
+ edge = next(iterator)
+ except StopIteration:
+ stack.pop()
+ result.append(('stop', vertex))
+ if not stack:
+ return result
+ else:
+ w = edge.target
+ if w in vertices and w not in seen:
+ seen.add(w)
+ root = w
+ break
def vertices_reachable_from(root, vertices, edges):
for event, v in depth_first_search(root, vertices, edges):
@@ -97,13 +106,20 @@
for edge in edges[v]:
if edge.target in vertices:
edgestack.append(edge)
- visit(edge.target)
+ yield visit(edge.target)
edgestack.pop()
stackpos[v] = None
else:
if stackpos[v] is not None: # back-edge
result.append(edgestack[stackpos[v]:])
- visit(root)
+
+ pending = [visit(root)]
+ while pending:
+ generator = pending[-1]
+ try:
+ pending.append(next(generator))
+ except StopIteration:
+ pending.pop()
return result
@@ -164,14 +180,20 @@
raise CycleFound
if w in unvisited:
del unvisited[w]
- visit(w)
+ yield visit(w)
del visiting[vertex]
try:
unvisited = vertices.copy()
while unvisited:
visiting = {}
root = unvisited.popitem()[0]
- visit(root)
+ pending = [visit(root)]
+ while pending:
+ generator = pending[-1]
+ try:
+ pending.append(next(generator))
+ except StopIteration:
+ pending.pop()
except CycleFound:
return False
else:
diff --git a/rpython/tool/algo/test/test_graphlib.py b/rpython/tool/algo/test/test_graphlib.py
--- a/rpython/tool/algo/test/test_graphlib.py
+++ b/rpython/tool/algo/test/test_graphlib.py
@@ -20,6 +20,22 @@
'G': [],
}
+ def test_depth_first_search(self):
+ # 'D' missing from the list of vertices
+ lst = depth_first_search('A', list('ABCEFG'), self.edges)
+ assert lst == [
+ ('start', 'A'),
+ ('start', 'B'),
+ ('start', 'E'),
+ ('start', 'C'),
+ ('start', 'F'),
+ ('stop', 'F'),
+ ('stop', 'C'),
+ ('stop', 'E'),
+ ('stop', 'B'),
+ ('stop', 'A'),
+ ]
+
def test_strong_components(self):
edges = self.edges
saved = copy_edges(edges)
|
