Resolve a ReWOO Plan into Execution Waves

1. Background Knowledge

This problem models static dependency resolution in a Directed Acyclic Graph (DAG). In AI agent planning, specifically the ReWOO (Reasoning Without Observation) framework, the planner generates a full execution plan before any tools are invoked. This requires the system to parse implicit dependencies—references like #E1—and determine a valid topological ordering of steps. The core concept is wave-based execution, where independent tasks are grouped into parallel "waves" to maximize concurrency.

The underlying data structure is a dependency graph where nodes are plan steps and directed edges represent data dependencies (e.g., E3 depends on E1). If the graph contains cycles or references to non-existent nodes, it violates the DAG property, making those nodes unexecutable. This is a classic application of Kahn’s Algorithm for topological sorting, which processes nodes with zero in-degree (no unresolved dependencies) iteratively.

Key technical terms include:

• In-degree: The number of dependencies a step has.
• Wave: A set of steps that can execute in parallel because all their dependencies were resolved in previous waves.
• Unresolved Reference: A dependency pointing to an ID not present in the plan.
• Cycle: A circular dependency chain (e.g., E1 needs E2, E2 needs E1).

2. Algorithm Approach

The optimal approach is a modified Breadth-First Search (BFS) using Kahn’s Algorithm. Standard topological sort produces a single linear order, but here we need to group nodes by their "level" or "wave."

1. Graph Construction: Parse each step's arguments to extract #E<n> references. Build an adjacency list or, more efficiently for this problem, an in-degree map and a reverse adjacency list (dependents).
2. Validation: Identify steps with references to IDs not in the plan. These are unresolved.
3. Wave Generation:

• Initialize a queue with all steps having an in-degree of 0 (no dependencies).
• Process the queue level-by-level. Each level corresponds to one wave.
• When a step is processed, decrement the in-degree of its dependents. If a dependent's in-degree hits 0, it becomes ready for the next wave.

4. Cycle Detection: After the BFS completes, any step that was never added to a wave is either part of a cycle or blocked by an unresolved reference. These form the blocked list.

3. Step-by-Step Strategy

1. Parse and Index:

• Create a set of all valid IDs from the plan for O(1) lookup.
• Use a regex or string search to find all #E\d+ patterns in each step's args.
• Build a dependencies map: step_id -> list of required_ids.

2. Identify Unresolved References:

• Iterate through all steps. For each dependency #E<n>, check if E<n> exists in the valid ID set.
• If not, add "<step_id>:#<missing_id>" to the unresolved list.
• Crucially, treat steps with unresolved references as having a "phantom" dependency that can never be satisfied. They will never reach in-degree 0.

3. Compute In-Degrees:

• Initialize in_degree for each step to 0.
• For every valid dependency A depends on B, increment in_degree[A].
• Note: Do not increment in-degree for unresolved references, as those steps are already doomed to be blocked.

4. Execute Wave BFS:

• Initialize queue with all steps where in_degree == 0.
• While queue is not empty:
• Create a new wave list.
• Process all nodes currently in the queue (this defines the parallel batch).
• For each node, find its dependents (steps that reference it) and decrement their in_degree.
• If a dependent's in_degree becomes 0, add it to the next_queue.
• Sort the current wave numerically by ID (e.g., E2 before E10) and append to waves.
• Set queue = next_queue.

5. Identify Blocked Steps:

• Any step ID not present in any wave is blocked.
• Collect these IDs, sort them numerically, and return.

4. Common Pitfalls

• Lexicographic vs. Numeric Sorting: The problem explicitly states IDs must be sorted numerically (E2 < E10). Using standard sorted() on strings will fail because '10' < '2' is true in lexicographical order. You must extract the integer part for sorting.
• Self-References: A step referencing itself (E1 depends on E1) creates a cycle of length 1. Ensure your in-degree logic handles this; the in-degree will never drop to 0, so it correctly ends up in blocked.
• Unresolved vs. Cycle: Both result in blocked steps, but unresolved requires specific reporting. Ensure you distinguish between "missing ID" (unresolved) and "present ID but circular dependency" (cycle).
• Argument Parsing: Ensure you correctly extract all #E<n> references. Missing a reference leads to incorrect in-degrees and wrong wave assignments.
• Empty Plan: Handle edge cases where the plan is empty or contains only blocked steps.

5. Time & Space Complexity

• Time Complexity: $O(N \cdot L)$, where $N$ is the number of steps and $L$ is the average length of the argument strings (for parsing). Building the graph takes $O(N \cdot L)$. The BFS visits each node and edge once, taking $O(N + E)$, where $E$ is the number of dependencies. Since $E$ is bounded by $N \cdot L$, the total time is dominated by parsing and graph traversal.
• Space Complexity: $O(N + E)$ to store the graph (adjacency list/in-degree map) and the output lists. The queue and wave lists also consume $O(N)$ space.

# Example of numeric sorting key
def sort_key(id_str):
 return int(id_str[1:]) # Extract number after 'E'