Soon.... Results

Another late post this week. I partially blame my lack of concentration on tutoring and other extra curricular activities, but they're still excuses...

Anyway, monthly meeting with supervisors yesterday came to a happy conclusion: I no longer have to worry about implementing the Eades best viewpoint finder. Instead, I will continue with my implementation of finding the 'polhodes': http://en.wikipedia.org/wiki/Polhode. [May be incorrect but the description matches].

Essentially, it is what I have implemented previously; finding the two or three most prominent axis in the graph (greatest direction of edges) and then move the viewer perpendicular to them. Bad that I didn't find the paper but reassuring that I was on the right lines without knowing it existed.

Before this, I am preparing my results for the 2D versions of the algorithms. The testing 'suite' is almost finished and last night was the first night of leaving my application working away (as a test run to ensure no errors are found). I have a few simple changes to make, but I should have full tests running over the weekend, with my first set of real results on Monday.

After I have got these running (later today), I will be continuing with the 'polhodes' work so I can finally test the 3D graphs. Again, this shouldnt take too long what with previous coding already existing.

This all finally leading to me returning to the domain of dynamic graph drawing! In retrospect, I feel slightly let down that I have not yet started on it, now being in my second year. Could be worse though, so back to work I go! Will update next week, hopefully to discuss my results, if not, the failure of the testing suite, and the rest of my work.

Freshers Week and Doom

This week I have been distant from my work, helping the CMS Mentors. This has involved me helping the new University of Greenwich students getting settled in and helping in the lab days, similar to last year.

My work has been slower because of this, but due to an issue with my viewpoints research, I have been avoiding the continuation of my work. I have a meeting with my supervisors next week so hopefully that will help decide my next plan of action.

Today I have been writing (refining) the tests for counting edge crossings and edge lengths for the 2D implementations, and preparing for the scaling forces (changing the power of repulsion and maybe spring forces in order to find the best forces and determine a default scalar value).

I will be continuing  with these tests and will continue to think of a method to calculate the final projection so 3D drawings can be tested as well.

Will update tomorrow or next week dependant on progress.

Not as easy as anticipated , how original

A week since my last post and I am still stuck on the viewpoints gibberish. Unfortunately I am stuck at a crossroads, with no idea where to go (self -confusion and the internetz to blame mostly).

Whilst reading throughout the papers, I have been neglecting the limitations of my understanding, and have stumbled on a problem. When a drawing is rotated, the space itself is being rotated as opposed to the individual line segments (I also use this rotation as a form of user input to find the best viewpoint manually). When calculating the 2D projection of the 3D drawing, the coordinates used are those held in each vertex, which are the same as before, however, the viewpoint has changed, so in the ideal world, I would calculate the angle of the viewpoint, and calculate the change in position of each vertex/line segment... no.

Behold, in theory, there is an easier method. I could use the projection matrix used by OpenGL project the drawing to the 2D viewing area, to determine the line segments and run the various tests upon those. Woefully, I cannot find a method of doing so.

Another method I have just though up, would be to reverse engineer what's happening within OpenGL and use this. Unfortunately, I am less keep on the mathematics of it all, but it doesnt look like I have much choice.

I cant help but feel there is something I am missing in this, some easy method of doing this that I am overlooking. I am aware there is a test for occlusions within OpenGL, which may help testing Eades et al. 'Finding Best Viewpoints for 3D Graph Drawings'. I am sure I will find out soon enough, but I am still disappointed as I did not want to spend so long on something which is not a (notable) concern in previous papers.

I will update again next week, for now, have a good weekend.

Forever Reading (again) + additional crazy

Research is slow. Apparently, finding good viewpoints is meant to be as slow. Most of the techniques I have looked at concentrate on viewpoints which do not cause occlusions, which is computationally expensive. Occlusions are undesirable as it can hide information within the graph, however, I am under the impression these approaches work well for smaller graphs, but are less effective in larger graphs.

NB: there are many methods which use these good/bad viewpoints and have different approaches to calculating them

Larger graphs are very likely to have occlusions, no matter which angle the drawing is observed. Although still offering the better viewpoints (by calculating the viewpoint with less occlusions), I am starting to see why it is not used (or at least referenced) in other placement/drawing algorithms where the viewpoint is left to the user.

There are other approaches which I have yet to research but a naive first glances suggests this area is lacking interest from researchers looking for a quicker and more ideal methods for finding viewpoints based on more than one criteria (see Purchase for multi-criteria and Eades for implementing more criteria in graph drawing.

Now for some monthly Carl Crazy; when looking at graphs, the more we can see, the more we can normally understand about the graph, even in cases where edge crossings can be seen. For example, rotating a cube so it is observed at a 45degree angle, we understand a lot more about the cube than if viewed head on (you could argue a planar drawing does this with no crossings, but the graph is warped and edge lengths suffer).

Using this same crazy, if you look at an edge within a graph, you ideally want to have the view perpendicular to it (or you will be looking at it from an angle which shortens the edge) in order to see it. If we look at this on the whole, we would be looking for the average direction of all edges within the graph. If the view was perpendicular to this, the observer would be looking at a view which offered the maximum view of all edges in the graph, albeit with occlusions/crossings.

<EDIT> This is a rather silly version of Kamada and Kawai 88, albeit ignoring the normals of the image and instead choosing to use the average edge direction to rotate the graph. In practise, this isn't as adequate as one would have hoped, with large numbers of occlusions and edge crossings. May be best to stick to Eades et al.Best Viewpoints for 3D Graph Drawings).

Of course I will continue reading, but I will test the crazy regardless due to the speed increase it offers.

That's pretty much all for this post, here's a picture of some output to liven this otherwise boring post up:

finan512.graph, drawn using 3D quadtree and 2D contraction approx. with different forces for each. The testing of parameters will hopefully find output for 'quadtree' which closer resembles that by Yifan Hu (although currently it is very close to his output of MSE(2). )

I've been following my plan? WTF?

As the title suggest, I have atypically been following the plan I laid out last week, so here is my progress:

1. Changing QuadTree and Grid to Components - Complete
• Some issues came from bad refactoring
• Vertices and Edges have now been abandoned for the Component but may return during memory optimisation (smaller footprint)
2. Finish Testing Suite - Ongoing
• Currently researching methods for finding the best viewpoint (not necessarily most efficient)
• "Plug and Play" attempted but requires additional code in most cases, albeit minimal
• Tests for 2D mostly complete; 3D await for viewpoint research
3. Convergence - Complete
• successfully implemented the convergence finishing rule
• preliminary testing shows using a tolerance of 0.001 gives longer running times that 50iterations
• 0.002 is on par, any higher gives faster results (but results may be reduced quality
4.  Matching - Ongoing
• no real progress since last update but still have the option to coarsen all incident vertices to a selected vertex
5. Comparison of Algorithms - Not Started
• Waiting on 2. and 4.
6. Yifan Hu implementation vs Contraction Approximation - Not Started
• waiting on 5.

Most of the work is now dependant on implementing a method for finding the best viewpoint, which will enable me to write accurate tests for the 3D output. There has been no thoughts on which initial starting positions should be used for the fairest results, a comparison of pre-set and random positions will be undertaken.

I will continue to work with this plan as it seems to be working for me so far. An update will be posted later this week. Almost one year since my start, quite scary...

Weapon C: because Weapon X was taken...

As mentioned yesterday, my objectives this week have been a bit of a mess, so I have finally decided to put them into a reasonable path;

1. Component data structure for BH and Grid
• Change my previous implementations to use the same data structure for fairer tests
• Can/Should be able to add to Weapon C with own structures but will not be as fair
2. Finish 'Weapon C'
• Plugin functionalities ( whether using Component or own Data Structure )
• Tests ( edge crossings, angles, edge lengths; to be used ubiquitously )
• Projections ( dependant on speed but finding the best viewpoint for said tests ) 
3. Walshaw Convergence
• Old news now, but change from iteration based to convergence based (before default forces found)
• This should be applied so either iteration or convergence can be used
4. Matching/Clumping
• Finish off the clumping/matching I had started
• User defined sizes; find matching with 'n' vertices
• NB: several ways for this, which gives best results? only one way to find out, EXPERIMENTS!
5. Comparison of algorithms
• testing in Weapon C (testing done entirely by application, increasing params without user input)
6. Comparison of optimised CApprox against Yifan Hu's own results

As a side note; I should remember that using random positions initially can alter results, as vertices can be given a better placement in some scenarios. Dependant on the inconsistency of results, using strict initial positions may be better (or worse), we will see.

Going nowhere quickly

This week has been very slow. Much of my time has been moving between bits of my work trying to fill in the gaps I missed when originally implementing the different algorithms, and attempting to implement an efficient method for matching/clumping multiple vertices during the coarsening process.

The multi-matching has proven to be quite a difficult to implement; it is easy enough to match two vertices by just looking at the list of edges, it is also easy enough to match all vertices connected to one vertex with this same list, the issue arises when coarsening with a user given number (i.e. 3). This is all due to the way I have coded my implementation, it is easy enough to create a list of adjacent vertices for each vertex, but this would require a significant amount of memory.

I really shouldn't be concerning myself with efficiency and memory just yet, however, I dislike the idea of making an application slower just to implement a different method of matching. I guess beggars cant be choosers.

Other work has been preparing to change to the convergence finishing criteria as opposed to the current method of running the placement algorithm 'n' times (where 'n = 50', give or take a few). I have also dug up the Huang and Eades paper's for the cos/sin forces for better graph untanglement.

In a random 'crazy of the month' type deal, I am now concentrating on this convergence idea proposed by Walshaw (when a vertex no longer moves further than some tolerance, the graph can be classified as converged, using the cooling schedule of Davidson & Harel). I hope to find a way of moving vertices into more accurate positions, requiring less iterations of the placement algorithm (instead of my current "how to make the algorithm" faster).

I will of course also be continuing with the test suite which currently awaits my finished algorithms. Reading back on this, my work load appears to be quite a mess, with intentions to do different bits in the same time as doing what I should be doing. Maybe I can clean this up a little... I guess we will find out soon (yay more plans which will never see the light of day again).

That is all (I can remember) for now, I will update tomorrow or next week dependant on progress. Have another good weekend.