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 14:08:48

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