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
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, gregod at, cpdaniel at, john at