Boost.Graph 引用 void

Question

我想使用 Boost.Graph 库中的 push_relabel_max_flow。我已经生成了图表，这是我目前的代码：

    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

据我所知，命名参数的解包代码中一定存在错误，因为以下代码可以干净地编译：

Live On Coliru

#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 等函数可以利用 named parameter idiom that the Boost Graph library provides。这些函数 return 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) 中不起作用。这是 5 月 2 日的 Boost Issue 12038, and was fixed in the development branch。我可以确认上面的示例在当前开发分支上有效。

使用函数的 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);

Boost.Graph 引用 void

Boost.Graph Reference to void

c++

boost

boost-graph