Hacker News Reader

Comment by bmitc | Hacker News Reader

I'm interested in knowing about graph layout algorithms that allow specific constraints. If anyone knows about these things please let me know. I do not, but I have a use case for them.

For example, the constraints may be:

1) The graph is read left to right. This informs the layout such that those spiral and circular graph layout algorithms that blow out the graph do not work.

2) Try to keep certain types of nodes vertical aligned, so that they lie on the same horizontal line.

3) Minimize edge crosses.

4) Have the edges be not lines but paths made up of horizontal and vertical lines. This probably requires some path finding as well.

5) Be able to live update in the sense that a new node or edge entry into the graph does not drastically re-layout the graph for reasonable inserts.

View on HN

Some time ago I found an interesting PDF about graph layout algorithms in general [0]. Nothing groundbreaking, but it also covers approaches for orthogonal layouts (aka only horizontal/vertical edge paths like in your fourth condition) and I liked how straightforward it is.

To meet all these criteria would indeed be amazing. For 5) you may get semi-reliable results by doing the layout deterministically and optimize for things like short edge length, so adding new nodes would just push around the rest a little bit. But good luck avoiding crossings at the same time.

[0] https://cs.brown.edu/people/rtamassi/papers/gd-tutorial/gd-c...

Toward 5, I've been able to get ELK.js to do somewhat stable things for simple graphs using `FIXED_ORDER` https://www.eclipse.org/elk/reference/options/org-eclipse-el...

Look at graphviz. Their "dot" program satisfies 1 through 4. Your fifth wish is hard to satisfy.

You could probably satisfy 5 with some kind of (mixed integer) linear optimization or so.

Would you mind elaborating? Thanks ahead of time.

Well, you formulate all your constraints in the language of your favourite constraint based programming solver (eg convex optimisation or mixed integer linear optimisation etc). For simplicity, let's call your candidate solution x (where x is a vector of suitable size) and the constraints are formulated as some function f from your vector to real numbers, so that the problem reduces to "minimize f(x)".

Then it's relatively easy to formulate your (5) as an additional constraint in the same language:

Given a previous solution x_0, find a new solution x_1 to slightly different constraints f_1 by minimizing af_1(x_1) + bdistance(x_1-x0)

You'd need to decide on the weights a and b and on the distance function. (Instead combining distance from old solution and constraints linearly, you could also use other ways to combine them. Eg you could also say:

Keep f_1(x_1) <= epsilon and minimize distance(x_1-x_0). Or you could do minimize the sum of squares:

af_1(x_1)^2 + bdistance(x_1-x0)^2

Specifics depends on what works well for your problem, and what your solver can handle.

See https://developers.google.com/optimization for a free library of solvers.

I have looked at Graphviz before, but wasn't aware of anything there that helped with these constraints Do you happen to have any specofic pointers?

And it may be the case that (5) is actually the most implrtant constraint. Haha.

Hi, Alejo Hausner!

We worked on this problem, too, and Gordon Woodhull created a working system for dynamic hierarchical layout. I think he also incorporated an improved node positioning and edge routing algorithm of Ulrik Brandes. The code is still available here, I think: https://www.dynagraph.org

It was great work. We meant well, but were overextended for the resources we had. Gordon is a brilliant programmer.

Reply on news.ycombinator.com