Subject: Re: [boost] [BGL] problem w/ push_relabel_max_flow and floating point capacities
From: Jeremiah Willcock (jewillco_at_[hidden])
Date: 2011-01-05 14:01:27
On Wed, 22 Dec 2010, Marc Schafer wrote:
> Using the push_relabel_max_flow feature on graphs that have edge
> capacities in double or single precision often results in a failed
> assertion (line 706 push_relabel_max_flow.hpp) on debug builds although
> the answer provided is correct for builds with assertions disabled.
> The is_flow() method (line 564, push_relabel_max_flow.hpp) performs some
> consistency checking after the algorithm completes and there is an
> assertion that it returns true. The comparisons inside is_flow are done
> using ==, !=, >, and <. Using a locally modified version, I was able to
> see that all the cases where is_flow returns false are caused by errors
> on the order of machine precision.
> I believe the error is a faulty comparison mechanism inside is_flow
> rather than a problem with my graphs or the push_relabel_max_flow
I agree with what you are saying. If you just replace the == and !=
operations in is_flow (and not < and >), does the code work correctly?
Boost already has floating point equality comparisons with a tolerance,
but does not appear to have inequalities.
-- Jeremiah Willcock
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk