orchestrata_tools.dependency.cycle_detector

Reference › orchestrata_tools › dependency › cycle_detector

This module finds circular imports in the graph built by import_graph. CycleDetector.find_cycles runs a depth-first search from each module, following dependencies_of, and records a cycle whenever a dependency already sits on the current path. Paths longer than max_length (default 6) are abandoned. Each cycle is rotated so it starts at its smallest module name and ends by repeating it, which prevents the same cycle being reported from several starting points. has_cycles returns true if any cycle of length up to 3 exists.

At a glance

Class diagram

Dependency diagram

API

Classes

CycleDetector

Line 11

Detect circular imports in the dependency graph.

Source

Permalink: https://gitlab.com/MSamy/orchestrata-ultimate-architecture/-/blob/a4cbc2bdf/src/orchestrata_tools/dependency/cycle_detector.py

"""Circular import detection using DFS."""

from __future__ import annotations

from typing import TYPE_CHECKING

if TYPE_CHECKING:
    from orchestrata_tools.dependency.import_graph import ImportGraph


class CycleDetector:
    """Detect circular imports in the dependency graph."""

    def __init__(self, graph: ImportGraph):
        self.graph = graph

    def find_cycles(self, max_length: int = 6) -> list[list[str]]:
        """Find all import cycles up to a maximum length."""
        cycles: list[list[str]] = []
        visited: set[str] = set()

        def _dfs(node: str, path: list[str]) -> None:
            if len(path) > max_length:
                return
            for dep in self.graph.dependencies_of(node):
                if dep in path:
                    cycle = path[path.index(dep) :] + [dep]
                    # Normalize: start from alphabetically smallest node
                    start = min(range(len(cycle) - 1), key=lambda i: cycle[i])
                    normalized = cycle[start:-1] + cycle[:start] + [cycle[start]]
                    if normalized not in cycles:
                        cycles.append(normalized)
                elif dep not in visited:
                    _dfs(dep, path + [dep])

        for module in self.graph.all_modules():
            if module not in visited:
                _dfs(module, [module])
                visited.add(module)

        return cycles

    def has_cycles(self) -> bool:
        """Return True if any cycles exist."""
        return len(self.find_cycles(max_length=3)) > 0