Workflow DAG Ordering

The problem, from first principles

An agent that decomposes a goal produces tasks with dependencies: you cannot summarize search results before searching, and you cannot send the email before drafting it. Those dependencies form a directed acyclic graph (DAG), and an executor needs an order in which every task runs after everything it depends on, a topological order. The standard method, Kahn's algorithm, repeatedly takes a task whose dependencies are all done. Two things can go wrong in a plan written by a language model, and both must be detected: a task may depend on a name that does not exist, and the dependencies may form a cycle, in which case no valid order exists.

From theory to code

Implement execution_order.

Constraints

• tasks is a dict mapping each task name to the list of task names it depends on. Return a list of all task names in an order where every task appears after all of its dependencies.
• When several tasks are ready at once, run the one that comes first alphabetically, so the result is deterministic.
• Raise ValueError if a dependency names a task that is not a key of tasks, or if the dependencies contain a cycle.
• Do not modify tasks.

Hints