Planning before the launch (or lunch)

Being happy with  my quad tree implementation (for now), I have begun on my contraction/binary tree approximation.

Most of the work has been paper-based, refining my plans for the easiest and less disaster-prone way of coding it out. Unfortunately the desired plan requires me to change significant amounts of the code, however, the changes are simple in theory and can be applied to older implementations with ease (of course, now that I have said 'ease', I'm doomed).

The coding has been started and I am roughly half way through the implementation, so I expect it completed by next week (including refinement). For now, that is all, but I intend to upload some scans of my theoretical scribbles, with a little discussion about what I'm attempting to do, in the near future.

For now, you don't get any pictures either, ha!

(fine.. here's one showing the normally dense hole in the centre of the graph, 3elt, being pushed out like a gravity well).

Forward, Upward, Progess, Stronger

Behold, I have fixed the z-expansion issue!

The cause? A small insignificant piece of code I had overlooked as I made the incorrect assumption it was in working condition based on its use in other force directed placement algorithms I have implemented (FR_limited, means nothing to you but its a personal variant of the Frutcherman and Reingold algorithm).

The detailed cause? A small piece of code used to normalise the forces when applying them, incorrectly added the same value twice. This was probably a change of mine made several weeks ago (used as a way to monitor behaviour in sections of the algorithm - not really important), and without changing it back, forgot about it.

Interestingly enough, with this fixed and my previous output resembling how the graph should look, the output this time does not look adequate, having undone whatever I did last time (dammit). Fortunately the changes where on refinement techniques so I just need to continue following my notes to get back to reasonable output.

A video, along with the previous posts video, will be available shortly. Below is the output for 55grid, drawn unoptimised and still buggy, in 2 seconds.

Next, my own contraction approximation. This will require some large scale changes to the coarsening scheme and Quad Tree currently employed, but has already been prepared for in the code (to some extent).

I predict this will take about two weeks assuming there are no stubborn problems, so the real time could be anywhere between tonight and 6 months from now (I think my expectations can be a little off sometimes...). Regardless, I will hope to have it done much quicker than this recently fixed problem took to resolve.

More Changes

Once again the output has changed, and although I cant tell if for better or worse, the results are making me a little happier.

Behold, 3elt;

As can be seen, the original graph is not exhibiting the structure as shown in my previous post (and is not easy to determine which graph is actually being drawn). Although the increased randomness and unorganised structure, the Z-axis expansion has changed to show a ball like structure (as opposed to +ve to -ve change shown previously). When rotating, the graph appears ball like as I would have liked (instead of the flat structure normally drawn), but the edges through the centre of the graph give it the unattractive view seen above.

The changes to cause this were insignificant changes to segments of code, so I will investigate how these segments affect the z coordinates of edges. Until I have further information, I would leave you with a video but Blogger is being rather difficult about playing it, so I will edit/upload when I can.

Why does it lie!

Interesting development last week, changing the order of some of the code and fixing some minor problems gave a slightly different output. Observe below;

The graph 3elt drawn in 3dimensions using the Barnes Hut approximation. As can be seen, the graph is drawn very well (much like outputs seen previously) when seen from the front (0,0,1 > 0,0,0), however, when rotated (1, 0, 0 > 0,0,0) the view shows the same z-expansion shown previously.

This makes this work, the most awkward and infuriating peice I have come across thus far. The code is now clean and most errors identified and fixed, but this output is awful. From one direction, the graph is fine, but any other, it isnt? What kind of sorcery is this? Why does my algorithm hate the z-axis? What is the significance of edges changing direction half way down? is that 0,0,0?

As always, I will continue to search for my mistake and will update accordingly. For now, here is my favourite graph, data, showing the same problem.

Ripping it to Shreds

As can probably be gauged, I'm very bad with estimating how longs things take. The weekend plan went to hell when unexpected circumstances left me without a laptop/computer (and there's only so much you can write on paper before thinking "can I even do that?").

I have been dropped to ripping my work to shreds to find this cause, and low and behold, I have a very good idea what's causing it. The problem lies in the repulsive force calculations, it seems as though the algorithm is taking nodes of a tree which would otherwise be null, or taking its own branch, and adding the additional force.

As my coding forbid this, it's my theory that I have hacked something up elsewhere, which caused the siblings of a child to be included in the force calculation, even if they're empty quadrants of the quad tree. My code-cleaning made this a little easier to read as the hacked code is hidden from plain sight.

Whether or not this is the issue is subject to some testing (once I finish re-engineering the code), but one thing is now for sure, the problems are with the forces, specifically repulsive force (thanks to some digging, ripping and shredding). 

I will update again soon, in the mean time, enjoy the wonderful cloud cover outside.

ReRezzed Up

Apologies for the lack of updates this week, I have been working on some large scale changes to the code (having a kind of clear-through) to better my future productivity.

Most changes involve the data structures, system architecture and the assortment of algorithms hacked together. The plan is to make it easier for me to spot the flaws, as currently I am having issue after issue, these changes will aim to point out the issue when and where its happening. I believe I tried something before to better this but that was much smaller.

The Barnes Hut approximation was still have issues Monday-Tuesday, with the causes still alternating between algorithm and refinement. A clear head after these changes (and maybe even a better understanding of some of my code) will clear this.

Only a small update to ensure I am still here working, but everything will be back on track over the weekend, where I intend to finish this fight with approximations, once and for all, Mortal Kombat style. So I leave you with these words of wisdom from my childhood and will update tomorrow or Monday, so stay tuned;

FINISH HIM

Limbo

Last time I described my plans for tackling the problem os squashed graphs in my implementation of the Barnes Hut quad/octree approximation for a general graph drawing algorithm. I have since implemented such plans and found something interesting: nothing.

The results are inconclusive, the animated drawing of the graphs shows that convergence is met quickly but is not achieving a good layout, the refinement of forces led to no real improvement and the output each time a force is made gave me a long list of numbers, none which are significant (none doing what it shouldn't be doing).

In retaliation to the animated drawing, I theorised that the cooling schedule could be affecting the algorithm reaching a local minimum, however, changing this led to no improvements. I am/will be researching Yifan Hu's cooling schedule to see if this differs but I don't recall any large changes.

As the edges are both too long and too short, it suggests the problem still resides in the force calculations, however, testing and improvement led to no significant or "better" changes to the layout.

There is a ray of hope though, the extensive stretching of edges in the Z direction suggests an error within the code or a miscalculation somewhere, which could be the cause of other issues, predominately the compression. Finding the cause of this stretching is my one of my next tasks.

That's all the news I have for now, so as a parting gift, here is the graph 3elt (though it looks closer to data so I may have labelled it wrong) drawn in 3D.

P.S. I have now moved all images regarding my research into a timeline-folder type system which allows viewers to see my work from beginning to end. It's quite impressive to see progression from simple 3 dimensional cubes to massive graphs. Hopefully I will be make it available soon!