blob: cb354809bfbe9799d39341140f2a05921f5bcddc (
plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
|
"""Helper methods related to graph theory."""
from __future__ import annotations
from collections import OrderedDict, defaultdict
def stable_topological_sort(graph: dict[str, set[str]]) -> list[str]:
to_order = set(graph.keys()) # keep a log of what we need to order
# normalize graph - fill missing nodes (assume no dependency)
for values in list(graph.values()):
for value in values:
if value not in graph:
graph[value] = set()
inverse_graph = defaultdict(set)
for key, depends in graph.items():
for depend in depends:
inverse_graph[depend].add(key)
topology = []
degree = {k: len(v) for k, v in graph.items()}
ready_to_visit = {n for n, d in degree.items() if not d}
need_to_visit = OrderedDict((i, None) for i in graph.keys())
while need_to_visit:
# to keep stable, pick the first node ready to visit in the original order
for node in need_to_visit:
if node in ready_to_visit:
break
else:
break
del need_to_visit[node]
topology.append(node)
# decrease degree for nodes we're going too
for to_node in inverse_graph[node]:
degree[to_node] -= 1
if not degree[to_node]: # if a node has no more incoming node it's ready to visit
ready_to_visit.add(to_node)
result = [n for n in topology if n in to_order] # filter out missing nodes we extended
if len(result) < len(to_order):
identify_cycle(graph)
msg = "could not order tox environments and failed to detect circle" # pragma: no cover
raise ValueError(msg) # pragma: no cover
return result
def identify_cycle(graph: dict[str, set[str]]) -> None:
path: dict[str, None] = OrderedDict()
visited = set()
def visit(vertex: str) -> dict[str, None] | None:
if vertex in visited:
return None
visited.add(vertex)
path[vertex] = None
for neighbour in graph.get(vertex, ()):
if neighbour in path or visit(neighbour):
return path
del path[vertex]
return None
for node in graph: # pragma: no branch # we never get here if the graph is empty
result = visit(node)
if result is not None:
raise ValueError(f"{' | '.join(result.keys())}")
|
