Multimatching and "Trailing" Results

After my last post, I have run some tests using the four matching techniques and collected the results (though the real test was to see if the trailing worked as expected). Before this though, I had a meeting with my supervisors (post-viva) and discussed the results of the viva; to summarize  all appears well (unless there is some secret panic i'm unaware of).

Some other topics of discussion:

• complete the Technical Report for the work on Multilevel Global Force Approximation and Multimatching
• Check how much the levels of the multilevel scheme change when layout is pushed back to coarser graphs when using MGF (used to keep the approximation structure up to date with new positions of vertices)
• Output the graphs (all or some of the coarser graphs) into one display area
• Output layout to xyz files so they can be visualised through other applications
• How does the "trailing" actually help?

Most I have yet to complete.

Moving on to what I have completed this week (and back to my results of the multimatching). For the Dynamic Matching work - I have had to alter the code so it no longer uses Arrays, and instead, use ArrayLists. This now ensures I can alter the graph when necessary (required for dynamic graphs) - other data structures are available, such as HashMaps or other ADTs, however, most of the algorithm used here require looping over the data - for which ArrayLists are considered better (Google it for a more in depth discussion). 

I have begun working on an "Operations Manager" which will house the methods for altering the graph (removing, adding or editing vertices, edges and hopefully subgraphs). More work is required on other aspects of the application before it can be considered a dynamic graph drawing system.

Moving back to the multimatching; for my most recent results, there is only a very weak correlation between the degree of vertices and the matching method used - not nearly enough to be able to identify the best matching number before coarsening (further analysis may improve upon this but for now it is not a consideration).

Now for some good news, the Trailing matching mechanism. So far, results show a noticeable decrease in the runtime required to generate layouts for the graph - so far, an average of about 25% reduction but have seen up to and over 50% in add20 (from 13s using standard edge contraction, to 6seconds using trailing with edge contraction - with comparable layouts). Further results will be given when I have finished analyzing the data and fixed a few irregularities. Unfortunately, these results are still not as  good as the Octree (runtime and edge crossings count).

I have 101 things to do, so for now that is all. I will update again next week. Sayonara.

Multimatching and Clustering Techniques

In a bid to complete some older work before moving onto Dynamic graph drawing problems, I have focused  on the multimatching once again. As a form of clustering, there is much research already out there which identifies the most efficient methods, the most useful for graph preservation, most useful in given scenarios for each graph type. Unfortunately, there is far too much information to read through for such a small task in my research.

In regard to this, I had implemented a multimatching form of clustering which when given a matching number, m, the matching/coarsening will group m vertices to form a new vertex in a coarser representation of the graph (as opposed to edge contraction or identifying a MIVS). To recap, I was identifying a way in which to reduce the time required to draw sparse star-type graphs, and to achieve an approximation tree similar to that of the Octree (primarily the star graph thing though).

Having revisited the multimatching results; there is some relation between the matching number and the average degree of vertices within the graph, albeit, making only a small difference to run-time (a few seconds under the 30-40 second run-time for add32). Nowhere near the reduction I wanted.

Following these "bad" results, I investigated other approaches for clustering, with the aim of reducing the run-time further (and hopefully improve drawing quality as well). With multimatching being the first, the second was using brute clustering - where all adjacent vertices, if not matched, are coarsened to form super nodes  regardless of the degree. This is theoretically bad, as it will generate several heavy nodes, and many smaller nodes (composed of the left over vertices). The approach focuses mostly on star type graphs as opposed to sparse graphs.

The third is oddly named trail finders. Analyzing the degree of vertices within graphs which cause the MGF approximation scheme issue, shows that the average degree is 1 or 2 vertices (with very few having 3 or more). Therefore, it is assumed (and backed by analysis of drawings and chaco files) that trails of vertices exist, where one vertex is connected to only one or two others to form strings of vertices. Therefore, multimatching and brute clustering will make little difference to standard edge contraction ( when edge contraction contracts the graph to a star graph, it also becomes obselete). Finding these trails and coarsening them before other matching techniques, means [in theory], the algorithm finds a better matching.

Currently, I am awaiting results which test each of these in order to identify the best approach for the graphs add20 and add32 (with the aim of identifying similar graphs through analysis of the their degree when being read from the chaco file). It should be noted, the adaptive matching described in Hu's work (which changes from edge contraction to MIVS when edge contraction fails) has not be implemented or tested due to difficulty integrating it into the MGF approximation scheme. 

Initial drawings show an improvement in quality when using trail findings, but runtime has not been compared yet. As this is a relatively small topic in terms of thesis, further research is unlikely, and therefore the best of those matching techniques given above will be used (unless otherwise specified by my supervisors).

Finally a PhD Student!

Good news, I've passed the MPhil/PhD transfer viva.

Time to get a move on I think!