Coverage for /var/srv/projects/api.amasfac.comuna18.com/tmp/venv/lib/python3.9/site-packages/django/utils/topological_sort.py: 17%
17 statements
« prev ^ index » next coverage.py v6.4.4, created at 2023-07-17 14:22 -0600
« prev ^ index » next coverage.py v6.4.4, created at 2023-07-17 14:22 -0600
1class CyclicDependencyError(ValueError):
2 pass
5def topological_sort_as_sets(dependency_graph):
6 """
7 Variation of Kahn's algorithm (1962) that returns sets.
9 Take a dependency graph as a dictionary of node => dependencies.
11 Yield sets of items in topological order, where the first set contains
12 all nodes without dependencies, and each following set contains all
13 nodes that may depend on the nodes only in the previously yielded sets.
14 """
15 todo = dependency_graph.copy()
16 while todo:
17 current = {node for node, deps in todo.items() if not deps}
19 if not current:
20 raise CyclicDependencyError(
21 "Cyclic dependency in graph: {}".format(
22 ", ".join(repr(x) for x in todo.items())
23 )
24 )
26 yield current
28 # remove current from todo's nodes & dependencies
29 todo = {
30 node: (dependencies - current)
31 for node, dependencies in todo.items()
32 if node not in current
33 }
36def stable_topological_sort(nodes, dependency_graph):
37 result = []
38 for layer in topological_sort_as_sets(dependency_graph):
39 for node in nodes:
40 if node in layer:
41 result.append(node)
42 return result