Blossom Algorithm in PHP

Following the Swiss Pairings Algorithm I wrote in python using weighted maximum matching I ported the blossom algorithm code to PHP.

This is a direct conversion of Joris van Rantwijk’s python code with the same tests and the same output.

The algorithm is taken from “Efficient Algorithms for Finding Maximum Matching in Graphs” by Zvi Galil, ACM Computing Surveys, 1986. It is based on the “blossom” method for finding augmenting paths and the “primal-dual” method for finding a matching of maximum weight, both due to Jack Edmonds.

Some ideas came from “Implementation of algorithms for maximum matching on non-bipartite graphs” by H.J. Gabow, Standford Ph.D. thesis, 1973.

A C program for maximum weight matching by Ed Rothberg was used extensively to validate this new code.

https://github.com/bakert/blossom-php/blob/master/mwmatching.php

Leave a Reply

Your email address will not be published.