使用 BFS 在 Boost BGL 图中查找所有可达的顶点
Find all reachable vertices in a Boost BGL graph using BFS
我构建了一个boost BGL图:
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;
并且我正在尝试查找(收集)从某个起点(顶点)可到达的所有顶点(按距离排序)。这意味着我想创建一个列表,其中包含从某个起始顶点可到达的所有顶点,其中 "nearer" 顶点较早地存储在 list/vector 中。因此我(认为我)需要BFS。
不幸的是,我没有找到如何在没有编译错误的情况下做到这一点:
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>>>>'
我的问题:
- 任何人都可以阐明我的错误吗?或者指向一个
例如?
- 是否有更好的(在效率方面)或不同的方法来实现该目标?
(我想先使用 "connected_components"...但它使用的 DFS 无法满足我的 distance/sorting 标准)。
文档说 Buffer 需要是 vertex_descriptors
的队列。您不小心声明它具有 vertex_t
(顶点 属性 束)作为值类型。
修复它:
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);
}
我构建了一个boost BGL图:
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;
并且我正在尝试查找(收集)从某个起点(顶点)可到达的所有顶点(按距离排序)。这意味着我想创建一个列表,其中包含从某个起始顶点可到达的所有顶点,其中 "nearer" 顶点较早地存储在 list/vector 中。因此我(认为我)需要BFS。
不幸的是,我没有找到如何在没有编译错误的情况下做到这一点:
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>>>>'
我的问题:
- 任何人都可以阐明我的错误吗?或者指向一个 例如?
- 是否有更好的(在效率方面)或不同的方法来实现该目标?
(我想先使用 "connected_components"...但它使用的 DFS 无法满足我的 distance/sorting 标准)。
文档说 Buffer 需要是 vertex_descriptors
的队列。您不小心声明它具有 vertex_t
(顶点 属性 束)作为值类型。
修复它:
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);
}