20. Validate Pipeline Has No Cycle

Problem

Fin runs pipeline stages with hard sequential dependencies — for example, retrieval must complete before generation. Before actually running a pipeline, you need to validate that its dependency graph is runnable at all: given the number of stages and a list of prerequisite pairs, determine whether every stage can be completed, i.e. whether the dependency graph is a DAG (has no cycle).

Stages are numbered 0..num_stages-1. Each prerequisite entry is (stage, prereq), meaning stage depends on prereq completing first.

Source: src/20_validate_pipeline_no_cycle.py

def can_complete_all(num_stages: int, prerequisites: list[tuple[int, int]]) -> bool: ...

>>> can_complete_all(4, [(1, 0), (2, 1), (3, 2)])
True
>>> can_complete_all(2, [(0, 1), (1, 0)])
False
>>> can_complete_all(3, [])
True

Step-by-Step Approach

1. Build an adjacency list: for each (stage, prereq) pair, add an edge prereq -> stage (prereq must run first, so it points toward what depends on it).
2. Compute the in-degree of every node: how many unmet prerequisites each stage currently has.
3. Initialize a queue with every stage that has in-degree 0 — these are the stages with no prerequisites, so they can run immediately.
4. Run Kahn's algorithm: repeatedly pop a stage from the queue, count it as processed, then decrement the in-degree of every stage it points to. Any neighbor whose in-degree drops to 0 gets pushed onto the queue.
5. Keep a running count of how many stages were processed this way.
6. At the end, compare the processed count to num_stages. If they match, every stage was eventually reachable with in-degree 0 at some point — no cycle. If the count is smaller, some stages were stuck in a cycle (their in-degree never reached 0) and were never processed.

The key insight is that Kahn's algorithm processes nodes in the same order a valid topological sort would, and a cycle is exactly the condition where that process gets stuck: nodes inside a cycle always have at least one unmet prerequisite from another node in the same cycle, so their in-degree never reaches 0 and they're never dequeued.

Reference solution

from collections import deque


def can_complete_all(num_stages: int, prerequisites: list[tuple[int, int]]) -> bool:
    # Kahn's algorithm: topologically process indegree-0 nodes; if we can't
    # process every node, a cycle remains. O(V + E).
    # adjacency list, one entry per stage
    graph: dict[int, list[int]] = {stage: [] for stage in range(num_stages)}
    indegree = [0] * num_stages
    for stage, prereq in prerequisites:
        # edge prereq -> stage
        graph[prereq].append(stage)
        indegree[stage] += 1

    # seed BFS frontier with indegree-0 stages
    queue = deque(stage for stage in range(num_stages) if indegree[stage] == 0)
    processed = 0
    while queue:
        # FIFO pop for breadth-first order
        node = queue.popleft()
        processed += 1
        for nxt in graph[node]:
            indegree[nxt] -= 1
            if indegree[nxt] == 0:
                # newly unblocked stage is ready to process
                queue.append(nxt)

    # fewer than num_stages processed means a cycle remains
    return processed == num_stages

Key Functions & Tricks

• from collections import deque — O(1) append/pop from both ends, unlike O(n) list.pop(0)
• {stage: [] for stage in range(num_stages)} — dict comprehension building the adjacency-list graph
• graph[prereq].append(stage) — adds directed edge prereq -> stage
• deque(stage for stage in range(num_stages) if indegree[stage] == 0) — seeds the initial BFS frontier in one line
• queue.popleft() — O(1) FIFO pop, giving breadth-first processing order
• queue.append(nxt) — O(1) enqueue once a stage's prerequisites are all satisfied
• Kahn's algorithm as cycle detection — nodes stuck in a cycle never reach indegree 0, so processed < num_stages means a cycle exists

How to Recognize This Pattern