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

Subject: [boost] [BGL] problem w/ push_relabel_max_flow and floating point capacities
From: Marc Schafer (Marc.Schafer_at_[hidden])
Date: 2011-01-03 16:33:54

I am still hoping to hear back from somebody regarding the issues described below.  Is the intent to support floating point?  If we were to make changes that added tolerances to the comparisons, would they be accepted?

-Marc

From: Marc Schafer
Sent: Wednesday, December 22, 2010 4:22 PM
To: 'boost_at_[hidden]'
Subject: [BGL] problem w/ push_relabel_max_flow and floating point capacities

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.

-Marc