DAG Planner

Build, validate, and explain task dependency graphs for parallel execution.

The Job

•Parse task dependencies into a DAG
•Detect cycles and report paths
•Compute topological order
•Explain blocking reasons
•Output ready queue and lock plan

Do NOT: author metadata, implement tasks, merge code, or review design.

DAG Validation

Cycle Detection

Use depth-first search with three states:

•unvisited - Not yet processed
•visiting - Currently in recursion stack
•visited - Fully processed

If we encounter a visiting node, we have a cycle.

Cycle output format:

code

Cycle detected: US-002 → US-003 → US-004 → US-002

Execution Planning

Ready Queue Rules

A task is ready when:

•All tasks in dependsOn are done
•None of its mutex are currently locked

Blocking Reasons

When a task cannot run, explain why:

code

Task US-003 blocked:
  - Waiting for: US-001, US-002 (not completed)
  - Mutex locked: db-migrations (held by US-005)

Output Formats

Topological Order

code

Execution order (topological):
  1. US-001 (no deps)
  2. US-002 (no deps)
  3. US-003 (after: US-001)
  4. US-004 (after: US-002, US-003)

Ready Queue Snapshot

code

Ready queue (3 tasks can run now):
  - US-001: mutex []
  - US-002: mutex []
  - US-005: mutex [lockfile]

Blocked (2 tasks waiting):
  - US-003: waiting for US-001
  - US-004: waiting for US-002, US-003

Mutex Lock Plan

code

Mutex usage plan:
  db-migrations: US-001, US-006 (sequential)
  lockfile: US-005 (exclusive)
  contract:auth-api: US-003, US-004 (sequential after US-001)

Deadlock Detection

Deadlock occurs when:

•No tasks are running
•No tasks are ready
•Pending tasks exist

Deadlock output:

code

DEADLOCK: No progress possible
  Pending tasks: US-003, US-004
  All blocked by unmet dependencies or locked mutex
  
  US-003 needs: US-001 (failed)
  US-004 needs: US-003 (blocked)

Example Analysis

Input tasks.yaml:

yaml

tasks:
  - id: A
    dependsOn: []
    mutex: [db-migrations]
  - id: B
    dependsOn: []
    mutex: []
  - id: C
    dependsOn: [A]
    mutex: [db-migrations]
  - id: D
    dependsOn: [B, C]
    mutex: []

Output:

code

DAG Analysis:
  Total tasks: 4
  Max parallelism: 2 (A and B can run together)
  Critical path: A → C → D (3 steps)
  
  Mutex contention:
    db-migrations: A, C must run sequentially
    
  Recommended execution waves:
    Wave 1: A, B (parallel)
    Wave 2: C (after A)
    Wave 3: D (after B, C)