Comment by ffsm8
14 hours ago
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
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.
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.
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
https://github.com/kieler/elkjs works well for auto layout.