c++ - 如何在提升图属性中使用参考?
问题描述
我正在尝试定义一个提升邻接列表,其中包含对外部容器中定义的属性的引用(不一定是基于 0 的!)。
因为我想在运行时过滤结果图,所以我试图在启动时添加所有顶点并将所有顶点相互连接(无循环)。
但是编译器总是抱怨某些东西不是默认可构造的,我不清楚为什么?有什么方法可以实现我想做的事情吗?
#include <boost/graph/adjacency_list.hpp>
struct vertex_t
{
uint32_t num1;
uint32_t num2;
};
using MyVec = std::vector<vertex_t>;
using AdjLst = boost::adjacency_list<boost::setS, boost::vecS, boost::undirectedS, std::reference_wrapper<vertex_t> >;
int main()
{
MyVec vc;
// Some sample data
vc.push_back({123, 456});
vc.push_back({23, 46 });
vc.push_back({3, 6 });
vc.push_back({12, 4 });
AdjLst graph;
for (auto it = vc.begin(); it != vc.end(); ++it)
{
add_vertex(*it, graph);
}
AdjLst::vertex_iterator vi, vend;
for (boost::tie(vi, vend) = vertices(graph); vi != vend; ++vi)
{
auto vi2 = vi;
while (++vi2 != vend)
{
add_edge(*vi, *vi2, graph); // <--------FAIL!
}
}
return 1;
}
编辑:
我刚刚看到(根据文档)该属性必须是默认可构造的。所以问题是:我该如何解决这个要求?(没有回到指针?)
解决方案
限制是属性必须是默认可构造的。std::reference_wrapper
不是。其实一个简单的
AdjLst graph(4);
会遇到同样的麻烦。原因是add_edge
能够增长顶点空间:
// Here we override the directed_graph_helper add_edge() function
// so that the number of vertices is automatically changed if
// either u or v is greater than the number of vertices.
template < class Graph, class Config, class Base >
inline std::pair< typename Config::edge_descriptor, bool > add_edge(
typename Config::vertex_descriptor u, typename Config::vertex_descriptor v,
const typename Config::edge_property_type& p,
vec_adj_list_impl< Graph, Config, Base >& g_)
{
BOOST_USING_STD_MAX();
typename Config::vertex_descriptor x
= max BOOST_PREVENT_MACRO_SUBSTITUTION(u, v);
if (x >= num_vertices(g_))
g_.m_vertices.resize(x + 1);
adj_list_helper< Config, Base >& g = g_;
return add_edge(u, v, p, g);
}
一种不太明显的解决方法是替换
vecS
为基于节点的容器选择器。原因是 BGL 不知道/尝试帮助添加顶点,因为顶点描述符不是隐含的顶点索引。看到Live On Coliru其他选项:
你可以使用
boost::optional<vertex_t&>
. 现场演示纯粹主义者会建议
std::optional<std::reference_wrapper<vertex_t> >
,但那时我只是存储一个vertex_t*
稍微花哨一点,您可以将所有权完全移到图表上,并在顶部使用侵入式容器:
namespace bi = boost::intrusive;
using Hook = bi::list_base_hook<bi::link_mode<bi::auto_unlink>>;
using MyList = bi::list<struct vertex_t, bi::constant_time_size<false>>;
struct vertex_t : Hook {
uint32_t num1;
uint32_t num2;
vertex_t() = default;
vertex_t(uint32_t a, uint32_t b) : num1(a), num2(b) {}
};
using AdjLst = boost::adjacency_list<boost::setS, boost::vecS,
boost::undirectedS, vertex_t>;
int main()
{
MyList vc;
AdjLst graph;
for (auto node : { vertex_t
{ 123, 456 },
{ 23, 46 },
{ 3, 6 },
{ 12, 4 },
})
{
auto v = add_vertex(node, graph);
vertex_t& stored_node = graph[v]; // note: intermediate variable for
// exposition purposes only
vc.push_back(stored_node);
}
最简单的清单
以上,我建议vertex_t*
作为捆绑类型:
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/graph_utility.hpp>
#include <iostream>
struct vertex_t {
uint32_t num1;
uint32_t num2;
};
using MyVec = std::vector<vertex_t>;
using AdjLst = boost::adjacency_list<
boost::setS,
boost::vecS,
boost::undirectedS,
vertex_t*
>;
int main()
{
MyVec vc {
{ 123, 456 },
{ 23, 46 },
{ 3, 6 },
{ 12, 4 },
};
AdjLst graph;
for (auto it = vc.begin(); it != vc.end(); ++it) {
add_vertex(&*it, graph);
}
for (auto v : boost::make_iterator_range(vertices(graph)))
{
auto& [num1,num2] = *graph[v];
std::cout << v << " {" << num1 << ", " << num2 << "}\n";
}
for (auto [src, e] = vertices(graph); src != e; ++src)
for (auto dest = src; ++dest != e;)
boost::add_edge(*src, *dest, graph);
}
推荐阅读
- python - Seaborn FacetGrid 多页 pdf 绘图
- spartacus-storefront - 将新的自定义 layoutSlot 添加到主页模板
- amazon-web-services - Amazon S3 公共访问价格?
- python - 为什么“订单详情”按钮打不开?
- javascript - 了解函数绑定行为
- php - 如何在有条件的情况下获取当前月份的平均数据?
- javascript - 在 Internet Explorer 中使用 javascript 将 HTML 表或 CSV 或 XML 或 RTF 导出为 excel
- javascript - 如何在 Node.js 包中打包特定于 Web 的 UI 代码?
- r - 根据其他两列的条件创建新列
- c++ - 暂停和恢复线程功能,将线程返回池