Hypergraphs

[mofeing]

Is there any intention to support hypergraphs? The main deadlock to integrate hypergraphs in Graphs is the assumption that edges point to 2 vertices. Currently is weird to implement a "undirected" HyperEdge type: dst and src have no point there (even in an undirected graph dst and src look weird) because there will be more than 2 vertices.

My proposal is the following:

1. See simple edges as a special case of hyperedges whose cardinality is 2.
2. Stop using dst and src for undirected edges $\rightarrow$ Use vertices(edge) where possible instead.
3. For graph algorithms that need a non-hyper graph view, a hyperedge can be seen as the powerset of cardinality 2 of the connecting vertices (i.e. all vertices in an hyperedge are at distance 1).

If we relax this assumption, open edges could also be supported and implemented as cardinality 1 hyperedges.

[gdalle]

Initially the intention was to leave hypergraphs aside, but your remark about undirected edges got me thinking (see also #16).
A more generic edge formalism might indeed be welcome, and there could be a function other_vertices(e, s) which does basically what dst(e) / src(e) would in an undirected graph.
But then the trouble comes with directedness, do you know how such a formalism would adapt?

[mofeing]

A directed hyperedge $H_D$ contains two sets of vertices: the set of source vertices $S$ and the set of target vertices $T$. $H_D$ can be seen as the collection of all directed edges from $S$ to $T$.

$$ H_D = S \times T $$

A undirected hyperedge $H_U$ contains only the set of connecting vertices $C$. As above, $H_U$ can be seen as a the collection of all undirected edges in $R$, which is equivalent to the powerset $\mathcal{P}$ of $R$ of cardinality 2.

$$ H_U = R \times R = \mathcal{P}_2(R) $$

Remark A undirected hyperedge can be seen as a directed hyperset where $R = S = T$.¹

A possible implementation would be:

struct HyperEdge{T}
    vertices::Set{T}
end

struct HyperDiEdge{T}
    src::Set{T}
    dst::Set{T}
end

# Base.issubset, Base.in definitions

Only question I have is what behavior should we define if src and dst are not disjoint in HyperDiEdge. In my head, the directed hyperedge would also contain all the directed edges from and to the repeated elements... but should we allow self-loops too?

Footnotes

1. The Wikipedia definition for undirected graph says something similar, but its definition is wrong because it leaves some edges out. ↩

[gdalle]

Oh god don't get me started about self-loops. No one really knows how far they are supported in the current code base

[mofeing]

Oh god don't get me started about self-loops. No one really knows how far they are supported in the current code base

😂 Then let's forget about self-loops for now and just check that $S$ and $T$ are disjoint when creating a HyperDiEdge.