31 lines
910 B
Python
31 lines
910 B
Python
|
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: (1, {2}), (2, {1})"
|
||
|
|
with self.assertRaisesMessage(CyclicDependencyError, msg):
|
||
|
|
list(topological_sort_as_sets({1: {2}, 2: {1}}))
|