## Parallel Force Atlas

Algorithms and parameters to put data in space
jeffg
Posts: 7
Joined: 26 Nov 2010 15:50

### Re: Parallel Force Atlas

I did do it in Java, but I'm not using the Gephi base code for my nodes / edges / graph, so I rewrote portions to reflect my code, but all the logic for the layout itself is consistent. For example, I didn't like that the layout used doubles to store everything as it consumes twice the memory (and a good amount for large graphs when your talking about 3 sets of x,y,z) and I don't need that level of precision, so I changed them all to floats. Stuff like this is what makes it a pain to port back.. haha

Most of the improvements were in the Region and ForceFactory. I think I'm laying out about 20,000 nodes in about 5sec (completed time). A good bit of changes to the buildRegions and converting to using a fast distance calculation when real distance was unnecessary (no need for square root).

Example - the current code does this in the Force Factory.

Code: Select all

``````double distance = (float) Math.sqrt(xDist * xDist + yDist * yDist);
if (distance > 0) {
double factor = coefficient * n1Layout.mass * n2Layout.mass / distance / distance;
}``````
So you have a sqrt and then divide the mass by distance twice - what's the point there? 200 / 10 / 10 = 2 or 200 /100 = 2. There are two expensive calculations there that don't need to be.

Code: Select all

``````double distance = (xDist * xDist + yDist * yDist);
if (distance > 0) {
double factor = coefficient * n1Layout.mass * n2Layout.mass / distance;
}``````
In the Barnes Hut, I made some changes to create the sub-regions faster (less loops and less object creation) - important since I was going from 4 to 8 regions for 3D. I added a region limit since computing to 1 node can be expensive when it's unnecessary at first for a quick convergence. I stage it out a bit, only processing to a node level of nodes.size() * .005f for the first 25 steps, then drop it to 0 after that, which is the current value.

So, when you add it all up along with other changes here and there, it can make a big difference.

bumper_boy2000
Posts: 4
Joined: 02 Feb 2012 13:38

### Re: Parallel Force Atlas

hi guys. I have a really trivial question. does PFA run indefinitely? I can see that it's much faster than FA1 and FA2, but my graphs don't seem to finish rendering. :/

pbittner
Gephi Plugin Developer
Posts: 35
Joined: 18 Mar 2010 23:03
Location: London, UK

### Re: Parallel Force Atlas

There is no convergence check at the end of each iteration of PFA. It is up to the user to stop the layout when satisfied with the result. If your graphs are small enough, the layout will stabilize itself quite quickly. If after running the layout for a while some nodes keep moving around from one position to another, you should reduce the speed parameter to help these nodes find a stable position.

bumper_boy2000
Posts: 4
Joined: 02 Feb 2012 13:38

### Re: Parallel Force Atlas

pbittner wrote:There is no convergence check at the end of each iteration of PFA. It is up to the user to stop the layout when satisfied with the result. If your graphs are small enough, the layout will stabilize itself quite quickly. If after running the layout for a while some nodes keep moving around from one position to another, you should reduce the speed parameter to help these nodes find a stable position.
alright got it. i have a few graphs to visualize. some are small, and "converge" easily. i will try reducing the speed parameter for the large graphs. thanks!

bumper_boy2000
Posts: 4
Joined: 02 Feb 2012 13:38

### Re: Parallel Force Atlas

i just checked. lol my speed's already been set to 1 for all graphs. i guess that's the best it can do. :/

martin.pernollet
Posts: 18
Joined: 05 Oct 2010 12:42

### Re: Parallel Force Atlas

Hi,
I recently noticed my laptop was able to switch to a non nvidia graphic card, so you have to explicitly set from nvidia settings panel that you want the OS to always use your nvidia, and not an alternative (maybe less energy consuming) chip.
See a screenshot in this discussion: http://forum.jogamp.org/Fail-to-run-a-d ... 15480.html.

That info may help for your doc.

Once changed, I noticed the checkbox does not uncheck itself, so I assume your plugin works

By the way, why not using JOCL to compute layout? Maybe easier to embed in a java program

Martin