Re: [Boost-users] taking the subgraph of a boost graph

On Wednesday, 29. December 2010 15:52:08 Ryan Lewis wrote:

Cedric,

Thanks! This however, is completely useless to me. I can't afford to duplicate the entire graph in memory! Is there some other way to achieve this? Maybe I could write to boost-developers for a feature request or something?

Well, of course you could do that. Who should tell you not to do so ;) Just joking. Looking a little bit closer on the documentation, it might actually be possible without duplicating the whole graph... At least for filtered_graph, AFAIK, this only wraps around the original adjacency_list and does not duplicate the whole graph. So it might very well be also the case for subgraph< adjacency_list >. This would at least sound logical to me. You could then simply create a subgraph out of the "bigger" subgraph just as illustrated in the documentation... This means, create a graph (as usual) as an adjacency_list (not sure if this will work with adjacency_matrix, so let's keep it simple for the moment :), let's call it "origG", create a subgraph out of that, basically by calling "subgraph< adjacency_list< .... > > bigG(origG)" and "subgraph< adjacency_list< .... > >& subG = bigG.create_subgraph()". Please not the reference for subG. Does this suit your needs better? Any other questions? Best, Cedric

-rhl

On Wed, Dec 29, 2010 at 6:36 AM, Cedric Laczny wrote:

...

Hi,

On Wednesday, 29. December 2010 04:19:04 Ryan Lewis wrote:

...

Hi,

Lets say your handed an arbitrary boost graph and an iterator to a subset of it's vertices. You want to induce a subgraph of this graph. How do you do this?

I looked at the boost docs and found the Subgraph < Graph > page:

http://www.boost.org/doc/libs/1_36_0/libs/graph/doc/subgraph.html

Indeed there exists a subgraph member function:

subgraph<Graph>& create_subgraph();

However this suggests, as does the example, that you want to take an induced subgraph of a graph whose type is Subgraph < Graph >. However my graph is just of type Graph. What is the right way to deal with this? I've tried asking at #boost, but no one seems to be awake there.

Maybe you could use boost::copy_graph()? At least it works for me when copying a filtered_graph into and adjacency_list. It's a comparable example where you "convert" one graph-type (loosely speaking) into another. Also have a look at the boost example code of subgraph. Basically, I would copy the _whole_ graph into a "subgraph<...> BigG", create a "subgraph<...> subG" from the subgraph BigG (the naming scheme may be a bit awkward at first sight) and then iterate over the vertex-set (probably need to newly create it to match the new vertices) and insert those vertices (and the respective edges) into the subG. AFAIK, copy_graph() only works for complete graphs and not for vertex-subsets, e.g. specified by an iterator_range. AFAIK, a subgraph is either the complete graph or a subgraph relative to a bigger subgraph ( also note local and global vertices), therefor the call for create_subgraph(). Another idea that jumps to my head is to use filtered_graph ( and a filter matching your vertices of interest) on the BigG and copy the resulting filtered_graph into subG, created via create_subgraph().

Hope that helps

...

Thanks,

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

Best,

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

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