Back
+30 XP
Concept

Topological Sort for Task Dependency Graph

Workflow orchestrators (like Airflow and Docker Compose) execute multi-stage pipelines where tasks require prerequisites. Topological sorting linearizes a Directed Acyclic Graph (DAG) into a valid linear execution sequence in $O(V + E)$ time, guaranteeing that prerequisites execute before dependents ⛓️📦⚡.

python
from collections import deque

def topo_sort(nodes, edges):
    in_deg = {n: 0 for n in nodes}
    adj = {n: [] for n in nodes}
    for u, v in edges: adj[u].append(v); in_deg[v] += 1
    q = deque([n for n in nodes if in_deg[n] == 0])
    order = []
    while q:
        n = q.popleft(); order.append(n)
        for m in adj[n]:
            in_deg[m] -= 1
            if in_deg[m] == 0: q.append(m)
    return order

print(topo_sort(["lint", "test", "build"], [("lint", "build"), ("build", "test")]))

# 27. Topological Sort for Task Dependency Graph Whenever you run `npm install`, `pnpm build`, or execute database schema migration scripts, the software must determine an exact linear schedule where parent dependencies finish before child tasks attempt execution 🛑. ```python # The Pipeline Dependency Graph: # [lint] --------> [build] --------> [test] --------> [deploy] # (in_deg=0) (in_deg=1) (in_deg=1) (in_deg=1) # # Valid Execution Schedule: # Step 1: Run 'lint' -> Frees 'build' # Step 2: Run 'build' -> Frees 'test' # Step 3: Run 'test' -> Frees 'deploy' # Step 4: Run 'deploy' -> COMPLETE! ``` ### Deterministic Scheduling - **Zero Prerequisite Queue**: Tasks with an in-degree of 0 are ready to execute immediately (and can be scheduled in parallel). - **Cascade Trigger**: As each task finishes, decrement the in-degree of its dependents. The moment a dependent hits 0, enqueue it. - **Fail-Fast Cycle Armor**: If a cycle exists, the remaining tasks are locked in mutual deadlock; detect this immediately and abort with a descriptive `ValueError` ⛓️📦⚡! --- ### Interactive Pop-Quiz 🧠 #### What does it indicate if a topological sort algorithm completes but the returned execution list contains fewer tasks than the input graph? - [ ] A circular dependency (cycle) exists in the task graph, causing deadlocked tasks to never become ready for execution 🛑 - [ ] Some tasks completed asynchronously in parallel - [ ] The queue exhausted operating system thread handles - [ ] Python optimized out redundant leaf nodes --- ### Practical Challenge 🎯 Implement `topological_sort(tasks: list[str], dependencies: list[tuple[str, str]]) -> list[str]`. Pair `(prereq, task)` means `prereq` must finish before `task` begins. Use an in-degree queue; if output length does not equal `len(tasks)`, raise `ValueError('Cycle detected')`. Test with tasks `['build', 'test', 'deploy', 'lint']` and deps `[('lint', 'build'), ('build', 'test'), ('test', 'deploy')]`. Assert correct linear order and assert cycle detection. Print result. <details> <summary>Solution</summary> ```python from collections import deque def topological_sort(tasks: list[str], dependencies: list[tuple[str, str]]) -> list[str]: in_degree = {t: 0 for t in tasks} adj = {t: [] for t in tasks} for prereq, task in dependencies: adj[prereq].append(task) in_degree[task] += 1 ready = deque(sorted([t for t in tasks if in_degree[t] == 0])) order = [] while ready: curr = ready.popleft() order.append(curr) for dependent in adj[curr]: in_degree[dependent] -= 1 if in_degree[dependent] == 0: ready.append(dependent) if len(order) != len(tasks): raise ValueError("Cycle detected") return order pipeline_tasks = ["build", "test", "deploy", "lint"] deps = [("lint", "build"), ("build", "test"), ("test", "deploy")] result = topological_sort(pipeline_tasks, deps) assert result == ["lint", "build", "test", "deploy"] try: topological_sort(["a", "b"], [("a", "b"), ("b", "a")]) assert False, "Failed to raise cycle exception" except ValueError: pass print(f"Topological sort verified: {result}") ``` </details>

Checkpoint

What does it indicate if a topological sort algorithm completes but the returned execution list contains fewer tasks than the input graph? 🧠

Practice

Implement `topological_sort(tasks: list[str], dependencies: list[tuple[str, str]]) -> list[str]`. Pair `(prereq, task)` means `prereq` must finish before `task` begins. Use an in-degree queue; if output length does not equal `len(tasks)`, raise `ValueError('Cycle detected')`. Test with tasks `['build', 'test', 'deploy', 'lint']` and deps `[('lint', 'build'), ('build', 'test'), ('test', 'deploy')]`. Assert correct linear order and assert cycle detection. Print result. 🎯

Terminal
01
Tap code blocks below to assemble
Available Blocks