dmeoli / ADS / 40624056709

96%

Build Type

push

github

Committed by dmeoli

Commit Message

Assignment, the assignment problem kept optimal as its costs change

graph/Assignment.h: the assignment of n rows to n columns by the
shortest augmenting paths of Jonker and Volgenant in the form of
Crouse, O( n^3 ), the forbidden pairs of cost infinity(). The costs
change by setCost(), setRow() and setColumn() and are worked at the next
query: a row or a column changed frees one pair, restores the dual by
one potential and augments once, O( n^2 ) (the incremental assignment
of Toroslu and Uecoluk, the dynamic Hungarian algorithm of Mills-Tettey,
Stentz and Dias), a single cost raised off the assignment or lowered
within the duals costs O( 1 ), and more than n / 2 changes go from
scratch; AssignmentObserver of Reoptimization.h on a bipartite graph.
The theory, with the lemma of the change of a row, in
theory_graph_assign.

The tests assignment (the boundaries, the outcomes, random costs with
forbidden pairs against the permutations, real costs, one augmentation
per row changed) and reopt-assignment; bench/assignment.cpp against
NetworkSimplex of LEMON and maximum_weighted_matching of Boost.

Coverage Stats

230 of 239 new or added lines in 4 files covered. (96.23%)

15 existing lines in 7 files now uncovered.

47416 of 48566 relevant lines covered (97.63%)

10702437.75 hits per line