Мне нужно рассчитать минимальную стоимость-максимальный поток для потоковой сети, используя
boost::successive_shortest_path_nonnegative_weights()
функция доступна в BGL (v 1_60_0). Как указано в документации,
ориентированный граф G = (V, E), представляющий сеть, должен быть расширен, чтобы включить обратное ребро для каждого ребра в E. То есть входной граф должен иметь вид Gin = (V, {E U ET}). [...] Ограничение аргумента CapacityEdgeMap должно отображать каждое ребро в E в положительное число, а каждое ребро в ET в 0. WeightMap должен отображать каждое ребро из E в неотрицательное число, а каждое ребро из ET в -вес его перевернутый край.
У меня есть простая функция, которая для каждого ребра, добавленного к графику, добавляет обратное ребро с емкостью и весом, как указано выше:
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;
}
Теперь граф содержит обратные ребра, и у них отрицательные веса, что явно контрастирует с названием алгоритма, который я использую. В результате, когда я выполняю алгоритм, я получаю такую ошибку:
ValueError: The graph may not contain an edge with negative weight.
Что я делаю неправильно?
