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

Subject: Re: [Boost-users] taking the subgraph of a boost graph
From: Jeremiah Willcock (jewillco_at_[hidden])
Date: 2010-12-29 18:21:04

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