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

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 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 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@lists.boost.org http://lists.boost.org/mailman/listinfo.cgi/boost-users

Best,

Cedric _______________________________________________ Boost-users mailing list Boost-users@lists.boost.org http://lists.boost.org/mailman/listinfo.cgi/boost-users

_______________________________________________ Boost-users mailing list Boost-users@lists.boost.org http://lists.boost.org/mailman/listinfo.cgi/boost-users