The problem
A planner agent splits a job into subtasks, and some subtasks need the results of others. Before agents can work, the orchestrator must decide what runs when: a task can start only after all the tasks it depends on are done. This is a classic graph problem (a topological order), and you will solve it in two forms.
tasks is a dict {name: [dependencies]}, in the order the planner listed them.
Example.
{"design": [], "db": ["design"], "api": ["design", "db"], "ui": ["design"], "tests": ["api", "ui"]}:dbneedsdesign;apineedsdesignanddb;testsneedsapiandui.
One task at a time
execution_order(tasks) returns a list of all task names where every task comes after its dependencies. Among the tasks that are ready at the same time, take them in the planner's order.
Example. At every step, take the first task in the planner's order whose dependencies are all done.
- Nothing is done: only
designis ready.- After
design:dbanduiare ready;dbcomes first in the planner's list.- After
db:apianduiare ready;apicomes first.- Then
ui, thentests.The order is
design, db, api, ui, tests.
Levels, for parallel work
parallel_levels(tasks) groups tasks into levels that can run in parallel. Level 0 holds the tasks with no dependencies; level holds the tasks whose dependencies are all in earlier levels. Keep the planner's order inside each level.
Example. For the tasks above: level 0 is
["design"]; level 1 is["db", "ui"](both need onlydesign); level 2 is["api"]; level 3 is["tests"]. Four rounds of work instead of five, becausedbanduican run together.
What to implement
execution_order(tasks)andparallel_levels(tasks).
Both raise ValueError if a dependency is not a known task, or if the dependencies form a cycle: {"a": ["b"], "b": ["a"]} has no valid order, because each waits for the other.
Requirements
- Standard library only.
Hint
Kahn's algorithm: repeatedly take the tasks whose dependencies are all done. If at some point tasks remain but none is ready, there is a cycle.