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

Cedric, That was the method I originally cited. I'm not sure I understand though, I am not constructing a graph, I am given a graph object as input, and I need to take it's subgraph. What are you suggesting I try to be able to use the create_subgraph() method without copying the entire graph? -rhl On Wed, Dec 29, 2010 at 2:08 PM, Cedric Laczny wrote:

On Wednesday, 29. December 2010 19:26:45 Ryan Lewis wrote:

...

Cedric, is: subgraph< adjacency_list< .... > > bigG(origG)

not a copy construction of bigG from origG ? is that not a copy of the original graph somehow? I'm not sure I follow.

Good point. Actually, that idea of mine seems not to work. Please see the following.

I tried the following code: #include #include <iostream> #include #include #include

int main(int,char*[]) {  using namespace boost;  typedef adjacency_list_traits Traits;  typedef adjacency_list, property > Graph;  typedef subgraph< adjacency_list, property > > SubGraph;

 const int N = 6;

 Graph G(N);

 SubGraph G0(G);

 return 0; }

and I get error-messages that seem to support that subgraph<> works differently from filtered_graph. This means that simply providing an adjacency_list as the argument for the constructor of a subgraph does not work that easily (boost-1.42). I had hoped that subgraph< ... > bigG(origG) would behave similar to filtered_graph< > fg(origG, keep_all(), keep_all() ) and would simply wrap the underlying graph without copying it in any way. Unfortunately, this seems not to be the case. (Also see the member functions of subgraph- class) Have a look at: " template <typename VertexIterator> subgraph<Graph>& create_subgraph(VertexIterator first, VertexIterator last)

Creates a subgraph object with the specified vertex set. The edges of the subgraph are induced by the vertex set. That is, every edge in the parent graph (which is this graph) that connects two vertices in the subgraph will be added to the subgraph. " That seems promising to me.... Although, together with the ideas from above, this would only work if your original graph was already a subgraph. So to use this, instead of adding the vertices and edges to adjacency_list<>, you would need to add them to subgraph< adjacency_list<> >... That seems feasible to me.

Is there something talking against using this for your case?

Best,

Cedric

...

-rhl

On Wed, Dec 29, 2010 at 10:14 AM, Cedric Laczny

wrote:

...

...

On Wednesday, 29. December 2010 15:52:08 Ryan Lewis wrote:

...

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?

Well, of course you could do that. Who should tell you not to do so ;) Just joking. Looking a little bit closer on the documentation, it might actually be possible without duplicating the whole graph... At least for filtered_graph, AFAIK, this only wraps around the original adjacency_list and does not duplicate the whole graph. So it might very well be also the case for subgraph< adjacency_list >. This would at least sound logical to me. You could then simply create a subgraph out of the "bigger" subgraph just as illustrated in the documentation... This means, create a graph (as usual) as an adjacency_list (not sure if this will work with adjacency_matrix, so let's keep it simple for the moment :), let's call it "origG", create a subgraph out of that, basically by calling "subgraph< adjacency_list< .... > > bigG(origG)" and "subgraph< adjacency_list< .... > >& subG = bigG.create_subgraph()". Please not the reference for subG. Does this suit your needs better? Any other questions?

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

_______________________________________________ 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

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