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

From: Gordon Woodhull (gordon_at_[hidden])
Date: 2008-07-04 14:13:22

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