
Boost : 
From: Gordon Woodhull (gordon_at_[hidden])
Date: 20080706 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
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk