Yes, thanks, I'm trying to implement filtered_graph now, I found it after a little more poking around, seems ideal. I might need some help with my filter function, but I'll try a bit harder first. Adam. -- Dr Adam Spargo High Performance Assembly Group email: aws@sanger.ac.uk Wellcome Trust Sanger Institute Tel: +44 (0)1223 834244 x7728 Hinxton, Cambridge CB10 1SA Fax: +44 (0)1223 494919 On Wed, 14 Jul 2010, Jeremiah Willcock wrote:

On Wed, 14 Jul 2010, Adam Spargo wrote:

...

Any tips on the best way to access a subgraph - ideally without the memory overhead of copying the subgraph to a new object.

I want to pass each component of my graph to an algorithm separately, but in some cases the original graph will only have a single or a few component(s), in other cases there will be many.

Maybe I will do it differently depending on how many components I have.

Any tips welcome.

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.

-- Jeremiah Willcock _______________________________________________ Boost-users mailing list Boost-users@lists.boost.org http://lists.boost.org/mailman/listinfo.cgi/boost-users

-- The Wellcome Trust Sanger Institute is operated by Genome Research Limited, a charity registered in England with number 1021457 and a company registered in England with number 2742969, whose registered office is 215 Euston Road, London, NW1 2BE.

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

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