vbpf / prevail / 29851285864

87%

push

github

Reset per-SCC vertex marks in select_potentials (fixes #1201) (#1210)

`select_potentials` runs Bellman-Ford per SCC to assign valid potentials during
meet, using `vert_marks` to track which vertices belong to the SCC currently
being processed (BF_SCC) so only intra-SCC relaxations requeue a vertex. But the
marks were cleared only once, up front, and never reset between SCCs.

Tarjan emits SCCs sinks-first, so a source SCC is processed last. 
Iterate the SCCs in topological order (sources first) by walking Tarjan's
reverse-topological output backwards. Every cross-SCC edge then points to a
later, not-yet-processed SCC, so its relaxation tightens that SCC's seed before
it runs and global validity is preserved. This also makes the requeue-a-finished-
vertex path unreachable, so the per-SCC mark reset is now defense-in-depth.

The regression test now also asserts the stored potentials are a valid model
(p(d) <= p(s) + w for every edge); this failed under the mark-reset-only fix
(0 <= -10 on the x==y edge) and passes with topological processing.

---------

Signed-off-by: Elazar Gershuni <elazarg@gmail.com>
Co-authored-by: Claude Opus 4.8 (1M context) <noreply@anthropic.com>

3 of 3 new or added lines in 1 file covered. (100.0%)

9328 of 10751 relevant lines covered (86.76%)

6317880.28 hits per line