Boost logo

Boost Users :

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

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