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!

If you do not care about particular ID values, just the fact that they should be unique for each component, you may use connected_components(). It's second argument is a writable property map, where integer labels will be written. — taketwo
"propagate a unique ID value for every vertex in that connected component." Please describe what is meant by this - a simple example of what you expect would be good. — ravenspoint
@ravenspoint taketwo's interpretation is basically what I was going for. Every connected component has to have a unique ID value. Every vertex in each component has to have the ID value stored. Thanks! — mskb
@taketwo thanks! The reason I was wondering about the BFSVisitor class is because of the following: I might be adding and removing edges, and I would be interested in seeing if there are new components emerging; a naive implication of this would be discovery of new components through BFS search from the source/target vertices of the edge I had added/removed. So I felt BFSVisitor would probably be more efficient than doing a connected_components search for the entire graph? — mskb
If you use BFS you should use discover_vertex. If you use examine_edge you should use the target of the edge to get a vertex. Also take a look at articulation points. By definition, removing them increases the number of components. — pbible

pbible pbible · Accepted Answer · 2014-08-04T21:13:49

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.

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

1 Answers