Boost 最大流算法无法编译.错误:形成对 void 的引用 [英] Boost max flow algorithms do not compile. error: forming reference to void
问题描述
Boost 提供了三种不同的算法来寻找有向图中的最大流:boykov_kolmogorov、edmonds_karp 和 push_relabel.它们都有命名和非命名参数版本.他们使用的参数集也非常相似.尽管如此,使用相同的参数,这些算法中的一些可以编译,而另一些则不能.
push_relabel 可以很好地编译命名和非命名版本:
使用 Graph =boost::adjacency_list<boost::vecS, boost::vecS, boost::directedS,VertexProperty、EdgeProperty>;auto props = boost::capacity_map(容量).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, 容量, 剩余容量,reverse_edge_map, vertex_index_map);
boykov_kolmogorov 使用未命名版本编译:
boost::boykov_kolmogorov_max_flow(g, 容量, 剩余容量,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,容量,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
我是否以错误的方式传递参数?如何正确传递它们?
谢谢!
这确实似乎是一个错误.
当没有定义内部 edge_capacity_t
属性(室内属性).
定义一个会使问题消失.但是,我们可以检查它是否始终优先于通过命名参数提供的参数:
struct Oops {};使用 EdgeProperty = boost::property;
导致编译问题,提示选择了错误的属性映射.
我找不到造成这种行为的明显原因 - 所有其他命名参数的行为都符合预期,并且以非常相似的方式声明(该过程由宏自动执行).我认为会涉及一些非常微妙的事情(例如名称冲突或 ADL 事故?).
这是对我有用的代码:
Live On Wandbox(注意显然不能成功运行,因为它不满足任何不变量)
#define BOOST_ALLOW_DEPRECATED_HEADERS#include #include #include #include <boost/graph/edmonds_karp_max_flow.hpp>#include #include #include int main() {struct VertexProperty final {};//struct EdgeProperty final {};使用 EdgeProperty = boost::property;使用图 =boost::adjacency_list<boost::vecS, boost::vecS, boost::directedS,VertexProperty、EdgeProperty>;使用 Edge = boost::graph_traits::edge_descriptor;使用 Vertex = boost::graph_traits::vertex_descriptor;自动 g = 图{};汽车 s = 顶点{};自动 t = 顶点{};自动残留容量映射 = std::vector{};auto reverseEdgeMap = std::vector{};auto colorMap = std::vector{};auto predcessorMap = std::vector{};auto distanceMap = std::vector{};自动顶点索引图 =boost::make_function_property_map([](Vertex) { return 0; });自动 edge_index_map =boost::make_function_property_map([](Edge) { return 0; });//自动容量 = boost::make_function_property_map( [](Edge) { return 0; });自动容量 = boost::get(boost::edge_capacity, g);自动剩余容量 = boost::make_iterator_property_map(残差图.begin(), edge_index_map);auto reverse_edge_map = boost::make_iterator_property_map(reverseEdgeMap.begin(), edge_index_map);自动 color_map =boost::make_iterator_property_map(colorMap.begin(), vertex_index_map);自动 predcessor_map = boost::make_iterator_property_map(predcessorMap.begin(), vertex_index_map);auto distance_map = boost::make_iterator_property_map(distanceMap.begin(),顶点索引图);auto props = boost::capacity_map(容量).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, 容量, 剩余容量,reverse_edge_map, vertex_index_map);boost::boykov_kolmogorov_max_flow(g,容量,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, 容量, 剩余容量,reverse_edge_map, color_map, predcessor_map);}
如您所见,所有算法调用现在都可以编译.
Boost provides three different algorithms for finding max flow in directed graphs: boykov_kolmogorov, edmonds_karp and push_relabel. All of them have named and non-named parameter versions. Parameter sets they use are also very similar. Despite that, with same parameters some of these algorithms compile and some of them do not.
push_relabel compiles nicely with both named and non-named version:
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 compiles with non-named version:
boost::boykov_kolmogorov_max_flow(g, capacity, residual_capacity,
reverse_edge_map,
vertex_index_map, s, t);
But fails with named version:
boost::boykov_kolmogorov_max_flow(g, s, t, props);
/celibs/boost_1_73_0/boost/graph/detail/adjacency_list.hpp:2768:17: error: forming reference to void
edmonds_karp fails with both named and non-named versions with same error:
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: error: use of deleted function
Full example is here: https://godbolt.org/z/dvjfec
Do I pass parameters in incorrect way? How to pass them correctly?
Thanks!
This indeed seems to be a bug.
It appears that the choose_const_pmap
for edge_capacity
fails when there is no interior edge_capacity_t
property defined (Interior Properties).
Defining one makes the problem go away. However, we can check that it always takes precedence over the one provided via named paramaters:
struct Oops {};
using EdgeProperty = boost::property<boost::edge_capacity_t, Oops>;
Leads to compilation problems, suggesting that the wrong property map is selected.
I could not find an obvious cause for this behaviour - all the other named arguments behave as expected, and are declared in very similar fashion (the process is automated by macro). I assume there will be something very subtle involved (like a name collision or ADL mishap?).
Here's the code that works for me:
Live On Wandbox (note obviously can't run successfully, because it doesn't satisfy any invariants)
#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);
}
As you can see all of the algorithm invocations now compile.
这篇关于Boost 最大流算法无法编译.错误:形成对 void 的引用的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!