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

Subject: Re: [Boost-users] taking the subgraph of a boost graph
From: Ryan Lewis (me_at_[hidden])
Date: 2010-12-29 13:26:45

Cedric,
is:
subgraph< adjacency_list< .... > > bigG(origG)

not a copy construction of bigG from origG ? is that not a copy of the
original graph somehow? I'm not sure I follow.

-rhl

On Wed, Dec 29, 2010 at 10:14 AM, Cedric Laczny <cedric.laczny_at_[hidden]> 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...
> 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
>
> _______________________________________________
> Boost-users mailing list
> Boost-users_at_[hidden]
> http://lists.boost.org/mailman/listinfo.cgi/boost-users
>