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

这些都不是全部,只有三个.如果您需要查看每一个,请发表评论我会添加它们.有没有人知道如何在不生成" 引用无效 "-error的情况下将参数传递给函数？

Answer 1

类似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 Issue 12038,并在5月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);