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