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.
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.