Boost.Graph Ссылка на void

Question

Я хочу использовать push_relabel_max_flow из библиотеки Boost.Graph. Я уже сгенерировал свой график, это мой код:

    struct EdgeProps {
        double capacity;
        double residual_capacity;
        Traits::edge_descriptor reverse;
    };

    typedef boost::adjacency_list<boost::vecS, boost::vecS, boost::directedS, boost::no_property, EdgeProps > DirectedGraph;

    DirectedGraph g;
    std::vector<DirectedGraph::vertex_descriptor> vertices;

    /* Filling the Graph with vertices and edges and saving the vertex-descriptors in "vertices" */
    //...
    //...

double flow = boost::push_relabel_max_flow(g,vertices[0],vertices[1],
                    vertex_index_map(boost::get(boost::vertex_index, g)).
                     residual_capacity_map(boost::get(&EdgeProps::residual_capacity, g)).
                      reverse_edge_map(boost::get(&EdgeProps::reverse, g)).
                       capacity_map(boost::get(&EdgeProps::capacity, g))
                    );

У меня проблемы с передачей параметров. Я получаю "Формирование ссылки на void" - ошибки:

    /usr/local/include/boost/graph/detail/adjacency_list.hpp:2696: error: forming reference to void
             typedef value_type& reference;
                                 ^

/usr/local/include/boost/graph/detail/adjacency_list.hpp:2697: error: forming reference to void
         typedef const value_type& const_reference;
                                   ^

/usr/local/include/boost/graph/detail/adjacency_list.hpp:2701: error: forming reference to void
             typename Graph::vertex_descriptor,Property,Tag> type;
                                                             ^

Это не все, только три из них. Если вам нужно увидеть все, пожалуйста, оставьте комментарий, и я добавлю их. Кто-нибудь знает, как я должен передать аргументы функции без генерации ошибки "Ссылка на void"?

Answer 1

Насколько я могу судить, в коде распаковки должна быть ошибка для названных параметров, так как следующее компилируется чисто:

Жить на Колиру

#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/push_relabel_max_flow.hpp>

typedef boost::graph_traits<boost::adjacency_list<boost::vecS, boost::vecS, boost::directedS> > Traits;

struct EdgeProps {
    double capacity;
    double residual_capacity;
    Traits::edge_descriptor reverse;
};

typedef boost::adjacency_list<boost::vecS, boost::vecS, boost::directedS, boost::no_property, EdgeProps> DirectedGraph;

int main() {
    DirectedGraph g;
    std::vector<DirectedGraph::vertex_descriptor> vertices;

    /* Filling the Graph with vertices and edges and saving the vertex-descriptors in "vertices" */
    //...
    //...

    double flow = boost::push_relabel_max_flow(g, vertices[0], vertices[1],
            boost::get(&EdgeProps::capacity, g),
            boost::get(&EdgeProps::residual_capacity, g),
            boost::get(&EdgeProps::reverse, g),
            boost::get(boost::vertex_index, g)
        );
}

Возможно, вы захотите сообщить об этом разработчикам библиотеки.

Answer 2

Функции как boost::capacity_map чтобы воспользоваться именованным параметром, который предоставляет библиотека Boost Graph. Эти функции возвращают экземпляр bgl_named_params, который имеет методы для добавления более именованных параметров. Таким образом, вместо разделения параметров запятыми, вы разделяете их точками; а для параметров после первого нет boost:: необходимо, так как они являются методами-членами.

Ваш оригинальный вопрос пытался позвонить так:

double flow = boost::push_relabel_max_flow(g, vertices[0], vertices[1],
                    boost::capacity_map(boost::get(&EdgeProps::capacity, g)),
                     boost::residual_capacity_map(boost::get(&EdgeProps::residual_capacity, g)),
                      boost::reverse_edge_map(boost::get(&EdgeProps::reverse, g)),
                       boost::vertex_index_map(boost::get(boost::vertex_index, g)));

Передача нескольких экземпляров bgl_named_params как это не поддерживается: должно выглядеть

double flow = boost::push_relabel_max_flow(g, vertices[0], vertices[1],
                    boost::capacity_map(boost::get(&EdgeProps::capacity, g)).
                     residual_capacity_map(boost::get(&EdgeProps::residual_capacity, g)).
                      reverse_edge_map(boost::get(&EdgeProps::reverse, g)));

vertex_index_map параметр опущен Пока VertexList в вашем графе является std::vector (то есть вторым параметром шаблона для adjacency_list является boost::vecS), свойство vertex_index присутствует автоматически, и параметр по умолчанию должен работать.

Однако именованные параметры для алгоритмов максимального потока не работают в текущей версии Boost (1.61). Это проблема Boost 12038, исправленная в ветви разработки 2 мая. Я могу подтвердить, что приведенный выше пример работает в текущей ветви разработки.

Использование 7-параметрической версии функции и передача всех необходимых карт работает, но эта версия не поддерживает параметры по умолчанию, поэтому вам придется указать карту vertex_index. Например:

auto capacity = boost::get(&EdgeProps::capacity, g);
auto reverse  = boost::get(&EdgeProps::reverse, g);
auto residcap = boost::get(&EdgeProps::residual_capacity, g);
auto indexmap = boost::get(boost::vertex_index, g);

double flow = boost::push_relabel_max_flow(g, vertices[0], vertices[1],
                    capacity, residcap, reverse, indexmap);