Re: [boost] [BGL] problem w/ push_relabel_max_flow and floating point capacities
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? What are the appropriate tolerances to use? Do the relational tests (<, >) also need modification to properly handle floating point? -Marc "Jeremiah Willcock" <jewillco@osl.iu.edu> wrote in message news:<alpine.LRH.2.00.1101051355460.26649@flowerpot.osl.iu.edu>...
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 algorithm.
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 _______________________________________________ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
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/fl... but I don't think there are < and > replacements there, so hopefully we won't need them. -- Jeremiah Willcock
participants (2)
-
Jeremiah Willcock -
Marc Schafer