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 15:33:52

I do mean adjacency list, and I agree this should be documented a lot better.

I'm not sure how the internals of adjacency_list<..> work, but I
fundamentally don't understand why a subgraph can't be a method built
on top of a simple adjacency list, it may be less efficient than
something typed as a 'subgraph' capable graph, but I don't see why a
graph shouldn't have one of it's fundamental operations work on it.

I will look into forcing our graph types to be subgraph < Graph >
types. What is the right way to 'raise' this question to an
appropriate developer?

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