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

Subject: Re: [Boost-users] taking the subgraph of a boost graph
From: Cedric Laczny (cedric.laczny_at_[hidden])
Date: 2010-12-29 10:14:06

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 <cedric.laczny_at_[hidden]> 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_at_[hidden]
> >> http://lists.boost.org/mailman/listinfo.cgi/boost-users
> > 
> > Best,
> > 
> > Cedric
> > _______________________________________________
> > Boost-users mailing list
> > Boost-users_at_[hidden]
> > http://lists.boost.org/mailman/listinfo.cgi/boost-users
> 
> _______________________________________________
> Boost-users mailing list
> Boost-users_at_[hidden]
> http://lists.boost.org/mailman/listinfo.cgi/boost-users