| 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() |