28. Validate a Model-Serving Pipeline Has No Cycle

Problem

A voice-agent pipeline is configured as a set of named stages (audio ingestion, speech-to-text, turn detection, an LLM, text-to-speech, and so on) wired together by "must run before" dependency edges. Before a pipeline config can be deployed, the orchestrator needs to reject any configuration whose dependency graph contains a cycle, since a cyclic pipeline can never be scheduled to run stage-by-stage at all.

Given the list of stage names and a list of directed dependency edges, decide whether the graph they form is a valid DAG or contains a cycle.

Source: src/28_validate_pipeline_dag.py

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

>>> has_cycle(["asr", "nlu", "llm", "tts"], [("asr", "nlu"), ("nlu", "llm"), ("llm", "tts")])
False
>>> has_cycle(["a", "b", "c"], [("a", "b"), ("b", "c"), ("c", "a")])
True

Step-by-Step Approach

1. Build an adjacency list from the dependency edges: for each (a, b), stage a has an edge to stage b.
2. Give every stage one of three colors: WHITE (unvisited), GRAY (currently on the DFS path from the root of this traversal), or BLACK (fully explored, no cycle found through it).
3. Run DFS from every WHITE stage in turn (the graph may not be connected). On entering a node, mark it GRAY.
4. For each outgoing edge from the current node: if the neighbor is GRAY, that's a back-edge into the current path — a cycle. If the neighbor is WHITE, recurse into it.
5. Once every outgoing edge from a node has been explored with no cycle found, mark that node BLACK — it can never be part of a cycle discovered later, so future traversals can skip re-exploring it.
6. If any DFS call ever finds a GRAY neighbor, the graph has a cycle; if every stage reaches BLACK without one, the graph is a valid DAG.

The key insight is that GRAY specifically marks "on the current recursion stack," which is different from "already visited" — a plain visited/unvisited DFS can't distinguish a legitimate re-visit of an already-finished node (fine, it's a DAG) from a back-edge into an ancestor still being explored (a cycle), which is exactly the distinction three-color DFS captures.

Reference solution

WHITE, GRAY, BLACK = 0, 1, 2


def has_cycle(stages: list[str], dependencies: list[tuple[str, str]]) -> bool:
    graph: dict[str, list[str]] = {s: [] for s in stages}
    for a, b in dependencies:
        graph[a].append(b)

    # WHITE = unvisited, GRAY = on the current DFS path, BLACK = fully
    # explored with no cycle found through it. A back-edge to a GRAY node
    # is exactly what makes a directed graph cyclic.
    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 into the current path: cycle
            if color[nxt] == WHITE and dfs(nxt):
                return True
        color[node] = BLACK
        return False

    for s in stages:
        if color[s] == WHITE and dfs(s):
            return True
    return False

Key Functions & Tricks

• Three-color DFS (WHITE/GRAY/BLACK) — distinguishes "ancestor on the current path" (GRAY) from "already fully explored elsewhere" (BLACK), which a simple visited-set can't.
• Looping over every stage as a potential DFS root — needed because the dependency graph may be disconnected; a single DFS from one stage won't reach every stage.
• Marking a node BLACK on the way out — prunes future DFS calls from re-exploring subgraphs already proven cycle-free.
• Short-circuiting with early return True — stops the search the instant any back-edge is found, avoiding wasted work.
• Adjacency list built once up front — O(V + E) to construct, keeping the whole algorithm O(V + E) instead of O(V · E).

How to Recognize This Pattern