3 Replies Latest reply on May 4, 2010 11:40 AM by 843853

perfect minimum weight matching in complete graphs

Hello everyone

I am faced with finding a perfect matching in a complete weighted graph, with a minimum total cost (regarding edge weights). I've found several pieces of information in the net, most of them implementations and improvements of Edmond's Blossom Shrinking Algorithm, including:
1) http://www.math.sfu.ca/~goddyn/Courseware/edmonds.pdf (Edmond's original algorithm)
2) http://citeseer.ist.psu.edu/cook98computing.html (Cook & Rohe's implementation from 1998)
3) http://www.mpi-inf.mpg.de/~mehlhorn/ftp/WAE00.ps.gz (a (most probably) better implementation from 2000)
4) http://www.dcg.ethz.ch/publications/ctw04.pdf (some approximation algorithms - although i need the exact minimum cost, i could use one of these)
5) http://www.math.sfu.ca/~goddyn/Courseware/Visual_Matching.html (a vizualization of edmond's algorithm)
6) http://www.isye.gatech.edu/~wcook/blossom4/ (a c++ code for Blossom IV, the latest improvement of the blossom-shirnking algorithm. It is, however, somewhat "unified" and very difficult to read. I would very much prefer using a code of my own.)

What I couldn't find was Lawler and Gabow's algorithm which appears to be the most appropriate one for my particular task.

Another problem I faced when reading these papers is that it isn't quite clear which work for planar graphs and which work for general graphs. Some state they do the latter, but I can't really be sure of that since the Edmond's first algorithm works for planar graphs only. I want a solution for general graphs, although I would also be happy with an efficient one for planar graphs only.

Now, to get to the point, my greatest problem is that all of these implementations seem very unclear and far too difficult to understand. I don't have much of an experience using academic papers and I really get lost in all the definitions and formulations. Furthermore, I never encountered a straightforward step-by-step description of an algorithm.
What I'd like is if someone gave me a pseudo-code or a simple (as far as it can be) C++ code of some algorithm solving the minimum weight perfect matching problem for complete graphs. I would also appreciate a more simple explanation of Edmond's algorithm and I guess it would be much easier for me to understand all the other implementations afterwards. If not that, a link to Lawler and Gabow's work on the topic should also help me.

Thanks to everyone in advance. I believe the minimum weight perfect matching problem is an interesting one and I hope someone has been concerned about it and can give me a hand :)
• 1. Re: perfect minimum weight matching in complete graphs
I am also looking for a self contained implementation. Number 6) has little or no documentation. I am looking for a code in which I can input the distance graph and get the matching as output (not just the total weight).

If anyone can make a recommendation, I would be grateful.
• 2. Re: perfect minimum weight matching in complete graphs
Hi Momtchil!

Found anything useful yet? I'm trying to implement perfect min. cost matching in 2D but I'm stuck exactly where you have been 2 years ago!

Bests,
Robert
• 3. Re: perfect minimum weight matching in complete graphs
Hi throbi!

You can view the source code of the 5th applet: http://www.math.sfu.ca/~goddyn/Courseware/
The algorithm is mainly in the following file:
http://www.math.sfu.ca/~goddyn/Courseware/matching/non_bipartite_perfect_matching/Algorithm.java

You can remove some unnecessary methods, which are just for visualization, the result is less then 1000 lines.

br,
zgabi