NetworkX: catch dependency loops in an AI project plan

Find a plan that cannot start

An AI assistant may draft a plausible website project plan in which design waits for intake, launch waits for design, and intake somehow waits for launch. Each task sounds reasonable in isolation. Together, those dependencies form a loop that prevents a valid prerequisite-first order.

This AI-assisted editorial guide tests a small NetworkX adapter that catches that structural problem. It uses four fictional tasks and returns either an order for review or a cycle requiring attention. It does not call a model, create project records, assign employees, approve scope or launch any work.

1. Set up a bounded task-plan check

We verified NetworkX 3.7 with Python 3.13.15 on Windows on November 11, 2026. The pinned package requires Python 3.12 or later and excludes Python 3.14.1. It uses the BSD-3-Clause license. [1] The graph operations below need only the basic package, without the optional drawing or scientific dependencies. [2]

Our demonstration contract accepts 1–100 tasks. Each task has exactly id and depends_on. IDs are unique lowercase strings beginning with a letter, followed by lowercase letters, digits or hyphens, with a maximum length of 32 characters. Dependencies are lists of existing task IDs with no duplicates.

Run these PowerShell commands in a new folder. Save the Python block as plan_check.py before the last command. Package installation needs internet access; the example then runs locally without network calls.

mkdir networkx-plan-demo
cd networkx-plan-demo
python -m venv .venv
.\.venv\Scripts\python.exe -m pip install "networkx==3.7"
# Save plan_check.py below first.
.\.venv\Scripts\python.exe plan_check.py

2. Make prerequisite direction explicit

For each dependency, create an edge from prerequisite to dependent task. If design depends on intake, the edge is intake → design. Reversing that convention would produce a misleading order even if the graph had no cycles.

DiGraph automatically creates nodes for unknown edge endpoints and does not preserve duplicate copies of the same node or edge. [3] That is convenient for graph construction, but inappropriate for silently accepting a misspelled task reference. Our adapter rejects missing references and duplicates before adding edges. Adding every validated ID also retains tasks that have no dependencies.

The adapter fully consumes lexicographical_topological_sort into a list before returning success. That function respects dependencies and breaks available-node ties by sortable ID. A cycle prevents a complete topological order and raises NetworkXUnfeasible. [4] We catch that exception and return one directed cycle found by find_cycle. [5]

import copy
import json
import re
import networkx as nx

ID = re.compile(r"[a-z][a-z0-9-]{0,31}")


def check_plan(tasks):
    if not isinstance(tasks, list) or not 1 <= len(tasks) <= 100:
        raise ValueError("Provide 1 to 100 tasks")
    ids = set()
    for task in tasks:
        if not isinstance(task, dict) or set(task) != {"id", "depends_on"}:
            raise ValueError("Each task needs id and depends_on")
        name = task["id"]
        if not isinstance(name, str) or not ID.fullmatch(name) or name in ids:
            raise ValueError("Invalid or duplicate task ID")
        ids.add(name)
        deps = task["depends_on"]
        if not isinstance(deps, list) or len(deps) > 100:
            raise ValueError("Dependencies must be a bounded list")
        if any(not isinstance(dep, str) or not ID.fullmatch(dep) for dep in deps):
            raise ValueError("Invalid dependency ID")
        if len(set(deps)) != len(deps):
            raise ValueError("Duplicate dependency")
    for task in tasks:
        if not set(task["depends_on"]) <= ids:
            raise ValueError("Unknown dependency")

    graph = nx.DiGraph()
    graph.add_nodes_from(sorted(ids))
    graph.add_edges_from(sorted(
        (dep, task["id"]) for task in tasks for dep in task["depends_on"]
    ))
    try:
        order = list(nx.lexicographical_topological_sort(graph))
    except nx.NetworkXUnfeasible:
        return {"status": "needs_review", "reason": "dependency_cycle",
                "cycle_edges": list(nx.find_cycle(graph))}
    return {"status": "dependency_order_only", "order": order}


PLAN = [
    {"id": "intake", "depends_on": []},
    {"id": "design", "depends_on": ["intake"]},
    {"id": "content", "depends_on": ["intake"]},
    {"id": "launch", "depends_on": ["design", "content"]},
]

if __name__ == "__main__":
    broken = copy.deepcopy(PLAN)
    broken[0]["depends_on"] = ["launch"]
    print(json.dumps({"valid": check_plan(PLAN),
                      "loop": check_plan(broken)}, indent=2))

3. Read the actual output

The valid fixture returned status dependency_order_only and the order intake, content, design, launch. Content and design both require intake; launch requires both of them. The test checked every declared prerequisite’s position against its dependent task, rather than trusting a familiar-looking list.

The broken fixture adds launch as a prerequisite of intake. It returned needs_review with reason dependency_cycle and edges content → launch, launch → intake, intake → content. There was no order field. That is one discovered loop, not a list of every cycle or a recommendation to delete a particular dependency.

Twelve local tests passed: the branching plan’s prerequisite positions, a single task, disconnected task retention, a cycle with real closed-loop edges and no order, a self-loop, an unknown dependency, duplicate tasks, duplicate dependencies, invalid IDs and dependency shapes, exact field names, the batch limits, and all 24 input-task permutations.

Every permutation of the four-task fixture produced the same order. That establishes repeatability for the tested input and tie-breaking rule. It does not establish that content is more urgent than design or that either task has the right scope.

4. Repair the dependency, not just the error message

When a cycle appears, show the reviewer the original task descriptions and the reported edges. Ask whether an edge means a real prerequisite or merely a preference. Correct the plan at its source and run the full check again; removing one edge can leave another cycle elsewhere.

Keep direction intact when inspecting cycles. find_cycle with its default orientation respects directed edges. Its ignore option treats edges as undirected and can find a different kind of loop in a graph that still has a valid dependency order. [5] Our example deliberately uses the default.

Invalid fields or references raise ValueError in this adapter. An application can display those validation errors as a repair request. It should not silently create the missing task or substitute a partial order. Preserve the submitted plan and the corrected version so the reviewer can compare them.

5. Add scheduling and approval separately

A topological order is not a calendar. This graph contains no durations, due dates, staff availability, budgets or completion states. Content and design are shown sequentially in one list even though the declared dependencies do not require one to wait for the other. Any actual overlap needs a separate scheduling decision.

The check also cannot discover a prerequisite that the AI forgot to include. A technically acyclic plan can still omit security review, content approval or an essential integration task. Review the proposed dependencies against the original request and your delivery checklist.

Before connecting an AI worker to project software, store a plan version, validate the proposed tasks, run this structural check, obtain the required approval and recheck the approved version before creating records. Persist created-record IDs and handle retries deliberately. Those workflow controls are proposed integration steps, not features implemented by this local example.

Sources & further reading

1. NetworkX 3.7 on PyPI: Python requirements and license
2. NetworkX installation: basic and optional dependencies
3. NetworkX DiGraph: nodes, directed edges and self-loops
4. NetworkX lexicographical_topological_sort: ordering and exceptions
5. NetworkX find_cycle: directed traversal and cycle reporting

Turn AI plans into reviewable project work

Sociologix can help connect requirements, task validation, approvals and project-tool handoffs. Bring a sample workflow and the decisions your team needs to approve before an AI worker creates work.