go-incremental-scc-invalidation-frontier

Answer

I built and verified the solution. The complete, self-contained markdown is at ~/SOLUTION.md, and the working implementation/tests are in ~/incscc/ (graph.go, graph_test.go, go.mod). I verified that the code embedded in the markdown byte-for-byte matches the tested files.

What was wrong (root causes the solution addresses)

A naive invalidator fails in five concrete ways:

1. Full Tarjan per edit — not incremental. Fix: insertions only merge {x : cv→*x} ∩ {x : x→*cu}; deletions run Tarjan only on the induced old component.
2. Condensation edges treated as booleans — components can share parallel node edges, so a first deletion wrongly severs a live dependency. Fix: keep Out/In as sets and drop only when hasCompEdge is false.
3. Stale topological order — a plain cross-component edge mutates the DAG without merging. Fix: topoDirty + lazy ensureTopo.
4. Over-invalidation — invalidating "all dependents" rebuilds on no-op edits. Fix: recursive content-addressed compHash over the acyclic condensation, stopping propagation where the hash is unchanged.
5. Nondeterministic order — Go map iteration. Fix: Kahn with a min-heap keyed by component ID (= min node ID) and sorted members.

Verification (all green, in ~/incscc)

gofmt -l .            # clean
go vet ./...          # clean
go test -race ./...   # ok  incscc  5.2s

--- PASS: TestCycleMergeAndSplit
--- PASS: TestNoOpContentProducesNoFrontier
--- PASS: TestMergeSplitsAcrossManyComponents
--- PASS: TestDeterminismAcrossReplays
--- PASS: TestRandomizedAgainstBruteForce   (40 seeds × 80 ops)
--- PASS: TestSparseDeletionIsLocal
--- PASS: TestSparseInsertionMergeIsLocal
--- PASS: ExampleGraph

The randomized differential test is the proof: after every edit it checks the SCC partition against from-scratch Tarjan, validates the topological build order, and asserts the emitted frontier equals the set of nodes whose semantic hash changed under an independent full recomputation. Locality is measured: a 500-node SCC inside a 5000-node graph touches exactly 500 nodes on deletion, and the benchmark stays ~180 µs per edit on a 400-node SCC inside a 40,000-node graph.

The markdown contains the full root-cause analysis, architecture/correctness argument, the complete graph.go/graph_test.go, and all reproduction commands.