Re: [boost] Re: Hypergraphs and the BGL

From: Chris Russell (cdr_at_[hidden])
Date: 2002-04-26 13:56:49

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?

Doug Gregor writes:

> 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?

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

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