Ouch, that's what happens when you're cocky

Big ouch this time.

You may or may not know that the implementation for testing my work on Primitives and Multimatching uses an alternate method of storing edges (storing them within each vertex as a collection of adjacent vertices as opposed to edge components) - so in short, they're different. For the purposes of making things easier, see the definitions below:

• Algorithm A : Vertices are stored as "Component" objects with their coordinates, weight and position in the coarsening tree. Edges are also stored as "Component" objects, with pointers to their connecting vertices. Both collections of vertices and edges are stored as a "Graph" object.
• Algorithm B: Vertices are stored as "Component" objects with their coordinates, weight and position in the coarsening tree. Edges are stored within each vertex as a collection of pointers to vertices in the vertices collection (storing edges twice in both connecting vertices)

For context, it should be known that the coarsening algorithm randomly shuffles the edges in order to provide random matching (this uses Java native code and has negligible effect on runtime). For Algorithm A, this only shuffles the collection of Edges, however for Algorithm B, the collection of Vertices is shuffled. After each test has run, the coordinates of the collection of vertices (in either algorithm) is output into a file, and foolishly, output in the order they appear in the collection.

For Algorithm A, this has no issue as the collection of vertices is in its correct order. For Algorithm B, however, the collection is shuffled for the coarsening scheme. So when analysing the layouts, the coordinates are fed in the order they are expected - but with no account of the randomisation considered - ergo, very bad layouts with lots of edge crossings (yet when drawn, have some shape to them). As such, many of the results collected for the multimatching and primitive work, have to be rerun with a mechanism to reorder the vertices (thankfully an easy job).

So once again, negligence does not pay. Heh, nevermind, onward to new results!

<EDIT>

In the first dynamic implementation, there was a problem of the graph "wandering" out of view, and eventually collapsing in on itself due to some issue with the forces, resulting in a bad layout after changes (number of change were indeterminate). The reason for this is due to the update of the positions of vertices in the approximation - without updating these, the graph uses old positions, which eventually overcome the remaining forces and push the graph in some direction. Simple PostOrder update fixes this (after some minor changes in the code).

The tree, in this case, still holds information relating to all vertices - therefore the structure is no different and repulsive force approximation still includes vertices which may not exist any longer. Roll on the experimentation!

</EDIT>

Skittish

Another few weeks since my last update (or it feels like). So what have I been doing?

• Analysis of Runtime - much of the runtime analysis has been written into the draft chapters of my Thesis,  with the general idea that my algorithm is faster than a quadtree and equivalent to a dual tree - with the hopeful benefit of having better quality (equal to that of the quadtree or better). Much of the runtime results for experimentation have also been written up.
  
• Analysis of Quality - oddly enough the more time consuming task (due to my unnecessary and possibly wasteful time researching speedy methods for counting edge crossings). Thankfully, after some aid from Dr Chris Walshaw and some Googling, I have implemented a far more efficient method of counting edge crossings and reduced the time required by more than half of my previous methods. Unfortunately this still takes a lot of time for huge graphs but better 20minutes than an hour... With this done, I am not awaiting results so I can write them up and hopefully get my first chapter ready for checking.
  
• Dynamic framework - having designed and implemented a chaco-style method of importing "operations" into the application, I now have a simplistic dynamic graph drawing algorithm ready and working - featuring changes based on the users input (through the operations file) and some adaptability in terms of when to update the layout etc. Still needs a lot of work though, however, the main concept is there - next I will be refining this and implementing a means of measuring the dynamic matching I've been waiting to complete. Also, there are some peculiar behaviours I would like to investigate - so this may inhibit plans. I would also like to implement a similar method of graph drawing to that published by Veldhuizen - so we will see how it goes.

Other various tasks have been completed but I cant remember them, so hopefully nothing important. I will update again when I have more information regarding anything of the above, for now, worky worky work work, lots to do and not enough time to do it - challenge accepted!