No BSD License  

4.11765

4.1 | 17 ratings Rate this file 153 Downloads (last 30 days) File Size: 9.11 KB File ID: #11609
image thumbnail

Hungarian Algorithm

by

 

30 Jun 2006 (Updated )

An algorithm to find the minimum edge weight matching for an arbitrary bipartite graph.

| Watch this File

File Information
Description

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.

Acknowledgements

This file inspired Munkres Assignment Algorithm.

MATLAB release MATLAB 7.2 (R2006a)
Tags for This File   Please login to tag files.
Please login to add a comment or rating.
Comments and Ratings (20)
07 Mar 2014 Shawn Lu  
04 May 2013 Mojeeb

nice

18 Apr 2013 Alvaro Bertelsen

Very good work.

03 Oct 2012 sixie yu

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.

25 Apr 2012 Yi

nice work

08 May 2011 hazem s

very good

02 Aug 2010 Andrey Kan

Alexander, thank you for this implementation. It has been useful to me.

I would like to point out to a possible bug.

Input:
8x10 distance matrix:
distMatrix = [

Inf Inf Inf Inf Inf Inf 5.0000 389.0000 65.0000 Inf
Inf Inf 481.0000 Inf Inf Inf Inf Inf Inf Inf
Inf Inf Inf Inf Inf Inf 464.0000 2.0000 200.0000 449.0000
0 Inf Inf Inf Inf Inf Inf Inf Inf Inf
Inf Inf Inf 26.0000 122.0000 169.0000 Inf Inf Inf Inf
Inf 362.0000 Inf Inf Inf Inf Inf 449.0000 Inf 2.0000
Inf 0 Inf Inf Inf Inf Inf Inf Inf 404.0000
Inf Inf Inf Inf Inf Inf 260.0000 Inf Inf Inf]

Output:
matching =

0 0 0 0 0 0 0 0 1 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 1 0 0
1 0 0 0 0 0 0 0 0 0
0 0 0 1 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 1
0 1 0 0 0 0 0 0 0 0
0 0 0 0 0 0 1 0 0 0

Note, that in the input row #2 can only be assigned to column #3, and column #3 can only be assigned to row #2.

However, in the output: matching(2, 3) == 0;

Implementation found at
http://www.mathworks.com/matlabcentral/fileexchange/6543
doesn't have this problem.

Andrey

26 Nov 2008 Gokhan Gulgezen

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:

D = [Inf Inf 0 2
0 Inf 3 Inf
0 Inf 1 Inf
Inf 0 Inf 0]

Clearly, the optimal match is

0 0 0 1
1 0 0 0
0 0 1 0
0 1 0 0

However,

Matching = Hungarian(D) gives

Matching =

0 0 1 0
0 0 0 0
1 0 0 0
0 1 0 0

row 2 and column 4 have not been matched!

09 Jan 2008 Peter L

The Hungarian algorithm was already available here:

http://www.mathworks.com/matlabcentral/fileexchange/loadFile.do?objectId=6543&objectType=file

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.

Contact us