From: Andrew Sutton (asutton_at_[hidden])
Date: 2008-07-05 07:05:05
>> Hypergraphs are (still) not supported in the BGL. I think the
>> workarounds tend to vary greatly depending on how you need to use
>> the hypergraph.
> This is one of the generalizations on the graph data structure that
> my Metagraph library is intended to support. I expect some form of
> this library to available later this summer.
> The most common workaround that I see (I work in graph drawing) is
> to model a hyperedge as a "connector" or "flow" node (vertex) with
> no visual representation. The disadvantage of this approach is
> that you'd often want the connector node to have different type /
> different data from regular nodes.
I like the solution given here: http://www2.toki.or.id/book/
It sounds like you might be able to use an adjacency list to build a
bipartite graph, with the "left" half of vertices representing the
vertices of your graph and the "right" half representing the edges.
Edges in the bipartite graph represent vertex/hyperedge incidence.
I think a good generalization of this solution and a couple
hypergraph algorithms would probably make a pretty good addition to
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk