Possible floating point issue in cycle_canceling.h

[Alpar Juttner]

From the lemon-devel@… mailing list:

Hello,

I am using the lemon library 1.2.1 to solve a minCostFlow-problem. I encountered a problem by using the cyclecanceling algorithm. Sometimes, depending on graph and flow settings, the function hangs in an infinity loop at cycle_canceling.h at line 935:

while (mmc.findCycleMean() && mmc.cycleCost() < 0) {

I do not have deep insight into the algorithm but by debugging I saw that mmc.cycleCost() returns constantly values around -10e-17. Everything seems to work correctly by changing the line to

while (mmc.findCycleMean() && mmc.cycleCost() < -10e-10) {

Maybe this is a rounding issue?

Regards, Michael

[Peter Kovacs]

The current min cost flow implementations support only integer data. It is a known and documented limitation of these codes.

[Peter Kovacs]

I think we should close this ticket. See e.g. #261 for the related feature request.