algorithms icon indicating copy to clipboard operation
algorithms copied to clipboard

Published 20 hours ago • verified publisher icon keon

Implementation of blossom algorithm for maximal cardinality matching

Open abhishekiitm opened this issue 2 years ago • 4 comments

Code by D. Eppstein, UC Irvine, 6 Sep 2003. Implementation of maximum cardinality matching code taken from https://code.activestate.com/recipes/221251-maximum-cardinality-matching-in-general-graphs/

I recently used this code on a Google Foobar challenge and it would be a nice addition to this repository.

abhishekiitm avatar Jan 25 '22 05:01 abhishekiitm

Nice work. :)

I am thinking of checking in a fast UnionFind (#830) and even though I have written a good number of tests for it, I would like to test its integration with the blossom algorithm implementation as well.

If you find some time to add your tests, I can refactor the API myself and test out the integration. Thanks!

aalekhpatel07 avatar Feb 16 '22 05:02 aalekhpatel07

Thanks @aalekhpatel07, I've added unit tests for blossom algorithm implementation. You can test your union find integration now. All the best and let me know if there's any way I can help!

abhishekiitm avatar Feb 20 '22 04:02 abhishekiitm

Nice. (927e73) contains the new blossom that uses the UnionFind API from algorithms.unionfind.

The tests are passing, so yay! :smile:

aalekhpatel07 avatar Feb 20 '22 06:02 aalekhpatel07

Looks great!

abhishekiitm avatar Feb 20 '22 06:02 abhishekiitm