ブーストミンコスト最大フロー:: successive_shortest_path_nonnegative_weights

Question

私はBGLで利用可能

boost::successive_shortest_path_nonnegative_weights() 

機能（V 1_60_0）を使用して、フローネットワークのための最小コスト最大フローを計算する必要があります。

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; 
} 

次に、上記指定され

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.

documentationで指定されるように 、

Iは、容量および重量と逆エッジを追加し、各エッジがグラフに追加するために、単純な機能を有しますグラフには逆の辺があり、負の重みがあります。これは明らかに私が使用しているアルゴリズムの名前とは対照的です。私はアルゴリズムを実行するときその結果 は、私はこのエラーを取得する：

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

は私が間違って何をしているのですか？

Answer 1

同じ問題が発生しました。デバッグの数分後、私は問題を発見しました。私は体重にフロートタイプを使用します。そのため、修正されたエッジウェイト（負の重みの場合のダイクストラのバージョン）は、数値エラーの場合は0よりわずかに低くなることがあります。 "successive_shortest_path_nonnegative_weights.hpp"を書き換えて小さな負の値を切り捨てるようにする可能性があります。