我在编译一个非常简单的图表的BFS时遇到了问题.无论我做什么,我得到了关于不匹配的方法调用的各种编译器消息(我尝试过boost :: visitor并扩展boost :: default_bfs_visitor等)
#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,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,graph);
result = boost::add_edge(a,c,1,graph);
result = boost::add_edge(c,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访问图表？
PS.我已经看到并编译了“How to create a C++ Boost undirected graph and traverse it in depth first search (DFS) order?”,但它没有帮助.
解决方法
您可以在
here中看到breadth_first_search的重载列表.如果您不想指定每个参数,则需要使用命名参数版本.它看起来像这样：
breadth_first_search(graph,boost::visitor(bfs_visitor));
如果您已在图形定义中使用vecS作为VertexList存储,或者已构建并初始化内部vertex_index属性映射,则此方法可以正常工作.由于您使用的是hash_setS,因此需要将调用更改为：
breath_first_search(graph,boost::visitor(bfs_visitor).vertex_index_map(my_index_map));
您已在uint32_t捆绑属性中使用索引映射.您可以使用get(boost :: vertex_bundle,graph)来访问它.
你的访客也有问题.您应该从boost :: default_bfs_visitor派生它,并且您的成员函数的graph_t参数需要是const限定的.
完整代码：
#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::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);
my_visitor vis;
breadth_first_search(graph,boost::visitor(vis).vertex_index_map(get(boost::vertex_bundle,graph)));
return 0;
}
