4 ms·

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

by alejohausner 3y ago

eru 3y ago
You could probably satisfy 5 with some kind of (mixed integer) linear optimization or so.
- bmitc 3y ago
  Would you mind elaborating? Thanks ahead of time.
  - eru 3y ago
    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 https://developers.google.com/optimization for a free library of solvers.
bmitc 3y ago
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.
graphviz 3y ago
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 https://www.dynagraph.org It was great work. We meant well, but were overextended for the resources we had. Gordon is a brilliant programmer.

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

eru 3y ago

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

bmitc 3y ago
Would you mind elaborating? Thanks ahead of time.
- eru 3y ago
  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 https://developers.google.com/optimization for a free library of solvers.

bmitc 3y ago

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.

graphviz 3y ago

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 https://www.dynagraph.org It was great work. We meant well, but were overextended for the resources we had. Gordon is a brilliant programmer.