Apologies for the double post. Outlook crashed while I was typing the first one and I didn't think it got sent. -Marc "Marc Schafer" <Marc.Schafer@mathworks.com> wrote in message news:<AA067D07858B794CA4E1612284A7E8DAFFF4@exmb-01-ah.ad.mathworks.com>...

Jeremiah, For my test case, is_flow fails on a comparison x==y where x and y are both approximately 1. and x-y is 1.e-14.

However, the graphs I want to process could have capacities that are any valid floating point numbers. This leads to several questions:

is_flow is a consistency check after the algorithm is complete, does the algorithm need modifications to work correctly with floating point numbers?

How do I determine the correct tolerances to use for comparisons?

How do I deal with the relational operators (<, >)?

-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

_______________________________________________ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost