Tree-like distribution problem (geometry, etc.)

[Seymour Clufley]

I doubt this forum will be the place to ask for a solution to this problem, but I ask if anyone can think of a more appropriate forum. Apart from the fact that the problem is very specific, I also don't intend to write the solution in PB, but in JavaScript. However, I can't just go onto some random JavaScript forum and ask about something like this - people expect syntax questions on such forums. This might be a problem for mathematicians - I don't know.

The problem is, I have a bunch of rectangles (about 50 in total) which represent linear chains of events, and I need to distribute these rectangles around a (limitless) 2D plane in the most optimal way. The rectangles are all of the same width, but of different heights. Furthermore, the chains of rectangles are occasionally inter-linked. There might be a "junction" rectangle which is linked to three, four, even five other rectangles. This is what has me completely stumped: how to distribute all of the rectangles such that the linkages are concentrated geographically, and don't sprawl all over the canvas? In other words: how to keep it tidy, and elegant?

Here is a mock-up of how the end result should look. The only difference is that the rectangles' heights will vary slightly. Note that there is a right-ward "drift", because the rectangles are prequels/sequels of each other.



I am not a mathematical guy, and it's a mystery to me that, in so many of my creative projects, I somehow end up needing mathematics and geometry. I wish it didn't happen, because I hate having to ask for help as a complete "maths newbie" like this. Anyway, if anyone can think of a way to approach this problem, or a forum where I'd be best asking, please let me know.

[jack]

hello Seymour Clufley, why not try http://www.mersenneforum.org/index.php, there are some sharp mathematicians there and programmers also.

[Tenaja]

I think this is what you want.
https://en.wikipedia.org/wiki/Dijkstra%27s_algorithm

[spikey]

Hmm, not really. Dijkstra's Algorithm finds the shortest path between two nodes in a mesh, it doesn't calculate a layout for a tree which is what I think Seymour is after.

What you want is the Reingold-Tilford algorithm. Possibly the Walker or Buchheim variation of same.
Try searching for these terms in proximity to JavaScript. I'd be most surprised if no-one has ever attempted it in JavaScript before.

But I'm afraid there is no solution that doesn't involve some maths of some form because although it might seem like a trivial issue on the surface, the problem is NP-Complete (mathematician speak for 'tricky').

Your example looks like a critical path analysis to me - is that what it is?

[Danilo]

May have something to do with Graph drawing and a special Graph Layout Algorithm.

Maybe Graphviz can help you with that (write .dot files and let Graphviz generate the picture
using different algorithms (dotty, neato, etc.))

Books are available for "Graph Theory" and "Graph Algorithms".

[spikey]

I found this, never used it before but it looks very promising...
http://getspringy.com

[DarkDragon]

Finding the optimal layout isn't easy. I think it isn't even solvable in polynomial time, and your picture shows a graph with cycles and so on, so we cannot limit the problem somehow. I would suggest using spring embedding with multiple random initial alignments, since you will probably sometimes end up in a local force minimum which is not optimal.

[EDIT]

Short explanation: this is an iterative approach where you put springs between the nodes with a specific spring constant and then let it align itself by calculating the physics. After a while it will stand still (check movement of the nodes), but it might not be optimal. Therefore you try it multiple times with different random initial positions of the nodes and you take the result with minimal tension in the springs.

You can also see the movement in the springy.js example of the poster above me.

[Seymour Clufley]

Thanks to all of you for replying.

Spikey's recommendation, the Springy library, seems to be exactly what I need! What a relief. Everything else in this project is being hand-coded by me, so I don't want to appear lazy, but this one part really had me stumped, so it's great to find a library to solve the problem for me.

Thanks again, everyone. I appreciate the help.