[Python] Python algorithm to arrange a set of graph nodes where one axis coordinate is fixed...

I found two similar questions like here: How to draw a graph layout where one axis is fixed

I am using Python, I want to draw a directed acyclic graph (DAG) in the following way. Each node has a value that should be used as the y-coordinate. I want the other coordinate to be 'optimized' in a way so that the graph is spread out in a way that it is readable. Other questions asked about minimizing edge crossings etc. but I am ignoring this and only looking at the nodes (assume I don't know what the edges are, but I am open to an algorithm that takes these into account).

As an illustration say I have the four points on the left where the y-axis value is fixed. Obviously this is bad because if I drew any edges they would overlap. The second is also bad because it is still "flat" even though the x-axes now differ, but they do so in a way that still doesn't spread out the "area" of the graph. I want something more like the third. Obviously, since the ultimately the graph axes will be spread out according to the observed range, the absolute values of the x-axis points don't matter, only their relative positions.



One solution I have found is Python's samply module, as such

from samply.subspace import orthogonal_ball, orthogonal_directional
import numpy as np
# set random seed for sampling process
np.random.seed(4)
ycoords = [1,3,5,7]
xcoords = orthogonal_ball(vector=ycoords)[0,:]

import matplotlib.pyplot as plt
plt.scatter(xcoords, ycoords)
plt.show()


It seems to work ok

Latin Squares also work ok

from scipy.stats.qmc import LatinHypercube
pos_sampler = LatinHypercube(d=2, seed=4)
pos = pos_sampler.random(n=len(ycoords))
# order coordinate rows by y-coordinate, in reverse order
pos = pos[np.argsort(pos[:, 1])[::-1], :]
# assign the y-coordinate, which is already sorted, to be the sorted value of sample mean
ord_sm = np.argsort(ycoords)[::-1]
print(ord_sm)
pos[:, 1] = np.array(ycoords)[ord_sm]
# now return positions in the order as the original sample means to maintain correspondence

plt.scatter(pos[:,0], pos[:,1])
plt.show()


Does anyone have alternative algorithms, or perhaps one that takes into account the edges so that there are minimal overlap (e.g. in a fully connected graph, three nodes arranged in a near-line would have overlap in edges that are hard to read).

Continue reading...