Function resolve_cycles

codewiki/src/be/dependency_analyzer/topo_sort.py:78–119

Resolve cycles in a dependency graph by identifying strongly connected components and breaking cycles. Args: graph: A dependency graph represented as adjacency lists (node -> set of dependencies) Returns: A new acyclic graph with the same nod

(graph: Dict[str, Set[str]])

    # Visit each node
    for node in graph:
        if node not in index:
            strongconnect(node)

    return result


def resolve_cycles(graph: dict[str, set[str]]) -> dict[str, set[str]]:
    """
    Resolve cycles in a dependency graph by identifying strongly connected
    components and breaking cycles.

    Args:
        graph: A dependency graph represented as adjacency lists
               (node -> set of dependencies)

    Returns:
        A new acyclic graph with the same nodes but with cycles broken
    """
    # Detect cycles (SCCs)
    cycles = detect_cycles(graph)

    if not cycles:
        logger.debug("No cycles detected in the dependency graph")
        return graph

    logger.debug(f"Detected {len(cycles)} cycles in the dependency graph")

    # Create a copy of the graph to modify
    new_graph = {node: deps.copy() for node, deps in graph.items()}

    # Process each cycle
    for i, cycle in enumerate(cycles):
        logger.debug(f"Cycle {i + 1}: {' -> '.join(cycle)}")

        # Strategy: Break the cycle by removing the "weakest" dependency
        # Here, we just arbitrarily remove the last edge to make the graph acyclic
        # In a real-world scenario, you might use heuristics to determine which edge to break
        # For example, removing edges between different modules before edges within the same module
        for j in range(len(cycle) - 1):
            current = cycle[j]
            next_node = cycle[j + 1]

            if next_node in new_graph[current]:
                logger.debug(f"Breaking cycle by removing dependency: {current} -> {next_node}")
                new_graph[current].remove(next_node)