From b878c73fc34e661e1cc30fc96171ce09918efced Mon Sep 17 00:00:00 2001 From: Ben Reilly Date: Fri, 5 Sep 2014 15:26:05 -0700 Subject: switch out recursive dfs for stack based approach, to avoid possibly hitting the recursion limit --- tests/migrations/test_graph.py | 15 +++++++++++++++ 1 file changed, 15 insertions(+) (limited to 'tests') diff --git a/tests/migrations/test_graph.py b/tests/migrations/test_graph.py index ada8a5a1e5..23ec450246 100644 --- a/tests/migrations/test_graph.py +++ b/tests/migrations/test_graph.py @@ -134,6 +134,21 @@ class GraphTests(TestCase): graph.forwards_plan, ("app_a", "0003"), ) + def test_dfs(self): + graph = MigrationGraph() + root = ("app_a", "1") + graph.add_node(root, None) + expected = [root] + for i in xrange(2, 1000): + parent = ("app_a", str(i - 1)) + child = ("app_a", str(i)) + graph.add_node(child, None) + graph.add_dependency(str(i), child, parent) + expected.append(child) + + actual = graph.dfs(root, lambda x: graph.dependents.get(x, set())) + self.assertEqual(expected[::-1], actual) + def test_plan_invalid_node(self): """ Tests for forwards/backwards_plan of nonexistent node. -- cgit v1.3