Boost logo

Boost :

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.


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

Boost list run by bdawes at, gregod at, cpdaniel at, john at