Error while computing the st min cut

[mathieuLacroix]

Hi,

The computation of the vertex set part1 in the mincut function defined in LightGraphsFlows is incorrect as it may contain multiple copies of a same node. The problem occurs for instance with the following example:

 g = CompleteDiGraph(10)
cap1 = [
            0.0  10.0   0.0  0.0  0.0  0.0  1.0  0.0  0.0  1.0;
           10.0   0.0   1.0  0.0  0.0  0.0  0.0  1.0  0.0  0.0;
            0.0   1.0   0.0  0.0  0.0  0.0  0.0  0.0  0.0  2.0;
            0.0   0.0   0.0  0.0  1.0  1.0  0.0  0.0  0.0  0.0;
            0.0   0.0   0.0  1.0  0.0  0.0  0.0  0.0  1.0  0.0;
            0.0   0.0   0.0  1.0  0.0  0.0  0.0  1.0  0.0  0.0;
            1.0   0.0   0.0  0.0  0.0  0.0  0.0  0.0  1.0  0.0;
            0.0   1.0   0.0  0.0  0.0  1.0  0.0  0.0  0.0  1.0;
            0.0   0.0   0.0  0.0  1.0  0.0  1.0  0.0  0.0  0.0;
            1.0   0.0   2.0  0.0  0.0  0.0  0.0  1.0  0.0  0.0
       ]
(part1, part2, value) = LightGraphsFlows.mincut(g,1,10,cap1,LightGraphsFlows.PushRelabelAlgorithm())

Running the previous code gives a vertex set part1 containing twice node 2.

I think that the problem comes from the computation of dests when computing the minimum cut. Instead of

[dst for dst in 1:lg.nv(flow_graph) if residual_matrix[node,dst]>0.0 && dst ∉ part1]

shouldn't we have

[dst for dst in 1:lg.nv(flow_graph) if residual_matrix[node,dst]>0.0 && dst ∉ part1 && dst ∉ queue]

since every node in the queue is then added to part1?

Best, Mathieu

[etiennedeg]

It is related to #27 I made a PR, but it is not merged yet.

[matbesancon]

I think this now works with the fixed PR, a release will be out soon

[matbesancon]

I just tested, working correctly, closing now

[matbesancon]

@JuliaRegistrator register()

[JuliaRegistrator]

Registration pull request created: JuliaRegistries/General/15465

After the above pull request is merged, it is recommended that a tag is created on this repository for the registered package version.

This will be done automatically if the Julia TagBot GitHub Action is installed, or can be done manually through the github interface, or via:

git tag -a v0.4.1 -m "<description of version>" a5b65164ab29966264393ceca5555d6dc777b77f
git push origin v0.4.1