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.
No comments:
Post a Comment