Re: [boost] [BGL] problem w/ push_relabel_max_flow and floating point capacities

Subject: Re: [boost] [BGL] problem w/ push_relabel_max_flow and floating point capacities
From: Marc Schafer (Marc.Schafer_at_[hidden])
Date: 2011-01-07 10:03:18

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_at_[hidden]> wrote in message news:<AA067D07858B794CA4E1612284A7E8DAFFF4_at_[hidden]>...
> 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_at_[hidden]> wrote in message news:<alpine.LRH.2.00.1101051355460.26649_at_[hidden]>...
> > 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
>