Boost logo

Boost :

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:

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
the BGL.

Andrew Sutton

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