[boost] Re: Hypergraphs and the BGL

From: Hoekstra, Robert J (rjhoeks_at_[hidden])
Date: 2002-04-27 13:08:58

>I'd like to be able to take two independent BGL graphs and combine
>them into one graph such that there is a set of well-defined
>connections (i.e. it is easy for me to know what they should be)
>from one graph to the other.  For me, it's usually just a single
>edge, but the ability to more generally add edges between the
>graphs would be useful -- there are other parts of my application
>that can make use of that.
>David Greene wrote:

>But let me throw in the other twist: these independent graphs
>are actually filtered_graphs.

>In essence, I need the opposite of a subgraph.  It's not
>quite as general as a hypergraph.  In fact it's just a
>regular old graph.

>Right now I just construct a third graph from the two existing
>graphs.  This is expensive both in terms of time and space.
>Since these graphs are often short-lived the time cost is
>especially onerous.  If I could just take two filtered_graphs
>and put a wrapper around them that specifies the extra
>connections, I'd save a lot.

>The major hangup I see right now is the vertex and edge
>indexing.  Since each independent graph has its own mappings
>some extra level of indirection will be needed.  Is this
>cost greater than the overhead of simply constructing a
>new graph?  I suppose it depends on how much indexing is
>done.

I would agree that what you are describing here has little or
no connection to hypergraphs.  Hypergraphs specifically relate
to graphs with hyperedges(edges which can have >2 connections
to vertices).

I disagree when you say this does not relate to subgraphs.  Your
original 2 graphs are exactly that, subgraphs of this 3rd graph.
Your description of what you want is what I would consider
hierarchical graph structure: graphs can be subgraphs of other
graphs.  What are the key problems with using BGL's 'subgraph'
support?  You may have already done this, but I would suggest
examining what you could currently do with subgraphs and edge_lists
and such operations such as unions and intersections, and decide if
there is some limited addition to these capabilities that would
support what you need efficiently.  I can guess it would have to
do with on-the-fly, efficient union/intersection of
graphs/edge_lists/vertices.

BTW, while I think hypergraph support would be great since I do
circuit simulation, it is important to understand that almost
all the algorithms in BGL would be invalid.  Many would be
inappropriate for hypergraphs and others become much more onerous
when generalized to hypergraphs.  My experience has been that
hypergraph support usually results in a related but separate library
for most practical purposes.

Rob Hoekstra

---------------------------------------------
Robert J Hoekstra
Computational Sciences
Sandia National Laboratories
PO Box 5800  MS-0316
Albuquerque, NM  87185-0316
Ph:     [phone]
Fax:   [phone]
Page: [phone]
rjhoeks_at_[hidden]