Module incremental_scc 

Incremental strongly-connected-component maintenance under edge updates.

IncrementalScc tracks the SCC partition of a DynamicGraph while edges are inserted and deleted one (or a batch) at a time, recomputing only the part of the structure that an update can actually change. The key structural facts exploited are:

• Insertion u → v can only merge SCCs, never split one. A merge happens exactly when v could already reach u (the new edge then closes a directed cycle). The SCCs that coalesce are precisely those lying on some comp(v) ⇝ comp(u) path in the condensation DAG — i.e. the components reachable from comp(v) and co-reachable to comp(u). We find that set by a forward search from comp(v) and a backward search to comp(u) over the condensation and fuse the intersection into one component. When v cannot reach u, the partition is unchanged (the common case), and the update costs only the reachability probe — no global recomputation.

• Deletion u → v can only split an SCC, never merge. It can affect at most the single component C = comp(u), and only when comp(u) == comp(v). We then re-run Tarjan restricted to the induced subgraph on C and replace C with the resulting sub-components. A deletion of a cross-component edge changes nothing.

Both paths are exact: after any sequence of updates the maintained partition equals a from-scratch scc_tarjan recomputation on the current graph (verified in the test suite over randomised update streams). Component identifiers are dense in 0..num_components() and are renumbered after structural changes.

Structs

IncrementalScc

Incremental SCC tracker over a mutable directed graph.