0

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!

mskb
  • 341
  • 3
  • 12
  • 1
    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()`](http://www.boost.org/doc/libs/1_55_0/libs/graph/doc/connected_components.html). It's second argument is a writable property map, where integer labels will be written. – taketwo Aug 02 '14 at 11:13
  • "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 Aug 02 '14 at 12:39
  • @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 Aug 02 '14 at 13:54
  • @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 Aug 02 '14 at 13:57
  • 1
    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](http://www.boost.org/doc/libs/1_55_0/libs/graph/doc/biconnected_components.html). By definition, removing them increases the number of components. – pbible Aug 03 '14 at 04:24

1 Answers1

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.

Community
  • 1
  • 1
pbible
  • 1,259
  • 1
  • 18
  • 34
  • Hey, 1. how do you pass in the `myNewId` to the `discover_vertex` function? and 2. with the property map idea, did you mean to say `put(s, component_id, myNewId)` (there can be many vertices with the same id). – mskb Aug 05 '14 at 14:14
  • 1) Just like any class, make a constructor with a private variable. All the vertices visited will need the same component id right?. 2) I'm looking at [here](http://www.boost.org/doc/libs/1_55_0/libs/graph/doc/using_property_maps.html). They have the first argument the property map. So it inserts myNewId into the map component_id, using s as a key. – pbible Aug 05 '14 at 17:57