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 16:48:46

On Wednesday, 29. December 2010 21:33:52 Ryan Lewis wrote:
> 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?
>

Before changing the whole code basis I would suggest to discuss this with the 
developers as you intend to.
A good start for how to the address the question would be to integrate a 
working example reflecting your actual situation (graph-object as 
adjacency_list as input) and then clearly specify what you would like to 
realize (getting a subgraph directly out of an adjacency_list) and what 
restrictions you impose (no copying in memory etc.).
Because subgraph seems to be based on adjacency_list in some way, you might be 
right that there is some way to achieve this.
However, I think that the developers did their homework and if they already 
have created the subgraph-concept, they may have had their reasons to not 
incorporate it directly into the adjacency_list-interface. It is obviously a 
design questions but a design has to be imposed at some point and one must 
take note of it accordingly, thus possibly using subgraph<adjacency_list> 
instead of adjacency_list alone. But then, one could at the same time argue 
that the functionality of filtering the adjacency_list could also be directly 
integrated into adjacency_list-class (instead of a separate class), even 
though the filtered_graph basically serves as a wrapper, whereas subgraph 
really requires an explicit creation of the original graph as a subgraph-
object. I think that a very crucial point here is efficiency (boost?!). After 
all, it's all about the design ;)
Also, it might be that the answer can take a bit as IMHO the developers (at 
least for the BGL) seem to be quite busy at the moment. I'm pretty sure that 
they would have answered on this topic already otherwise. Nevertheless, this 
would be the way to go IMHO to further clarify this.

I hope that you will find a suitable answer and it would be nice to keep me 
informed if you have figured out an elegant solution to this problem.
Thank you.

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