diff options
| -rw-r--r-- | django/db/migrations/graph.py | 17 |
1 files changed, 10 insertions, 7 deletions
diff --git a/django/db/migrations/graph.py b/django/db/migrations/graph.py index b454d17f35..a2c14f2ba6 100644 --- a/django/db/migrations/graph.py +++ b/django/db/migrations/graph.py @@ -1,4 +1,5 @@ from __future__ import unicode_literals +from collections import deque from django.db.migrations.state import ProjectState from django.utils.datastructures import OrderedSet @@ -100,26 +101,28 @@ class MigrationGraph(object): def dfs(self, start, get_children): """ - Dynamic programming based depth first search, for finding dependencies. + Iterative depth first search, for finding dependencies. """ - visited = [] + visited = deque() visited.append(start) path = [start] - stack = sorted(get_children(start)) + stack = deque(sorted(get_children(start))) while stack: - node = stack.pop(0) + node = stack.popleft() if node in path: raise CircularDependencyError() path.append(node) - visited.insert(0, node) - children = sorted(get_children(node)) + visited.appendleft(node) + children = sorted(get_children(node), reverse=True) + # reverse sorting is needed because prepending using deque.extendleft + # also effectively reverses values if path[-1] == node: path.pop() - stack = children + stack + stack.extendleft(children) return list(OrderedSet(visited)) |