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 15:20:59

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 <cedric.laczny_at_[hidden]> 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 <boost/config.hpp>
> > #include <iostream>
> > #include <boost/graph/subgraph.hpp>
> > #include <boost/graph/adjacency_list.hpp>
> > #include <boost/graph/graph_utility.hpp>
> > 
> > int main(int,char*[])
> > {
> >  using namespace boost;
> >  typedef adjacency_list_traits<vecS, vecS, directedS> Traits;
> >  typedef adjacency_list<vecS, vecS, directedS,
> >    property<vertex_color_t, int>, property<edge_index_t, int> > Graph;
> >  typedef subgraph< adjacency_list<vecS, vecS, directedS,
> >    property<vertex_color_t, int>, property<edge_index_t, int> > >
> > 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 <cedric.laczny_at_[hidden]>
> > 
> > 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 <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
> >> > 
> >> > _______________________________________________
> >> > 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
> > 
> > _______________________________________________
> > 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