How to traverse graph in boost use BFS

boost, boost-graph, breadth-first-search, c++

Solution

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));

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));

You are already using an index map in your uint32_t bundled property. You can use `get(boost::vertex_bundle, graph)` to access it.

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.

Full code:

#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;
}

Problem

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; } ``` How to visit the graph using `bfs_visitor`? 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.

Original source

Related problems