dmeoli / ADS / 40762529711

98%

Build Type

push

github

Committed by dmeoli

Commit Message

SpanningForestObserver: a batch with many cuts joined again at once

At 10^5 nodes, batches of m / 100 changes cost about 10% more than
Kruskal from scratch: each raise or deletion of an edge of the forest
sought its replacement alone. Such a batch now cuts those edges, sets
aside the edges lowered or inserted off the forest, and joins the trees
again by Kruskal on the trees contracted, on the edges between two
trees found at the nodes out of the largest one, by blocks of the
lightest ones (filter-Kruskal of Osipov, Sanders and Singler); the edges
set aside are then taken one at a time by their cycles. The observer
takes this way when the cuts times the mean work of its replacements so
far exceed n plus the edges off the forest. The theory, with why the
forest so joined is minimum, in theory_graph_dynamic; the test of
batches of 60 changes on 300 nodes against Kruskal.

Coverage Stats

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

13 existing lines in 3 files now uncovered.

47711 of 48864 relevant lines covered (97.64%)

10667067.17 hits per line