[2.2.x] Refs #30179 -- Moved topological sort functions to django.utils.

Backport of e04209e181c99ac16ca769d115ac640015a83757 from master.

1 files changed, 36 insertions, 0 deletions

diff --git a/django/utils/topological_sort.py b/django/utils/topological_sort.py
new file mode 100644
index 0000000000..3f8ea0f2e4
--- /dev/null
+++ b/django/utils/topological_sort.py
@@ -0,0 +1,36 @@
+class CyclicDependencyError(ValueError):
+    pass
+
+
+def topological_sort_as_sets(dependency_graph):
+    """
+    Variation of Kahn's algorithm (1962) that returns sets.
+
+    Take a dependency graph as a dictionary of node => dependencies.
+
+    Yield sets of items in topological order, where the first set contains
+    all nodes without dependencies, and each following set contains all
+    nodes that may depend on the nodes only in the previously yielded sets.
+    """
+    todo = dependency_graph.copy()
+    while todo:
+        current = {node for node, deps in todo.items() if not deps}
+
+        if not current:
+            raise CyclicDependencyError('Cyclic dependency in graph: {}'.format(
+                ', '.join(repr(x) for x in todo.items())))
+
+        yield current
+
+        # remove current from todo's nodes & dependencies
+        todo = {node: (dependencies - current) for node, dependencies in
+                todo.items() if node not in current}
+
+
+def stable_topological_sort(l, dependency_graph):
+    result = []
+    for layer in topological_sort_as_sets(dependency_graph):
+        for node in l:
+            if node in layer:
+                result.append(node)
+    return result