COIN-OR::LEMON - Graph Library

Opened 2 years ago

Last modified 20 months ago

#625 reopened defect

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

Reported by: zhaofeng-shu33 Owned by: Alpar Juttner
Priority: major Milestone: LEMON 1.4 release
Component: core Version: hg main
Keywords: Cc:
Revision id:


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 . Hope some tolerance can be added.

Change History (10)

comment:1 Changed 2 years ago by 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?

comment:2 Changed 2 years ago by zhaofeng-shu33

I use LEMON 1.3.1

comment:3 Changed 2 years ago by zhaofeng-shu33

test mycode with the latest development version fixes the problem.

comment:4 in reply to:  3 Changed 2 years ago by Peter Kovacs

Thank you for the quick response.

comment:5 Changed 2 years ago by Alpar Juttner

Resolution: duplicate
Status: newclosed

comment:6 Changed 23 months ago by zhaofeng-shu33

The problem still exists for some input graph. I prepare one working input graph which makes init(flowMap) fails. See The result can be seen from the continuous integration build log.

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

comment:7 Changed 23 months ago by Peter Kovacs

Resolution: duplicate
Status: closedreopened

comment:8 Changed 20 months ago by 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.)

comment:9 Changed 20 months ago by 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

comment:10 Changed 20 months ago by 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?

Note: See TracTickets for help on using tickets.