From 77e53da127cfb5d4f0c9a3540a02ff24f04fe9e2 Mon Sep 17 00:00:00 2001 From: Matthias Kestenholz Date: Sun, 24 Feb 2019 13:08:59 +0100 Subject: [2.2.x] Refs #30179 -- Moved topological sort functions to django.utils. Backport of e04209e181c99ac16ca769d115ac640015a83757 from master. --- tests/utils_tests/test_topological_sort.py | 24 ++++++++++++++++++++++++ 1 file changed, 24 insertions(+) create mode 100644 tests/utils_tests/test_topological_sort.py (limited to 'tests') diff --git a/tests/utils_tests/test_topological_sort.py b/tests/utils_tests/test_topological_sort.py new file mode 100644 index 0000000000..ed8f9fd5a6 --- /dev/null +++ b/tests/utils_tests/test_topological_sort.py @@ -0,0 +1,24 @@ +from django.test import SimpleTestCase +from django.utils.topological_sort import ( + CyclicDependencyError, stable_topological_sort, topological_sort_as_sets, +) + + +class TopologicalSortTests(SimpleTestCase): + + def test_basic(self): + dependency_graph = { + 1: {2, 3}, + 2: set(), + 3: set(), + 4: {5, 6}, + 5: set(), + 6: {5}, + } + self.assertEqual(list(topological_sort_as_sets(dependency_graph)), [{2, 3, 5}, {1, 6}, {4}]) + self.assertEqual(stable_topological_sort([1, 2, 3, 4, 5, 6], dependency_graph), [2, 3, 5, 1, 6, 4]) + + def test_cyclic_dependency(self): + msg = 'Cyclic dependency in graph: ' + with self.assertRaisesMessage(CyclicDependencyError, msg): + list(topological_sort_as_sets({1: {2}, 2: {1}})) -- cgit v1.3