Boost logo

Boost :

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
> > you could interconnect these N circuits. This too I believe can be
> > 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:

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