Re: [boost] Re: Hypergraphs and the BGL

From: David A. Greene (greened_at_[hidden])
Date: 2002-04-26 15:03:13

Chris Russell wrote:
> Cool. I understand what you're trying to do I think. There would seem to be
> a lot problems that reduce into this type of relationship. I find it helpful
> to think about the graph, it's contained data, and the algorithms that
> operate on it as some kind of higher-order class. My vague notion of the
> hypergraph is as a graph whose vertices represent instances of these
> higher-order class constructs (based on BGL based on STL), and whose edges
> represent these pesky relationships that you discuss in the included post.
> Indeed - how to efficiently allocate and deallocate these high-order class
> constructs is what? It's a graph problem. Beyond a certain point of
> complexity you're just spinning your wheels trying to deal with it as
> anything other than this. No?

As I underatand it, a hypergraph has hyperedges that essentially
represent multiple edges.  A hyperedge connects multiple vertices.  I
don't need anything that complex.  I just want regular ol' edges.
Essentially I want to concatenate two graphs with some "glue" edges.

I suppose this could be modeled with a hypergraph where the (single)
hyperedge represents those glue edges.  But I don't have any idea how
shortest path, etc. is run on such a beast.  There is still the
vertex/edge indexing problem to deal with.  The hyperedge adds no
useful information for me because I really don't care what parts
of the final graph came from the independent graphs.  I only care
about paths, etc.

Implementing full hypergraph support seems overkill for my needs.
Plus a (pure) hypergraph shouldn't have to deal with multiple
graphs (i.e. the indexing problem).  A hypergraph is a concept,
while I think what I'm striving for is a model for a graph
concept (the same concept my filtered_graphs model).  In other
words, the BGL already supports what I need to do with my
cobbled_together_graph.  The fact that this model happens to
do some extra bookkeeping to overcome the indexing problem
shouldn't matter.  A hypergraph, on the other hand, requires
new algorithms.

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

>>Doug Gregor:
>> This isn't a twist in the BGL sense. A filtered_graph is just a graph
>> adaptor. It's no different conceptually from any other type of graph.

> To which I respond: You're right Doug. But, consider the design of a system
> that lends itself to being modeled as networks of graphs and graph adaptors.
> Maybe a hypergraph edge is a graph adaptor?

It seems to me that a hyperedge would really require a reworking of
the BGL algorithms.  As Jeremy noted, source() and target() no longer
have a simple meaning in such a situation.  Again, this is overkill
for my needs.

An adaptor can be possibly used to model the hypergraph concept, but
new algorithms are needed to make use of it.

                                       -Dave

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