Never ending min-cut with push-relabel algorithm

[fypc]

Hi,

I got the same kind of floating point error as etienneINSA in a previous issue while solving a min-cut problem with the push-relabel algorithm. Here is the code below to reproduce it with the graph capacity matrix files in attachment.

using LightGraphsFlows
import LightGraphs
const lg = LightGraphs
using NPZ

sg = lg.loadgraph("lsg.lg")
cm = npzread("lcm.npy")
(part1, part2, maxflow) = LightGraphsFlows.mincut(sg, 1, 16, cm, LightGraphsFlows.PushRelabelAlgorithm())

Archive.zip

[etiennedeg]

This is probably the same issue. I have filled a PR #31 fixing the problem, but it is not merged yet. If you really need to get it work, I think you can safely use it, maintainers don't seem to be very active at the moment, so this could take a while to get merged.

[fypc]

Thank you so much Etienne, I will apply your fix! Meanwhile, it works flawlessly with the Dinic algorithm.

[etiennedeg]

Though far less often, I already ran into infinite loops using dinic's algorithm. My PR should fix this also. While browsing the other files, I realized edmonds_karp could also lead to an infinite loop (but it never happened for me). I might add that to the PR. Other algorithms seems to already handle floating points.

Also, if you use my PR, take care to remove the last commit from matbesancon, as it invalidates the PR.