Having read more about matching, more specifically, the problems of finding a maximal independant set, I have discovered my algorithm is unusually quick for a number of reasons. Several methods have been implemented to find the maxmimal set most efficiently, and quickly, including a path orientated approach [1] - by creating an alternating or augmented path through the graph, or a debt-first search [2] - where each adjacent vertex of a singular vertex, is visited to determine if at all, its best fit.
[1] Combinatorial Optimization, Algorithms and Complexity - Papadimitriou & Steiglitz
[2] A multilevel Algorithm for Partitioning Graphs - Hendrickson & Leland
These are both mentioned in Walshaws Multilevel Force Directed Drawing, which uses the same method for finding a maximal independant set as [2], due to [1] being too slow, and not essential.
My method of finding a maximal independant set differs greatly, in that it completely ignores weighting or finding the best edge matching, and goes for the closest and first available match. Having check this in comparison to the methods above, in theory, this does not greatly affect the matching of edges, and any differences, are minimal. This is open to speculation, and more research should be carried out to find an optimal solution which is both quick and efficient.
One large noticeable issue, is the lack of weighting in the matching. Vertices are paired on a first come first serve basis, whereas a more intelligent algorithm would match the vertices with less or similar weights. The way in which data is stored may also need to change, so to include these weights if and where necessary.
The next step, as mentioned previously, is coarsening, giving the new vertices edges in place of lower level edges, and iterating the matching algorithm. Other work may include experimentation with this maximal matching problem.
Meeting
Today I met with my supervisor to discuss my work with matching and my change to storing the graph data. Although the matching may be efficient, a bug is expected to appear when applying force-directed drawing techniques. Whether or not I have to change my current model is yet to be determined, but it is very likely. In anticipation of this, me and my supervisor discussed making my code polymorphic, so that if I do change my method of storing information, the code will work in the same manner.
Our monthly meeting is to be scheduled for next week, where I will hopefully have something to report upon (more than my matching algorithm).
No comments:
Post a Comment