This algorithm allows you to find the minimum weight matching of a bipartite graph. The graph can be of arbitrary size and connectedness. The edge weights are captured by a MxN weight matrix where an infinite(Inf) weight designates that that pair of vertices given by that position are not connected.

This function can effectively calculate NxN matrices, and can also process NxM matrices. But it is a little difficult to understand the source code. Maybe my abilities matter. In sum, it is useful.

The algorithm works pretty well I think but I need to find maximum weight matching of a bipartite graph not minimum.
So can I use this code to find the maximum weight matching of a bipartite graph just multiplying the performance matrix with negative. Is there anyone to help me or provide information for finding maximum weight matching.
Thanks in advance.

Gokhan

25 Jul 2008

E J

I hear the author is really hot.

25 Jun 2008

Yi Cao

I just found the code has a bug when the cost matrix has some inf elements. For example:

This submission even provides a lot more: A brute-force version for reference, suboptimal (but faster) versions and an implementation as a mex-file which is very fast.

20 Oct 2007

zikai wu

Good Job.

19 Oct 2007

Mody Avinash

Great Job

02 Aug 2007

ali hosseinzadeh

Do you know where i can find a matlab code for maximum weight matching in general graphs?

08 Jul 2007

anand sunali

Great Job

14 Jun 2007

ashin mukherjee

Great job, works pretty fast too.
But aren't there any algorithm for general graphs and not only for bipartite graphs

04 Jun 2007

Richard Brown

Good:
* works
* easy to use
* plenty of comments
* doesn't require you to convert your graph to have equal numbers of nodes

Bad:
* Potentially speed, although I imagine a large amount more work has gone into the BNT version
* Help section could use an example, and an H1 line

I was thrilled that this was here - it was exactly what I needed, and I got it working with no effort at all, really.

Thanks for sharing it.

02 Mar 2007

Jean-Francois Lalonde

This works pretty well, but I've found that the hungarian.m function part of the Bayes net toolbox (FullBNT) http://www.cs.ubc.ca/~murphyk/Software/BNT/bnt.html
is approximately twice as fast. It took 17 seconds to process a random 400x400 matrix with the BNT code, whereas this code took 31 sec.

04 Feb 2007

Alan Cramton

Works great !!! 400 X 400 takes about 32 seconds on 1.6 Ghz Pentium M laptop. And it works. I think this is much better than the other ones posted.

27 Dec 2006

Minh Hoai Nguyen

This works pretty well. I don't know if it could be faster; It took 63s for a random 400*400 matrix.

Updates

21 Jul 2006

Bug Fix: Now returns a zero cost if the edge weight matrix is fully disconnected, instead of giving an error.