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.
P.S. To insert some more keywords into the thread: splayed edges,
split edges, merged edges, tree edges