Function topological_sort

codewiki/src/be/dependency_analyzer/topo_sort.py:121–169

Perform a topological sort on a dependency graph. Args: graph: A dependency graph represented as adjacency lists (node -> set of dependencies) Returns: A list of nodes in topological order (dependencies first)

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

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

    return new_graph


def topological_sort(graph: dict[str, set[str]]) -> list[str]:
    """
    Perform a topological sort on a dependency graph.

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

    Returns:
        A list of nodes in topological order (dependencies first)
    """
    # First, check for and resolve cycles
    acyclic_graph = resolve_cycles(graph)

    # Initialize in-degree counter for all nodes
    in_degree = {node: 0 for node in acyclic_graph}

    # Count in-degrees
    for node, dependencies in acyclic_graph.items():
        for dep in dependencies:
            if dep in in_degree:
                in_degree[dep] += 1

    # Queue of nodes with no dependencies (in-degree of 0)
    queue = deque([node for node, degree in in_degree.items() if degree == 0])

    # Result list to store the topological order
    result = []

    # Process nodes in topological order
    while queue:
        node = queue.popleft()
        result.append(node)

        # Reduce in-degree for each node that depends on the current node
        for dependent, deps in acyclic_graph.items():
            if node in deps:
                in_degree[dependent] -= 1
                if in_degree[dependent] == 0:
                    queue.append(dependent)

    # Check if the sort was successful (all nodes included)
    if len(result) != len(acyclic_graph):
        logger.warning("Topological sort failed: graph has cycles that weren't resolved")
        # Return all nodes in some order to avoid breaking the process