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
>>>But let me throw in the other twist: these independent graphs
>>>are actually filtered_graphs.
>> 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 acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk