Open mofeing opened 9 months ago
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?
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$.[^1]
[^1]: The Wikipedia definition for undirected graph says something similar, but its definition is wrong because it leaves some edges out.
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?
Oh god don't get me started about self-loops. No one really knows how far they are supported in the current code base
Oh god don't get me started about self-loops. No one really knows how far they are supported in the current code base
:joy: Then let's forget about self-loops for now and just check that $S$ and $T$ are disjoint when creating a HyperDiEdge
.
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
andsrc
have no point there (even in an undirected graphdst
andsrc
look weird) because there will be more than 2 vertices.My proposal is the following:
dst
andsrc
for undirected edges $\rightarrow$ Usevertices(edge)
where possible instead.If we relax this assumption, open edges could also be supported and implemented as cardinality 1 hyperedges.