Layout for SetHypergraph?

[thomasleaute]

Hi,

I would like to render a hypergraph (with edges connecting > 2 vertices). I understood that I need to use SetHypergraph instead of Graph (which is confusing because Graph implements Hypergraph), but the layout constructors I have found expect Graph instances as input. Which layout should I use to render SetHypergraphs?

More general question: where is the JUNG user manual? Where is the discussion forum? I am looking for a Java library to render hypergraphs, and at first I thought JUNG looked like a good candidate, but I've been struggling to figure out how to use it.

Thanks in advance.

[jrtom]

@thomasleaute In order:

(1) JUNG doesn't provide layouts for hypergraphs. The last we checked, laying out hypergraphs is a much harder problem than laying out graphs, and rendering them in a useful fashion is not exactly an easy task either; for any non-trivial hypergraphs. (Nor does JUNG have any rendering support for hypergraphs.)

There's a paper here that talks about a possible approach, but I haven't read it in detail: https://www.researchgate.net/publication/246394010_How_to_draw_a_hypergraph

Your best bet to render a hypergraph with JUNG is to represent it as a bipartite graph (partition N devoted to the nodes of the hypergraph, partition H to the hyperedges, connect a node n in N to a node h in H if n is incident to h in the hypergraph) and then lay it out with one of the standard layout algorithms, or a layout of your own devising.

If you're interested in contributing mechanisms for laying out and/or rendering hypergraphs, let us know. (Or if you find another open-source library or tool that does this; we're not aware of any.)

All that said: what problem are you actually trying to solve by rendering your hypergraph? There may be another way to solve your problem.

(2) There is a tutorial for JUNG 2.x here: http://www.grotto-networking.com/JUNG/JUNG2-Tutorial.pdf

At present JUNG doesn't have a discussion forum per se, but you're welcome to open issues here as a place to discuss things. (We're also open to creating a discussion forum if there's enough interest in it.) If you have specific questions on the "how-to" front, StackOverflow is the best place for that (we follow issues tagged with "jung").

We're currently working (as you can see by the state of the repo) on JUNG 3.0, which makes some radical changes to the data model and elsewhere; once that's ready to go, or almost so, we'll create a new manual (and tutorial) for it.

Hope this helps.

[thomasleaute]

Thanks for your prompt and detailed answer.

1) Rendering hypergraphs: I have now spent a few hours searching for open-source libraries that implement layouts for hypergraphs, and indeed I have not found any. I was hoping I could find one that renders hyperedges in the form of Venn diagrams, but my search was fruitless (TikZ is a good candidate when it comes to drawing the hyperedges, but doesn't help with auto-positioning the vertices). The only workaround I have found is your suggestion to use bi-partite graphs; I am going to investigate this approach.

2) Thanks for the pointer. I was already aware of this tutorial, but it looks like I skimmed over it a bit too fast, and I should spend more time to read it through in detail.

[jrtom]

You're welcome on all counts. I'm still curious as to what problem you're trying to solve (and might be able to help more if I knew that), but of course whether you want to share that is up to you.

[thomasleaute]

I'm trying to implement a new visualization interface for FRODO. It's about representing Distributed Constraint Optimization problems, in which intelligent agents try to make decisions (= assign values to variables), taking constraints and preferences into account. One way to represent such problems is as hypergraphs in which the vertices are the decision variables, and the hyperedges are the constraints/preferences expressed over subsets of decision variables.

[jrtom]

Thanks for the additional context. FRODO sounds interesting, and reminds me of some things I was studying a while back during my MSc work.

I agree that hypergraphs/bipartite graphs sound like an reasonable data model (bipartite graphs might be more useful if you have weights associated with constraints/preferences that are not uniform over the decision variable subsets, but otherwise hypergraphs are probably more space-efficient).

However, I'm curious about what task you think will be aided by creating visualizations. Unless there are relatively few decision variables, and relatively few constraints/preferences, even a hand-constructed visualization is likely to be difficult to interpret. What are some typical model sizes (variables and constraints)? What user problems do you think that visualizations might help with?

(I'm not in any position to suggest that you shouldn't do this unless it's useful; some things are worth doing for the intrinsic challenge, or just for fun. :) But IME people often overemphasize the utility of graph visualizations.)

[thomasleaute]

Such hypergraph visualizations would only be used on small hypergraph instances (max 10 vertices), for didactic and educational purposes.

For a long time, the DCOP research community has been treating constraints as second-class citizens (compared to variables). The vast majority of papers in the DCOP literature start by making the simplifying assumption that all constraints are binary, i.e. each constraint is expressed over only 2 variables. As a result, the most common graphical representation of a DCOP instance is in the form of a constraint graph, which is a graph in which the vertices are the variables, and there is an edge between two vertices if an only if the two corresponding variables are involved in a common constraint. Under the binary-constraint assumption, this representation is decent (although, a multi-graph would be better).

As a (former) DCOP researcher myself, I have been fighting against the abuse of this simplifying, binary-constraint assumption, because I believe that it constrains the community in the way we design algorithms. Most applications of DCOP involve problems in which some of the constraints are n-ary, in which case the constraint graph representation is misleading, because one n-ary constraint ends up represented as a clique of n (n-1) / 2 binary constraints over n variables. Many researchers measure DCOP algorithm performance in terms of constraint checks, i.e. how many times one agent needs to look up the value of a constraint against a tentative assignment of values to variables. In this context, one n-ary constraint is absolutely not equivalent to n (n-1) / 2 binary constraints.

My hope is that a hypergraph representation of DCOP instances in FRODO would contribute to bringing a mind shift change to the community, by reasoning about constraints as full-class citizens. In fact, there are classes of DCOPs in which it is more beneficial to reason primarily in terms of constraints, rather than primarily in terms of variables (example: the traditional meeting scheduling problem class).

Using bipartite graphs in a good first step. In fact, it is already used by one particular DCOP algorithm, the Max-Sum algorithm, which represents the DCOP as a factor graph with two types of vertices: variable nodes stand for variables, and function nodes stand for constraints. The reason this representation is used for this particular algorithm is because, unlike most other algorithms, in Max-Sum the (virtual) agents are the nodes in this factor graph: there is a virtual agent for each variable, but also a virtual agent for each constraint, and these virtual agents exchange virtual messages to solve the DCOP. This is what justifies introducing vertices for constraints: it is because constraints behave like virtual agents. Traditionally, in graphical visualizations of DCOP instances, the vertices are the agents, and the edges are communication paths between these agents.

So my motivation for generalizing this visualization to hypergraphs is: let's use a graphical representation in which the vertices are the agents (as usual), but let's use a more faithful representation of n-ary constraints as hyperedges, rather than cliques of edges. Such a visualization could help the community come up with algorithms that are better suited to real-world applications involving n-ary constraints.

[jrtom]

Ah, that puts some pieces into place, thanks.

The position you're in with respect to the DCOP community reminds me of where I was with the social network analysis community about 10-15 years ago. (I haven't been doing much with SNA in the meantime, so it's possible that they're still overly focused on graphs when hypergraphs would make more sense. :/ ) Cliques of edges are particularly bad for representing things that are properly hyperedges, because (aside from the horrible complexity issues) you lose the semantic unity of the relationship by representing it as a clique.

Anyway, if you're really just looking to create visualizations for didactic/educational purposes, I recommend that you'd probably be best served by creating them by hand, which is easy enough with tools like OmniGraffle and such.

Good luck!