如何在命名图上使用 boost 图算法？
我正在尝试编译一个简单的代码示例，该示例使用 BFS 遍历命名图并回答我的上一个问题。
我认为主要问题是为算法提供正确的索引图。
代码（没有命名图特征样板）如下：
Graph g;
// add a few named vertices
auto v1 = add_vertex(1111, g);
auto v2 = add_vertex(2222, g);
auto v3 = add_vertex(3333, g);
// add 2 edges
add_edge(1111, 2222, g);
add_edge(2222, 3333, g);
simple_bfs_visitor bfs_visitor_instance{};
//boost::breadth_first_search(g, v1, boost::visitor(bfs_visitor_instance)); // fails to compile
//boost::breadth_first_search(g, v1, boost::visitor(bfs_visitor_instance).vertex_index_map(boost::get(&Vertex::id, g))); // compiles but fails with exception
有人可以提供一个关于如何在提供的图上调用图算法的示例吗？
我将不胜感激对所涉及概念的解释，因为我无法理解属性映射/索引映射等各种术语如何发挥作用以及它们在使用命名图时有何不同。
这是完整的（不起作用）代码：
struct Vertex
{
size_t id;
std::string other = "default-constructed";
};
// traits
template <> struct boost::graph::internal_vertex_name<Vertex> {
struct type {
using result_type = size_t;
result_type const& operator()(Vertex const& bundle) const {
return bundle.id;
}
};
};
template <> struct boost::graph::internal_vertex_constructor<Vertex> {
struct type {
private:
using extractor = typename internal_vertex_name<Vertex>::type;
using name_t = std::decay_t<typename extractor::result_type>;
public:
using argument_type = name_t;
using result_type = Vertex;
result_type operator()(const name_t& id) const { return { id }; }
};
};
using Graph = boost::adjacency_list<boost::vecS, boost::listS, boost::directedS, Vertex>;
class simple_bfs_visitor : public boost::default_bfs_visitor
{
public:
void discover_vertex(const Graph::vertex_descriptor& v, const Graph& g) const
{
std::cout << "hi from bfs" << '\n';
}
};
void Func()
{
Graph g;
// add a few named vertices
auto v1 = add_vertex(1111, g);
auto v2 = add_vertex(2222, g);
auto v3 = add_vertex(3333, g);
// add 2 edges
add_edge(1111, 2222, g);
add_edge(2222, 3333, g);
simple_bfs_visitor bfs_visitor_instance{};
//boost::breadth_first_search(g, v1, boost::visitor(bfs_visitor_instance)); // fails to compile
//boost::breadth_first_search(g, v1, boost::visitor(bfs_visitor_instance).vertex_index_map(boost::get(&Vertex::id, g))); // fails with exception
}
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（1）
前几天我警告过你：
listS因为 它提供引用/描述符稳定性。然而，这意味着没有隐式的vertex_index_t属性。vecS，那么您将获得与重载中的 id 类型 (size_t) 冲突分辨率检查 3. 下的一些内容
，让我们检查一下
breadth_first_search的文档，是的，它明确指出：所以，不要做你尝试过的事情！这将导致未定义行为。但请继续阅读：
不幸的消息：你所有的问题都被准确地指出了。
好消息：我们有 3 个选项来修复它：
vecS，但避免重载冲突1. 传递您自己的颜色图
您可以查看在文档中查看要求。满足该要求的最简单方法：
现在您可以这样称呼它：
2. 传递您自己的顶点索引
相反，您可以提供一个索引。非常相似：
但是这次您必须确保地图按照预期填充！
我们再次称呼它为：
2b。 Intermezzo
当然，您可以同时提供两者，但这不是必需的。如果您多次调用 BFS 或想要使用自己的数据结构（例如
flat_map > ），这可能是一种优化，这样您就可以避免所有那里的分配）：3. 使用 VecS...
这对描述符稳定性有影响，但至少让我们展示一下。我建议对 id 使用包装类型：
我们需要哈希/相等来进行名称查找，并使用
operator<<来打印图表。当然，实现是微不足道的。有了这个，一切就“正常工作”了，因为
Graph有一个内部隐式vertex_index：以上所有内容的实时列表
Live On Coliru
编译两次，有或没有
USE_VCES定义：编译并运行：
打印
I warned you the other day:
listSbecause it offers reference/descriptor stability. This however implies there is no implicitvertex_index_tproperty.vecS, then you'll have conflict with the id type (size_t) in overload resolutionget(&Vertex::id, g)) it will not go well.Checking Some Things
Under 3., let's check the Documentation for
breadth_first_searchand yes, it explicitly states:So, don't do what you tried! It's going to lead to Undefined Behaviour. But read on:
The sad news: all your issues were exactly called out.
The good news: we have 3 options to fix it:
vecSagain, but avoid the overload conflicts1. Pass Your Own Color Map
You can look at the documentation to see the requirements. The simplest way to satisfy that:
Now you call it:
2. Pass Your Own Vertex Index
Instead you could supply an index. Very similarly:
But this time you have to make sure the map is populated according to expectations!
And we call it again like:
2b. Intermezzo
Of course you could provide both, although that's not required. It might be an optimization if you call BFS a lot of times or want to use your own data structure (like a
flat_map<V, color, small_vector<V, N> >so you can avoid all allocations there):3. Use VecS...
This has implications for descriptor stability, but let's at least show. I'd suggest using a wrapper type for the id:
We need hash/equality for the name lookups and
operator<<for printing the graph. Of course, the implementation is trivial.With that in place, everything "just works" because
Graphhas an internal implicitvertex_index:Live Listing Of All The Above
Live On Coliru
Compiled twice, with or without
USE_VCESdefined:Compile and run:
Prints