In a graph with merge migrations, iterative_dfs() traverses each node only once even if there are multiple paths leading to it.
(self)
| 194 | self.assertEqual(expected[::-1], backwards_plan) |
| 195 | |
| 196 | def test_iterative_dfs_complexity(self): |
| 197 | """ |
| 198 | In a graph with merge migrations, iterative_dfs() traverses each node |
| 199 | only once even if there are multiple paths leading to it. |
| 200 | """ |
| 201 | n = 50 |
| 202 | graph = MigrationGraph() |
| 203 | for i in range(1, n + 1): |
| 204 | graph.add_node(("app_a", str(i)), None) |
| 205 | graph.add_node(("app_b", str(i)), None) |
| 206 | graph.add_node(("app_c", str(i)), None) |
| 207 | for i in range(1, n): |
| 208 | graph.add_dependency(None, ("app_b", str(i)), ("app_a", str(i))) |
| 209 | graph.add_dependency(None, ("app_c", str(i)), ("app_a", str(i))) |
| 210 | graph.add_dependency(None, ("app_a", str(i + 1)), ("app_b", str(i))) |
| 211 | graph.add_dependency(None, ("app_a", str(i + 1)), ("app_c", str(i))) |
| 212 | plan = graph.forwards_plan(("app_a", str(n))) |
| 213 | expected = [ |
| 214 | (app, str(i)) for i in range(1, n) for app in ["app_a", "app_c", "app_b"] |
| 215 | ] + [("app_a", str(n))] |
| 216 | self.assertEqual(plan, expected) |
| 217 | |
| 218 | def test_plan_invalid_node(self): |
| 219 | """ |
nothing calls this directly
no test coverage detected