COIN-OR::LEMON - Graph Library

Opened 5 months ago

Last modified 3 weeks 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:

Description

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.

Change History (10)

comment:1 Changed 5 months 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 5 months ago by zhaofeng-shu33

I use LEMON 1.3.1

comment:3 Changed 5 months ago by zhaofeng-shu33

test mycode with the latest development version fixes the problem.

comment:4 in reply to:  3 Changed 5 months ago by Peter Kovacs

Thank you for the quick response.

comment:5 Changed 5 months ago by Alpar Juttner

Resolution: duplicate
Status: newclosed

comment:6 Changed 4 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 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.

comment:7 Changed 4 months ago by Peter Kovacs

Resolution: duplicate
Status: closedreopened

comment:8 Changed 3 weeks 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 3 weeks 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 3 weeks 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.