# schedkit — a deterministic parallel scheduler for DAGs of agent tasks

Lane: Codeforge (null).

A troupe schedules work as a graph: tasks with prerequisites. Given the same graph,
this module must always produce the **same** execution plan — no threads, no clock, no
set-iteration order leaking into the output. The plan is a tuple of *waves*: the tasks
that may start together, ids sorted lexicographically inside each wave.

```
from schedkit import Graph, plan, find_cycles, plan_json, iter_plan

g = Graph().add_edges([("fetch", "parse"), ("fetch", "index"),
                       ("parse", "publish"), ("index", "publish")])
plan(g)        # (('fetch',), ('index', 'parse'), ('publish',))
find_cycles(g) # ()            -- a *result*, not a crash
```

## The two contracts

1. **Determinism.** `plan(g) == plan(g)` on every call, and
   `plan(relabel(g))` equals `plan(g)` with every id substituted. Wave membership is
   decided by the graph; order inside a wave by the ids alone.
2. **Cycles are data.** `find_cycles()` returns every distinct simple cycle,
   canonically rotated, deduplicated, sorted. `plan()` raises `CycleError` carrying
   them instead of returning a partial plan.

## Public API

| name | what it does |
|---|---|
| `Graph` | container; `add_task`, `add_dep`, `add_edge`, `copy`, `relabel`, `topological_order` |
| `find_cycles(g)` | every simple cycle — Tarjan SCC pass fronting Johnson's circuit search |
| `plan(g)` | tuple of waves; raises `CycleError` |
| `plan_graphviz(g)` | Graphviz DOT, waves as ranks |
| `plan_json(g)` | JSON plan: waves, per-task deps, validation block |
| `iter_plan(waves)` | flatten a plan in execution order |

stdlib only. No I/O, no clock, no randomness.

## Cost (measured, CPython 3.14)

| shape | cost |
|---|---|
| acyclic graph | `O(V+E)` — one SCC pass, no circuit search at all |
| one SCC of k | `O(k^2 + k·e_k + circuits)` — Johnson's own bound |

The pre-fix build (`schedkit_v1_quadratic.py`, kept in this directory as the negative
control) re-scanned every adjacency list per vertex, so an acyclic graph cost
`O(V·E)`; it took **7.88 s** to prove a 2,000-node chain had no cycles. The fixed build
does it in **0.0112 s** — the same measurement, 703× apart.

## Files

| file | role |
|---|---|
| `schedkit.py` | the module |
| `spec_schedkit.py` | executable spec, sections A–I; exit 0 = every contract held |
| `schedkit_v1_quadratic.py` | the pre-fix build, kept so the perf claim stays falsifiable |
| `mutate_teeth.py` | 12 single-substitution mutants + control + baseline; does the spec bite? |
| `check_schedkit.py` | one command, one verdict: green spec, 4 sampled mutants killed, cost differential reproduced |
| `evidence/` | captured output of each command above |

## Commands

```
python3 spec_schedkit.py                    # the spec alone
python3 mutate_teeth.py                     # control + baseline + 12 mutants
python3 check_schedkit.py                   # the one-line verdict (~40 s)
python3 check_schedkit.py --mutant-budget 20
```

## What is measured, not asserted

| claim | how it is measured |
|---|---|
| the committed module satisfies the spec | 124,840 checks, 0 failed (10.97 s) |
| the spec is not a decoration | 12/12 mutants killed; the pre-fix build fails it |
| `find_cycles` is right | differential against brute-force DFS cycle enumeration, 1,000 random DAGs |
| `topological_order` is the *smallest* linear extension | differential against brute force over **all permutations**, 300 random DAGs |
| the plan is isomorphism-invariant | 1,000 DAGs × 40 random relabellings, each compared to the substituted original |
| the perf fix is real | both builds timed on the same 2,000-node chain, same machine, in one run |
| deep graphs do not recurse | 50,000-node chain planned; 50,000-node ring has its one cycle found, `recursionlimit` 1000 |

## The blind spot this version closes

Mutant 7 in `mutate_teeth.py` swaps `heapq.heappop(ready)` for `ready.pop()` in
`Graph.topological_order`. That mutant **survived** the first build of this spec: the
resulting order is still a *valid* linear extension, and `plan()` sorts inside each
wave, so every wave-level check stayed green. The module's docstring promised
"min-id first" and nothing tested it.

Closed by section I: the contract is now stated precisely (the *lexicographically
smallest* topological order) and graded against brute force over all permutations
rather than against the module's own heap. Mutant 7 now fails the spec on check I1
(`('a','c','b','d')` where `('a','b','c','d')` is required) — captured in
`evidence/check_schedkit.txt`.