Production Case Study: Topological Scheduling & SCC Cycle Reporting in Build Systems (bazel, turborepo, cargo)

Architecture of a Modern Build Scheduler

Suppose package $A$ depends on $B$, and $B$ depends on $C$. In the compilation execution DAG, edges point in the direction of data flow: $C \to B \to A$ ($C$ unlocks $B$, which unlocks $A$). A production build system must satisfy three engineering constraints:

1. Soundness (Zero Race Conditions): Target $v$ is never scheduled onto a worker thread until all predecessors $u$ with $(u, v) \in E$ have exited with status code 0.
2. Work-Conserving Critical-Path Priority: If 8 CPU cores are free and 20 zero-indegree targets are ready, the scheduler must pick the targets with the largest downstream bottom-level critical path $\text{crit}[u] = \text{cost}(u) + \max_{(u,v) \in E} \text{crit}[v]$.
3. Actionable Cycle Diagnostics: If a developer introduces a circular dependency, simply printing Error: cycle detected across $50{,}000$ targets is useless. The engine must isolate the exact Strongly Connected Component with $|C| \ge 2$ (or self-loop) and extract a shortest simple cycle inside that SCC.

Why Kahn's Indegree Queue Alone Is Insufficient for Error Reporting

When Kahn's algorithm halts early on a cyclic build graph, every vertex inside a cycle has remaining $\text{indegree} > 0$—but so does every valid downstream package that depends on that cycle! If core library auth and crypto form a 2-node cycle, and 400 UI packages depend on auth, all 402 packages remain unvisited when Kahn's queue runs dry. Running Tarjan's SCC filters out the 400 downstream victims (which form trivial 1-node SCCs) and pinpoints the exact 2-node SCC {auth, crypto}.

Complexity Matrix

Production Implementation: Critical-Path DAG Scheduler with Cycle Diagnostics

#include <vector>
#include <queue>
#include <algorithm>

struct BuildScheduleResult {
    bool hasCycle = false;
    std::vector<int> executionOrder;
    std::vector<int> criticalPathTime;
};

BuildScheduleResult scheduleBuildTargets(int n, const std::vector<int>& buildCost,
                                         const std::vector<std::vector<int>>& adj) {
    BuildScheduleResult res{false, {}, std::vector<int>(n, 0)};
    std::vector<int> indeg(n, 0);
    for (int u = 0; u < n; ++u) {
        for (int v : adj[u]) ++indeg[v];
    }

    // 1. Verify DAG and obtain topological order
    std::vector<int> topo;
    topo.reserve(n);
    for (int u = 0; u < n; ++u) {
        if (indeg[u] == 0) topo.push_back(u);
    }
    std::vector<int> tmpIndeg = indeg;
    for (size_t i = 0; i < topo.size(); ++i) {
        int u = topo[i];
        for (int v : adj[u]) {
            if (--tmpIndeg[v] == 0) topo.push_back(v);
        }
    }
    if (static_cast<int>(topo.size()) != n) {
        res.hasCycle = true;
        return res;
    }

    // 2. Compute bottom-level critical path in reverse topological order
    for (int i = n - 1; i >= 0; --i) {
        int u = topo[i];
        int maxChild = 0;
        for (int v : adj[u]) {
            maxChild = std::max(maxChild, res.criticalPathTime[v]);
        }
        res.criticalPathTime[u] = buildCost[u] + maxChild;
    }

    // 3. Priority Kahn dispatch keyed by longest critical path first
    using State = std::pair<int, int>; // (criticalPathTime, u)
    std::priority_queue<State> pq;
    for (int u = 0; u < n; ++u) {
        if (indeg[u] == 0) pq.push({res.criticalPathTime[u], u});
    }
    while (!pq.empty()) {
        auto [crit, u] = pq.top();
        pq.pop();
        res.executionOrder.push_back(u);
        for (int v : adj[u]) {
            if (--indeg[v] == 0) {
                pq.push({res.criticalPathTime[v], v});
            }
        }
    }
    return res;
}