03 — Graphs, Cycle Detection & DAG Task Scheduling

At a glance

After completing this lesson you can:

• Represent directed and undirected graphs via adjacency lists.
• Detect deadlocks, dependency cycles, and infinite loops using 3-color DFS.
• Compute topological execution orders for task workflows (Airflow/Celery/Temporal DAGs) using Kahn's algorithm (indegree BFS).

Time: ~50 minutes · Prerequisites: 02 — Binary Search & Predicates

Reading Companion

• Book: Grokking Algorithms (2nd Edition) — Aditya Y. Bhargava
• Chapter 6: Breadth-First Search (Shortest Path, Queue traversal).
• Chapter 7: Trees and Graphs (Graph modeling, directed vs undirected).

Why this matters in production

Workflow engines (Temporal, Celery Canvas, Airflow) schedule jobs based on Directed Acyclic Graphs (DAGs). If a developer creates a circular task dependency (Job A depends on Job B, which depends on Job A), a naive scheduler will hang forever or crash when stack overflow occurs. Running topological sorting and cycle detection upfront guarantees that tasks run in valid dependency order with guaranteed termination.

Deep dive

1. Adjacency List Representation

Graphs are represented in Python as dictionaries of sets/lists:

graph = {
    "extract": ["transform"],
    "transform": ["validate", "enrich"],
    "validate": ["load"],
    "enrich": ["load"],
    "load": []
}

2. Kahn's Algorithm (Topological Sort via In-degrees)

1. Calculate the in-degree (number of incoming edges/dependencies) for each node.
2. Initialize a queue with all nodes having in_degree == 0.
3. While queue is not empty: - Pop node $u$, add to topological order. - For each neighbor $v$ of $u$, decrement $v$'s in-degree. - If $v$'s in-degree becomes $0$, enqueue $v$.
4. If topological order length $

e$ total node count, a cycle exists!

Hands on

python3 phase1-cs-and-architecture/02-algorithmic-patterns/03-graphs-bfs-dfs-and-toposort/examples/01_demo.py
python3 phase1-cs-and-architecture/02-algorithmic-patterns/03-graphs-bfs-dfs-and-toposort/examples/02_trap.py

AI Trap & Code Review

# BAD AI-GENERATED CODE — RECURSIVE DFS WITHOUT CYCLE DETECTION
def run_dag(node, graph, visited):
    visited.append(node)
    for neighbor in graph.get(node, []):
        run_dag(neighbor, graph, visited)  # Infinite recursion on cycle!

Exercises

1. Rung 1 (compute_indegrees): Calculate the in-degree of every node in a directed graph dict[str, list[str]].
2. Rung 2 (detect_cycle_directed — Fix the AI Bug): Fix an infinite recursion bug in dependency resolution using 3-color DFS (WHITE, GRAY, BLACK) to detect cycles.
3. Rung 3 (topological_sort_kahn): Implement Kahn's algorithm returning a valid execution order or raising ValueError("Cycle detected in DAG").
4. Rung 4 (shortest_dependency_path): Use BFS to find the shortest dependency chain between two services in a service-to-service call graph.
5. Rung 5 (parallel_dag_scheduler): Given a DAG of tasks, compute the minimum number of parallel execution stages where independent tasks run concurrently.

Wrapping up

Can you explain?

1. Why does Kahn's algorithm detect circular dependencies automatically?
2. What do the 3 colors (WHITE, GRAY, BLACK) represent during cycle detection in DFS?
3. What is the difference between BFS and DFS in graph exploration?

Further Reading & References

• CPython Source: listobject.c (Dynamic Array Implementation)
• Raymond Hettinger: Modern Dictionaries by Key-Sharing
• Alex Xu: System Design Interview — Rate Limiter Design
• Tim Roughgarden: Algorithms Illuminated Series