Subject: [boost] [BGL] problem w/ push_relabel_max_flow and floating point capacities
From: Marc Schafer (Marc.Schafer_at_[hidden])
Date: 2010-12-22 16:21:57
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.
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk