COIN-OR::LEMON - Graph Library

Opened 3 weeks ago

Last modified 2 weeks ago

#620 new defect

Infinite loop in Nagamochi-Ibaraki with floating-point capacities

Reported by: Malte Schürks Owned by: Alpar Juttner
Priority: minor Milestone: LEMON 1.4 release
Component: core Version: hg main
Keywords: Cc:
Revision id:

Description

Floating point errors can cause the current Nagamochi-Ibaraki-implementation to get stuck because no edges are contracted in the iteration. I fixed this by using Tolerance in the relevant place (see attached patch). I also added a test case for this issue.

Attachments (1)

fp-nagamochi-ibaraki-89dd204d3d12.patch (3.4 KB) - added by Malte Schürks 3 weeks ago.

Download all attachments as: .zip

Change History (2)

Changed 3 weeks ago by Malte Schürks

comment:1 Changed 2 weeks ago by Alpar Juttner

Many thanks for the patch. I will review it soon.

Note: See TracTickets for help on using tickets.