Check AI Task Dependencies Before Scheduling With Python

An AI assistant turns your meeting notes into a five-task publishing plan. The steps sound sensible, but “review” waits for “publish,” while “publish” waits for “review.” Nothing can start that pair. A different response names a prerequisite that does not exist.

Check the dependency structure before connecting the plan to any scheduler. This tutorial builds a read-only Python preview that rejects both mistakes and returns a complete ordering for a valid plan. It complements the planning concepts in agentic AI design patterns; no model call, account, or external package is required.

1. Define what the plan means

Use a mapping from each task ID to its prerequisites. For example, {"review": ["draft"]} means drafting must finish before review, not the reverse. An empty list marks a task with no prerequisites.

Set a small, explicit contract:

• Accept 1–100 tasks, each with a lowercase ASCII ID of at most 40 characters, starting with a letter; digits and underscores may follow.
• Require a list of distinct prerequisite IDs for every task.
• Reject undeclared prerequisites and circular dependencies, including a task depending on itself.

The function below accepts an already decoded mapping, not raw model text. If receiving JSON, enforce an input-size limit before decoding and reject duplicate object keys separately. Python’s JSON documentation warns that untrusted input can consume excessive resources. The 100-task limit here is a tutorial policy, not a scheduler capacity claim.

2. Build a preview-only validator

Python’s graphlib documentation describes prerequisite mappings and cycle detection. It also notes that undeclared prerequisites are automatically added as nodes. Reject those ourselves so an invented task cannot quietly enter the plan.

Materialize static_order() into a tuple before returning anything. Never execute tasks while consuming that iterator: validation must finish first. Save this as check_plan.py, using Python 3.11 or newer:

import re
from graphlib import CycleError, TopologicalSorter

TASK_ID = re.compile(r"[a-z][a-z0-9_]{0,39}")


def checked_order(plan):
    if not isinstance(plan, dict) or not 1 <= len(plan) <= 100:
        raise ValueError("expected 1 to 100 tasks")
    if any(not isinstance(t, str) or not TASK_ID.fullmatch(t) for t in plan):
        raise ValueError("invalid task ID")
    for dependencies in plan.values():
        if not isinstance(dependencies, list) or any(
            not isinstance(d, str) for d in dependencies
        ):
            raise ValueError("dependencies must be lists of task IDs")
        if len(dependencies) != len(set(dependencies)):
            raise ValueError("repeated dependency")
    unknown = sorted({d for deps in plan.values() for d in deps} - set(plan))
    if unknown:
        raise ValueError("unknown dependencies: " + ", ".join(unknown))
    try:
        return tuple(TopologicalSorter(plan).static_order())
    except CycleError as error:
        raise ValueError("cycle detected") from error


def main():
    plan = {
        "collect": [],
        "draft": ["collect"],
        "artwork": ["collect"],
        "review": ["draft", "artwork"],
        "publish": ["review"],
    }
    order = checked_order(plan)
    positions = {task: i for i, task in enumerate(order)}
    assert set(order) == set(plan) and len(order) == len(plan)
    assert all(positions[d] < positions[t] for t in plan for d in plan[t])
    print("valid: 5 tasks, all prerequisites precede dependents")
    cases = [
        ("unknown", {"draft": ["missing"]}, "unknown dependencies: missing"),
        ("cycle", {"draft": ["review"], "review": ["draft"]}, "cycle detected"),
        ("self_cycle", {"review": ["review"]}, "cycle detected"),
        ("bad_shape", {"draft": "collect"}, "dependencies must be lists of task IDs"),
        ("repeated", {"a": [], "b": ["a", "a"]}, "repeated dependency"),
        ("empty", {}, "expected 1 to 100 tasks"),
    ]
    for label, candidate, expected in cases:
        try:
            checked_order(candidate)
        except ValueError as error:
            assert str(error) == expected
            print(f"{label}: rejected ({error})")
        else:
            raise AssertionError(f"{label} was accepted")


if __name__ == "__main__":
    main()

The function returns IDs only. Names such as publish are inert fixture labels, not commands, approvals, or permission to publish anything. Keep executable handlers in application-owned code, outside the model’s response.

3. Validate the positive and negative cases

Run without Python’s -O option so the fixture assertions stay enabled:

python3 check_plan.py

Expected stdout:

valid: 5 tasks, all prerequisites precede dependents
unknown: rejected (unknown dependencies: missing)
cycle: rejected (cycle detected)
self_cycle: rejected (cycle detected)
bad_shape: rejected (dependencies must be lists of task IDs)
repeated: rejected (repeated dependency)
empty: rejected (expected 1 to 100 tasks)

This command was tested locally with Python 3.11.4: exit status 0, empty stderr. The fixture accepts one five-task plan and rejects six invalid plans. Rejections are expected test outcomes, so the overall command succeeds; an unexpectedly accepted case raises an assertion instead.

The positive case checks that every task appears once and every prerequisite precedes its dependent. It does not insist on one exact order for independent tasks. Keep these cases when changing prompts, following the same fixed-fixture approach as AI prompt regression testing.

4. Troubleshoot before adding execution

• Unknown dependency: check for a typo or an omitted task. Ask for a corrected proposal; do not silently create a blank task to satisfy the reference.
• Cycle detected: inspect the prerequisite lists with the task owner. Remove an edge only when the underlying requirement changes, not merely to make validation pass.
• Bad shape or repeated dependency: request the same mapping contract again. Avoid guessing whether a string means one ID, several IDs, or explanatory prose.
• Valid graph, wrong workflow: structural checks cannot detect a missing approval step or an invented but declared task. Compare IDs and mandatory prerequisites against an application-owned registry and policy. The AI JSON field allowlist tutorial shows the related principle of restricting proposed changes before writing.
• Tasks fail at runtime: an ordering is not a completion record. A real executor must wait for successful prerequisites, handle failures and retries, and check permissions before side effects. This preview implements none of those behaviors.

Practical takeaway

Treat an AI-generated plan as a proposal. Require known references, reject cycles, and validate the entire graph before presenting an order for approval. A plan that can be ordered is ready for workflow review, not automatic execution.