Boost logo

Boost Users :

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

Boost-users list run by williamkempf at, kalb at, bjorn.karlsson at, gregod at, wekempf at