Battle for Barnes Hut

Over the past 2-3 days I have been trying to find cause for the compression of graphs when put through my Barnes Hut implementation, with my primary idea of doing so by expanding the algorithm to 3 dimensions.

This led to an unexpected output; the 3D interpretation  is drawn very similar to the 2D output from the original viewing angle, however, when rotating the graph, edges appear to be extensively stretched in the Z axis, the picture below shows the output for a 10x10 grid.

Left: 2D grid shown from the front and the side (verifying it is 2D)
Right: 3D grid from the front and side, showing extended edges in the Z direction

Note the graph is still compressed when viewed from the "nice" viewpoint. The behaviour itself is very peculiar, as there could be a number of causes. As both graphs are compressed, it could be the algorithm for applying and calculating forces that is causing the problem, however, I feel it may be closer connected to the quadtree structure.

What can be assured is the theory and methodology work, and it is only the refinement left at this stage. It is also likely similar problems will arise for the Contraction approximation, so the solution here will most likely be applicable to it.

As a premature battle plan, I will attempt to output all force calculations to check if any are doubled due to the structure of the tree, this would explain why some vertices are pushed further away and to some extent, why graphs are "squashed". Also, although I don't recall any large changes with using the quad tree, I will check again with Yifan Hu's work to ensure there are no differences (I'm confident I have not missed anything but I have not read the paper for over a month so always best to check).

In any case, the output should hint to the cause and should allow me to correct the behaviour.

For now there is not much left to report on, I am and will be continuing my investigation into the deformations and will update as soon as a breakthrough is made. For now, sit tight and if you can, enjoy the sun!

Rollin'

This week I am looking to complete the Barnes Hut work, my current task being to understand and explain why the vertices in the coarser graqgs collapse in on themselves, as mentioned in last weeks blog post (image below). Initially, I am expanding the algorithm to 3 dimensions to see what happens, as vertices need less force to pass each other (low chance of them being closer together due to the additional space), so should resemble the graph more so.

The next check will be to test dynamic forces, where the power of repulsive forces is increased the further you move from the original vertex through the Barnes Hut tree (as some vertices have been given a semi-reasonable layout, it suggests the forces are working at some points in the Barnes Hut structure, but not everywhere, this will test that behaviour).

The next few steps are not as clear at the moment but I will update my blog as I go. This is a short post to show my intentions this week, so for now, have a fun week.

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!

Just keep on driving...

Regular readers can probably guess my next few words - "I'm continuing with the Barnes Hut work this week".

The work is going slow and much of the time is trying to understand some of the behaviour exhibited by my code. For a brief explanation of what I am attempting to do, see below, but the issue remains the forces are not being applied (or in some cases, calculated) correctly. As far as can be seen, the tree structure itself is correct (printing out the tree shows that each vertex has a region of its own as opposed to two vertices per region), and the problem remains in calculating the forces whilst climbing the tree.

Barnes Hut quad tree idea (simple version) (octree for 3D)

Set up structure

• split the plane into 4quadrants
• determine which vertices belong in which quadrant
• if a quadrant has more than 1 vertex, split into 4 and continue until each vertex occupies one quadrant
• ensure to calculate the weights and coordinates of each quadrant after

Use in force directed placement

• Get the parent quadrant of the current vertex
• check if any siblings in parent (in the other 3 quadrants)
• if any, calculate forces between vertex and that quadrant
• move to the parents' parent
• check if any siblings and calculate forces as before, repeat until the root is reached

The rest

• calculate the spring (edge) forces
• calculate and apply displacement

The theory is pretty air tight from my perspective, apparently I am limited by my coding abilities. If a reader can see anything wrong with this, please let me know, thanks.

Errors

As I mentioned before I have been having some issues with this technique, the biggest being StackOverflow exceptions caused by the recursion when making the tree; in some cases the tree is too deep and causes this exception, the cause being two vertices are initially extremely close together.

Currently I am attempting to get output at all, it appears that some forces are being calculated incorrectly which cripples the rest of the graph. Ambiguous I know but when I know more I will update (just writing about it helps me think about the problem and what the causes could be).

I will update when i gather some more useful information, until then, have a nice day.

Back to work

With the epic awesomeness of greatness that was my holiday over, it's back to work.

Following the advancements in the grid approximation I am not continuing with the Barnes Hut and what I am now calling (until a better name can be though of) the Contraction approximation, named after the methods I am using to coarsen the graph (Readers can feel free to submit names in the comments).

The Barnes Hut quadtree is proving somewhat of a chore, my implementation of developing the tree no longer calculates correctly and throws a StackOverflow exception which isnt particularly nice. I will mostly likely revert back to a working version instead of fixing it again.

As the BHTree and Contraction approximation both use tree's, I ideally want them to be as identical code-wise so they can be better compared (similarly for the grid but the structure is very different so cannot be reused).

For now, there is not much else to mention, work has been slow (as should be expected the day after holiday) but is looking to speed up as the week progresses. Hopefully a more constructive update later this week.

Gotcha!

The grid approximation output now looks as it should, thanks to some carefully planned and intelligent testing (aka calculated guessing). As I had expected after my previous attemptsfailed, the parameters used to scale the force between a grid and vertex were too low.

Actually, the parameters were far too low. I had been using the parameters used in Walshaw's work; -Cwk²/d, where C was 0.2 (or some value less than 1). For my implementation, the better results are using a value of 50. These are preliminary values, a more suitable value will be found in the future.

The higher this value, the more a grid will affect a vertex (so pushing the vertices out of its square and not keeping it on the edge). Below is a few images to show the differences. On the left is the force calculation, on the right, the output.

0.1 * weight * distance As can be seen the graph is sticking to the grid.
0.5 * weight * distance Same again, the graph is sticking to the grid, but the vertices within squares appear better spaced.
1.0 * weight * distance As above, the structure begins to look clearer at this point and the graph resembles its normal self (loosely)
5.0 * weight * distance As the force increases, the graph looks more and more as it should (with no grid) but there is still vertices sticking.
25.0 * weight * distance Skipping ahead a large value, the graph looks almost normal again (I know subjective), but there are still vertices clumping
50.0 * weight * distance Skip to another larger value and the graph now looks as it should (albeit "squashed"). This output resembles that given in Chris Walshaws paper.
1000.0 * weight * distance I wanted to see what would happen with an extremely large value, so I put in 1000. The graph takes an unusual shape, it looks compressed but also very smooth

Holiday Week of Wonder

This week will start off my first major holiday of the year, so I'm in a rather happy mood. Unfortunately, this starts Wednesday and leaves only today and tomorrow (Mon and Tues) for work. I have therefore decided to spend these two days "profiling", organising and protecting my existing code. Refinement of the approximations may be continued but as this is a long process, I feel there is not enough time to warrant starting what I will only pick up again after a weeks break.

I'm also hoping the clearer and more organised code will help in understanding the behaviour of some of the algorithms; such as why, when taking into account all parts of the grid containing vertices, the vertices stick to the outside of their parent section (as shown in my previous post).

This is most likely to be my last post until I return next Tuesday, unless I discover anything interesting hidden in my work, so for now, have a fun week working and lets all prayer the weather clears up, and don't let the thought of me relaxing in the middle of a field, with the sun shining down on me, drinking an ice cold beer, put you off your work.

<EDIT>

Having monitored the output from a single randomly chosen vertex (I chose vertices[0] heh, totally random), and printed the coordinates and grid reference in order to watch its path. The test runs 50 iterations per coarse level.

During the beginning of each level, there is a quick movement due to the change in the environment (two vertices being placed in the same place as one for example). This "cools" off due to the cooling scheme as the level progresses. These changes become less powerful as levels pass.

In the last 2 levels, the vertex skips between two grid squares, suggesting the forces push it out of one, then the forces from the new square push it back. Peculiar behaviour. I will need to check with the forces between vertex and grid to see what's causing this but it seems likely the forces do not match up (they're "unfair").

</EDIT>

The output is a lie...

Further work on approximations this week/month. Output from the grid approximation looks promising but appears to be affected by the grid in unintended ways as mentioned in my previous approach. The Barnes Hut Quadtree being used by the FDP algorithm needs much more work, though the structure and tree itself is fine.

Monthly meeting yesterday, minutes hidden from you all (mwahaha), but are found in the usual place. The meeting itself was not as comfortable as normal, I had very little work to show (as most of my developments have been in the coding domain and have very little observable outputs at the moment). We did however mention my intentions and the work I have done so it was not completely in vain.

Continuation of the approximation refinement is planned for the rest of this work and tomorrow, with some of my time being spent on some mandatory postgraduate courses  which happen to take up the majority of my time as I am forced to print every answer one by one (here's an idea, wait until the end and then show the user a page of their answers, or even better, don't use flash).

Sarcasm aside, I am still trying to stop my grid approximation outputs clumping together and will update here as soon as I have results. My last few attempts, using all "boxes" containing vertices as opposed to the immediately surrounding boxes, changing the weightings, changing the strength of forces, changing the way vertices move between boxes, have not produced any significant changes. However, I feel I am getting close to a fix so bare with me!

Not much else to say I'm afraid, so here is a picture showing vertices being stuck to the border of their grid, drawn by creating a new grid every FDP iteration (purely to see what would happen, I don't intend to do this as that's madness and very inefficient).