CODEWITHSUNDEEP
c++pythonalgorithmgraph
nomad
nomad

Reputation: 1809

Maximum Weight / Minimum Cost Bipartite Matching Code in Python

I'm searching for Python code for maximum weight / minimum cost matching in a bipartite graph. I've been using the general case max weight matching code in NetworkX, but am finding it too slow for my needs. This is likely due to both the fact that the general algorithm is slower, and the fact that the NetworkX solution is implemented entirely in Python. Ideally, I'd like to find a some Python code for the bipartite matching problem that wraps some C/C++ code, but right now, anything faster than the NetworkX implementation would be helpful.

Upvotes: 13

Views: 15229

Answers (5)

fuglede
fuglede

Reputation: 18221

When you say "minimum cost matching", I assume that you mean the problem of finding the matching with lowest cost among all maximum matchings.

As of version 2.4 (released 2019-10-17), NetworkX does handle the bipartite case specifically with nx.algorithms.bipartite.minimum_weight_full_matching.

Under the hood, it relies on scipy.optimize.linear_sum_assignment. As of version 1.6.0, SciPy also ships with scipy.sparse.csgraph.min_weight_full_bipartite_matching which does the same thing but for sparse inputs, and which can offer performance improvements for sparse graphs.

Upvotes: 3

Sina Mansour L.
Sina Mansour L.

Reputation: 428

Have you tried scipy implementation of the Hungarian algorithm, also known as the Munkres or Kuhn-Munkres algorithm?

scipy.optimize.linear_sum_assignment

Upvotes: 9

nomad
nomad

Reputation: 1809

After some further investigation, I've found the following two modules particularly helpful (http://pypi.python.org/pypi/pyLAPJV/0.3 and http://pypi.python.org/pypi/hungarian). They are both algorithms implemented in C++ with Python bindings, and run much faster than the NetworkX matching implementation. The pyLAPJV implementation, however, seems to be a bit too fickle for my needs and doesn't properly handle identically weighted edges well. The hungarian module (though supposedly slower than the pyLAPJV algorithm) runs about 3 orders of magnitude faster than the NetworkX implementation on the data sizes I'm currently dealing with. I'm also going to give another look at the code suggested by kunigami, as I believe that it can be run though Shedskin fairly easily to give a reasonably fast implementation.

Upvotes: 7

kunigami
kunigami

Reputation: 3086

The minimum weight bipartite matching can be solved by the Hungarian algorithm (wikipedia). The link in wikipedia links to a python implementation. I'm not sure if it's faster than the code you mentioned, though.

Upvotes: 0

Nico Huysamen
Nico Huysamen

Reputation: 10427

Not too sure if this is what you are looking for, but it is a python implementation of the Hopcroft-Karp bipartite graph matching algorithm. If not, it can probably be a good starting place for you.

Hopcroft-Karp Bipartite Matching

Upvotes: 0

Related Questions