Re: [boost] Re: Hypergraphs and the BGL

From: Chris Russell (cdr_at_[hidden])
Date: 2002-04-26 16:55:52

Thanks for the reply David. Everything you say makes sense to me. You bring
up some points about the semantics of my hyperedge = graph adaptor assertion
that I'm going to have to think about some more. There's some sensible
relationship buried in there somewhere. Off to read and think about this
some more. Thanks for the input.

- Chris

----- Original Message -----
From: "David A. Greene" <greened_at_[hidden]>
To: <boost_at_[hidden]>
Sent: Friday, April 26, 2002 4:03 PM
Subject: Re: [boost] Re: Hypergraphs and the BGL

> 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
>
> _______________________________________________
> Unsubscribe & other changes:
http://lists.boost.org/mailman/listinfo.cgi/boost
>