Edmonds Karp Algorithm for maximum flows not returning the labels for the s-t min cut

[CBongiova]

Hello, I am running the maximum_flow function (Edmonds Karp Algorithm) but I have noticed that the function does not return the labelling associated with the minimum cut.
Is there a way to return this output? Thanks!

[matbesancon]

you're right, from some quick research, this is an information you can extract from the dual variables at the optimum. From an API perspective, a mincost function could be called, using maxflow under the hood but returning a set of arcs corresponding to this min cut If you want to give it a try, don't hesistate to PR ;)

[CBongiova]

Actually I have just found out that it is possible to extract the mincut with the Erdos package (https://carlolucibello.github.io/Erdos.jl/latest/flow/). So the problem is solved :)

[matbesancon]

I'll keep this open since having a min-cut format of the flow algorithms still seems interesting for LightGraphs

[sbromberger]

Are we sure we don't have this functionality already? If not, Erdos would be a good reference.

[matbesancon]

there is a mincut function in LG, but it does not seem to be the same concept (or I don't understand it). Nothing of the kind in LGFlows yet

[CBongiova]

@mbesancon Indeed it is not the same concept. You want to retrieve the labelling associated with the mincut from a source-sink maximum flow problem. This link should explain the concept: https://www.geeksforgeeks.org/minimum-cut-in-a-directed-graph/

[matbesancon]

thanks @CBongiova, I was thinking about how to solve this one but the residual flow approach seems to be the simplest. I'll start working on this

[matbesancon]

See the #11 PR ;)