splitting a boost graph into connected components

Question

My program starts out by creating a graph (~1K-50K vertices) that usually consists of a few hundred connected components.

The program only needs to be able to manipulate and visualize individual components (using force-directed layout algorithm).

It would be great (but not essential) to have the capability of further splitting each connected component into connected subcomponents (by removing edges or vertices).

So my question is, can I use use subgraph or filtered_graph class templates to achieve the required functionality (maintain a collection of component graphs that can be individually manipulated and possibly further subdivided by removing edges/vertices)? Or is there an another, better approach?

I apologize if this question is too basic. I've just started to learn BGL and not comfortable with this library yet. Thanks in advance!

Answer 1

Use connected_components to assign a unique number to each component, storing it in a property of the nodes. Then you can use that property in the filtered_graph predicate to decide whether a given component belongs to the currently active graph or not. The vertex predicate would be straight-forward, whereas the edge predicate could simply look at either endpoint to make its choice. The number of the subgraph would be stored in the predicate objects themselves.

Whether a different approach would be beter depends on your use case. If the components don't change much, and you have to perform a lot of operations which iterate over all nodes, then having separate graph objects might be better. You could create them as copies of filtered graphs constructed as described above. If the graph gets modified a lot, some approach which will not have to scan the whole graph to update connected components would be useful. If no edges get removed, incremental_components might do the trick.