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

From: Gordon Woodhull (gordon_at_[hidden])
Date: 2008-07-06 10:51:11

On Jul 5, 2008, at 7:05 AM, Andrew Sutton wrote:

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

Nice, bipartite graph is a better way of saying that the nodes  
alternate between node and hyperedge.

The motivation for the metagraph library is that an application is  
rarely going to turn a hyperedge into a node, so it is a pity to use  
the same type and pay various abstraction penalties (mostly in clarity).

On the other hand, a disjoint subgraph / partitioned graph  
implementation where the different subgraphs had different types (of  
data) would be equivalent to a metagraph, which I'll define in the  
next message.

> I think a good generalization of this solution and a couple  
> hypergraph algorithms would probably make a pretty good addition to  
> the BGL.

Agreed.  There are lots of good ways to solve these problems.

Gordon