Graph layout positioning

Question

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.

Answer 1

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.

Answer 2

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.

Answer 3

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.addConstraint(constraint)

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