Алгоритмы увеличения максимального потока не компилируются. ошибка: формирование ссылки на void

Question

Boost предоставляет три различных алгоритма для поиска максимального потока в ориентированных графах: boykov_kolmogorov, edmonds_karp и push_relabel. Все они имеют версии параметров с именем и без имени. Наборы параметров, которые они используют, также очень похожи. Несмотря на это, с одинаковыми параметрами некоторые из этих алгоритмов компилируются, а некоторые - нет.

push_relabel прекрасно компилируется как с именованной, так и с неименованной версией:

         using Graph =
    boost::adjacency_list<boost::vecS, boost::vecS, boost::directedS,
                        VertexProperty, EdgeProperty>;
  auto props = boost::capacity_map(capacity)
               .residual_capacity_map(residual_capacity)
               .reverse_edge_map(reverse_edge_map)
               .vertex_index_map(vertex_index_map)
               .color_map(color_map)
               .predecessor_map(predcessor_map)
               .distance_map(distance_map);
  boost::push_relabel_max_flow(g, s, t, props);
  boost::push_relabel_max_flow(g, s, t, capacity, residual_capacity,
                   reverse_edge_map, vertex_index_map);

boykov_kolmogorov компилируется с неназванной версией:

         boost::boykov_kolmogorov_max_flow(g, capacity, residual_capacity,
                                    reverse_edge_map,
                                    vertex_index_map, s, t);

Но не работает с названной версией:

         boost::boykov_kolmogorov_max_flow(g, s, t, props);

/celibs/boost_1_73_0/boost/graph/detail/adjacency_list.hpp:2768:17: ошибка: формирование ссылки на void

edmonds_karp не работает как с именованными, так и без именованными версиями с той же ошибкой:

       boost::edmonds_karp_max_flow(g, s, t, props);
boost::edmonds_karp_max_flow(g, s, t, capacity, residual_capacity, reverse_edge_map,
                          color_map, predcessor_map);

/celibs/boost_1_73_0/boost/concept_check.hpp:147:9: ошибка: использование удаленной функции

Полный пример здесь: https://godbolt.org/z/dvjfec

Могу ли я передать параметры неправильно? Как их правильно сдать?

Благодаря!

Answer 1

Это действительно похоже на ошибку.

Похоже, что choose_const_pmap за edge_capacity терпит неудачу, когда нет интерьера edge_capacity_tсвойство определено (внутренние свойства).

Определение одного снимает проблему. Однако мы можем проверить, что он всегда имеет приоритет над параметром, указанным с помощью named paramaters:

struct Oops {};
using EdgeProperty = boost::property<boost::edge_capacity_t, Oops>;

Приводит к проблемам компиляции, предполагая, что выбрана неправильная карта свойств.

Я не смог найти очевидную причину такого поведения - все остальные именованные аргументы ведут себя так, как ожидалось, и объявлены очень похожим образом (процесс автоматизирован с помощью макроса). Я предполагаю, что здесь будет что-то очень тонкое (например, конфликт имен или неудача с ADL?).

Вот код, который мне подходит:

Live On Wandbox (примечание, очевидно, не может работать успешно, потому что он не удовлетворяет никаким инвариантам)

#define BOOST_ALLOW_DEPRECATED_HEADERS
#include <boost/config.hpp>
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/boykov_kolmogorov_max_flow.hpp>
#include <boost/graph/edmonds_karp_max_flow.hpp>
#include <boost/graph/graph_utility.hpp>
#include <boost/graph/push_relabel_max_flow.hpp>
#include <boost/property_map/function_property_map.hpp>

int main() {
    struct VertexProperty final {};
    // struct EdgeProperty final {};
    using EdgeProperty = boost::property<boost::edge_capacity_t, int>;
    using Graph =
        boost::adjacency_list<boost::vecS, boost::vecS, boost::directedS,
                              VertexProperty, EdgeProperty>;
    using Edge = boost::graph_traits<Graph>::edge_descriptor;
    using Vertex = boost::graph_traits<Graph>::vertex_descriptor;
    auto g = Graph{};
    auto s = Vertex{};
    auto t = Vertex{};

    auto residualCapacityMap = std::vector<int>{};
    auto reverseEdgeMap = std::vector<Edge>{};
    auto colorMap = std::vector<boost::default_color_type>{};
    auto predcessorMap = std::vector<Edge>{};
    auto distanceMap = std::vector<int>{};

    auto vertex_index_map =
        boost::make_function_property_map<Vertex>([](Vertex) { return 0; });
    auto edge_index_map =
        boost::make_function_property_map<Edge>([](Edge) { return 0; });
    // auto capacity = boost::make_function_property_map<Edge>( [](Edge) { return 0; });
    auto capacity = boost::get(boost::edge_capacity, g);
    auto residual_capacity = boost::make_iterator_property_map(
        residualCapacityMap.begin(), edge_index_map);
    auto reverse_edge_map = boost::make_iterator_property_map(
        reverseEdgeMap.begin(), edge_index_map);
    auto color_map =
        boost::make_iterator_property_map(colorMap.begin(), vertex_index_map);
    auto predcessor_map = boost::make_iterator_property_map(
        predcessorMap.begin(), vertex_index_map);
    auto distance_map = boost::make_iterator_property_map(distanceMap.begin(),
                                                          vertex_index_map);

    auto props = boost::capacity_map(capacity)
                     .residual_capacity_map(residual_capacity)
                     .reverse_edge_map(reverse_edge_map)
                     .vertex_index_map(vertex_index_map)
                     .color_map(color_map)
                     .predecessor_map(predcessor_map)
                     .distance_map(distance_map);

    boost::push_relabel_max_flow(g, s, t, props);
    boost::push_relabel_max_flow(g, s, t, capacity, residual_capacity,
                                 reverse_edge_map, vertex_index_map);

    boost::boykov_kolmogorov_max_flow(g, capacity, residual_capacity,
                                      reverse_edge_map, vertex_index_map, s, t);
    boost::boykov_kolmogorov_max_flow(g, s, t, props);

    boost::edmonds_karp_max_flow(g, s, t, props);
    boost::edmonds_karp_max_flow(g, s, t, capacity, residual_capacity,
                                 reverse_edge_map, color_map, predcessor_map);
}

Как видите, теперь все вызовы алгоритмов компилируются.