taking the subgraph of a boost graph

Ryan Lewis

29 Dec 2010 29 Dec '10

3:19 a.m.

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. Thanks, -rhl

Show replies by date

Cedric Laczny

29 Dec 29 Dec

11:36 a.m.

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

Ryan Lewis

2:52 p.m.

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

Cedric Laczny

3:14 p.m.

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

Ryan Lewis

6:26 p.m.

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

Cedric Laczny

7:08 p.m.

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

Ryan Lewis

7:21 p.m.

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

Cedric Laczny

8:20 p.m.

On Wednesday, 29. December 2010 20:21:51 Ryan Lewis wrote:

...

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?

If you are given a graph-object (do you mean an adjacency_list - object?) and need to take it's subgraph, I don't see an easy way that will not involve copying. Also, I can not think of how this should easily be done, when using e.g. adjacency_list. After all, the underyling concept must provide the necessary mechanisms for such tasks and AFAIK, adjacency_list (or adjacency_matrix) do not provide such things. That's what subgraph< adjacency_list< > > is for. Of course I might miss some things that the developers might know. If so, I would like to have that information integrated into the corresponding documentation ;) Is there perhaps a way to directly provide a subgraph< adjacency_list <> >- object as input? After all, the interface seems pretty similar to the "pure" adjacency_list interface... Because otherwise, as above, I see no way of getting around the copying unfortunately. Maybe providing some example code (at best a short working example, except for the subgraph part of course) could help clarify your situation further to the list (and me :). Best, Cedric

...

-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

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

Jeremiah Willcock

11:21 p.m.

On Wed, 29 Dec 2010, 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...

I believe subgraph is likely to keep a copy, and it is fairly complicated because it handles a whole tree of subgraphs. I think what you want is filtered_graph (which does not copy the graph), and using (without copying) that filtered_graph. That would mean that your algorithm would need to be a template since its input won't be an adjacency_list anymore.

...

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?

I'd do roughly the same idea but with filtered_graph. There is special support in there for induced subgraphs (converting a filter on vertices to a filter on edges). -- Jeremiah Willcock

Ryan Lewis

8:33 p.m.

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

Cedric Laczny

9:48 p.m.

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

Jeremiah Willcock

11:23 p.m.

On Wed, 29 Dec 2010, 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.

What would a built-in subgraph capability do? If you want it to produce an adjacency_list without copying the original graph, it would need to wrap all of the iteration functions (like filtered_graph does), leading to a slowdown for graphs whose subgraphs aren't used.

...

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?

Boost-users works for that. -- Jeremiah Willcock

Ryan Lewis

11:52 p.m.

an interface called subgraph(Graph g, Graph s, vertexiterator begin, vertexiterator end), doing the obvious thing. I don't see why that needs to be hard. -rhl On Wed, Dec 29, 2010 at 6:23 PM, Jeremiah Willcock wrote:

...

On Wed, 29 Dec 2010, 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.

What would a built-in subgraph capability do? If you want it to produce an adjacency_list without copying the original graph, it would need to wrap all of the iteration functions (like filtered_graph does), leading to a slowdown for graphs whose subgraphs aren't used.

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

Boost-users works for that.

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

Cedric Laczny

30 Dec 30 Dec

7:36 a.m.

On Thursday, 30. December 2010 00:52:04 Ryan Lewis wrote:

...

an interface called subgraph(Graph g, Graph s, vertexiterator begin, vertexiterator end), doing the obvious thing.

Referring and agreeing to the answer from Jeremiah Willcock about filtered_graph, this might actually do this obvious thing. After all, you have only vaguely stated your requirements and still not included an example. You could create your subgraph like so: "filtered_graph< adjacency_list< ... >, EdgePredicate, VertexPredicate > subgraph( origG, edge_pred, vertex_pred)" by simply defining appropriate predicates. It might even be enough to specify a vertex-predicate in order to select the vertices you otherwise specify by the VertexIterator-range, like so: filtered_graph< adjacency_list< ... >, keep_all, VertexPredicate > subgraph( origG, keep_all(), vertex_pred) Also, you would not have to take care of the edges, because, unless a separate edge-predicate is provided, only those edges will be visible where both of the incident vertices are visible. The filtered_graph interface does only introduce little overhead and is also fast for simple predicates. Of course, if the predicate is complex and perhaps needs a lot of interaction with the internals of the graph, it will be slow. But this is not due to an inefficiency of the interface but the design of the predicate. I experienced dramatic differences, e.g. when retrieving properties from the graph each time instead of providing a property_map directly.

...

I don't see why that needs to be hard.

If the functionality of filtered_graph does exactly that for you, you are right. Please let me know if this actually does not suit your needs.

...

-rhl

Best, Cedric

...

On Wed, Dec 29, 2010 at 6:23 PM, Jeremiah Willcock wrote:

...
On Wed, 29 Dec 2010, 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.

What would a built-in subgraph capability do? If you want it to produce an adjacency_list without copying the original graph, it would need to wrap all of the iteration functions (like filtered_graph does), leading to a slowdown for graphs whose subgraphs aren't used.

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

Boost-users works for that.

-- Jeremiah Willcock _______________________________________________ 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

Ryan Lewis

2:58 p.m.

Ah, yes. This is fine. Although, I still maintain a simple function with some type-dispatching should exist. -rhl On Thu, Dec 30, 2010 at 2:36 AM, Cedric Laczny wrote:

...

On Thursday, 30. December 2010 00:52:04 Ryan Lewis wrote:

...
an interface called subgraph(Graph g, Graph s, vertexiterator begin, vertexiterator end), doing the obvious thing.

Referring and agreeing to the answer from Jeremiah Willcock about filtered_graph, this might actually do this obvious thing. After all, you have only vaguely stated your requirements and still not included an example. You could create your subgraph like so: "filtered_graph< adjacency_list< ... >, EdgePredicate, VertexPredicate > subgraph( origG, edge_pred, vertex_pred)" by simply defining appropriate predicates. It might even be enough to specify a vertex-predicate in order to select the vertices you otherwise specify by the VertexIterator-range, like so: filtered_graph< adjacency_list< ... >, keep_all, VertexPredicate > subgraph( origG, keep_all(), vertex_pred) Also, you would not have to take care of the edges, because, unless a separate edge-predicate is provided, only those edges will be visible where both of the incident vertices are visible.

The filtered_graph interface does only introduce little overhead and is also fast for simple predicates. Of course, if the predicate is complex and perhaps needs a lot of interaction with the internals of the graph, it will be slow. But this is not due to an inefficiency of the interface but the design of the predicate. I experienced dramatic differences, e.g. when retrieving properties from the graph each time instead of providing a property_map directly.

...
I don't see why that needs to be hard.

If the functionality of filtered_graph does exactly that for you, you are right. Please let me know if this actually does not suit your needs.

...
-rhl

Best,

Cedric

...
On Wed, Dec 29, 2010 at 6:23 PM, Jeremiah Willcock wrote:

...
On Wed, 29 Dec 2010, 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.

What would a built-in subgraph capability do? If you want it to produce an adjacency_list without copying the original graph, it would need to wrap all of the iteration functions (like filtered_graph does), leading to a slowdown for graphs whose subgraphs aren't used.

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

Boost-users works for that.

-- Jeremiah Willcock _______________________________________________ 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

Michael Caisse

5:52 p.m.

On 12/30/2010 06:58 AM, Ryan Lewis wrote:

...

Ah, yes. This is fine. Although, I still maintain a simple function with some type-dispatching should exist.

-rhl

Hi Ryan - Please don't top post. It makes following and interacting with the discussion difficult: http://www.boost.org/community/policy.html#quoting -- Michael Caisse Object Modeling Designs www.objectmodelingdesigns.com

5064

Age (days ago)

5065

Last active (days ago)

List overview

Download

15 comments

4 participants

participants (4)

Cedric Laczny
Jeremiah Willcock
Michael Caisse
Ryan Lewis