Just a quick update today.
I have been progressing on with the multi-matchings and have finally got a version working, expanding on the edge contraction used previously and allowing multiple connected edges to be collapsed at once. This has been shown to work for any number above one and generates a much shorter multilevel/contraction tree.
In order to successfully achieve this, the method of storing the graph has changed. We now omit the Edges list and store all related vertices in a list attached to each vertex - almost exactly as it is stored in the chaco file, and exactly as implemented by Walshaw.
With every silver lining is that underlying cloud though, and here, that cloud is what I call "dumb matching". Currently, the algorithm reads through all vertices and if applicable, finds a match with any related vertices, however, this is only limited to vertices it is connected to, as opposed to a trail of connected vertices, leading to an independent vertex subset which is not maximal.
The "smart matching" implementation is paused, but will be underway when the "dumb matching" is successfully integrated into the current testing suite (due to the change in storage structures - existing code needs to be altered to accept both new and old data structures).
Progress on the report is unchanged at a level between slow and none.
The iV2012 conference has accepted my paper with some useful comments, unfortunately highlighting one of my fears with this work - that it is not particularly original, having reused other peoples work to generate something new. Regardless, this is good news so I am relatively happy.
That's all for now. I will hopefully include some descriptive images of the matching technique I've used in future posts when I have finished playing with my code and I will keep you updated with any other progress, and if course, if my research is ever accepted by the Research Degrees Committee.
No comments:
Post a Comment