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 09:52:08

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?

-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
>