Boost logo

Boost :

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:

> Jeremiah,

> 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
http://www.boost.org/doc/libs/1_45_0/libs/test/doc/html/utf/testing-tools/floating_point_comparison.html
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