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

Subject: Re: [Boost-users] taking the subgraph of a boost graph
From: Ryan Lewis (me_at_[hidden])
Date: 2010-12-29 14:21:51

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