Closed axsk closed 8 months ago
I removed the weird computation of cutweight
alltogether and set it to the weight of the last cut (what was adj_weight
) before.
To my understanding this is what plain Stoer-Wagner does.
I now believe the trick to remove stronger connected vertices early still works with this "simple" cutweight computation.
Attention: 1 lines
in your changes are missing coverage. Please review.
Comparison is base (
da6f801
) 97.26% compared to head (dca0cc8
) 97.28%. Report is 2 commits behind head on master.
Files | Patch % | Lines |
---|---|---|
src/traversals/maxadjvisit.jl | 90.00% | 1 Missing :warning: |
:umbrella: View full report in Codecov by Sentry.
:loudspeaker: Have feedback on the report? Share it here.
Thanks for this contribution! I will need a bit of time to review it but I fully intend to
Feel free to ping me if I take too long
Sure let me know if you have any questions.
Oh well, you are right, the computation of cutweight inside the cut of the phase is unneeded. What it does is to compute the running cut of the phase (which upper bound the mincut). It was part of the previous incorrect implementation when the cutweght was compared to the mincut at each step of each phase. I kept it in a first time because used in combination with my heuristic, it may save times, but according to by benchmarks, it was not worth it, so I removed it, but then, the whole cutweight calculation is unneeded.
Thus I think we can continue with this PR, I will close mine.
To my understanding
adj_cost
stores the cut weight between the last two vertices, s and t. If that is lower then the current best cut it becomes the new best.
This is only true at the last step of the phase. during the phase, it is equal to $w(A_v, v)$ from wikipedia, and it gives a lower bound on the $uv$-mincut, where $u$ is the last vertex added before $v$ (which is the justification of the heuristic)
If nobody disagree, I will merge, there is nothing controversial in these changes
To my understanding
adj_cost
stores the cut weight between the last two vertices, s and t. If that is lower then the current best cut it becomes the new best.I do not really understand the
cutweight
computation inside the mincut phase. (It reminds me more of a flow computation) but also didn't think hard enough about the new intermediate pruning.Anyways, with this change I get the correct cut for the AoC graph (c.f. #324). I did not test this any further, so please someone knowledgable look into it before merge