Re: [boost] Re: Hypergraphs and the BGL

From: Chris Russell (cdr_at_[hidden])
Date: 2002-04-26 11:44:27

Thanks for the reply Jeremy and thanks for the graphnet mailing list
reference. This is helpful.. I am going to be giving this some more thought
and writing up some notes over the next several weeks.

It would be useful to be able to code hypergraph algorithms generically and
extend them through something similar to BGL's notion of the algorithm
visitor. What would such a thing be? Could a generic hypergraph algorithm
visitor be modeled as a graph of graph algorithm visitors do you think you
think? Here a generic hypergraph algorithm would dispatch to a specific
graph algorithm visitor by examining the hypervisitor's graph and selecting
the right dimension? I'm just not sure yet.

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).

What's this? I'm not entirely sure I've got it right, but to me this sounds
like the basis of a meta-type library - something that is capable of
generically representing patterns. Suppose I had a meta-type library modeled
as a hypergraph.

Computer: Here are my known system inputs and here is a collection of my
required outputs. I'm way over my head here but it seems reasonable to think
that a set of zero or more specific hypergraphs could then be deduced from
the hyper-hypergraph (the meta-type library) that each model a valid
interconnection of plugins to realize the transform from the know set of
system inputs to the required set of system output. MapQuest driving
directions for software if you will.

You guys might all be laughing at this point but it seems defensibly
deductive at least for hardware circuits and not much of a stretch for
software if you think of an algorithm as a chip, and a pattern as a little
circuit. My brain however starts to cook when I consider that at an even
more general level of abstraction, this hypergraph to hypergraph
transformation system starts to look and feel a little like protein
sequencing DNA.

Discounting this last point as wild speculation, I'd be very interested in
talking about this subject further as it seems as though building such a
system would solve many very fundamental problems.

Thanks for holding your laughter until the end.

- Regards
Chris Russell

----- Original Message -----
From: "Jeremy Siek" <jsiek_at_[hidden]>
To: <boost_at_[hidden]>
Sent: Friday, April 26, 2002 9:33 AM
Subject: [boost] Re: Hypergraphs and the BGL

> Hi Chris,
>
> It would not be easy to represent a hypergraph with existing BGL classes
> or interfaces. If you search in the boost mailing list archives you will
> find some earlier discussions about hypergraphs. There was someone
> interested
> in adding hypergraph support to the BGL, but that work was not finished.
> The interface I suggested for hypergraphs would be that a hypergraph would
> not use the source() and target() functions of the current BGL interface,
> and instead would have an incident_vertices() function that returns an
> iterator range.
>
> Cheers,
> Jeremy