On Jul 1, 2008, at 3:09 PM, Doug Gregor wrote:

On Jul 1, 2008, at 11:55 AM, Aman Sinha wrote:

...

I am looking to build a graph where an edge can be incident on multiple vertices. I believe this is also called a hypergraph. The boost archives have some discussion of hypergraphs from way back in year 2002. Does anyone know what is the status of that? If is is not supported, is there a reasonable workaround to build such graphs?

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. As for real support for hyperedges, I foresee a few possible implementations, which would be appropriate in different applications: 1. A hyperedge is of unlimited degree, like a node. A graph becomes a set of alternating node and edge objects with the same capabilities but different types. a. directed: it has an unlimited number of in-branches and out- branches (sources, targets) b. undirected: it has unlimited branches (connections) 2. Hyperedge has fixed number of in- or out- branches. E.g. a family tree hyperedge has exactly 2 in-branches and unlimited out-branches 3. There are different types of branches than "in" or "out", e.g. a divider data flow node has numerator, denominator, and output. If these types are known at compile time, and the structure is regular (all edges in the graph are the same kind), this generalization can be modeled very efficiently. Hmm, I just noticed that this example is a node not hyperedge, but they're all the same thing once you start thinking about it. ;-) The Metagraph library purports to implement all of these capabilities and more. However, I must be clear that it remains vaporware at this time. (Almost there, I think...) There is some code in the sandbox which will generate a data structure which does these things, but it doesn't have niceties like coordinating assigning a edge target with adding the edge to the in-edge-list of the target vertex, so I wouldn't recommend trying it yet. I would be very interested to hear about your specific application. Thanks, Gordon P.S. To insert some more keywords into the thread: splayed edges, split edges, merged edges, tree edges

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