32. Validate a Multi-Stage Eval Pipeline Has No Cycle

Problem

A lab's eval harness runs a config-driven pipeline of named stages — e.g. load_dataset, generate_responses, grade_responses, aggregate_metrics — where each stage can declare which other stages must finish first. Before launching a run, the harness must validate that the declared dependencies don't form a cycle, which would make the pipeline unrunnable.

Given the stage names and a list of dependency pairs, determine whether the dependency graph contains a cycle. Each dependency entry is (stage, depends_on), meaning stage cannot start until depends_on has completed.

Source: src/32_validate_eval_pipeline_dag.py

def pipeline_has_cycle(stages: list[str], dependencies: list[tuple[str, str]]) -> bool:
    ...

Examples:
>>> pipeline_has_cycle(
...     ["load_dataset", "generate", "grade", "aggregate"],
...     [("generate", "load_dataset"), ("grade", "generate"), ("aggregate", "grade")],
... )
False

>>> pipeline_has_cycle(["a", "b"], [("a", "b"), ("b", "a")])
True

Step-by-Step Approach

1. Build an adjacency list from the dependency pairs: for each (stage, depends_on), add an edge stage -> depends_on.
2. Recognize this as cycle detection in a directed graph, which needs three states per node, not two — a plain visited/unvisited boolean can't distinguish "currently being explored on this DFS path" from "fully explored and known safe."
3. Track a color per stage: WHITE (unvisited), GRAY (on the current DFS path, not yet finished), BLACK (fully explored, no cycle found through it).
4. DFS from every WHITE stage. When visiting a node, mark it GRAY, then recurse into each of its dependencies. If a dependency is already GRAY, that's a back edge onto the current path — a cycle. If a dependency is WHITE, recurse into it.
5. After all of a node's dependencies are explored with no cycle found, mark it BLACK — this node is permanently safe and will never need to be re-explored, even if reached again via a different path.
6. Handle edge cases: a stage that depends on itself (("a", "a")) is a degenerate one-node cycle caught by the same GRAY check; a stage with no dependencies at all is trivially safe.

The key insight is that the three-color scheme is what makes this O(V + E) instead of exponential: BLACK nodes are never re-explored no matter how many other nodes point to them, and only a GRAY node — one still open on the current recursion stack — can signal an actual cycle, whereas revisiting an already-finished (BLACK) node just means the graph has a shared dependency, not a cycle.

Reference solution

def pipeline_has_cycle(stages: list[str], dependencies: list[tuple[str, str]]) -> bool:
    # adjacency list: stage -> stages it directly depends on
    graph: dict[str, list[str]] = {s: [] for s in stages}
    for stage, depends_on in dependencies:
        graph[stage].append(depends_on)

    WHITE, GRAY, BLACK = 0, 1, 2  # unvisited, on current DFS path, fully explored
    color = {s: WHITE for s in stages}

    def dfs(node: str) -> bool:
        color[node] = GRAY
        for nxt in graph[node]:
            if color[nxt] == GRAY:
                return True  # back edge onto the current path -- cycle found
            if color[nxt] == WHITE and dfs(nxt):
                return True
        color[node] = BLACK
        return False

    # O(V + E) overall: each node is DFS'd from exactly once thanks to the color check
    for s in stages:
        if color[s] == WHITE and dfs(s):
            return True
    return False

Key Functions & Tricks

• graph: dict[str, list[str]] = {s: [] for s in stages} — pre-seeds every stage so isolated stages (no dependencies, no dependents) are still handled uniformly
• Three-color DFS — WHITE/GRAY/BLACK distinguishes "on the current path" from "already fully explored," which two-color visited/unvisited cannot
• if color[nxt] == GRAY: return True — the actual cycle detection: a back edge onto the active recursion stack
• color[node] = BLACK after full exploration — memoizes "this subtree is safe," so a shared dependency reached via two different stages is only explored once total
• Looping over every stage as a potential DFS root — needed because the dependency graph may be disconnected

How to Recognize This Pattern