How to arrange a graph linearly with no overlapping?

Question

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.

Answer 1

A topological sort of nodes, if it exists, will provide you with a correct ordering of nodes for display. If two nodes are not related but sorted adjacent, they can be placed at the same X coordinate if you like.

In general, drawing trees with proper spacing is NP-complete [see references at Drawing Presentable Trees, by Bill Mill], and drawing graphs is no easier.

Answer 2

I would utilize GraphViz for this: http://www.graphviz.org/

1. Read your Blender graph into memory
2. Write out the same graph in the GraphViz graph file format
3. Run one of the GraphViz executables (I would suggest dot (link))
4. Read the equivalent graph but with node positions created by GraphViz
5. Write your Blender graph, with the positions modified based on GraphViz results

Unless you want to for academic reasons, don't reinvent the wheel. This approach should be easy to do, and it won't require designing a complex graph layout algorithm.