Run Kahn's topological sort on every AI-generated plan
AI architects emit multi-file plans that compile, run, and crash because the dependency graph has a cycle nobody looked at. Validate the plan with Kahn's algorithm before you spend tokens generating. Twenty lines of TypeScript catches a class of runtime bugs at near-zero compute cost.
AppX team ·
An AI architect emits a plan: "create LoginScreen.tsx, HomeScreen.tsx, theme.ts, AuthContext.tsx, and a useUser hook." The builder generates all five files. They compile. They land on disk. The app boots, hits the login screen, and crashes with Cannot read property 'user' of undefined.
The architect, on its second turn, can't find the bug from the stack trace. The user sees a broken app and types "fix it." You spend another 8k tokens and 30 seconds re-generating files that were never going to work, because the plan had a dependency cycle that nobody — model or human — looked at before generation started.
This post is about the 20-line algorithm that catches the entire class.
The bug we kept seeing
LLM architects are stochastic generators. They emit "AuthContext exposes a useUser hook" on one line and "useUser reads from AuthContext" three lines later. Both statements are individually plausible. Jointly, they describe a cycle: AuthContext → useUser → AuthContext. The architect has no global view of its own plan. It's emitting tokens left-to-right and the cycle is only visible if you draw the graph.
In React Native this fails in particularly miserable ways. ES module cycles don't throw at import time — they resolve to undefined for one of the participants, depending on evaluation order. You get a runtime crash that looks nothing like an import problem. The error message is about a property access; the cause is a graph the model never saw.
The fix is not "make the model smarter." The fix is to add a deterministic graph-validation step between the architect and the builder. Before you generate a single line of code, run Kahn's topological sort over the proposed dependency edges. If it succeeds, the plan is acyclic and safe. If it fails, you have the exact cycle path, and you can hand it back to the architect with a structured error.
What Kahn's actually does (90-second refresher)
flowchart LR
subgraph plan["The plan as a dependency graph"]
T["theme.ts"] --> B["Button.tsx"]
B --> H["Home.tsx"]
API["api.ts"] --> H
end
plan --> O["Kahn's order:<br/>theme.ts → api.ts → Button.tsx → Home.tsx"]
style O fill:#13241a,stroke:#2ecc71,color:#d7f7e3
Kahn's algorithm computes a topological order of a DAG by repeatedly peeling off nodes with no incoming edges. Concretely:
function topoSort(nodes: string[], edges: [string, string][]): string[] | { cycle: string[] } {
const inDeg = new Map(nodes.map(n => [n, 0]));
const adj = new Map(nodes.map(n => [n, [] as string[]]));
for (const [from, to] of edges) {
adj.get(from)!.push(to);
inDeg.set(to, inDeg.get(to)! + 1);
}
const queue = nodes.filter(n => inDeg.get(n) === 0);
const order: string[] = [];
while (queue.length) {
const n = queue.shift()!;
order.push(n);
for (const m of adj.get(n)!) {
inDeg.set(m, inDeg.get(m)! - 1);
if (inDeg.get(m) === 0) queue.push(m);
}
}
if (order.length < nodes.length) return { cycle: findCycle(nodes, edges) };
return order;
}
That's it. Maintain a queue of zero-in-degree nodes, peel them off, decrement neighbours, push neighbours that hit zero. If you finish with fewer nodes than you started with, every remaining node is part of a cycle — and findCycle (a DFS variant, another 15 lines) can walk the remaining subgraph to return the exact path.
Runtime: O(V + E). For a plan of 10–20 files with maybe 40 edges, this is microseconds. The check is essentially free.
The validation step
The architect prompt already emits a JSON plan. Add one field to each file: the list of files it imports from. This is information the architect must already have in order to write the file correctly — you're just asking it to surface the edge set explicitly, in the plan, before generation starts.
{
"files": [
{ "path": "src/screens/LoginScreen.tsx", "imports": ["src/auth/AuthContext.tsx", "src/theme.ts"] },
{ "path": "src/auth/AuthContext.tsx", "imports": ["src/hooks/useUser.ts"] },
{ "path": "src/hooks/useUser.ts", "imports": ["src/auth/AuthContext.tsx"] },
{ "path": "src/theme.ts", "imports": [] }
]
}
Now run Kahn's over (files, edges) where edges = files.flatMap(f => f.imports.map(i => [f.path, i])). The two files AuthContext.tsx and useUser.ts will never reach in-degree zero. The sort returns a cycle.
You return a structured error to the architect — same model, same conversation, same tool-call loop:
{
"error": "DEPENDENCY_CYCLE",
"cycle": ["src/auth/AuthContext.tsx", "src/hooks/useUser.ts", "src/auth/AuthContext.tsx"],
"message": "AuthContext.tsx imports useUser.ts, which imports AuthContext.tsx. Break the cycle by inlining the hook into AuthContext, or by extracting the shared type/context value into a third module that both can import."
}
The architect re-plans. Usually it merges the two files, sometimes it extracts a auth-types.ts neutral module both can depend on. Either way you do not generate a single token of code until the plan is a DAG.
What this catches that linting doesn't
ESLint, tsc, and madge all detect cycles — but only after the code exists. By the time madge is screaming, you've already spent the generation budget. The user has already seen a progress bar. The credit is already deducted.
Kahn's at the plan stage catches cycles before generation. The cost of a re-plan is one architect call — typically 1–2k tokens. The cost of generating a broken plan, watching it crash, refunding credits, and re-running the whole loop is 20–40k tokens plus a user-visible failure plus erosion of trust in the product.
There's a second benefit: a topological order is a generation order. Once the sort succeeds, you have a sequence — theme.ts first, then useUser.ts, then AuthContext.tsx, then LoginScreen.tsx — in which every file's dependencies already exist when it's written. This makes file-by-file streaming generation tractable and makes the "read your own dependencies for context" step in the builder loop cheap and bounded.
When cycles are legitimate
flowchart LR
A["A.tsx"] --> B["B.tsx"]
B --> C["C.tsx"]
C --> A
A -.-> X(("cycle ·<br/>Kahn's can't order it"))
style X fill:#3a1414,stroke:#c0392b,color:#f7d7d7
Rarely. The honest answer is: in well-designed TypeScript, almost never. The two cases worth knowing:
- Type-only imports.
import type { Foo } from './x'erases at runtime. Two modules can mutually import each other's types without a runtime cycle, because the import statements themselves disappear after compilation. If you want to allow these, require the architect to mark such edges as"typeOnly": trueand exclude them from the graph fed to Kahn's. - Function-level references in the same module group, where one function calls another that is hoisted. This isn't really an import cycle; it's a same-file question. The graph is per-file, so it's not a concern.
Everything else is a bug. Treat all non-type-only cycles as a hard fail. If the architect insists a value-level cycle is "fine," it isn't — it's emitting tokens that look fine.
A useful escalation: pair Kahn's with two cheaper checks before it. Validate that every import path in the plan corresponds to either an existing file or another file in the plan (catches typo'd paths). Validate that the plan's roots — files with no in-edges — match the entry points the architect declared (catches "I forgot to wire up the new screen to the router"). Kahn's is the load-bearing check; these two are the cheap wins you should run alongside it.
Takeaways
- Run Kahn's topological sort over the architect's proposed import graph before any code is generated. It's 20 lines and microseconds of compute, and it catches a runtime bug class that linting can only find after the fact.
- Require the architect to emit, in its plan, the import edge list for every new file. This is one structured field — no new tool, no new round-trip.
- On cycle detection, return the exact cycle path to the architect and let it re-plan. The architect almost always fixes it on the next turn; you pay one extra plan call instead of one wasted generation.
- The topological order Kahn's produces is also your generation order. Stream files in topo order and dependencies always exist before dependents.
- Allow type-only cycles only if the architect explicitly marks edges as type-only. Default to treating every detected cycle as a bug.
- This is the cheapest pre-generation validation step in your pipeline. If you're not running it, you're paying for it in user-visible failures instead.