I'm attempting to write a plugin for Blender that automatically arranges a node-tree neatly, without overlaps or connections that flow to the left. I have access to the list of nodes, their positions, their dimensions and a list of connections/links. The graph runs from left to right and can multiple start and end nodes. The output of a node cannot connect to the input of a node before it, or it's own input (no cyclic dependencies.)
Does anyone know of a paper or article that focuses on coding something that can turn this:
Into this?
The method I originally came up with was: For all nodes that have no input connections, line them up on the left. For all nodes that are connected to these starting nodes, put them to the right of the connecting start node. Repeat this for each node until the end. If one node overlaps another, move it, and the chain of nodes to it's right, down.
This worked great for each isolated chain, but when a node of one chain connected to a node of another (a branch that connects back to the trunk for example), it would often have a backward connection:
This method I've come up with seems to be quite... crude. I've read up a little about Spring Force-Directed layouts, but they seems to be more for graphs that flow in any/all directions, and I'm not entirely sure how I'd manually implement that here anyways, since I'm restricted to using core math alone with no other external libraries.
It's not exactly a common problem, but I'm far from the first to try to figure it out. I'm not asking for code examples exactly, just something to look at to help me work out a decent algorithm.
