boost - Boost 最大流量算法无法编译。错误:形成对 void 的引用
问题描述
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
我是否以不正确的方式传递参数?如何正确传递它们?
谢谢!
解决方案
这似乎确实是一个错误。
当没有定义内部属性(内部属性)时,似乎choose_const_pmap
for失败。edge_capacity
edge_capacity_t
定义一个使问题消失。但是,我们可以检查它是否总是优先于通过命名参数提供的那个:
struct Oops {};
using EdgeProperty = boost::property<boost::edge_capacity_t, Oops>;
导致编译问题,提示选择了错误的property map。
我找不到这种行为的明显原因 - 所有其他命名参数的行为都符合预期,并且以非常相似的方式声明(该过程由宏自动化)。我认为会涉及一些非常微妙的事情(比如名称冲突或 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);
}
如您所见,所有算法调用现在都已编译。
推荐阅读
- javascript - 为 Gulp 4 重新编写 gulpfile.js,默认任务现在挂起
- python - 分割一行文本得到两个变量
- tensorflow - 在 Intel Atom 上构建 TensorFlow
- postgresql - 为什么`psql postgres`说我的密码错误?
- java - 玩!框架日志记录仅适用于系统级别
- android-workmanager - 如何在没有序列化的情况下将对象作为输入传递给 WorkManager?
- r - 需要拆分包含不同数量的变量名称和观察值的双重连接数据的列
- intellij-idea - 为什么我不能在 IntelliJ IDEA 中输入“@”?
- c - 修复可能由于 STM32 Nucleo-F334R8 上的 malloc 导致的内存覆盖错误
- powershell - Powershell 模块中 *.psm1 文件的用途是什么?