Min-cost-max-flow with boost :: successive_shortest_path_nonnegative_weights

Question

I need to calculate min-cost-max stream for stream network using

boost::successive_shortest_path_nonnegative_weights() 

available in BGL (v 1_60_0). As stated in the documentation ,

the directed graph G = (V, E), which represents the network, must be supplemented to include the inverse edge for each edge in E. That is, the input graph must be Gin = (V, {EU ET}). [...] The argument key of CapacityEdgeMap must match each edge in E with a positive number, and each edge in ET is 0. WeightMap must map each edge from E to a non-negative number, and each edge from ET to weight is its inverse edge.

I have a simple function that for each edge added to the graph, adds a back edge with capacity and weight, as described above:

 void add_edge_and_reverse(vertex_desc& source, vertex_desc& target, Edge& edge, flow_network_t& fn, boost::associative_property_map<std::map<edge_desc, edge_desc>>& rev_map) { std::pair<edge_desc, bool> e = boost::add_edge(source, target, edge, fn); Edge reverse_edge(-edge.cost, 0); std::pair<edge_desc, bool> e_rev = boost::add_edge(target, source, reverse_edge, fn); rev_map[e.first] = e_rev.first; rev_map[e_rev.first] = e.first; } 

Now the graph contains inverse edges, and they have negative weights, which clearly contrasts with the name of the algorithm used. As a result, when I execute the algorithm, I get this error:

 ValueError: The graph may not contain an edge with negative weight. 

What am I doing wrong?

Answer 1

Just ran into the same problem. After a few minutes of debugging, I found the problem. I use the float type for weights. Because of this, the changed edge weight (dijkstra version for negative weights) may become slightly lower than 0 for a numerical error. A possible solution can be rewritten by "successive_shortest_path_nonnegative_weights.hpp" so that it rounds off small negative values