Re: [Boost-users] BGL - accessing component subgraphs.

Subject: Re: [Boost-users] BGL - accessing component subgraphs.
From: Jeremiah Willcock (jewillco_at_[hidden])
Date: 2010-07-15 13:20:41

On Thu, 15 Jul 2010, Adam Spargo wrote:

>> There is a subgraph class in BGL, and also filtered_graph.  Are the 
>> subgraphs you're working with induced subgraphs (i.e., you do not 
>> selectively remove edges other than by filtering out their endpoints)? The 
>> subgraph class seems to make the subgraphs look more like normal graphs, 
>> while filtered_graph is probably much simpler (it doesn't update 
>> num_vertices() to match the subgraph size, for example).  If you're passing 
>> in something like the connected components of a graph individually, that is 
>> an induced subgraph and so either of those classes will work directly.
>
> Thanks, I think that it is filtered_graph that I want as the vertex indices 
> are meaningful to me. I've adapted the filtered_graph example to do what I 
> want on a small graph, code attached. Just a couple questions - is finding 
> the components, then copying into a property map the most efficient method, 
> could I have the component algorithm populate the property map directly.

I don't see why you can't just pass get(vertex_component, g) as the 
component map in connected_components(), rather than using an 
iterator_property_map.  That would accomplish your goal.  In terms of the 
vertex filter, I think you are doing it the right way.  I would have 
thought that there would be a component filter in BGL, but I could not 
find one.  There is a property_map_filter in filtered_graph.hpp, but that 
does not check an integer value, only a bool.

> Second, I could only get this working by adding an edge filter AND a vertex 
> filter, but really I only need a vertex filter, how to pass an 'empty' 
> function object to the constructor?

Look at boost::keep_all (in filtered_graph.hpp); that can be used to keep 
all of a certain kind of entity.

-- Jeremiah Willcock