Vertices, No Edges (not disconnected graphs)

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.

Multimatching - back to you is it?

If the title was an unsuccessful hint, this week I have been working on the multimatching algorithm for replacing the currently used edge contraction method. This has been started countless times before and progress has been made - however, due to the amount of time between my work on it, I've had to spend the majority of a day catching up on my own work.

Additionally, I realised that some of my work is not longer applicable - the paper I have written for the IV2012 conference uses the edge contraction for comparisons, but the newer multimatching uses hashmaps for its storage (and other tasks), resulting in an unfair comparison. I now get to choose whether to continue with the previous approach and provide compareable results or continue using hashmaps for this report and provide new results. <EDIT> In a sudden moment of clarity (and remembering the obvious) - the multimatching method should work for edge contraction in the same way, albeit a little slower. Therefore I will be using the multimatching method for all result. </EDIT>

Much of the report itself has been put together (as mentioned in my previous blog entry) but no significant work has gone into refining it. Some may call this laziness, I call it preparation and excitement for my return to coding. In the mean time, I am going to return to the code and hopefully finish that before the end of the week. I will update again when any progress is made. Sayonara!

Better extinguish my laziness (again)

I recently remember I had a blog to continue, so before I let it become one of those "I'll do it later" tasks, I better pull it back from near-extinction.

Last week saw my return after my Easter Holiday (Wednesday was my official day of return to be specific - should it come up later), which also saw my return to marking. Fortunately my marking was complete and I was only required to transfer my marking from paper to its required digital format. Additionally, I spent my time working on little bits and peices (my way of saying I may have procastinated a little).

This week has seen my return to paper writing! Although no part of me enjoys writing papers, it was comforting that I have already provided myself with a template for my intended technical report, and having written a conference paper for IV2012 (of which I should hear whether it was accepted or not on the 22md April) it has made it a lot easier for me to continue onwards.

I am hoping to complete a reasonable draft (for myself) this Friday, so I can begin my process of improving the report - similar to the approach I took with the conference paper, which didn't turn out so bad.

Having read through my previous attempt at this report - I am realising I will be returning back to my code soon enough in order to gather some more results (words cant describe how happy this return makes me feel). These additionally results will hopefully identify the causes of some of the behaviours present in my work.

I will update again soon, for now, I leave you with Professor Meowthykins to brighten up your Wednesday: