Skip to content

Cycles

cycles

Import-cycle detection for the move pipeline.

GraphEdits dataclass

Edge additions and removals to apply to an import graph.

Source code in packages/axm-anvil/src/axm_anvil/core/cycles.py
Python
10
11
12
13
14
15
@dataclass
class GraphEdits:
    """Edge additions and removals to apply to an import graph."""

    adds: list[tuple[str, str]] = field(default_factory=list)
    removes: list[tuple[str, str]] = field(default_factory=list)

cycles(graph)

Return SCCs of size > 1 plus self-loops.

Source code in packages/axm-anvil/src/axm_anvil/core/cycles.py
Python
82
83
84
85
86
87
88
89
90
def cycles(graph: dict[str, set[str]]) -> list[list[str]]:
    """Return SCCs of size > 1 plus self-loops."""
    out: list[list[str]] = []
    for scc in _tarjan_sccs(graph):
        if len(scc) > 1:
            out.append(scc)
        elif len(scc) == 1 and scc[0] in graph.get(scc[0], set()):
            out.append(scc)
    return out

detect_new_cycle(graph, edits)

Apply edits to a copy of graph and return the first newly introduced cycle, or None if the edits do not create any new cycle.

Pre-existing cycles (already present in graph) are ignored.

Source code in packages/axm-anvil/src/axm_anvil/core/cycles.py
Python
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
def detect_new_cycle(graph: dict[str, set[str]], edits: GraphEdits) -> list[str] | None:
    """Apply ``edits`` to a copy of ``graph`` and return the first newly
    introduced cycle, or ``None`` if the edits do not create any new cycle.

    Pre-existing cycles (already present in ``graph``) are ignored.
    """
    pre = {frozenset(c) for c in cycles(graph)}
    new_graph: dict[str, set[str]] = {k: set(v) for k, v in graph.items()}
    for src, dst in edits.removes:
        if src in new_graph:
            new_graph[src].discard(dst)
    for src, dst in edits.adds:
        new_graph.setdefault(src, set()).add(dst)
        new_graph.setdefault(dst, set())
    for scc in cycles(new_graph):
        if frozenset(scc) not in pre:
            return _order_cycle(scc, new_graph)
    return None