Incremental graph update (Pearce-Kelly)

[milanofthe]

Context

Current graph assembly: full rebuild on every topology change via _graph_dirty flag. Costs 0.4ms at 1000 blocks, 3.7ms at 5000, 10ms at 10000. Linear scaling, Vec-based (no HashMap).

Problem

For real-time applications with frequent topology changes (digital twins, online learning), a full rebuild per change is wasteful. Most changes are forward-edge additions that don't affect the existing evaluation order.

Proposed Solution

Pearce-Kelly algorithm for incremental topological sort. Rust crate: incremental_topo.

• On add_edge(u, v): if u is already before v in the order, no work needed (O(1)). Otherwise, reorder only the affected region between v and u.
• On remove_edge: order remains valid (possibly suboptimal). Optionally lazy re-optimize.
• On add_node: append to order. O(1).

Challenge

Our hot path (_dag()) iterates precomputed flat arrays (dag_flat_blocks, dag_flat_conns) with offsets per depth level. Incremental sort maintains a linear ordering but not depth-level flat arrays. Options:

1. Rebuild flat arrays from ordering — still O(n) but with a smaller constant than full DFS + Tarjan
2. Evaluate in ordering directly — eliminate flat arrays, iterate Pearce-Kelly order. Loses cache-friendly batched evaluation.
3. Hybrid — use flat arrays normally, only rebuild when _graph_dirty. Use Pearce-Kelly to decide IF rebuild is needed (classify changes as forward vs backward edge in O(1)).

Option 3 is the pragmatic choice: Pearce-Kelly as a fast classifier, full rebuild only when truly necessary.

Incremental SCC

For algebraic loop detection under edge insertion: Bernstein-Dudeja (ESA 2021) maintains SCC decomposition in O~(m^{4/3}) total time. Relevant for very large models.

References

• Pearce & Kelly, "A Dynamic Topological Sort Algorithm for DAGs" (JEA 2007)
• incremental_topo Rust crate: https://docs.rs/incremental-topo
• Bernstein & Dudeja, "Incremental SCC Maintenance" (ESA 2021)