
Boost : 
From: Chris Russell (cdr_at_[hidden])
Date: 20020426 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 higherorder class. My vague notion of the
hypergraph is as a graph whose vertices represent instances of these
higherorder 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 highorder 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 boostusers 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 welldefined
> 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 shortlived 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
>
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk