Maximum Weight Bipartite Matching implementation in Java

It’s been too long, but I’ve finally contributed to an open source project again. A number of years ago I implemented a polynomial-time algorithm for find the maximum weight matching of a bipartite graph, based on the Hungarian algorithm.

Well, the code wasn’t being used anymore, and my employer was kind enough to allow me to open source it. I ended up adding it to the jgrapht project. Feels good to be contributing to open source again. The jgrapht project is a very capable theoretical graph library, with a lot of handy algorithms, including some for finding spanning trees and shortest paths.

The jgrapht project is on github now here.

Leave a Reply

Your email address will not be published.