alt Hacker NewsA 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
Replies
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.
https://github.com/kieler/elkjs works well for auto layout.
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.