[BUG] mincut() gives wrong result

[axsk]

Attempting to use the mincut() in todays advent of code problem I had to discover that it was not actually finding the min-cut.

The provided graph has a min-cut of 3 edges. mincut() on the other side returns another cut with 4 edges.

The following excerpt computes the true min-cut via karger_min_cut, and also computes the wrong one with mincut() of length 4.

function test_mincut()
    g, nodes = parseinput(readlines("25.in"))
    while true
        cut = karger_min_cut(g)
        length(karger_cut_edges(g, cut)) == 3 && break
    end

    cut2, _ = mincut(g)
    @show cut == cut2
    @show length.(karger_cut_edges.(Ref(g), [cut, cut2]))
end

The whole code+graph data (file 25.in) can be found here.

Julia 1.10rc3 with Graphs 1.9.0.

[gdalle]

Thank you for filing the issue! It seems you wrote your own version of mincut instead? Could you explain what you changed to fix it?

[gdalle]

Related: #105

[axsk]

I ported the first C++ implementation from Wikipedia (seem pretty solid and nice to me. iirc i only exchanged the dense for a sparse matrix).
They keep all state in a single copy of the weight matrix, doing the vertex-merging by weight updates.

I tried crosschecking it with the packages mincut but could not really align them.
Especially L77 I still don't understand (in the classical Stoer Wagner edge weights increase only). Then there is the new additional vertex merge
The vertex merging was also not clear to me (whats merged into what? whats root/non-root?)