Subject: Re: [boost] [BGL] problem w/ push_relabel_max_flow and floating point capacities
From: Jeremiah Willcock (jewillco_at_[hidden])
Date: 2011-01-07 11:35:14
On Fri, 7 Jan 2011, Marc Schafer wrote:
> I am looking at a particular case in the debugger and I see that is_flow
> returns false because of comparisons that fail by an error that is many
> orders of magnitude smaller than the numbers being compared. For
> example, x==y fails because x and y are both approximately 1. and x-y is
> 1.e-14. I could replace the particular comparisons that are failing for
> my test case, but I need to know how to make the entire algorithm
> generically suitable for use with floating point numbers.
> is_flow just performs a consistency check after the calculation is
> complete. Does the calculation itself require any modifications to work
> correctly with floating point numbers?
I don't know, but I wouldn't imagine it would.
> What are the appropriate
> tolerances to use?
I would guess, if is_flow() is just for debugging, that a tolerance of
1e-5 or 1e-8 would work.
> Do the relational tests (<, >) also need
> modification to properly handle floating point?
I don't know. I had suggested that you try replacing == and != but not <
and > and see if the code works correctly. There are replacements for ==
and != documented at
but I don't think there are < and > replacements there, so hopefully we
won't need them.
-- Jeremiah Willcock
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk