search

Murali-group / halp

Hypergraph Algorithms Package
GNU General Public License v3.0
95 stars 21 forks source link

Creating figures #28

Open grhawk opened 5 years ago

grhawk commented 5 years ago

Hi, it would be very nice to have a tool that creates a graph (hypergraph) on as a graphical representation. Are you aware of anything that goes in that direction?

mohawk2 commented 3 years ago

I'm looking for something similar, inspired by Gallo et al's Directed Hypergraphs and Applications.

Sadly Graphviz doesn't seem to elegantly allow invisible nodes with edges entering and exiting in the same direction (which I'd call a "through node"). But this looks promising, using LaTeX: https://tex.stackexchange.com/questions/108064/typesetting-a-directed-hypergraph-in-tikz

Did you find anything else?

mohawk2 commented 3 years ago

I've proposed to the Graphviz folks to add hypergraph support: https://gitlab.com/graphviz/graphviz/-/issues/1911

mohawk2 commented 3 years ago

Additional notes on the above: the LaTeX answer was really using Asymptote. It looks like https://commons.wikimedia.org/wiki/File:Directed_hypergraph_example.svg has similar code (in XML comments) to achieve a similar aim.

tmmurali commented 3 years ago

@grhawk @mohawk2 I am sorry for the very late reply. This issue escaped my notice. Drawing directed hypegraphs is a challenging problem. I do not recall good algorithms for this problem. The discussion on Graphviz's GitLab page suggests many good options that come close.

The hack that I am aware of is to convert the directed hypergraph into a bipartite graph: every hyperedge (S, T) becomes a new type of node u, with edges coming into u from every node in S and edges leaving u to every node in T. Then draw the bipartite graph like a standard directed graph but with the new type of node in a different shape. Needless to say, the layouts do not look pretty.