Capstone Thread: A Dependency Planner with Evidence

Build a dependency-analysis CLI or library using the module primitives. Budget 8–12 hours after the labs. The core operates on a finite in-memory snapshot; distributed execution, retries, persistence and graph mutation are extensions.

Input and outputs

Tasks have unique integer IDs and nonnegative integer durations. An edge u→v means u must finish before v starts. Decide whether duplicate prerequisites are preserved as records or deduplicated consistently. Keep isolated tasks.

Return an SCC partition and identify cyclic regions: components with more than one vertex, or singleton components with a self-loop. Separately mark downstream vertices blocked by those regions. Return no complete schedule if any cycle exists; give a cycle witness from an affected SCC and explain the refusal.

For a DAG, return a valid topological order, earliest start/finish values and a critical-path witness under unlimited workers, fixed durations and no added resource constraints. A source task starts at zero; each task starts at the maximum finish of its predecessors, then finishes after its own duration. Empty input has an empty order and makespan zero. A witness follows one predecessor achieving each maximum; ties may choose any valid predecessor.

Starter fixture and expected evidence

Durations [3,2,4,1], edges 0→2,1→2,2→3: starts [0,0,3,7], finishes [3,2,7,8], critical path 0→2→3, makespan 8. One worker would need total duration 10, so do not present 8 as a guarantee under arbitrary worker limits. Adding 2→0 makes {0,2} a cyclic region and blocks task 3 downstream.

Independent validation

Check every declared task occurs once in the SCC partition and, for DAG input, the order. Verify every edge's precedence constraint, every start/finish recurrence, and the critical path's duration. For tiny DAGs, enumerate source-to-sink paths as a separate makespan oracle. Test isolated tasks, zero durations, multiple roots, tied critical paths, parallel prerequisite records, a self-loop, several cycles and tasks downstream of cycles. Validate cycle edge identities.

Include source, contract, commands, fixtures, tests, proof sketches, O(V+E) traversal/DP analysis under unit-cost arithmetic, and memory accounting. If you sort output for deterministic presentation, price that separately. Do not label every Kahn-blocked vertex as cyclic or treat SCC condensation as execution of the tasks inside cycles.

Change request

Choose one: a fixed worker limit; graph updates arriving during analysis; or tasks requiring both memory and a worker. Explain which correctness or optimality claim no longer follows. For a heuristic scheduler, promise feasibility and measure its quality against a valid lower bound; do not claim general optimality from a topological order. For graph updates, state snapshot/version semantics before reusing an old certificate. Retain a counterexample to the unchanged design.