Resolve a Plan DAG into Parallel Waves

mediumPROAgent Loop Control & PlanningAI AgentsAI Agents 1

Problem Statement

Given a plan where each step declares which prior steps it depends on, group the steps into execution waves: each wave contains every step whose dependencies are all satisfied by earlier waves. This maximizes parallelism.

Background

This is a layered topological sort. Wave 0 is all steps with no dependencies. Wave w is all not-yet-scheduled steps whose deps are entirely within waves 0..w-1. Within a wave, step ids are sorted ascending. If a cycle prevents scheduling all steps, return "CYCLE".

Your Task

def plan_waves(steps):

steps: list of {"id": int, "deps": [int, ...]}.
Return a list of waves, each a sorted list of ids; or "CYCLE".

Input Format

steps (list of dicts).

Output Format

A list of lists of ints, or "CYCLE".

Sample

print(plan_waves([{"id":1,"deps":[]},{"id":2,"deps":[1]},{"id":3,"deps":[1]}]))

Output:

[[1], [2, 3]]

Example

Input

print(plan_waves([{"id":1,"deps":[]},{"id":2,"deps":[1]},{"id":3,"deps":[1]}]))

Output

[[1], [2, 3]]

Reasoning

Initialize the dependency map from the input: Step 1 has no dependencies ( $\emptyset$ ), while Steps 2 and 3 both depend on Step 1 ( $\{1\}$ ). The set of remaining unscheduled steps is $\{1, 2, 3\}$ and the set of scheduled steps is initially empty.
Identify the first wave by finding all remaining steps whose dependencies are fully contained in the scheduled set. Only Step 1 qualifies because its dependency set $\emptyset$ is a subset of the empty scheduled set, resulting in Wave 0: $[1]$ .
Update the state by adding Step 1 to the scheduled set $\{1\}$ and removing it from the remaining set, leaving $\{2, 3\}$ for subsequent processing.
Identify the second wave from the remaining steps. Both Step 2 and Step 3 have dependencies $\{1\}$ , which is now a subset of the scheduled set $\{1\}$ , so both are ready. Sorting their IDs yields Wave 1: $[2, 3]$ .
Update the state by adding Steps 2 and 3 to the scheduled set and removing them from the remaining set, which becomes empty, signaling the end of the process.
The final output is [[1], [2, 3]]

Constraints

Wave 0: steps with no deps. Wave w: deps all scheduled in earlier waves.
Sort ids ascending within each wave.
Return "CYCLE" if not all steps can be scheduled.

Learn this in

The Agent Loop & ReAct FoundationsAgent Engineering Study Plan Planning Patterns: Plan-and-Execute, ReWOO, HTNAgent Engineering Study Plan Tool Use & Function CallingAgent Engineering Study Plan Workflow Patterns & LangGraph Stateful GraphsAgent Engineering Study Plan

More from AI Agents 1

Cheapest Cache TTL Meeting a Freshness SLAhard Bootstrap Confidence Interval Width for Eval Accuracymedium Route to the Cheapest Model Meeting Qualitymedium pass@k Estimatormedium Savings from a Semantic Cachemedium

Concept primerPREVIEW

1. Background Knowledge

This problem is a variation of topological sorting, a fundamental graph algorithm used to order vertices such that for every directed edge $u \to v$ , vertex $u$ comes before vertex $v$ in the ordering. In the context of AI agent planning, the graph represents a Directed Acyclic Graph (DAG) where nodes are tasks and edges represent dependencies. If a cycle exists, the plan is invalid because a task would depend on itself (directly or indirectly), making execution impossible.

Standard topological sort produces a single linear sequence. However, in parallel execution environments (like multi-threaded agents or distributed systems), we care about levels or waves. A "wave" represents the maximum set of tasks that can be executed simultaneously. This is often called level-based topological sort or BFS-based topological sort. The key insight is that all nodes at the same "distance" from the source (in terms of dependency depth) can be processed in parallel.

The problem also introduces a specific constraint: within each wave, step IDs must be sorted in ascending order. This means we are not just finding any valid parallel grouping, but a specific deterministic one. This is crucial for reproducibility in agent loops where the execution plan must be consistent across runs.

2. Algorithm Approach

The most efficient approach is Breadth-First Search (BFS) using a queue, which naturally processes nodes level by level. This is more direct than DFS for this specific "wave" requirement.

Build the Graph: Create an adjacency list and an in-degree array. The in-degree of a node is the number of its dependencies.
Initialize: Identify all nodes with in-degree 0. These form the first wave (Wave 0).
Iterate by Wave:

Process all nodes in the current wave.
For each node, decrement the in-degree of its neighbors (dependents).
If a neighbor's in-degree becomes 0, add it to the next wave's candidate list.
Once the current wave is fully processed, sort the next wave's candidates by ID and move to the next iteration.

Cycle Detection: If the total number of processed nodes is less than the total number of steps, a cycle exists.

3. Step-by-Step Strategy

PRO

Continue the full explanation

You're reading the free preview. Unlock the complete walkthrough, the code editor, test runner and reference solution with Premium.