Issue:Minor changes in border affect forcedir layout strongly

Description:	variations in the 'border' parameter have strange effects on the overall layout.
Extension / Version:	aiSee   /   2.2
Type / Status:	Feature   /   won't fix, by design (see explanation below)

Problem

• The current changes in layout which happen if one uses border values between 900..905 (ceteris paribus) are unexpected.
• Watch the huge change in overall scaling between 901/903 and 902!
• Why are there crossing edges when 904 is used?

I would consider the current behaviour as 'not conformant with reasonable expectation'.

See Wgraph:Demo border

Reply

I see where you're coming from, but that is kind of the whole point of the border attribute. In fact, it would be strange if it did not behave that way. Let me explain.

Force-directed layout is calculated in lots of iteration steps. In each iteration step, nodes change their positions slightly, due to the forces acting on them. The algorithm tries to balance out all the various forces and to minimize the global energy level by moving the nodes in the direction of the forces. In addition, every now and then, the nodes are "tickled" and randomly moved so as to avoid being trapped at a local energy minimum.

Note that while the random movement is being ceased towards the end in order to stabilize the final layout, the system usually never comes to a complete halt. The "final" layout that you see is basically a shot of the system taken after X iterations.

Now, depending on the graph and the number of iterations, it is possible for nodes to move very far away from the starting point and/or from one another (especially if the graph consists of several unconnected components, as in this particular case). The idea behind the border attributes is to prevent just that from happening. These attributes specify a rectangle within which the graph is kept.

In other words, whenever a node reaches the border of that rectangle, it bounces back.

Now, obviously, if you change the size of the rectangle, the node will bounce back in a different iteration, and might bounce back in a different direction. Note that the latter is actually irrelevant, the former is already sufficient to make the final layout look completely different, because we're still looking at the system after a fixed amount of iterations.

Imagine you're playing with a ball, throwing it at a wall, and taking a photo after exactly X milliseconds. If you always throw the ball with exactly the same speed, and always in the exact same direction, but move the wall each time, you will always get different results.

(And that's just one ball and one wall. Now imagine doing that with four walls and X balls thrown in different directions at differents speeds. And then, imagine that some of these balls are connected by rubber bands with one another. You get the idea.)

As a simple experiment, try selecting higher values for the border attribute (6000, 10000, 916342...). Note that you always get the exact same layout. That is because from a certain point on (in this particular example, it happens to be 1000), none of the nodes ever reaches the border and never bounces back. Which, obviously, doesn't change if you move the border even farther away.

See the aiSee user manual for more information on how force-directed layout works.

You might also wish to run aiSee (offline) with the command line option -epanim that animates the internal layout calculations. It should be immediately obvious why you end up with the layout you end up with. And it's fun to watch, too. (^_^)

--Schwallex 16:48, 12 October 2007 (CEST)

Reply (2)

Thanks, your explanation makes everything quite clear. I understand that you use simulated annealing and that borders behave as reflectors. Is it conceivable that walls absorb energy, i.e. are not seen as ideal reflectors but would have a damping/absorbing characteristic? This could lead to a behaviour where 'fleeing nodes' end up quite close to the wall after a sufficient number of iterations. I suspect that such an approach would lead to a more "natural behaviour" -- as you see I do not want to adapt my perception of what I regard as 'expectancy conformance' to your model of bouncing borders ;-).

Gero 18:54, 12 October 2007 (CEST)

Well, don't get me wrong, I absolutely agree on the 'not what the user might expect' part. Force-directed layout schemes are very capricious by nature. Tweaking just a single little parameter just a tiny bit often results in a totally different layout, and people get confused very quickly.

Anyway, the energy-absorbing border approach sounds interesting. Can't promise anything right now, but I'll pass it on.

--Schwallex 23:44, 12 October 2007 (CEST)