The Post Christmas Something

Although we started back at work two weeks ago, this is the first I've remember to update (and by the looks of it I haven't updated in a long time). So, what news do I have to share; following from the last post, I have been spending much of my time observing the cooling schedule, I have also been working on the Technical Report for the MGF algorithm (splitting that into a Technical Report and a separate paper for the Multimatching stuff due to crossovers in the text), and making some progress on the dynamic works - although progress is slow due to my dislike of the cooling schedule (which is arguably not designed for dynamic drawing). First things first;

Cooling Schedule

The cooling schedule has been a main aim of the work, and in preparation of questions that may arise in the Viva, I have continued my revisit to previous implementations of Octree and Multilevel Global Force approximation. The aim is to ensure I know how the algorithm works and why it works (achieved long ago but experience tells me to question whatever I think is right). 

The cooling schedule is used alongside the placement forces modified by Fruchterman and Reingold, to limit the movement of vertices. The forces themselves provide a vector and the cooling schedule reduces the magnitude, stopping the algorithm when the magnitude (or average magnitude of all vectors) is below some tolerance. The forces themselves are too strong to ever be less than this tolerance, and so the algorithm is entirely based upon the cooling schedule. 

The reason this becomes important is the crossover to dynamic graph drawing - if a cooling schedule is used, the algorithm will inevitably reach this tolerance and so will need to be reset after any change. How the cooling schedule should be altered after changes is yet to be identified (research has not highlighted this with most just resetting to the original value or not highlighting the issue). 

The "original" graph drawing spring embedder implemented by Eades provide placement forces which do not require such cooling schedule, and instead uses an iterative approach. This may introduce a problem of layouts never being found - but I have yet to see a multilevel dynamic algorithm using these forces. May be worth looking at, maybe not. For now, the few attempts I have had at identifying a cooling schedule which relates to the convergence of a layout have hit brick walls, and so I am moving on with the dynamic work before I waste too much time.

Technical Report and Multimatching

The technical report, which has now been going for well over 4 or 5 months now, has finally reached some kind of end point - with only some checking and small editing required. I have spent a large amount of time checking the implementations used (when writing the paper - different to my more recent multimatching algorithms) so I can better discuss the results. 

Specifically, an analysis of runtime - including a breakdown of how much time is spent within each approximation structure, how many levels exist in the approximation structure (octree is limited to 11 or 13 to avoid stack overflows, MGF is limited by coarsening - much much higher), and how the structures affect convergence (the answer is: screw the cooling schedule). 

In addition, I have now split the report into a report and a paper specific to multimatching (as intended long ago). The multimatching approach has shown to decrease the runtime associated with the MGF approximation in comparison to standard edge contraction, and possible my own implementation of the Octree. However, it is still much slower than the algorithm used by Hu due to the coarsening technique (identification of MIVS is a much better method of tackling sparse graphs it seems, and has yet to be extended to work MGF, if it even can be).

Dynamic Drawing

So far, the only sure thing is that the operations implemented work, resetting the cooling schedule after each change (rather messy and a lot of work required to smooth this out). There is still a lot of work to go before I'm happy to call the algorithm dynamic, but have been limited by my problems with the cooling schedule. Unfortunately its come to a case where I have to bite the bullet and continue as is, and either improve or explain my choices later on.

The approach is much similar to other dynamic approaches which focus on smaller graphs (extensions of the spring embedder of Kamada and Kawai, and Eades), as opposed to the literal dynamics approach implemented by Veldhuizen. An implementation of the Veldhuizen algorithm was once attempted but due to problems understanding the next, was never completed, so there is nothing which can currently be compared (other than a user interface - in summary, he wins... for now). 

Over the next few weeks I will be implementing the dynamic matching and collecting results for that work (with the intention of writing a paper), followed by some research into a type of "Mental Movement Map" for the movement of vertices at different levels of a dynamic multilevel scheme (as discussed in a previous post).

After this, or during this, I may also revisit the cooling schedule with the intention of making it more representative of the progress of a layout. But for now, I am running out of time and should focus on the more related subjects of my Thesis. I will hopefully update you again soon, depends how guilty I feel regarding my progress. 

Until next time, cya!