Every import cycle, deterministically

Turn “we should not have circular imports” from a habit into a test.

def find_import_cycles(graph: Mapping[str, Sequence[str]]) -> list[tuple[str, ...]]:

graph maps a module name to the modules it imports. Return every elementary cycle — a cycle that visits no module twice — with these normalisation rules, which exist so the output is comparable across runs:

• Each cycle is a tuple listing its members once, in traversal order, rotated so that it starts at its lexicographically smallest member. The cycle b → c → b is reported as ("b", "c"), never as ("c", "b") and never with a repeated closing element.
• A self-import is a cycle of length one: ("a",).
• The returned list is sorted.
• An import of a module that is not a key of graph is ignored. Third-party and stdlib imports appear in a real graph and are not part of your cycles.

Why the normalisation is the hard part. A three-node cycle can be discovered from three different starting points and traversed in two directions. Without a canonical form you report the same architectural problem three times, the numbers move every time somebody adds an unrelated module, and nobody trusts the check. A fitness function that produces unstable output gets deleted.

What this is for. This is the primitive under import-linter‘s cycle contract and under ruff analyze graph. Once find_import_cycles(graph) == [] is an assertion in your suite, a cycle stops being something you discover from a stack trace at 3 a.m. and becomes a failing test on the branch that introduced it.

Watch the figure-eight case: two cycles sharing one node are two findings, not one four-node cycle. That distinction is the difference between “one module is over-connected” and “these four modules are a tangle”, and a reviewer needs to be told which.

Your submission must pass mypy --strict. Note that graph.get(node, ()) needs a default whose type is compatible with Sequence[str] — the empty tuple is, the empty list also is.