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

Question

I need to calculate the min-cost-max-flow for a flow network using the

boost::successive_shortest_path_nonnegative_weights()

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

the directed graph G=(V,E) that represents the network must be augmented to include the reverse edge for every edge in E. That is, the input graph should be Gin = (V,{E U ET}). [...] The CapacityEdgeMap argument cap must map each edge in E to a positive number, and each edge in ET to 0. The WeightMap has to map each edge from E to nonnegative number, and each edge from ET to -weight of its reversed edge.

I have a simple function which, for each edge added to the graph, adds a reverse edge with capacity and weight as specified 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 reverse edges, and they have negative weights, which is clearly in contrast with the name of the algorithm I'm using. 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?

Benumb

Fiddling around, I found out I have the same error even if I don't add the reverse edges, i.e. the graph has no negative weights. – Benumb

Answer 1

Just ran into the same problem. After a few minutes of debugging I found the problem. I use float type for the weights. Because of that the modified edge weight (a version of dijkstra for negative weights) may become slightly below 0 for numerical error. The possible solution maybe rewriting "successive_shortest_path_nonnegative_weights.hpp" so that it rounds up small negative values

Symptom