Going somewhere, but where?

For those regular readers, you must be as sick of me talking about approximations as I am, so good news everybody! I'm making some leeway.

I have successfully managed to get the Grid approximation  working* (*working is subjective). The way in which the graph "stuck" to the grid structure suggested that the forces between one section and another were not playing happily together (a force would push the vertex out of a section but the adjacent section would push back an equal amount, causing it to get stuck in limbo).

Increasing the effect of the grid repulsive force, meant that the vertices could move more freely between sections, giving better layouts. See the evolution below showing the graph sticking, then the affect of increasing repulsive forces.

Click on the image to enlarge. From left to right, the repulsive forces

are multiplied by a parameter. Best results are around 50 but some graphs may 

look better with more or less powerful forces.

My Barnes Hut implementation is also giving results, however, they are becoming more and more of an issue. The results show the algorithm working with coarse versions of graphs but failing in the finer versions, collapsing inwards upon itself.

Note the coarse graphs are fine up to the 4th level however the

graph degrades rapidly after. The same can be seen in my comparison of data

 (below). This is a 10x10 grid.

Left to right; normal output, grid output and barnes hut output. The graph

still shows qualities of the graph, however, it is "squashed".

This squashed effect is currently blamed on the weakness of repulsive forces, however, changing the power of these forces does not have such a desired effect.Below is the same 10x10 grid of above with increased forces showing an improvement to some of the graph but not overall. This suggests that as the algorithm moves through the barnes hut structure, the repulsive forces should change in order to work best.

Some tests will be run first to test the behaviour here in order to formulate whether a changing force is required. But this shows promising results. The better news is, the FDP used for the Barnes Hut quadtree can also be used for my own Contraction approximation, which will hopefully be shown next week.

For now, I leave you with this, have a good weekend!