Re: [Boost-Users] BGL: "Supergraphs?"

From: Jeremy Siek (jsiek_at_[hidden])
Date: 2002-04-27 11:10:13

Hi David,

On Fri, 26 Apr 2002, David A. Greene wrote:
greene> I've been learning the BGL and porting some existing code over
greene> to it.  First off, Kudos to Jeremy, Lie-Quan and all the BGL
greene> developers.  This library is great!

You're welcome :)

greene> I find the filtered_graph potentially very useful for my
greene> application except for one case.  In some (not rare)
greene> instances I need to be able to create a filtered_graph
greene> that spans two graphs.  In other words, I have two
greene> separate graphs.  Most of the time the information I need
greene> is entirely contained in one graph so a filtered_graph
greene> works perfectly.  However, sometimes I need to create a
greene> filtered_graph from several separate graphs and link them
greene> together in a well-defined manner (i.e. I easily know where
greene> the edges should go).  I need a "supergraph" that is the
greene> combination of the two filtered graphs.

It seems that the right approach would be to first have something that
"virtually" combines the two graphs, and then simply apply filtered_graph
to the result. However, off the top of my head I don't know of a good way
to "virtually" combine two graphs without lots of memory overhead. I'm
open to ideas :)

greene> Right now the application handles this problem by creating
greene> a new graph from the existing graphs.  But this takes time
greene> and memory.  I'd like to get rid of this overhead if possible,
greene> especially since these are often short-lived graphs.
greene>
greene> The filtered_graph objects would not be induced subgraphs
greene> so a subgraph object wouldn't work (subgraph also doesn't
greene> support something that spans multiple graphs anyway).  What
greene> I need is the opposite of subgraph -- a unified interface
greene> to multiple filtered_graphs.
greene>
greene> This seems very hard to do because each filtered_graph will
greene> have its own vertex and edge index mappings.  An extra level
greene> of indirection would solve the problem but I'm not sure the
greene> overhead would be less than simply creating a new graph.
greene>
greene> Thoughts?  Opinions?
greene>
greene> Thanks again for a great library!
greene>
greene>                                -Dave

----------------------------------------------------------------------
 Jeremy Siek                          http://php.indiana.edu/~jsiek/
 Ph.D. Student, Indiana Univ. B'ton   email: jsiek_at_[hidden]
 C++ Booster (http://www.boost.org)   office phone: [phone]
----------------------------------------------------------------------