[Boost-bugs] [Boost C++ Libraries] #10805: Bugs: problem in push_relabel_max_flow algorithm when using std::numeric_limits<double>::max() as capacity in some edges

Subject: [Boost-bugs] [Boost C++ Libraries] #10805: Bugs: problem in push_relabel_max_flow algorithm when using std::numeric_limits<double>::max() as capacity in some edges
From: Boost C++ Libraries (noreply_at_[hidden])
Date: 2014-11-19 15:29:51

#10805: Bugs: problem in push_relabel_max_flow algorithm when using
std::numeric_limits<double>::max() as capacity in some edges
-------------------------------------+-------------------------------------
 Reporter:  Pablo Madoery            |       Type:  Bugs
  <madoerypablo@…>                   |  Milestone:  To Be Determined
   Status:  new                      |    Version:  Boost 1.55.0
Component:  None                     |   Keywords:  BGL,
 Severity:  Problem                  |  push_relabel_max_flow
-------------------------------------+-------------------------------------
 I am having trouble using the push_relabel_max_flow algorithm when I put
 std::numeric_limits<double>::max() as capacity attribute in some edges.
 is there a maximum value that I can use as capacities. which ?.

 I adjunct an example that reproduces the error:

  /home/madoery/boost_1_55_0/boost/graph/push_relabel_max_flow.hpp:750:
 typename boost::property_traits<CapacityEdgeMap>::value_type
 boost::push_relabel_max_flow(Graph&, typename
 boost::graph_traits<Graph>::vertex_descriptor, typename
 boost::graph_traits<Graph>::vertex_descriptor, CapacityEdgeMap,
 ResidualCapacityEdgeMap, ReverseEdgeMap, VertexIndexMap) [with Graph =
 boost::adjacency_list<boost::vecS, boost::vecS, boost::bidirectionalS,
 vertexInfo, edgeInfo>, CapacityEdgeMap =
 boost::adj_list_edge_property_map<boost::bidirectional_tag, double,
 double&, long unsigned int, edgeInfo, double edgeInfo::*>,
 ResidualCapacityEdgeMap =
 boost::adj_list_edge_property_map<boost::bidirectional_tag, double,
 double&, long unsigned int, edgeInfo, double edgeInfo::*>, ReverseEdgeMap
 = boost::adj_list_edge_property_map<boost::bidirectional_tag,
 boost::detail::edge_desc_impl<boost::bidirectional_tag, long unsigned
 int>, boost::detail::edge_desc_impl<boost::bidirectional_tag, long
 unsigned int>&, long unsigned int, edgeInfo,
 boost::detail::edge_desc_impl<boost::bidirectional_tag, long unsigned int>
 edgeInfo::*>, VertexIndexMap =
 boost::vec_adj_list_vertex_id_map<vertexInfo, long unsigned int>, typename
 boost::property_traits<CapacityEdgeMap>::value_type = double, typename
 boost::graph_traits<Graph>::vertex_descriptor = long unsigned int]:
 Assertion `algo.is_flow()' failed.

 On the other side,
 http://lists.boost.org/Archives/boost/2011/01/174683.php

 treats the problem of using double precision as capacity attributes on the
 edges.
 Jeremiah Willcock advices to just replace the == and != operations in
 is_flow (and not < and >) and asks if the code works correctly in that
 case. I made the replacement but I had to use precision (epsilon) too
 high (in the order of 0.2, 0.3) to make the BOOST_ASSERT(algo.is_flow())
 to pass.

 Maybe these are two different problems or not. I am not sure, but they
 seems to be regarding the same assert that is failing

-- 
Ticket URL: <https://svn.boost.org/trac/boost/ticket/10805>
Boost C++ Libraries <http://www.boost.org/>
Boost provides free peer-reviewed portable C++ source libraries.