我在编译一个非常简单的图形的 BFS 时遇到问题.无论我做什么，我都会收到有关不匹配方法调用的各种编译器消息(我尝试过 boost::visitor 并扩展 boost::default_bfs_visitor 等)
I have problems getting to compile the BFS of a very simple graph. Whatever I do I get various compiler messages about unmatched method calls (I've tried boost::visitor and extending boost::default_bfs_visitor etc.)
#include <stdint.h>
#include <iostream>
#include <vector>
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/breadth_first_search.hpp>
int main() {
typedef boost::adjacency_list<boost::vecS, boost::hash_setS, boost::undirectedS, uint32_t, uint32_t, boost::no_property> graph_t;
graph_t graph(4);
graph_t::vertex_descriptor a = boost::vertex(0, graph);
graph_t::vertex_descriptor b = boost::vertex(1, graph);
graph_t::vertex_descriptor c = boost::vertex(2, graph);
graph_t::vertex_descriptor d = boost::vertex(3, graph);
graph[a] = 0;
graph[b] = 1;
graph[c] = 2;
graph[d] = 3;
std::pair<graph_t::edge_descriptor, bool> result = boost::add_edge(a, b, 0, graph);
result = boost::add_edge(a, c, 1, graph);
result = boost::add_edge(c, b, 2, graph);
class {
public:
void initialize_vertex(const graph_t::vertex_descriptor &s, graph_t &g) {
std::cout << "Initialize: " << g[s] << std::endl;
}
void discover_vertex(const graph_t::vertex_descriptor &s, graph_t &g) {
std::cout << "Discover: " << g[s] << std::endl;
}
void examine_vertex(const graph_t::vertex_descriptor &s, graph_t &g) {
std::cout << "Examine vertex: " << g[s] << std::endl;
}
void examine_edge(const graph_t::edge_descriptor &e, graph_t &g) {
std::cout << "Examine edge: " << g[e] << std::endl;
}
void tree_edge(const graph_t::edge_descriptor &e, graph_t &g) {
std::cout << "Tree edge: " << g[e] << std::endl;
}
void non_tree_edge(const graph_t::edge_descriptor &e, graph_t &g) {
std::cout << "Non-Tree edge: " << g[e] << std::endl;
}
void gray_target(const graph_t::edge_descriptor &e, graph_t &g) {
std::cout << "Gray target: " << g[e] << std::endl;
}
void black_target(const graph_t::edge_descriptor &e, graph_t &g) {
std::cout << "Black target: " << g[e] << std::endl;
}
void finish_vertex(const graph_t::vertex_descriptor &s, graph_t &g) {
std::cout << "Finish vertex: " << g[s] << std::endl;
}
} bfs_visitor;
boost::breadth_first_search(graph, a, bfs_visitor);
return 0;
}
如何使用bfs_visitor访问图表?
附注.我看过并编译过 如何创建 C++ Boost 无向图并以深度优先搜索 (DFS) 顺序遍历它?" 但它没有帮助.
PS. I've seen and compiled "How to create a C++ Boost undirected graph and traverse it in depth first search (DFS) order?" but it didn't help.
可以查看 此处 breadth_first_search 的重载列表.如果您不想指定每个需要使用的参数，请使用命名参数版本.它看起来像这样:
You can see here a list of the overloads of breadth_first_search. If you don't want to specify every one of the parameters you need to use the named-parameter version. It would look like this:
breadth_first_search(graph, a, boost::visitor(bfs_visitor));
如果您在图形定义中使用 vecS 作为 VertexList 存储，或者如果您构建并初始化了一个内部 vertex_index 属性映射，这将正常工作.由于您使用的是 hash_setS，您需要将调用更改为:
This would work as is if you had used vecS as your VertexList storage in your graph definition or if you had constructed and initialized an internal vertex_index property map. Since you are using hash_setS you need to change the invocation to:
breath_first_search(graph, a, boost::visitor(bfs_visitor).vertex_index_map(my_index_map));
您已经在 uint32_t 捆绑属性中使用了索引映射.您可以使用 get(boost::vertex_bundle, graph) 来访问它.
You are already using an index map in your uint32_t bundled property. You can use get(boost::vertex_bundle, graph) to access it.
您的访客也有问题.你应该从 boost::default_bfs_visitor 派生它，并且你的成员函数的 graph_t 参数需要是 const 限定的.
There was also a problem with your visitor. You should derive it from boost::default_bfs_visitor and the graph_t parameter of your member functions needs to be const qualified.
完整代码:
#include <stdint.h>
#include <iostream>
#include <vector>
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/breadth_first_search.hpp>
typedef boost::adjacency_list<boost::vecS, boost::hash_setS, boost::undirectedS, uint32_t, uint32_t, boost::no_property> graph_t;
struct my_visitor : boost::default_bfs_visitor{
void initialize_vertex(const graph_t::vertex_descriptor &s, const graph_t &g) const {
std::cout << "Initialize: " << g[s] << std::endl;
}
void discover_vertex(const graph_t::vertex_descriptor &s, const graph_t &g) const {
std::cout << "Discover: " << g[s] << std::endl;
}
void examine_vertex(const graph_t::vertex_descriptor &s, const graph_t &g) const {
std::cout << "Examine vertex: " << g[s] << std::endl;
}
void examine_edge(const graph_t::edge_descriptor &e, const graph_t &g) const {
std::cout << "Examine edge: " << g[e] << std::endl;
}
void tree_edge(const graph_t::edge_descriptor &e, const graph_t &g) const {
std::cout << "Tree edge: " << g[e] << std::endl;
}
void non_tree_edge(const graph_t::edge_descriptor &e, const graph_t &g) const {
std::cout << "Non-Tree edge: " << g[e] << std::endl;
}
void gray_target(const graph_t::edge_descriptor &e, const graph_t &g) const {
std::cout << "Gray target: " << g[e] << std::endl;
}
void black_target(const graph_t::edge_descriptor &e, const graph_t &g) const {
std::cout << "Black target: " << g[e] << std::endl;
}
void finish_vertex(const graph_t::vertex_descriptor &s, const graph_t &g) const {
std::cout << "Finish vertex: " << g[s] << std::endl;
}
};
int main() {
graph_t graph(4);
graph_t::vertex_descriptor a = boost::vertex(0, graph);
graph_t::vertex_descriptor b = boost::vertex(1, graph);
graph_t::vertex_descriptor c = boost::vertex(2, graph);
graph_t::vertex_descriptor d = boost::vertex(3, graph);
graph[a] = 0;
graph[b] = 1;
graph[c] = 2;
graph[d] = 3;
std::pair<graph_t::edge_descriptor, bool> result = boost::add_edge(a, b, 0, graph);
result = boost::add_edge(a, c, 1, graph);
result = boost::add_edge(c, b, 2, graph);
my_visitor vis;
breadth_first_search(graph, a, boost::visitor(vis).vertex_index_map(get(boost::vertex_bundle,graph)));
return 0;
}
这篇关于如何在boost中遍历图使用BFS的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持跟版网！