Min-Maks kosztów przepływu z przypominającego :: successive_shortest_path_nonnegative_weights

Question

potrzebne do wyliczenia kosztów min-maks przepływu do sieci przepływu za pomocą funkcji dostępnej w BGL

boost::successive_shortest_path_nonnegative_weights() 

1_60_0 (V). Jak określono w 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.

mam prostą funkcję, która dla każdej krawędzi dodany do wykresu dodaje odwrotnej krawędź o wydajności i masy, jak określono powyżej:

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

Teraz wykres zawiera odwrócone krawędzie i ma ujemne masy, co wyraźnie kontrastuje z nazwą algorytmu, którego używam. W rezultacie, kiedy wykonać algorytm, otrzymuję ten błąd:

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

Co robię źle?

Answer 1

Wystąpił tylko ten sam problem. Po kilku minutach debugowania znalazłem problem. Używam typu float dla ciężarów. Z tego powodu zmodyfikowana waga krawędzi (wersja dijkstra dla ujemnych ciężarów) może stać się nieco poniżej 0 dla błędu numerycznego. Możliwe rozwiązanie polegające na przepisywaniu "successive_shortest_path_nonnegative_weights.hpp" w taki sposób, aby zaokrąglać małe wartości ujemne