lemon preflow algorithm init with flowmap failed because of excess < 0

[zhaofeng-shu33]

I use the returned flowMap of Preflow algorithm to initialize the next Preflow class. But it fails because of in the Preflow code, the excess check gives -1e-19 < 0. The test code can be seen at ​https://gitee.com/freewind201301/test_preflow/blob/master/test_preflow.cpp . Hope some tolerance can be added.

[Peter Kovacs]

I think this issue has already been fixed in #608.

Which version of LEMON do you use? Could you test your code with the latest development version?

[zhaofeng-shu33]

I use LEMON 1.3.1

[zhaofeng-shu33]

test mycode with the latest development version fixes the problem.

[Peter Kovacs]

Thank you for the quick response.

[zhaofeng-shu33]

The problem still exists for some input graph. I prepare one working input graph which makes init(flowMap) fails. See ​https://gitee.com/freewind201301/test_preflow/blob/master/test_preflow.cpp. The result can be seen from the continuous integration build log.

I guess the excess < -1.0 * tolerance.epsilon() check is not enough.

[Peter Kovacs]

I'm sorry for the late answer. Have you tried using different values of "epsilon" for the tolerance object? Its default value is 1e-10 for double type, while your code uses 1e-5 for checking the capacities. I suspect that with a larger tolerance value, e.g. 1e-4, the code will work fine. (Anyway, the capacity values in the input file use only 3 fractional digits.)

[zhaofeng-shu33]

Actually, ​assert passed without problem. I modify the capacity using binary capacity file since text file loses the accuracy to store double type. The problem is ​this line returning false. The actual return value for L37 can be seen from ​AppveyorL1348

[Peter Kovacs]

Could you check if preflow_second works the same with different values of "epsilon" for its tolerance, e.g. 1e-4? And could you check if L30 passes with a stricter tolerance, e.g. 1e-10 or 1e-12?

Furthermore, could you try using long double for the second preflow execution (by copying the values of cap into a new object of type ArcMap<long double>)? And could you try using long double for both executions?