search

JuliaGraphs / LightGraphsFlows.jl

Flow algorithms on LightGraphs
Other
36 stars 11 forks source link

Never ending min-cut with push-relabel algorithm #41

Open fypc opened 3 years ago

fypc commented 3 years ago

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 commented 3 years ago

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 commented 3 years ago

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

etiennedeg commented 3 years ago

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.