Propagate values within a connected component using BFSVisitor? (Boost, C++)?

Question

I am constructing a boost graph. For every connected component in the graph, I would like to propagate a unique ID value for every vertex in that connected component. I am wondering if there is a way to do this using Boost's BFSVisitor Concept?

I am guessing this can be done using the examine_edge function (http://www.boost.org/doc/libs/1_55_0/libs/graph/doc/BFSVisitor.html), but I am having a hard time figuring out implementing a class like that. Any insights/links to examples would greatly help!

Answer 1

It sounds like you just want to implement a custom BFS visitor. This has been answered here.

Specifically in your discover_vertex method. You could just use:

void discover_vertex(const graph_t::vertex_descriptor &s, const graph_t &g) const {
  std::cout << "Discover: " << g[s] << std::endl;
  g[s].component_id = myNewId;
}

Or you can use a property map.

put(component_id,s,myNewId);

provided you have that as a vertex property. You could also add a variable to your BFS visitor constructor that is the new ID you want your vertices to have.

Here is an example custom DFS passing a variable to the constructor. It is the same principle as BFS.