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.