最大重量/最小成本偶匹配code在Python [英] Maximum Weight / Minimum Cost Bipartite Matching Code in Python
问题描述
我的二分图搜索的Python code的最大重量/最低的成本匹配。我一直在使用一般情况下最大重量匹配code在NetworkX，但我发现我需要它太慢了。这可能是由于这两个事实，即一般算法较慢，并且该NetworkX溶液在Python完全实现的事实。理想情况下，我想找到一个一些Python $ C $下的双边匹配问题，它包装一些C / C ++ code，但现在，任何比NetworkX实现更快的将是有益的。
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.
推荐答案
在一些进一步的调查，我发现下面的两个模块特别有帮助（http://pypi.python.org/pypi/pyLAPJV/0.3和< A HREF =http://pypi.python.org/pypi/hungarian相对=nofollow> http://pypi.python.org/pypi/hungarian ）。他们是用C ++实现与Python绑定两种算法，并运行比NetworkX配套实施要快得多。该pyLAPJV实施，但是，似乎有点太善变了我的需求，并不能正确处理相同的加权边缘很好。匈牙利模块（尽管据说比pyLAPJV算法慢）运行幅度约3个数量比NetworkX执行上的数据的大小，我目前正在处理速度更快。我也要去放弃再看看code。通过国头建议，因为我相信，它可以运行，虽然Shedskin很容易给一个合理的快速实现。
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.
这篇关于最大重量/最小成本偶匹配code在Python的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
