Debian Codegraph @

Lib/test/test_graphlib.py

raw
1 import graphlib
2 import os
3 import unittest
4
5 from test.support.script_helper import assert_python_ok
6
7 class TestTopologicalSort(unittest.TestCase):
8 def _test_graph(self, graph, expected):
9 def static_order_with_groups(ts):
10 ts.prepare()
11 while ts.is_active():
12 nodes = ts.get_ready()
13 for node in nodes:
14 ts.done(node)
15 yield tuple(sorted(nodes))
16
17 ts = graphlib.TopologicalSorter(graph)
18 self.assertEqual(list(static_order_with_groups(ts)), list(expected))
19
20 ts = graphlib.TopologicalSorter(graph)
21 # need to be a bit careful comparing the result of ts.static_order and
22 # expected, because the order within a group is dependent on set
23 # iteration order
24 it = iter(ts.static_order())
25 for group in expected:
26 tsgroup = {next(it) for element in group}
27 self.assertEqual(set(group), tsgroup)
28
29 def _assert_cycle(self, graph, cycle):
30 ts = graphlib.TopologicalSorter()
31 for node, dependson in graph.items():
32 ts.add(node, *dependson)
33 try:
34 ts.prepare()
35 except graphlib.CycleError as e:
36 _, seq = e.args
37 self.assertIn(" ".join(map(str, cycle)), " ".join(map(str, seq * 2)))
38 else:
39 raise
40
41 def test_simple_cases(self):
42 self._test_graph(
43 {2: {11}, 9: {11, 8}, 10: {11, 3}, 11: {7, 5}, 8: {7, 3}},
44 [(3, 5, 7), (8, 11), (2, 9, 10)],
45 )
46
47 self._test_graph({1: {}}, [(1,)])
48
49 self._test_graph(
50 {x: {x + 1} for x in range(10)}, [(x,) for x in range(10, -1, -1)]
51 )
52
53 self._test_graph(
54 {2: {3}, 3: {4}, 4: {5}, 5: {1}, 11: {12}, 12: {13}, 13: {14}, 14: {15}},
55 [(1, 15), (5, 14), (4, 13), (3, 12), (2, 11)],
56 )
57
58 self._test_graph(
59 {
60 0: [1, 2],
61 1: [3],
62 2: [5, 6],
63 3: [4],
64 4: [9],
65 5: [3],
66 6: [7],
67 7: [8],
68 8: [4],
69 9: [],
70 },
71 [(9,), (4,), (3, 8), (1, 5, 7), (6,), (2,), (0,)],
72 )
73
74 self._test_graph({0: [1, 2], 1: [], 2: [3], 3: []}, [(1, 3), (2,), (0,)])
75
76 self._test_graph(
77 {0: [1, 2], 1: [], 2: [3], 3: [], 4: [5], 5: [6], 6: []},
78 [(1, 3, 6), (2, 5), (0, 4)],
79 )
80
81 def test_no_dependencies(self):
82 self._test_graph({1: {2}, 3: {4}, 5: {6}}, [(2, 4, 6), (1, 3, 5)])
83
84 self._test_graph({1: set(), 3: set(), 5: set()}, [(1, 3, 5)])
85
86 def test_the_node_multiple_times(self):
87 # Test same node multiple times in dependencies
88 self._test_graph({1: {2}, 3: {4}, 0: [2, 4, 4, 4, 4, 4]}, [(2, 4), (0, 1, 3)])
89
90 # Test adding the same dependency multiple times
91 ts = graphlib.TopologicalSorter()
92 ts.add(1, 2)
93 ts.add(1, 2)
94 ts.add(1, 2)
95 self.assertEqual([*ts.static_order()], [2, 1])
96
97 def test_graph_with_iterables(self):
98 dependson = (2 * x + 1 for x in range(5))
99 ts = graphlib.TopologicalSorter({0: dependson})
100 self.assertEqual(list(ts.static_order()), [1, 3, 5, 7, 9, 0])
101
102 def test_add_dependencies_for_same_node_incrementally(self):
103 # Test same node multiple times
104 ts = graphlib.TopologicalSorter()
105 ts.add(1, 2)
106 ts.add(1, 3)
107 ts.add(1, 4)
108 ts.add(1, 5)
109
110 ts2 = graphlib.TopologicalSorter({1: {2, 3, 4, 5}})
111 self.assertEqual([*ts.static_order()], [*ts2.static_order()])
112
113 def test_empty(self):
114 self._test_graph({}, [])
115
116 def test_cycle(self):
117 # Self cycle
118 self._assert_cycle({1: {1}}, [1, 1])
119 # Simple cycle
120 self._assert_cycle({1: {2}, 2: {1}}, [1, 2, 1])
121 # Indirect cycle
122 self._assert_cycle({1: {2}, 2: {3}, 3: {1}}, [1, 3, 2, 1])
123 # not all elements involved in a cycle
124 self._assert_cycle({1: {2}, 2: {3}, 3: {1}, 5: {4}, 4: {6}}, [1, 3, 2, 1])
125 # Multiple cycles
126 self._assert_cycle({1: {2}, 2: {1}, 3: {4}, 4: {5}, 6: {7}, 7: {6}}, [1, 2, 1])
127 # Cycle in the middle of the graph
128 self._assert_cycle({1: {2}, 2: {3}, 3: {2, 4}, 4: {5}}, [3, 2])
129
130 def test_calls_before_prepare(self):
131 ts = graphlib.TopologicalSorter()
132
133 with self.assertRaisesRegex(ValueError, r"prepare\(\) must be called first"):
134 ts.get_ready()
135 with self.assertRaisesRegex(ValueError, r"prepare\(\) must be called first"):
136 ts.done(3)
137 with self.assertRaisesRegex(ValueError, r"prepare\(\) must be called first"):
138 ts.is_active()
139
140 def test_prepare_multiple_times(self):
141 ts = graphlib.TopologicalSorter()
142 ts.prepare()
143 ts.prepare()
144
145 def test_prepare_after_pass_out(self):
146 ts = graphlib.TopologicalSorter({'a': 'bc'})
147 ts.prepare()
148 self.assertEqual(set(ts.get_ready()), {'b', 'c'})
149 with self.assertRaisesRegex(ValueError, r"cannot prepare\(\) after starting sort"):
150 ts.prepare()
151
152 def test_prepare_cycleerror_each_time(self):
153 ts = graphlib.TopologicalSorter({'a': 'b', 'b': 'a'})
154 for attempt in range(1, 4):
155 with self.assertRaises(graphlib.CycleError, msg=f"{attempt=}"):
156 ts.prepare()
157
158 def test_invalid_nodes_in_done(self):
159 ts = graphlib.TopologicalSorter()
160 ts.add(1, 2, 3, 4)
161 ts.add(2, 3, 4)
162 ts.prepare()
163 ts.get_ready()
164
165 with self.assertRaisesRegex(ValueError, "node 2 was not passed out"):
166 ts.done(2)
167 with self.assertRaisesRegex(ValueError, r"node 24 was not added using add\(\)"):
168 ts.done(24)
169
170 def test_done(self):
171 ts = graphlib.TopologicalSorter()
172 ts.add(1, 2, 3, 4)
173 ts.add(2, 3)
174 ts.prepare()
175
176 self.assertEqual(ts.get_ready(), (3, 4))
177 # If we don't mark anything as done, get_ready() returns nothing
178 self.assertEqual(ts.get_ready(), ())
179 ts.done(3)
180 # Now 2 becomes available as 3 is done
181 self.assertEqual(ts.get_ready(), (2,))
182 self.assertEqual(ts.get_ready(), ())
183 ts.done(4)
184 ts.done(2)
185 # Only 1 is missing
186 self.assertEqual(ts.get_ready(), (1,))
187 self.assertEqual(ts.get_ready(), ())
188 ts.done(1)
189 self.assertEqual(ts.get_ready(), ())
190 self.assertFalse(ts.is_active())
191
192 def test_is_active(self):
193 ts = graphlib.TopologicalSorter()
194 ts.add(1, 2)
195 ts.prepare()
196
197 self.assertTrue(ts.is_active())
198 self.assertEqual(ts.get_ready(), (2,))
199 self.assertTrue(ts.is_active())
200 ts.done(2)
201 self.assertTrue(ts.is_active())
202 self.assertEqual(ts.get_ready(), (1,))
203 self.assertTrue(ts.is_active())
204 ts.done(1)
205 self.assertFalse(ts.is_active())
206
207 def test_not_hashable_nodes(self):
208 ts = graphlib.TopologicalSorter()
209 self.assertRaises(TypeError, ts.add, dict(), 1)
210 self.assertRaises(TypeError, ts.add, 1, dict())
211 self.assertRaises(TypeError, ts.add, dict(), dict())
212
213 def test_order_of_insertion_does_not_matter_between_groups(self):
214 def get_groups(ts):
215 ts.prepare()
216 while ts.is_active():
217 nodes = ts.get_ready()
218 ts.done(*nodes)
219 yield set(nodes)
220
221 ts = graphlib.TopologicalSorter()
222 ts.add(3, 2, 1)
223 ts.add(1, 0)
224 ts.add(4, 5)
225 ts.add(6, 7)
226 ts.add(4, 7)
227
228 ts2 = graphlib.TopologicalSorter()
229 ts2.add(1, 0)
230 ts2.add(3, 2, 1)
231 ts2.add(4, 7)
232 ts2.add(6, 7)
233 ts2.add(4, 5)
234
235 self.assertEqual(list(get_groups(ts)), list(get_groups(ts2)))
236
237 def test_static_order_does_not_change_with_the_hash_seed(self):
238 def check_order_with_hash_seed(seed):
239 code = """if 1:
240 import graphlib
241 ts = graphlib.TopologicalSorter()
242 ts.add('blech', 'bluch', 'hola')
243 ts.add('abcd', 'blech', 'bluch', 'a', 'b')
244 ts.add('a', 'a string', 'something', 'b')
245 ts.add('bluch', 'hola', 'abcde', 'a', 'b')
246 print(list(ts.static_order()))
247 """
248 env = os.environ.copy()
249 # signal to assert_python not to do a copy
250 # of os.environ on its own
251 env["__cleanenv"] = True
252 env["PYTHONHASHSEED"] = str(seed)
253 out = assert_python_ok("-c", code, **env)
254 return out
255
256 run1 = check_order_with_hash_seed(1234)
257 run2 = check_order_with_hash_seed(31415)
258
259 self.assertNotEqual(run1, "")
260 self.assertNotEqual(run2, "")
261 self.assertEqual(run1, run2)
262
263 if __name__ == "__main__":
264 unittest.main()