Well, I've been looking at it, and the sort of algorithm you really need is way too complicated to explain on this site. And I don't really feel like relearning all that stuff, since it would take me days to get up to speed enough to be able to design new graphing algorithms. Seriously, if you want to do this right, get the book I recommended, and read through the flow and orthogonal drawings section (with your math books open on your lap).
However, if you observe a few simple limitations, this can be done without too much effort. Suppose for example that you were to say that your graph looks like a tree, with a tree root node, and two children per node. So, for example A is the root node, and points to B and C, B points to D, and C points to E and F. That is a tree without cycles, without merging of separate paths, and with at most two children per node. This is easy to layout:
- place the root node at the top left
- place the first child of the root node to the right of the root node, and the second child to the bottom
- with each child node, repeat the process, place one child to the right of it, one child to the bottom
- in some cases this will cause nodes from two branches to overlap, so for each node you place, check that it doesn't overlap any previously placed nodes, and if so, move the right-most branch to the right until there is no more overlap
The result of this is an orthogonal tree that runs mostly horizontally, with vertical split-offs for the branches.
Now, what you really need is a minimum cost orthogonal network flow layout algorithm. There is source code for one
here, but it may be difficult to figure out, and the author admits that it doesn't always work correctly and is slow (common for graph layout algorithms, since this is a problem of complexity class NP, meaning you can do it right, or you can do it in reasonable time, but not both).
Or maybe someone else can suggest a quick fix.
Threaded Mode
