A few years ago I created a similar layout engine, it was extremely janky when I abandoned it because I first wanted to solve order/placing of the tiles but was unable to figure out a good algorithm for it

Eg your example diagram has an optimal order in which there are no overlapping lines... But it's surprisingly hard to figure that out without doing n^m calculations... And I wanted to use it in a game, so a shitton of tiles.

Dunno where I was going with this, just got reminded of that project after looking at this great implementation.

It also reminded me of the xyflow lib

▲

johndough 5 hours ago | parent | next [-]

In academia, this is called "planar embedding" and can be computed in O(V) where V is the number of vertices of the graph.

However, there are graphs that do not allow planar embeddings (e.g. K_5 or K_3,3, see https://en.wikipedia.org/wiki/Planar_graph).

In this case, you'll probably want to look into heuristics that produce a low number of crossings and little distortion when new vertices are added.

▲

tharkun__ an hour ago | parent | prev | next [-]

Not sure what you're seeing, but I see quite a few overlapping lines. One of them easily solvable if you move `addresses` down. It starts with the `orders->users` overlapping `orders->addresses`.

Also, the `reviews` table overlaps the line from `order_items` to `products` and moving `order_items` down for example gets rid of that problem.

Not saying the project isn't cool, but this layout isn't optimal as per your constraints.

	▲	ffsm8 44 minutes ago \| parent [-]
		Ah, I was imprecise in my comment. I didn't mean that this implementation was doing the optimal ordering - I was just reminiscing about a similar project I worked on an why I abandoned it (I was unable to get the ordering done while keeping performance good enough with thousands of tiles

▲

jeffreygoesto 2 hours ago | parent | prev [-]

https://github.com/kieler/elkjs works well for auto layout.