# Graph layout positioning

Given a graph layout like the following image, where the layers/rows (y coordinate) and ordering of nodes within each layer have already been computed, what algorithm can I use to make it look "nicer"?

Just to clarify, all I am wanting to change is the X coordinate of each node. The y coordinate (the layer) should remain the same. And the order of the nodes within the layer should remain the same.

One thing I have tried is simply centering the node between its connected nodes in adjacent layers. But this is tricky, as for example in the case of 'i' you need to take a top down approach and a bottom up approach .. which I can't get to produce a nice result .. it looks worse than the original.

I might stick to full column positions to keep the problem simpler.  So, for `i`, shown in the 2nd column position, choose instead the 3rd column position (leaving column 2 blank).  This would have `g-i` and `i-j` lines straight, while lessening the angle of `k-i`.

Decide on a maximum width, i.e. number of columns, perhaps in your example, 4, but you could go to 5 or more.

Define a measurement score of a graph layout, which might simply be the sum of the distances of all the lines/connectors in the graph, smaller is better.

Compute that score with elements laid out in each possible position.  So, for the `h`, `i` row alone, for example, try all combinations of `h` in columns 1 to 3, and `i` in columns 2 to 4.  But of course, doing that in context of all the other rows varying as well, so focusing on whole graph layout score rather than on any given row or on one row in relation to its superior or inferior.

And finally, pick the graph layout that has the lowest score.

• Wouldn't that result in a crazy amount of combinations though? so for example, if I did as you said and moved 'i', then computed a score for the graph. Then I moved 'h' and computed another score. Wouldn't I also need to compute the score of 'h' without 'i'? Commented Aug 27, 2023 at 15:13
• "Wouldn't that result in a crazy amount of combinations though?" sure, but so what, computers are pretty powerful these days. Commented Aug 27, 2023 at 15:16
• "Wouldn't I also need to compute the score of 'h' without 'i'?" The score I'm suggesting applies to an entire graph layout, not to any node or line. Commented Aug 27, 2023 at 15:17
• okie doke. I'll give it a shot. Fortunately, the graphs I'm dealing with will never have any more than about 50 nodes, so brute force might be an option. Commented Aug 27, 2023 at 15:20
• Yeah, if you limit the number of columns to 4 for your example, then there's only one layout choice for rows 1 and 4, since they have 4 elements, and for the rows that have 3 elements, there are 4 layout options, for 2 elements, 6 I think, while for 1 element, 4 again. These are fairly small multipliers. Commented Aug 27, 2023 at 15:24

Before asking for an algorithm to make your graph layout look nicer, first and foremost you need to define formally what you mean by "nicer". Possible criteria, which come into my mind:

• the number of intersections of the edges (you probably want to minimize)

• the angles of all the edges (you probably want them as vertical as possible)

• the length of all edges (you probably want them as short as possible)

• the distance between the node boxes in one row (do you want them to be as near as possible to each other, without overlaps, or mostly equally spaced?)

• the distance of the left box from the left edge in each row

You should also decide whether the X positions are bound to certain columns, as in your picture, or if the boxes can float freely in each row as long they don't overlap.

From the criteria above, you need to construct a target function, probably a weighted sum which you want to or minimize. What you get then is called an optimization problem, which is a huge field with tons of algorithms available.

In your particular case, I would probably start with a simple brute force search, at least when restricting the problem to the use of specific columns. In case that's too slow, or for the case where arbitrary X values are allowed, I would try some heuristics like hill climbing or simulated annealing, which are not particular hard to implement.

FWIW, in case you were allowed to change of the order within each row, I would recommend a two-step approach: in the first step, I would modify the order of the boxes in each row by applying some random swaps (global search). Then, I would optimize the layout while keeping that order (local search). The final layout for that order will then be compared to the final layout of other orders, which makes it a global optimization. You can use SA or hill climbing for the global search as well as SA or hill climbing for the local search.

• Yes, you're right. By nicer, what I meant was visually pleasing (doesn't need to be restricted to columns), which I appreciate is still too vague of an answer. I guess the best I can say is nodes should try to be centered within their connected adjacent layer nodes. So in the case of 'i', it would be centered between 'e' and 'g' and also between 'j' and 'k'. How would you define that though? Commented Aug 27, 2023 at 16:02
• @wforl: I would probably experiment with this, by giving all criteria different weights, run the optimization and see how it looks like or changes when I change the weights. Commented Aug 27, 2023 at 16:42
• Yes, I guess the problem is now much larger though, as now it's not fixed columns, so instead of moving by a column at a time, it's now move a fraction in x and scoring the result. So even more combinations. Commented Aug 27, 2023 at 20:01
• I can see how SA works in 1D, but am having trouble with how to apply it to this scenario. What happens if you go down a path where the result gets better and better for a while but then stop, as its not the optimum path? Do you back out and try again? Do you start from the beginning? How do you know how much to move things by? Commented Aug 27, 2023 at 20:13
• @wforl: for SA, you first have to choose a way for making random modifications which I guess here should be either a slight x-shift of one box or more, or some operation which involves switching two neighbored boxes. Now these operations are applied in a loop, they will be accepted when they improve the score. When a modification decreases the score, it will only be accepted with a certain probability. That probability will be high at the beginning, getting lower and lower over time. Commented Aug 27, 2023 at 21:51

After clarifying your criteria for niceness as suggested in another answer, you may utilize a constraint solving algorithm, which are often pretty successful at graphical layout problems. Choosing which one depends a bit on experience and availability for your programming language, you may need to look around and experiment a little to find one that suits you.

If you're into Python or C++, the kiwisolver package may be a possible approach. It's an implementation of the Cassowary algorithm which is able to solve linear constraints in an intuitive manner.

For fun, I've tried running the example through kiwisolver (was too lazy to add painting the graph):

``````from kiwisolver import Variable, Solver

solver = Solver()

# row 1
a = Variable("a")
b = Variable("b")
c = Variable("c")
d = Variable("d")
# row 2
e = Variable("e")
f = Variable("f")
g = Variable("g")
# row 3
h = Variable("h")
i = Variable("i")
# row 4
j = Variable("j")
k = Variable("k")
l = Variable("l")
m = Variable("m")
# row 5
n = Variable("n")
o = Variable("o")

constraints = [
# row 1
b >= 0, a >= b+10, d >= a+10, c >= d+10, c <= 30,
# row 2
f >= 0, e >= f+10, g >= e+10, g <= 30,
# row1 -> row2
(f == (b + d) / 2) | "strong", (e == (a + d) / 2) | "strong", (g == (d + c) / 2) | "strong",
# row 3
h >= 0, i >= h+10, i <= 30,
# row 2 -> row 3
(h == (f + e) / 2) | "strong", (i == (e + g) / 2) | "strong",
# row 4
l >= 0, m >= l+10, j >= m+10, k >= j+10, k <= 30,
# row 3 -> row 4
(l == h) | "strong", (m == h) | "strong", (j == i) | "strong", (k == i) | "strong",
# row 5
n >= 0, o >= n+10, o <= 30,
# row 4 -> row 5
(n == (l + j) / 2) | "strong", (o == (m + j) / 2) | "strong",
]

for constraint in constraints:

solver.updateVariables()

for v in [b,a,d,c,f,e,g,h,i,l,m,j,k,n,o]:
print(v.name(), "=", v.value())
``````

Result:

``````b = 0.0
a = 10.0
d = 20.0
c = 30.0
f = 5.0
e = 15.0
g = 25.0
h = 10.0
i = 20.0
l = 0.0
m = 10.0
j = 20.0
k = 30.0
n = 10.0
o = 20.0
``````
• Do you have some references? Commented Aug 28, 2023 at 8:09
• This was mainly from memory, it was a somewhat active issue about 25 years ago and I tried some stuff way back then and was pretty satisfied. I don't have references for up-to-date options, looking for "python constraint solving" for example brings up a finite domain solver (python-constraint) but here you'd like to solve for continuous variables, which is probably possible with CPMpy but I did not dig deeper. Commented Aug 28, 2023 at 8:18
• Looks interesting, but can you explain where do we see in this example the optimization of a certain target function towards some minimum or maximum? For example, for the sake of simplicity, lets say we want to minimize the sum of all the variables (those are the x values of the boxes, right?). Can this solver find this minimum? Commented Aug 29, 2023 at 12:21
• You could add constraints equalling the variables to 0, with a strength that allows the constraints to be violated if other, required, constraints would be violated otherwise. But minimum x wasn't a criterion, only order within row, minimum distance, and approximate centering of boxes below their "parents". I must admit I didn't add constraints in the other direction, that's left as an exercise for the reader. Commented Aug 29, 2023 at 18:14