Re: [boost] Re: Hypergraphs and the BGL

From: David A. Greene (greened_at_[hidden])
Date: 2002-04-26 12:36:09

Chris Russell wrote:

> For anyone who is interested, hypergraphs are useful for modeling things
> like electrical circuits. Now suppose you had a system that modeled N
> different electrical circuits and additionally modeled all the possible ways
> you could interconnect these N circuits. This too I believe can be described
> by a hypergraph (just add a few more dimensions).

Chris pointed me to this thread (thanks, Chris!).

Over on boost-users I posted a somewhat different set of
requirements I have for the BGL.  I'll not repost the whole
message here but I'll summarize my needs.

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.

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.

Thoughts?

Thanks for a great library!

                         -Dave

-- 
"Some little people have music in them, but Fats, he was all music,
  and you know how big he was."  --  James P. Johnson