1import graphlib 2import os 3import unittest 4 5from test.support.script_helper import assert_python_ok 6 7class 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 with self.assertRaisesRegex(ValueError, r"cannot prepare\(\) more than once"): 144 ts.prepare() 145 146 def test_invalid_nodes_in_done(self): 147 ts = graphlib.TopologicalSorter() 148 ts.add(1, 2, 3, 4) 149 ts.add(2, 3, 4) 150 ts.prepare() 151 ts.get_ready() 152 153 with self.assertRaisesRegex(ValueError, "node 2 was not passed out"): 154 ts.done(2) 155 with self.assertRaisesRegex(ValueError, r"node 24 was not added using add\(\)"): 156 ts.done(24) 157 158 def test_done(self): 159 ts = graphlib.TopologicalSorter() 160 ts.add(1, 2, 3, 4) 161 ts.add(2, 3) 162 ts.prepare() 163 164 self.assertEqual(ts.get_ready(), (3, 4)) 165 # If we don't mark anything as done, get_ready() returns nothing 166 self.assertEqual(ts.get_ready(), ()) 167 ts.done(3) 168 # Now 2 becomes available as 3 is done 169 self.assertEqual(ts.get_ready(), (2,)) 170 self.assertEqual(ts.get_ready(), ()) 171 ts.done(4) 172 ts.done(2) 173 # Only 1 is missing 174 self.assertEqual(ts.get_ready(), (1,)) 175 self.assertEqual(ts.get_ready(), ()) 176 ts.done(1) 177 self.assertEqual(ts.get_ready(), ()) 178 self.assertFalse(ts.is_active()) 179 180 def test_is_active(self): 181 ts = graphlib.TopologicalSorter() 182 ts.add(1, 2) 183 ts.prepare() 184 185 self.assertTrue(ts.is_active()) 186 self.assertEqual(ts.get_ready(), (2,)) 187 self.assertTrue(ts.is_active()) 188 ts.done(2) 189 self.assertTrue(ts.is_active()) 190 self.assertEqual(ts.get_ready(), (1,)) 191 self.assertTrue(ts.is_active()) 192 ts.done(1) 193 self.assertFalse(ts.is_active()) 194 195 def test_not_hashable_nodes(self): 196 ts = graphlib.TopologicalSorter() 197 self.assertRaises(TypeError, ts.add, dict(), 1) 198 self.assertRaises(TypeError, ts.add, 1, dict()) 199 self.assertRaises(TypeError, ts.add, dict(), dict()) 200 201 def test_order_of_insertion_does_not_matter_between_groups(self): 202 def get_groups(ts): 203 ts.prepare() 204 while ts.is_active(): 205 nodes = ts.get_ready() 206 ts.done(*nodes) 207 yield set(nodes) 208 209 ts = graphlib.TopologicalSorter() 210 ts.add(3, 2, 1) 211 ts.add(1, 0) 212 ts.add(4, 5) 213 ts.add(6, 7) 214 ts.add(4, 7) 215 216 ts2 = graphlib.TopologicalSorter() 217 ts2.add(1, 0) 218 ts2.add(3, 2, 1) 219 ts2.add(4, 7) 220 ts2.add(6, 7) 221 ts2.add(4, 5) 222 223 self.assertEqual(list(get_groups(ts)), list(get_groups(ts2))) 224 225 def test_static_order_does_not_change_with_the_hash_seed(self): 226 def check_order_with_hash_seed(seed): 227 code = """if 1: 228 import graphlib 229 ts = graphlib.TopologicalSorter() 230 ts.add('blech', 'bluch', 'hola') 231 ts.add('abcd', 'blech', 'bluch', 'a', 'b') 232 ts.add('a', 'a string', 'something', 'b') 233 ts.add('bluch', 'hola', 'abcde', 'a', 'b') 234 print(list(ts.static_order())) 235 """ 236 env = os.environ.copy() 237 # signal to assert_python not to do a copy 238 # of os.environ on its own 239 env["__cleanenv"] = True 240 env["PYTHONHASHSEED"] = str(seed) 241 out = assert_python_ok("-c", code, **env) 242 return out 243 244 run1 = check_order_with_hash_seed(1234) 245 run2 = check_order_with_hash_seed(31415) 246 247 self.assertNotEqual(run1, "") 248 self.assertNotEqual(run2, "") 249 self.assertEqual(run1, run2) 250 251if __name__ == "__main__": 252 unittest.main() 253