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: Jeremiah Willcock (jewillco_at_[hidden])
Date: 2011-01-05 14:01:27

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