Re: [boost]: Hypergraph

From: Joel Young (jdy_at_[hidden])
Date: 2001-06-21 17:03:09

Ruth,

Ruth Brown said
>> Looking for ideas on how to represent a hypergraph (more than 2
>> vertices per edge) using BGL (and/or other graph template libraries).

Andy Alness said
> Couldn't you keep an external property map containing your own edge
> identity information and just make new edges actually connecting the
> vertices but in the property map u know that the new edges u create are

Another choice would be to have two different kinds of nodes so that
your graph is bipartite:  data nodes and hyper nodes.  Each data node
only connects to hyper nodes and hyper nodes only connect to data nodes.

(edgeset of hyper-node and the hyper-node itself) = hyper-edge.

You could have an additional map (as a graph property) that contains
only the hyper-nodes.

A nicer solution would be to generalize the concept of edge to support
more than two ends.

What kind of algorithms are you thinking of?  Hypergraph Partitioning,
coloring, vertex cover, etc. would be interesting, especially if they
were generic enough to work for the special case where each hyperedge
only has two ends.  Are you looking at constraint satisfaction?

A nice (and expensive) algorithm would take a graph and publish a
hypergraph such that there is one hyperedge per clique.  And of course
the inverse transform.

Joel