Topologically Sort Build Targets with Cycle Detection

from __future__ import annotations

from collections import defaultdict, deque


def build_order(prerequisites: dict[str, list[str]]) -> list[str]:
    indegree = {node: 0 for node in prerequisites}
    dependents: dict[str, list[str]] = defaultdict(list)
    for node, deps in prerequisites.items():
        for dep in deps:
            indegree.setdefault(dep, 0)
            dependents[dep].append(node)
            indegree[node] += 1

    ready = deque(sorted(node for node, degree in indegree.items() if degree == 0))
    order: list[str] = []
    while ready:
        node = ready.popleft()
        order.append(node)
        for child in sorted(dependents[node]):
            indegree[child] -= 1
            if indegree[child] == 0:
                ready.append(child)

    if len(order) != len(indegree):
        blocked = sorted(node for node, degree in indegree.items() if degree > 0)
        raise ValueError(f"dependency cycle among: {', '.join(blocked)}")
    return order


def main() -> None:
    graph = {
        "app": ["api", "db"],
        "api": ["db", "auth"],
        "auth": ["db"],
        "db": [],
        "docs": [],
    }
    order = build_order(graph)
    print(" -> ".join(order))
    assert order.index("db") < order.index("api") < order.index("app")
    try:
        build_order({"a": ["b"], "b": ["a"]})
    except ValueError as exc:
        print(f"cycle: {exc}")


if __name__ == "__main__":
    main()