Menu
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.
548
Definition 1. A graph G = (V,E) is called bipartite if there is a partition of V into two disjoint subsets: V = L ∪ R, such every edge e ∈ E joins some vertex in L to some vertex in R. When the bipartition V = L ∪ R is specified, we sometimes denote this bipartite graph as G = (L, R, E). Theorem 2.
Maximum bipartite matching solutionSuch a problem can be solved very effectively by the Ford Fulkerson algorithm, which connects and disconnects all possible edges in the graph till the maximum match number is found, such as the highest edge count.
Theorem 2 The exact weight perfect matching problem of bipartite graph is NP-complete.
Have you tried scipy implementation of the Hungarian algorithm, also known as the Munkres or Kuhn-Munkres algorithm?
scipy.optimize.linear_sum_assignment
146
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
