Directed Hypergraphs?

[stustd]

Great work! Are there any future plans to also include directed hypergraphs?

[pszufe]

We do not have currently anyone to do it. However, if you have some proposals and would like to contribute we are open to talk and guide you.

[stustd]

We do not have currently anyone to do it. However, if you have some proposals and would like to contribute we are open to talk and guide you.

I'm reading into it and will let you know when I'm sure I can commit myself to the effort it requires.

[pszufe]

The first issue is that there are several possible definitions for "directed" hypergraphs. One would need to do a review study and decide which criteria should be used to choosing a particular "being directed" interpretation for hypergraphs.

[Philogicatician]

there are several possible definitions for "directed" hypergraphs.

@pszufe I'm gonna build this since it might be useful for what I'm trying to do (plus it'll be good practice in developing Julia packages). Any tips you can give regarding the possible definitions would be appreciated.

[pszufe]

Hi, I am open to comment if you propose some functionality. I think that generally extending the functionality to some form of directed hyper-graphs is a good idea.

[pszufe]

One possible representation could be to have a directed hyper-graph as two undirected hypergraphs where the first one represents out-going hyperedges and the second incoming hyperedges. This would be quite compatible with the current data structures. But perhaps there are better ideas.

[Philogicatician]

This might be a silly question, but why not just have positive and negative weights indicating incoming and outgoing edges, respectively?

Oh, and I should probably mention that regardless of what the current implementation is in SimpleHypergraphs.jl, I'm trying to make it compatible with the Graphs.jl package since that seems to be the de-facto library for graphs in Julia. Here's an issue I opened up there seeking design advice.

[pszufe]

SimpleHypergraphs is using weighted hypergraphs representations and this actually already works and perhaps you can use SimpleHyprgraphs to analyze directed hypergraphs.

Just note that we use nothing rather 0 to represent missing connection (we allow a connection with zero value to exist).

Here is the full code:

julia> m = Matrix{Union{Nothing,Int}}([-1 0 0 0 0;
       -1 0 0 0 0;
       0 -1 0 0 0;
       1 -1 0 0 0;
       1 0 0 0 0;
       1 0 -1 0 0;
       0 1 0 0 0;
       0 1 0 0 -1;
       0 0 1 0 -1;]);

julia> h = Hypergraph(replace(m, 0=>nothing))
9×5 Hypergraph{Int64, Nothing, Nothing, Dict{Int64, Int64}}:
 -1           nothing    nothing  nothing    nothing
 -1           nothing    nothing  nothing    nothing
   nothing  -1           nothing  nothing    nothing
  1         -1           nothing  nothing    nothing
  1           nothing    nothing  nothing    nothing
  1           nothing  -1         nothing    nothing
   nothing   1           nothing  nothing    nothing
   nothing   1           nothing  nothing  -1
   nothing    nothing   1         nothing  -1

julia> gethyperedges(h, 4)
Dict{Int64, Int64} with 2 entries:
  2 => -1
  1 => 1

[pszufe]

SimpleHypergraphs is also already compatible with Graphs.jl as this is the most standard library in the Julia graph ecosystem.

julia> supertype(BipartiteView)
Graphs.SimpleGraphs.AbstractSimpleGraph{Int64}

julia> b = BipartiteView(h)
{14, 13} undirected simple Int64 graph

Now b is seen and behaves as a standard Graphs.jl graph (but it is still an actual view so hypegraph is used as the internal data storage and mutating h will mutate what is seen as b.

[Philogicatician]

That's great news. 👍 Any thoughts on the representation for hypergraphs I mentioned on the Graph.jl issue I opened? (It just occurred to me that you may not get notifications for that.)

Also, another stumbling block I'm trying to preempt (as I mentioned in that comment) is how to represent directed hypergraphs in way that also allows for the use of "oriented hypergraphs" (generalization of signed graphs) like on pg. 3 of this paper by Rusnak... Although, as long as the data structure allows for positive and negative values, I think that should be enough for something like Gallo, Longo, & Pallottino's approach to directed hypergraphs (on pg. 179) to allowed for oriented hypergraphs, but it feels like it might not be enough information...