On Wed, 29 Dec 2010, Cedric Laczny wrote:
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...
I believe subgraph is likely to keep a copy, and it is fairly complicated because it handles a whole tree of subgraphs. I think what you want is filtered_graph (which does not copy the graph), and using (without copying) that filtered_graph. That would mean that your algorithm would need to be a template since its input won't be an adjacency_list anymore.
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?
I'd do roughly the same idea but with filtered_graph. There is special support in there for induced subgraphs (converting a filter on vertices to a filter on edges). -- Jeremiah Willcock