Re: [boost] BGL: Graph edges with greater than 2 vertices

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/ 
AlgDesignManual/BOOK/BOOK3/NODE132.HTM

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
asutton_at_[hidden]