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

Subject: Re: [Boost-users] BGL - accessing component subgraphs.
From: Jeremiah Willcock (jewillco_at_[hidden])
Date: 2010-07-16 14:19:09

On Fri, 16 Jul 2010, Adam Spargo wrote:

>> I don't see why you can't just pass get(vertex_component, g) as the 
>> component map in connected_components()
>
> Yes, that works, code attached. I've also changed to using pointers for my 
> graph and filtered graph so that I can use new and delete.

Why do you need to use pointers?  Anyway, you might want to consider 
scoped_ptr or shared_ptr for those to ensure that the graphs are cleaned 
up appropriately when you are done with them.

> In my real code I have a StringGraph class with Graph and FilteredGraph 
> member pointers. I'm assuming that I should free any memory associated 
> with FilteredGraph, before I allocate a new one, as I could have many 
> many components.

I doubt it will have much memory associated with it.  The filtered_graph 
class has only three members: a reference to the underlying graph, the 
vertex predicate, and the edge predicate.  If you make your vertex 
predicate refer to an external property map (note that property maps are 
small and cheap to copy too) and use keep_all as the edge predicate, the 
filtered_graph object itself will be tiny and fast to allocate/deallocate.

> Also I will want to deallocate the memory for the whole Graph before the 
> program finishes as I need to use it for something else. So is delete 
> the best way? Does the destructor for Graph/FilteredGraph actually 
> release all the memory? I don't see any other clean-up functions in the 
> documentation.

Yes, the destructors clean everything up.  Be sure to destroy the 
filtered_graph before destroying its underlying graph, but constructing 
them in the necessary order and using local variables or scoped_ptr will 
do that automatically.

>> Look at boost::keep_all (in filtered_graph.hpp); that can be used to keep 
>> all of a certain kind of entity.
>
> It's seems to me that these filters are only actually called when you 
> ask for vertices or edges of the FilteredGraph. That being true I guess 
> I would need both function objects?

You don't need the edge predicate if you're using an induced subgraph 
(which I believe you are).  Filtering the endpoints of an edge to ensure 
that both vertices are present in the filtered graph is done automatically 
no matter what edge predicate you use, so keep_all will work for what you 
want to do.

-- Jeremiah Willcock