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 06:36:02

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