Task-DAG Parallel Scheduler

Background

A planner outputs a DAG of sub-tasks with dependencies. The scheduler groups tasks into parallel execution levels — each level contains tasks whose dependencies have all completed, so they can run concurrently. The number of levels equals the critical-path length of the DAG.

Problem statement

Implement schedule_levels(graph) where graph[task] = [deps] (list of tasks this one depends on):

1. Compute the in-degree of each task.
2. Each iteration: all tasks with in-degree 0 form the current level (sorted alphabetically for determinism).
3. Remove them; decrement the in-degree of their successors.
4. Repeat until no tasks remain.

Raise ValueError on a cycle.

Input

• graph — dict[hashable, list[hashable]]. The list value is the task's dependencies (tasks that must complete before it can run).

Output

Returns list[list] — one inner list per parallel level.

Examples

Example 1 — linear chain → N levels of 1 task each

Input:  {"a": [], "b": ["a"], "c": ["b"]}
Output: [["a"], ["b"], ["c"]]

Example 2 — independent tasks → single level

Input:  {"a": [], "b": [], "c": []}
Output: [["a", "b", "c"]]   (sorted within the level)

Example 3 — diamond a → {b,c} → d → 3 levels

Input:  {"a": [], "b": ["a"], "c": ["a"], "d": ["b", "c"]}
Output: [["a"], ["b", "c"], ["d"]]

Example 4 — cycle → ValueError

Input:  {"a": ["b"], "b": ["a"]}
Output: ValueError

Constraints

• Tasks within a level are sorted (deterministic output).
• Tasks that appear only as dependencies (not as graph keys) are treated as having no deps.
• Cycle → ValueError, not infinite loop.

Notes

• Why levels, not topological order. A flat topological order forces serial execution. Levels expose the actual concurrency in the DAG.
• Lookahead scheduling. Production setups also account for per-task duration — Critical Path Method (CPM) — to minimise wall-clock instead of level count. Out of scope here.