Good God that looks horrifying...

Small Update today, the approximations are beginning to take shape, or not if you take a look at the output. Below are some images of some well known graphs in the field of graph drawing, showing their distortion.

 The image shows, from left to right; 3elt, a 10x10x10 grid, data and a 55x55grid. All are drawn in 2D. As can be seen, the output resembles its better drawing (see previous posts), but the global untanglement is not adequete.

This is most likely due to the calculation of forces between grids (if you see, the tangles generally occur over the grid lines which suggests the cause), which will need to be experimented with to get the most pleasing layouts.

The drawing times are far more impressive:

Graph	Normal (ms)	Grid (ms)
55grid	67850	9186
3elt	168175	19330
data	62814	12513
10grid3d	8311	2112

The runtime is far smaller, proving the strength of the grid approximation. The Barnes Hut implementation will be posted as soon as a reasonable output is given. For now, that's all folks.

<edit> Note to self; the grid variant can either use the average position of vertices or go through the vertices in an adjacent square to the current square. This is the cause for the incredibly fast results currently. Also, if iterating over the vertices instead of the average, the number of squares should be reduced so less vertices per square </edit>

Difficult Difficulties

Surprise, I'm at a stand still once again. I am having some hardship getting the approximations to work they way they should. Previously I showed images of the structures built on top of graphs, which show a graph being successfully split into grids or into a tree at multiple levels in the multilevel paradigm.

Along with this I was able to get a very crude example of the Barnes Hut working with a singular level, however, pushing (A better) a newer version onto the multiple levels is not yielding results (other than exceptions after exceptions).

The cause of this is still to be identified but its likely I have made assumptions in my code somewhere, which is stopping it from moving between levels. Only a matter of time before the cause is found and fixed. This section of my work has taken a lot of time now and, although ive said this before, more needs to be done to get it out of the way. Other areas of interest such as smart placement of 2 vertices from 1 (when moving from coarse to finer graph) and other optimisation ideas for the calculation of repulsive forces is required.

Just a small, slightly unhappy update on my progress. I WILL have results soon, even if its the last thing I do.

To keep it interesting, a picture of what is becoming my favourite graph: data, with the Barnes Hut structure on top (minus a few borders due to cropping and display area of the output).

Where's the finish line?

Once again falling behind my own crazy schedules, this time out of my past laziness.

I have spent far too long, over a month, on the approximation work due to my use of time, and as a result, I am falling further and further behind as I did not leave enough room to fix the problems I/we/the universe knew I was going to have. To add to the time dilemma, its also Iivigilation time and as it happens, exams love me so I have a lot of invigilation.

I am now fully concentrating on the approximations completeness and am changing my deadline from end of the week to weekend/early next week. Engines are on go and, oh damn, making this blog post is using that time up....

Looks like I will be updating as soon as I can, in the mean time, here's a picture of the grid approximation (the squares edges are based on the coordinate boundaries within each square and not just a load of lines I've put on top of the image). Barnes Hut is being a little more difficult.

As I havnt shown any pictures for a while, here are the outputs from my approximations at the moment; the grid variant shows  boxes on top of the graph (these are drawn based on the boundaries of each box, not just lines scattered wherever). Each box contains a list of vertices within it, boundaries for the coordinates of those vertices (if they go over they move box) and a centre of mass.

The image below shows my bugged up version of the Barnes Hut approximation. The boundaries on lower levels are wrong which suggests the problem is when the boundaries of the parent node are passed to the child node to make their own boundaries, but its not clear in my code.

NB: the size of the grid can be changed but requires some experimentation to find the ideal parameters (as mentioned by Fruchterman and Reingold).

<EDIT> Figures I would find the cause after I post the problem; this shift to the left is due to the lower levels having boundaries adjacent to the lower x boundary of the entire grid. This had been overlooked as I had assumed the problem was due to the values I had been passing as the boundaries, when instead it was ignoring these inputs and assigning incorrect values. Bad that I didnt notice this before but now it works so I'm happy.

Few more changes to my coarsening approximation scheme and it will be time to get the results.

Below is a new pic of  the Barnes Hut working in 2D (top cut off by accident due to the size of the viewing window so ignore the missing boundaries please).</EDIT>

Seminar Win-Fail-ish?

Seminar Completed! Achievement Unlocked: Ability to talk in front of people!

So my seminar for this year is over (if you couldnt have guessed by now), and as far as I can tell, it didnt go horribly wrong. Albeit the seminar coordinator wasn't there, only about 10 people turned up and I cant remember anything I said, I'm still counting this as a win.

Moving on to future work, I have a plan to finish my approximation work off, hopefully proving my method of approximating values is better than my implementation of other techniques. Also, I will be looking to complete the "smart placement" of vertex function in the code (this doesnt need testing as it is proven to work).

Other than that, not much else to say, other than "enjoy the sun, i'll be here in the cold glow of my monitor".

See you next time

Impending Dooooooooooom

Seminar is tomorrow.

...

I'm a little nervous...

In any case, last week was a 3day working week so not a lot of work got done unfortunately. My presentation for the impending doom is coming along nicely, few improvements here and there and a few animations may help people understand what's going on, but its nearly there.

Biggest problem is my fear of public speaking. Practising in front of only two people, whom are very good friends, still gave me the worst drymouth imaginanable. Odd considering I can tutor complete strangers without an issue...

Just got to hold it together and I'll be free! (to do more work). So no doubt I will update tomorrow with a Yay or Nay, so stay tuned for Amazing Awesomeness or More Doom.

NB: Most coding has stopped in preparation of the seminar, will get right back on it tomorrow!