General Update 3.1.607-33

It's been a bit of a busy week, but I'm almost there; our draft conference paper for IV2012 was finished Monday, or Tuesday (it's all blurred into one long day...) with some of my own corrections made yesterday and my supervisors comments today - so all in all, its going well.

Today is our second meeting in a month (mother of god...) and no doubt will focus on how to improve on the conference paper, and if the School budget will allow me to even present at the conference. I would like to take this chance to say "small papers are the best!", due to the ease of writing and not having to explain everything in the explaining of everything, everwhere.

There is no much else to discuss this week, but in the mean time, here are some graph drawings from the past month. For each of the images, the drawings from the coarseing tree/contraction approximation are on the left, and those from the quadtree/octree are on the right. Click on the image to view in higher quality.

 

10x10x10 cubic grid 

1000 vertices 2700 edges

 

3025, a 55x55 square grid

3025 vertices 5940 edges

 

3025 edit, the 55x55grid from above with opposite corners connected by edges

3025 vertices 5942 edges

 data

2851 vertices 15093 edges

 

 whitaker3 (supposed to be a rectangular drawing but some part of my algorithm forces this warping)

9800 vertices 28989 edges

 3elt

4720 vertices 13722 edges

 4elt

15606 vertices 45878 edges

 finan512

74752 vertices 261120 edges

 sierpinski10

88575 vertices 177147 edges

dime20

224843 vertices 336024 edges

Super Special Awesome News Batman!

Looks like I finally have a deadline for my paper-related nonesense; this time the aim is for a small 6-page conference paper for Information Visualisation 2012. The deadline is 1st March, which gives me 2 weeks to write a 6 page version of something thats taken me several months, and as many would agree, far longer than it should have.

The great news is for the paper, I will not have to explain anything and everything that might be linked to the subject, and will provide me some experience of reducing an idea into a very compact document - a useful skill for journals (so i'm told).

On top of this, I have finishing the results half of my document having fixed a bug in my implementation of the quad tree approximation (apparently I cant change small peices of code without the algorithm freezing for 3hours on a 75k vertex graph...). That will be sent off to the supervisors today in order for them to look over in order to prepare for the conference paper.

For now, I will stop procrastinating and get back to writing. Sayonara.

A developing topic

For the past few days I have been collecting, preparing and discussing various output drawings from my graph drawing algorithm, comparing to that used by Yifan Hu. It was always an interest how the different approximation techniques affect the output (a bit obvious, considering its the only difference), but it is becoming more and more prevalent in smaller graphs.

The contraction technique causes a final approximation tree with a root and two children; each child with a weight summated from all the vertices it models, which is used when calculating how much force that supernode exerts on a singular vertex. As there are only two children, in comparison to the quadtree's 4, or octree's 8, it causes the graph to warp around the vector seperating them (due to one side of the graph pushing the other away and vice versa instead of an all outward force).

In comparison, the quadtree pushes out in 4 directions, which causes a much more uniform drawing. As mentioned before this technique is more prevalent in smaller graphs, which much large graphs looking much more like they should. As a brief experiment, I took out the weight from the repulsive force function, which as expected, reduced the stretching (unfortunately, it also caused the collapse of global structure, a result of weak repulsive forces between supernodes and vertices).

The future work on matching will provide some more critical evidence to further investigate this effect and how the contraction approximation can be altered to tackle it (without having to match large numbers of vertices - 8+).

Damn You NetBeans!

When testing the Multilevel force directed placement algorithm, with no approximation, for multiple parameters (running 100+ times), be wary not to agitate NetBeans. Having attempted to delete a different project, I have now caused a verification pop-up which will never close.

I have come across this once before; the pop up wont close until all java applications have finished running - I had previously thought I found a way past the bug, however, my actions are limited by the running application which I want to avoid stopping prematurely, so I can't play around by closing related Services. As a result of this pop up, I am unable to use ANY features in NetBeans whatsoever - so am unable to run or edit any other of my programs until the others have finished

To further improve on this situation, the application has been running all weekend and still not finished.

Bitterness aside; during the end of last week I made some more progress on the papers - collecting some output images to include and compare, collecting results for a wider selection of graphs (for comparison against Hu), begun testing on the quadtree for the wider selection of graphs after some minor changes, and made some further progress writing for the second paper - though realising I have more research to do in order to investigate the effects of different matching techniques.

This week I will also be aiming to begin implementing the dynamic algorithm given by Veldhuizen - as an attempt to escape static graphs.

Behold, the Things To Do Notepad!

This week I have made an incredible discovery: there are notepads dedicated to daily To Do lists available at the CMS School Office. I guess its not that big of a deal but now I can keep record of what I have done and what I need to do in clearer detail.

So, since my last post (and acquisition of the To Do book), I have:

• Finished generating the charts required for a comparison of the Contracton Approximation and Hu/Barnes Hut Quadtree approximation. [prepared]
• Discussed the comparison in runtime and quality [written]
• Explained the relationship between the size of the output area and the behaviour of the FDP algorithm [written]
• Explained the relationship the strength of repulsive forces and the size of the graph [written]
• Organised some of the output images (subjective results) [prepared]
• Discussed the choice of default values for graphs [written]

 In addition, I am also currently:

• Discussing subjective results (output images) [in writing]
• Generating new results for a wider range of graphs (specifically those mentioned in Hu's work) using the "default values" gained from the experimentation [running]
• Generating normal Multilevel results (no approximation) for comparison to test data [running]

And for future work, I have planned to:

• Organise references for the papers
• When complete, analyse and discuss the results of other graphs (using default values)
• Critically analyse the subjective results
• All the multi-matching stuff/things/work

Just a small insight into the week in a quick and easy to read format (though without context its all pretty meaningless, but thats not so much of an issue).