Hungarian Algorithm in C#

The Hungarian algorithm, also known as the Kuhn-Munkres algorithm, is well-known to be the most efficient algorithm for solving the assignment problem. In fact, it does what is considered by many to an exponential time algorithm (more specifically, factorial time), in O(n3).

The Wikipedia page describes the general form of the problem quite well.

There are a number of agents and a number of tasks. Any agent can be assigned to perform any task, incurring some cost that may vary depending on the agent-task assignment. It is required to perform all tasks by assigning exactly one agent to each task in such a way that the total cost of the assignment is minimized.

However, the implementation of this algorithm is far from trivial. In fact, for all my Googling, not a single implementation in C# turned up (though there was at least one in each of C, C++, Java, and Python). Given this opportunity, I took on the task of porting this code given on this page in the Ada language, to C# 3.0. With almost 300 lines of code, and a bit of debugging with the sample problem,

Download the full (documented) code for the algorithm here.

The algorithm is contained within a single static class that exposes an extension method that operates on a matrix (2D array), for ease of use. Although I believe that as an almost line-for-line port of the Ada code, there should not be any issues with my implementation, any bug reports would be appreciated.

Updated 15/10/09: Several bug fixes have been made that fix issues (most noticeably, endless looping) for non-square as well as various other sorts of matrices.

Updated 24/10/09: Fixed bug (endless looping) that affects large variety of matrices, involving ConvertPath function.

28 Responses to “Hungarian Algorithm in C#”

  1. Chris says:

    Server Error in ‘/’ Application.
    This type of page is not served.
    Description: The type of page you have requested is not served because it has been explicitly forbidden. The extension ‘.cs’ may be incorrect. Please review the URL below and make sure that it is spelled correctly.

    Requested URL: /programming/HungarianAlgorithm.cs

  2. Angelo says:

    Hi! This code has some bugs on the index (very simple to fix). How can I work with float values in the cost matrix?
    Transform the matrix from integer to float is not enought, there are some terminal conditions inside the algorithm and it’s going in loop.
    any idea?
    thanks

  3. Noldorin says:

    Hi Angelo,
    I suspect the reason that your modified version using floats is not working is due to floating point arithmetic errors – the solution would seem to be to use some small tolerance value. i.e. Instead of `foo == 0`, try `Math.Abs(foo) < 1e-6`.
    I’m also curious what precisely this bug that exists in the code is? Could you please describe it in more detail, and ideally, give me an example cost matrix where it becomes apparent?

  4. Angelo says:

    If you try with a non quadratic matrix an index error appears.
    I have a float non quadratic matrix with distance values between 0 and 1. The dimension changes from 5 to 20 (es. 5×5, 5×6,…20×20). I debugged the code and in the while (step != -1) the iteration loops and no end.

    thanks

  5. Noldorin says:

    Thanks for the report, Angelo. I’ll have a look into it and will try to update the post soon.

  6. Massimiliano says:

    Hi Noldorin,

    We have ported very easily your code for Visual C# 2005. I am experiencing the same problem as Angelo for square matrices. Debugging the code, I noticed that it loops always among steps 1,2 and 3. It never reaches step 4 and, hence, it cannot terminate.
    The problem does not occur always; I would say over 50% of the matrices I tried
    For instance, it does not work with the following:

    23,21,3,4
    83,7,6,52
    4,31,2,1
    0,4,3,2

    Have you found the bug and tested it?

    It is quite important for me, since I work for an university and I want to use it for an implementation, on which I wish to write a scientific journal article. Of course, if you solve the problem, I would mention you in the article itself.

  7. Noldorin says:

    Hi Massimiliano,

    I’ve finally gotten around to releasing an update which includes fixes for all known bugs. It seems I managed to resolve whatever issue was causing trouble with the matrix you gave, some time ago in fact, but failed to re-upload! The algorithm was however still not working for non-square matrices. Now, I believe all is fixed, at least according to my tests. :)

    Anyway, thanks to you and Angelo for pointing these problems out to me. Hopefully you won’t encounter any more issues with the new version.

    I’m glad to hear you’re using this implementation in scientific research. (Note: I’ve intentionally not put any license restrictions on the code, so it’s fully public domain.) An attribute to me is not necessary, but would be appreciated, of course.

    Alex

  8. Massimiliano says:

    Hi,

    Alex. Thanks for having taken care of this.
    I assume that the version downloadble in the upper part of this web page is the fixed one, isn’t it?

    I will let you know whether it works. I did understand you could also manage to fix for non-square matrices. I will try that, as well.

  9. Noldorin says:

    That’s right, I’ve just updated the original file. The changes were only minor, really (you can do a diff to see exactly what). Anyway, good luck.

  10. gelder says:

    Hi Noldorin,
    thanks for this great implementation of the hungarian algorithm.
    It works fine for smaller matrices, however it fails to terminate for bigger ones (e.g. 30×34 matrice). As mentioned above, it endlessly loops between Step 1,2 and 3 (although I’m using the updated version).
    The reason might be, that I try to use it for a slightly altered problem: In my “cost”-matric i have values where a bigger value is better (as apposed to real costs).
    I didn’t want to alter the algorithm, so I tried to alter my cost matrices. My first idea was to use negative cost values. It worked fine vor smaller matrices, but failed for bigger ones. My second idea was using the reciprocal value in the cost matrix, but the same problem occurs.
    I hope this is understandable.
    Do you have any clue why this could to problems or how i could easily alter the algorithm to fit to my problem?

    Thanks for any help!

  11. gelder says:

    Hi,
    I think I could drill down to the problem. It doesn’t work with a matrix like this:

    1 8
    8 9

    Is a matrix like this not suitable to the problem/algorithm or is there still a bug?
    Thanks for your help!

  12. Noldorin says:

    Hi gelder,

    Thanks for reporting this issue. Indeed, the algorithm did fail on the example matrix you gave. The problem seemed to be that the array used for converting the path was iterated over too far sometimes, causing the matrix of marks to be incorrectly modified.

    The problem should now be resolved in the updated code (v1.2), which you can download again from the same address. I should really create some unit tests for this, to be honest, but a few brief checks indicate that the algorithm still works on all sorts of other matrices.

  13. gelder says:

    Hi Noldorin,
    thanks for your quick reply and your effort to solving this problem. The updated version is indeed working for the example from above but furthermore it works fine for all bigger (e.g. 30×30 matrices) I have tested so far!
    Even matrices with negative values and a slightly modified version of your algorithm (that works with double values) work perfectly fine. Thanks for this good work!

    If I find other matrices that could lead to problems, I will report back – but so far everything is fine.

    Thanks again, gelder

  14. gelder says:

    Hi,
    I came across another type of matrices, that doesn’t work. This time it might be because of a faulty use – a job is not connected to the workers.
    A matrix like this produces looping between Step 2 and Step 4:

    int[,] values=new int[6,5];
    values[0, 0] = 1;
    values[0, 1] = 0;
    values[0, 2] = 0;
    values[0, 3] = 0;
    values[0, 4] = 0;
    values[1, 0] = 0;
    values[1, 1] = 2;
    values[1, 2] = 0;
    values[1, 3] = 0;
    values[1, 4] = 0;
    values[2, 0] = 0;
    values[2, 1] = 0;
    values[2, 2] = 0;
    values[2, 3] = 0;
    values[2, 4] = 0;
    values[3, 0] = 0;
    values[3, 1] = 3;
    values[3, 2] = 0;
    values[3, 3] = 0;
    values[3, 4] = 0;
    values[4, 0] = 3;
    values[4, 1] = 0;
    values[4, 2] = 0;
    values[4, 3] = 0;
    values[4, 4] = 0;
    values[5, 0] = 0;
    values[5, 1] = 0;
    values[5, 2] = 0;
    values[5, 3] = 3;
    values[5, 4] = 0;

    Is this still a bug in the algorithm or should I just try to avoid using matrices like this?
    Thanks, gelder

  15. gelder says:

    Hi,
    just a quick update: It works fine with matrices like the one above, if you make them square yourself!

    gelder

  16. Martin says:

    Hi Noldorin.
    I’m having trouble downloading your cs file from http://noldorin.com/programming/HungarianAlgorithm.cs

    I get the message:
    HTTP Error 404.7 – Not Found. The request filtering module is configured to deny the file extension
    Can you fix it or is there a mirror somewhere?

    Best regards Martin

  17. Mauro says:

    Hi Noldorin,
    I get the following error when I try to get the .cs file:

    HTTP Error 404.7 – Not Found
    The request filtering module is configured to deny the file extension.

    Mauro

  18. Noldorin says:

    Hi all,

    Apologies for the file being down at the moment. There have been some problems with the server – I’ll try to get it up shortly. In the meanwhile, you can view the code at http://pastebin.ca/1708378.

  19. Mauro says:

    Thanks Noldorin!

  20. Martin says:

    This is great!

    Thank you for a great work. Got it working right away

    Regards Martin

  21. Bruce says:

    I’m having problems with this 5×5 matrix:
    7,2,1,9,4
    9,6,9,6,5
    3,8,3,1,8
    7,9,4,2,2
    8,4,7,4,8

    giving an incorrect cost of 18 (ie. agentstasks={2,4,3,0,1}) when it should be 15={2,4,0,3,1}.

    ref: Papadimitriou (ISBN 0-486-40258-4), p. 255.

    In Papadimitrou, row 2 is {9,6,9,5,5}. Nodorin… your alg produces a matching sum=15 via {2,3,0,4,1} instead. This is good.

    I then altered the costs in row 2 to be {9,6,9,6,5} instead which should force the {2,4,0,3,1}=15 answer but instead it gives the incorrect {2,4,3,0,1}=18 answer.

    Awesome work, though… thanks for all the effort on this!

  22. Noldorin says:

    Hi Bruce,

    That’s odd that you’re getting a resulting vector of {2,4,3,0,1}, as I just ran the latest version of the code and it returned {2,4,0,3,1}, which is correct as you say. If you could download the latest algorithm code via the link in the original post (it is now fixed) and let me know if the problem is persisting, that would be helpful.

    In case there’s any confusion over how to use it, this is my brief test code:

    var costs = new int[,]
        {
            {7,2,1,9,4},
            {9,6,9,6,5},
            {3,8,3,1,8},
            {7,9,4,2,2},
            {8,4,7,4,8},
        };
    var result = costs.FindAssignments(); // returns {2,4,3,0,1}
    

    Hope that resolves the matter for you.

  23. Bruce says:

    Found my bug… i’m porting to VB, using cols 0-4 and rows 0-4 for a 5×5 matrix. I needed to init colsCoveredCount=-1 in Step 1 instead, and I’m all good.

    Question: why the difference in your code vs. the Ada version for ConvertPath? You perform an additional test for masks==2, whereas the Ada code doesn’t. Bug in the Ada code?

    I’m also a little fuzzy on this C# code (in FindAssignment):
    var path = new Location[w * h];
    Location pathStart = default(Location);
    Assuming a 5×5 matrix, this code creates 25 instances of Location, all inited to (row,col)=(-1,-1) with Pathstart is initially nil. That’s how I’ve recoded it.

  24. Robert says:

    Thank you!

  25. Fedor says:

    Hi,

    Thanks for your code! You are marvelous.

    When I use the code for my purpose, I get 2 loops.
    The result is two loops, the main loop never reaches 1 and 4, and there’s a small loop between 1 and 4.

    This is the matrix that will return these two loops:

    costs = new int[8, 8] { { 99, 99, 99, 99,99, 0, 99, 99 }, //A
    { 99, 99, 99, 99,0, 99, 99, 99 }, //B
    { 99, 99, 99, 99,99, 99, 0, 99 }, //B’
    { 99, 99, 99, 99,99, 99, 99, 0 }, //A’
    { 0, 99, 2, 3, 99,99, 99, 99 }, //1
    { 1, 99, 1, 2, 99,99, 99, 99 }, //2
    { 0, 99, 2, 3, 99,99, 99, 99 }, //1′
    { 1, 99, 1, 2, 99,99, 99, 99 }};//2′

    Where in your code can I check if there are multiple loops?

    With regards,

    Fedor

  26. simin says:

    Hi,
    I want to use this code in a part of my thesis method. I would be happy to know about the last probable limits or bugs of this code.
    BR,
    Cmin

  27. E-S says:

    Hi
    Thank you very much for the code, but there is a problem

    {1,5},
    {4,8},
    {3,5},
    {7,2},
    {9,3}

    Above matrix is trapped in a loop!
    Why?

  28. LD says:

    @E-S I believe this implementation will only work correctly on cost matrices where #rows<=#columns. The return array's ith value is the assignment of row i to a column.

RSS feed for comments on this post. And trackBack URL.

Leave a Reply


%d bloggers like this: