使用BFS查找Boost BGL图中的所有可达顶点 [英] Find all reachable vertices in a Boost BGL graph using BFS
问题描述
我已经构建了一个增强的BGL图:
I have constructed a boost BGL graph:
using vertex_t = std::variant<node_t, specialNode_t>; // structs
using edge_t = std::variant<TerminalType>; // enum
using Graph_t = boost::adjacency_list<
boost::vecS,
boost::vecS,
boost::undirectedS,
vertex_t,
edge_t>;
Graph_t myGraph;
,并且我试图查找(收集)从某个起点(顶点)可到达的所有顶点(按其距离排序).这意味着我想创建一个从某个起始顶点可到达的所有顶点的列表,其中较近"的顶点存储在列表/向量中的较早位置.因此,我(我想)需要BFS.
and I'm trying to find (collect) all vertices reachable from a certain starting point (vertex) sorted by their distance. That means I'd like to create a list of all vertices reachable from a certain starting vertex where "nearer" vertices are stored earlier in the list/vector. Therefore I (think I) need BFS.
不幸的是,我未能找出如何做到这一点而没有编译错误:
Unfortunately I failed to find out how to do that without compile error:
boost::queue<vertex_t> Q;
boost::default_bfs_visitor vis; // Will do my collecting visitor later...
auto indexmap = boost::get(boost::vertex_index, myGraph);
auto colormap = boost::make_vector_property_map<boost::default_color_type>(indexmap);
boost::breadth_first_visit(myGraph, start, std::ref(Q), vis, colormap);
这会导致以下错误:
Error C2039 'push': is not a member of 'std::reference_wrapper<boost::queue<ListSim::vertex_t,std::deque<_Tp,std::allocator<_Ty>>>>'
Error C2039 'empty': is not a member of 'std::reference_wrapper<boost::queue<ListSim::vertex_t,std::deque<_Tp,std::allocator<_Ty>>>>'
Error C2039 'top': is not a member of 'std::reference_wrapper<boost::queue<ListSim::vertex_t,std::deque<_Tp,std::allocator<_Ty>>>>'
Error C2039 'pop': is not a member of 'std::reference_wrapper<boost::queue<ListSim::vertex_t,std::deque<_Tp,std::allocator<_Ty>>>>'
Error C2039 'push': is not a member of 'std::reference_wrapper<boost::queue<ListSim::vertex_t,std::deque<_Tp,std::allocator<_Ty>>>>'
我的问题:
- 有人能阐明我的错误吗?或者也许是指向 例子吗?
- 是否可能有更好的(就效率而言)或不同的方法来实现该目标?
- Can anyone shed some light on my mistake? Or maybe a pointer to an example?
- Is there possibly a better (in terms of efficiency) or different approach to reach that goal?
(我虽然首先要使用"connected_components" ...但是它使用的DFS无法满足我的距离/排序标准).
(I though about using "connected_components" first... but it uses DFS which cannot fulfill the distance/sorting criteria I have).
推荐答案
文档说Buffer需要是vertex_descriptors
的队列.您不小心声明了它具有vertex_t
(顶点属性束)作为值类型.
The docs say that the Buffer needs to be a queue of vertex_descriptors
. You accidentally declared it to have vertex_t
(the vertex property bundle) as the value type.
解决此问题:
using vertex_descriptor = boost::graph_traits<Graph_t>::vertex_descriptor;
boost::queue<vertex_descriptor> Q;
它会编译:
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/breadth_first_search.hpp>
#include <variant>
#include <queue>
struct node_t {
};
struct specialNode_t {
};
enum class TerminalType {
};
using vertex_t = std::variant<node_t, specialNode_t>; // structs
using edge_t = std::variant<TerminalType>; // enum
using Graph_t = boost::adjacency_list<boost::vecS, boost::vecS, boost::undirectedS, vertex_t, edge_t>;
int main() {
Graph_t myGraph(5);
boost::default_bfs_visitor vis; // Will do my collecting visitor later...
auto indexmap = boost::get(boost::vertex_index, myGraph);
auto colormap = boost::make_vector_property_map<boost::default_color_type>(indexmap);
using vertex_descriptor = boost::graph_traits<Graph_t>::vertex_descriptor;
boost::queue<vertex_descriptor> Q;
boost::breadth_first_visit(myGraph, 0, Q, vis, colormap);
}
这篇关于使用BFS查找Boost BGL图中的所有可达顶点的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!