munkres' assignment algorithm modified for rectangular matrices

• BRC Management Team
• Company History
• Mission & Vision Statements
• Research & Technology
• Systems Analysis & Integration
• Test & Evaluation
• Security & Intelligence
• Seaport NxG
• The Algorithm Workshop

Munkres’ Assignment Algorithm

Modified for Rectangular Matrices  

Assignment Problem – Let C be an nxn matrix representing the costs of each of n workers to perform any of n jobs.  The assignment problem is to assign jobs to workers so as to minimize the total cost. Since each worker can perform only one job and each job can be assigned to only one worker the assignments constitute an independent set of the matrix C .

An arbitrary assignment is shown above in which worker  a  is assigned job  q , worker  b  is assigned job  s  and so on.  The total cost of this assignment is  23 .  Can you find a lower cost assignment? Can you find the minimal cost assignment? Remember that each assignment must be unique in its row and column.

A brute-force algorithm for solving the assignment problem involves generating all independent sets of the matrix  C , computing the total costs of each assignment and a search of all assignment to find a minimal-sum independent set. The complexity of this method is driven by the number of independent assignments possible in an  nxn  matrix. There are  n  choices for the first assignment,  n-1  choices for the second assignment and so on, giving n! possible assignment sets. Therefore, this approach has, at least, an exponential runtime complexity.

As each assignment is chosen that row and column are eliminated from consideration.  The question is raised as to whether there is a better algorithm.  In fact there exists a polynomial runtime complexity algorithm for solving the assignment problem developed by James Munkre’s in the late 1950’s despite the fact that some references still describe this as a problem of exponential complexity.

The following 6-step algorithm is a modified form of the original Munkres’ Assignment Algorithm (sometimes referred to as the Hungarian Algorithm).  This algorithm describes to the manual manipulation of a two-dimensional matrix by starring and priming zeros and by covering and uncovering rows and columns.  This is because, at the time of publication (1957), few people had access to a computer and the algorithm was exercised by hand. Step 0:   Create an nxm  matrix called the cost matrix in which each element represents the cost of assigning one of n workers to one of m jobs.  Rotate the matrix so that there are at least as many columns as rows and let k=min(n,m).

Step 1:   For each row of the matrix, find the smallest element and subtract it from every element in its row.  Go to Step 2.

Step 2:   Find a zero (Z) in the resulting matrix.  If there is no starred zero in its row or column, star Z. Repeat for each element in the matrix. Go to Step 3.

Step 3:   Cover each column containing a starred zero.  If K columns are covered, the starred zeros describe a complete set of unique assignments.  In this case, Go to DONE, otherwise, Go to Step 4.

Step 4:   Find a noncovered zero and prime it.  If there is no starred zero in the row containing this primed zero, Go to Step 5.  Otherwise, cover this row and uncover the column containing the starred zero. Continue in this manner until there are no uncovered zeros left. Save the smallest uncovered value and Go to Step 6.

Step 5:   Construct a series of alternating primed and starred zeros as follows.  Let Z 0  represent the uncovered primed zero found in Step 4.  Let Z 1  denote the starred zero in the column of Z 0  (if any). Let Z 2  denote the primed zero in the row of Z 1  (there will always be one).  Continue until the series terminates at a primed zero that has no starred zero in its column.  Unstar each starred zero of the series, star each primed zero of the series, erase all primes and uncover every line in the matrix.  Return to Step 3.

Step 6:   Add the value found in Step 4 to every element of each covered row, and subtract it from every element of each uncovered column.  Return to Step 4 without altering any stars, primes, or covered lines.

DONE:   Assignment pairs are indicated by the positions of the starred zeros in the cost matrix.  If C(i,j) is a starred zero, then the element associated with row i is assigned to the element associated with column j.

Some of these descriptions require careful interpretation.  In Step 4, for example, the possible situations are, that there is a noncovered zero which get primed and if there is no starred zero in its row the program goes onto Step 5.  The other possible way out of Step 4 is that there are no noncovered zeros at all, in which case the program goes to Step 6.

At first it may seem that the erratic nature of this algorithm would make its implementation difficult.  However, we can apply a few general rules of programming style to simplify this problem.  The same rules can be applied to any step-algorithm.

Good Programming Style and Design Practices

1. Strive to create readable source code through the use of blank lines, comments and spacing.

2. Use consistent naming conventions, for variable and constant identifiers and subprograms.

3. Use consistent indentation and always indent the bodies of conditionals and looping constructs.

4. Place logically distinct computations in their own execution blocks or in separate subprograms.

5. Don’t use global variables inside subprograms except where such use is clear and improves readability and efficiency.

6. Use local variables where appropriate and try to limit the creation of unnecessary identifiers in the main program.

7. Open I/O files only when needed and close them as soon as they are no longer required.

8. Work to keep the level of nesting of conditionals and loops at a minimum.

9. Use constant identifiers instead of hardwiring for-loop and array ranges in the body of the code with literal values.

10. When you feel that things are getting out of control, start over. Re-coding is good coding.

By applying Rule 4 to the step-algorithm we decide to make each step its own procedure.  Now we can apply Rule 8 by using a case statement in a loop to control the ordering of step execution.  The main loop for Munkres as a step-wise algorithm is shown here implemented in C#.

In each pass of the loop the step procedure called sets the value of step for the next pass.  When the algorithm is finished the value of step is set to some value outside the range 1..7 so that done will be set to true and the program will end.  In the completed program the tagged (starred) zeros flag the row/column pairs that have been assigned to each other.  We will discuss the implementation of a procedure for each step of Munkres’ Algorithm below. We will assume that the cost matrix  C(i,j)  has already been loaded with the first index referring to the row number and the second index referring to the column number.

Step 1 For each row of the matrix, find the smallest element and subtract it from every element in its row.  Go to Step 2.  We can define a local variable called  minval  that is used to hold the smallest value in a row.  Notice that there are two loops over the index  j  appearing inside an outer loop over the index  i . The first inner loop over the index  j  searches a row for the  minval .  Once  minval  has been found this value is subtracted from each element of that row in the second inner loop over  j .  The value of step is set to  2  just before  stepone  ends.

Step 2 Find a zero (Z) in the resulting matrix.  If there is no starred zero in its row or column, star Z. Repeat for each element in the matrix. Go to Step 3.   In this step, we introduce the mask matrix M, which in the same dimensions as the cost matrix and is used to star and prime zeros of the cost matrix.  If M(i,j)=1 then C(i,j) is a starred zero,  If M(i,j)=2 then C(i,j) is a primed zero.  We also define two vectors R_cov and C_cov that are used to “cover” the rows and columns of the cost matrix C.  In the nested loop (over indices i and j) we check to see if C(i,j) is a zero value and if its column or row is not already covered.  If not then we star this zero (i.e. set M(i,j)=1) and cover its row and column (i.e. set R_cov(i)=1 and C_cov(j)=1).  Before we go on to Step 3, we uncover all rows and columns so that we can use the cover vectors to help us count the number of starred zeros.

Step 3 Cover each column containing a starred zero.  If K columns are covered, the starred zeros describe a complete set of unique assignments.  In this case, Go to DONE, otherwise, Go to Step 4.  Once we have searched the entire cost matrix, we count the number of independent zeros found.  If we have found (and starred) K independent zeros then we are done.  If not we procede to Step 4.

Find a noncovered zero and prime it.  If there is no starred zero in the row containing this primed zero, Go to Step 5.  Otherwise, cover this row and uncover the column containing the starred zero. Continue in this manner until there are no uncovered zeros left. Save the smallest uncovered value and Go to Step 6.

In this step, statements such as “find a noncovered zero” are clearly distinct operations that deserve their own functional blocks.  We have decomposed this step into a main method and three subprograms (2 methods and a boolean function).

Step 5 Construct a series of alternating primed and starred zeros as follows.  Let Z 0  represent the uncovered primed zero found in Step 4.  Let Z 1  denote the starred zero in the column of Z 0  (if any). Let Z 2  denote the primed zero in the row of Z 1  (there will always be one).  Continue until the series terminates at a primed zero that has no starred zero in its column.  Unstar each starred zero of the series, star each primed zero of the series, erase all primes and uncover every line in the matrix.  Return to Step 3.   You may notice that Step 5 seems vaguely familiar.  It is a verbal description of the augmenting path algorithm (for solving the maximal matching problem) which we discussed in Lecture 3.  We decompose the operations of this step into a main procedure and five relatively simple subprograms.

As with the previous step we have decomposed Step 5 into a number of separate methods each performing a functionally distinct task corresponding to the description in Munkres algorithm.

Step 6 Add the value found in Step 4 to every element of each covered row, and subtract it from every element of each uncovered column.  Return to Step 4 without altering any stars, primes, or covered lines.  Notice that this step uses the smallest uncovered value in the cost matrix to modify the matrix.  Even though this step refers to the value being found in Step 4 it is more convenient to wait until you reach Step 6 before searching for this value.  It may seem that since the values in the cost matrix are being altered, we would lose sight of the original problem.  However, we are only changing certain values that have already been tested and found not to be elements of the minimal assignment.  Also we are only changing the values by an amount equal to the smallest value in the cost matrix, so we will not jump over the optimal (i.e. minimal assignment) with this change.

For Step 6, there is one supporting method to find the smallest uncovered value (described in Step 4).

The   code used above is available in a complete Microsoft Visual Studio .NET 2010 C# project –  Munkres .  This is a console application that can read a text-file containing the cost matrix values arranged in a two-dimensional array or generate test matrices.  The input file should be placed in the same folder as the calling executable.  This project application can generate a random value cost matrix or a worst-case test matrix C(i,j) = i*j.  Setting the value of each element C(i,j) of the cost matrix to the value i*j ensures that the maximum number of operations will be required to find the minimal assignment (which is the back diagonal).  The locations of the ones (1’s) in the associated mask matrix M correspond to the assignment pairs selected by Munkres’ Algorithm.  The following is an example run of the algorithm on a 3×3 worst-case test matrix.

An Example Execution of Munkres’ Algorithm

Workers = { a, b, c} Jobs = {p, q, r}

Cost of assigning job j to work i is

This example illustrates the method of implementing a step-algorithm.  It also serves to demonstrate why we do not attempt to implement every algorithm discussed in this course.  🙂

Answers to Frequently Asked Questions

1. The algorthm will work even when the minimum values in two or more rows are in the same column.

2. The algorithm will work even when two or more of the rows contain the same values in the the same order.

3. The algorithm will work even when all the values are the same (although the result is not very interesting).

4. Munkres Assignment Algorithm is not exponential run time or intractable; Munkres can achieve a low order polynomial run time, worst-case O(n3). see doi: 10.1007/BF01930994

5. Optimality is guaranteed in Munkres Assignment Algorithm.

6. Setting the cost matrix to C(i,j) = i*j  makes a good testing matrix for this problem.

7. In this algorithm the range of indices is[0..n-1] rather than [1..n].

8. Step 3 is an example of the greedy method.  If the minimum values are all in different rows then their positions represent the minimal pairwise assignments.

9. Step 5 is an example of the Augmenting Path Algorithm (Stable Marriage Problem).

10. Step 6 is an example of constraint relaxation.  It is “giving up” on a particular cost and raising the constraint by the least amount possible.

11. If your implementation is jumping between Step 4 and Step 6 without entering Step 5, you probably have not properly dealt with recognizing that there are no uncovered zeros in Step 4.

12. In the matrix M 1=starred zero and 2=primed zero.  So, if C[i,j] is a starred zero we would set M[i,j]=1.  All other elements in M are set to zero

13. The Munkres assignment algorithm can be implemented as a sparse matrix, but you will need to ensure that the correct (optimal) assignment pairs are active in the sparse cost matrix C

14. Munkres Assignment can be applied to TSP, pattern matching, track initiation, data correlation, and (of course) any pairwise assignment application.

15. Munkres can be extended to rectangular arrays (i.e. more jobs than workers, or more workers than jobs).

16. The best way to find a maximal assignment is to replace the values ci,j in the cost matrix with C[i,j] = bigval – ci,j.

17. Original Reference:  Algorithms for Assignment and Transportation Problems, James Munkres, Journal of the Society for Industrial and Applied Mathematics Volume 5, Number 1, March, 1957

18. Extension to Rectangular Arrays Ref:  F. Burgeois and J.-C. Lasalle. An extension of the Munkres algorithm for the assignment problem to rectangular matrices. Communications of the ACM, 142302-806, 1971.

Introduction

Assignment problem.

Let C be an n by n matrix representing the costs of each of n workers to perform any of n jobs. The assignment problem is to assign jobs to workers in a way that minimizes the total cost. Since each worker can perform only one job and each job can be assigned to only one worker the assignments represent an independent set of the matrix C .

One way to generate the optimal set is to create all permutations of the indexes necessary to traverse the matrix so that no row and column are used more than once. For instance, given this matrix (expressed in Python):

You could use this code to generate the traversal indexes:

After the call to permute(), the results matrix would look like this:

You could then use that index matrix to loop over the original cost matrix and calculate the smallest cost of the combinations:

While this approach works fine for small matrices, it does not scale. It executes in O( n !) time: Calculating the permutations for an n x n matrix requires n ! operations. For a 12x12 matrix, that’s 479,001,600 traversals. Even if you could manage to perform each traversal in just one millisecond, it would still take more than 133 hours to perform the entire traversal. A 20x20 matrix would take 2,432,902,008,176,640,000 operations. At an optimistic millisecond per operation, that’s more than 77 million years.

The Munkres algorithm runs in O( n ^3) time, rather than O( n !). This package provides an implementation of that algorithm.

This version is based on http://csclab.murraystate.edu/~bob.pilgrim/445/munkres.html

This version was written for Python by Brian Clapper from the algorithm at the above web site. (The Algorithm:Munkres Perl version, in CPAN, was clearly adapted from the same web site.)

Construct a Munkres object:

Then use it to compute the lowest cost assignment from a cost matrix. Here’s a sample program:

Running that program produces:

The instantiated Munkres object can be used multiple times on different matrices.

Non-square Cost Matrices

The Munkres algorithm assumes that the cost matrix is square. However, it’s possible to use a rectangular matrix if you first pad it with 0 values to make it square. This module automatically pads rectangular cost matrices to make them square.

• The module operates on a copy of the caller’s matrix, so any padding will not be seen by the caller.
• The cost matrix must be rectangular or square. An irregular matrix will not work.

Calculating Profit, Rather than Cost

The cost matrix is just that: A cost matrix. The Munkres algorithm finds the combination of elements (one from each row and column) that results in the smallest cost. It’s also possible to use the algorithm to maximize profit. To do that, however, you have to convert your profit matrix to a cost matrix. The simplest way to do that is to subtract all elements from a large value. For example:

The munkres module provides a convenience method for creating a cost matrix from a profit matrix. By default, it calculates the maximum profit and subtracts every profit from it to obtain a cost. If, however, you need a more general function, you can provide the conversion function; but the convenience method takes care of the actual creation of the matrix:

So, the above profit-calculation program can be recast as:

Disallowed Assignments

You can also mark assignments in your cost or profit matrix as disallowed. Simply use the munkres.DISALLOWED constant.

Running this program produces:

http://www.public.iastate.edu/~ddoty/HungarianAlgorithm.html

• Harold W. Kuhn. The Hungarian Method for the assignment problem. Naval Research Logistics Quarterly , 2:83-97, 1955.
• Harold W. Kuhn. Variants of the Hungarian method for assignment problems. Naval Research Logistics Quarterly , 3: 253-258, 1956.
• Munkres, J. Algorithms for the Assignment and Transportation Problems. Journal of the Society of Industrial and Applied Mathematics , 5(1):32-38, March, 1957.
• http://en.wikipedia.org/wiki/Hungarian_algorithm

Getting and installing munkres

Because munkres is available via PyPI , if you have pip installed on your system, installing munkres is as easy as running this command:

WARNING: As of version 1.1.0, munkres no longer supports Python 2. If you need to use it with Python 2, install an earlier version (e.g., 1.0.12):

Installing from source

You can also install munkres from source. Either download the source (as a zip or tarball) from http://github.com/bmc/munkres/downloads , or make a local read-only clone of the Git repository using one of the following commands:

Once you have a local munkres source directory, change your working directory to the source directory, and type:

To install it somewhere other than the default location (such as in your home directory) type:

Documentation

Consult the API documentation for details. The API documentation is generated from the source code, so you can also just browse the source .

• http://csclab.murraystate.edu/bob.pilgrim/445/munkres.html

This module is released under the Apache Software License, version 2. See the license file for details.

Navigation Menu

Search code, repositories, users, issues, pull requests..., provide feedback.

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly.

To see all available qualifiers, see our documentation .

• Notifications

Inplementation of the Munkres assignment method (also know as the Hungarian Algorithm). This implementation handles rectangular problems (non-square matrix). OpenCV is used for manipulating matrices, handling both float and double data.

vminotto/munkres-rect-cv

Folders and files, repository files navigation, munkres-rect-cv.

Munkres assignment method (also know as the Hungarian Algorithm). This implementation handles both square and rectangular problems (non-square cost matrices). OpenCV is used for manipulating data, and either float or double-typed costs are allowed. The current implementation was developed and tested using OpenCV 2.49, but lower and higher versions of the library should compile with no problem. The project needs to be linked to the opencv_coreVER.lib (where VER is the the version suffix).

Examples on how to use the algorithm are found in main.cpp.

This code is based on a Matlab implementation, by Yi Cao, that can be found in the link below. http://www.mathworks.com/matlabcentral/fileexchange/20652-hungarian-algorithm-for-linear-assignment-problems--v2-3-

As is, the code may still receive some optimizations, which might be necesasary if very large assignment problems are being solved. For small problems, about 15x15, the runtime is lower than 0.1ms.

At your own risk, feel free to use this code to whatever purposes you wish.

An extension of the Munkres algorithm for the assignment problem to rectangular matrices

• Hacker News
• Download PDF
• Join the Discussion
• View in the ACM Digital Library

The assignment problem, together with Munkres proposed algorithm for its solution in square matrices, is presented first. Then the authors develop an extension of this algorithm which permits a solution for rectangular matrices. Timing results obtained by using an adapted version of Silver's Algol procedure are discussed, and a relation between solution time and problem size is given.

View this article in the ACM Digital Library.

Submit an Article to CACM

CACM welcomes unsolicited submissions on topics of relevance and value to the computing community.

You Just Read

December 1971 Issue

Published: December 1, 1971

Vol. 14 No. 12

Pages: 802-804

Advertisement

Join the Discussion (0)

Become a member or sign in to post a comment, the latest from cacm.

3D Printing Finds a Home

HiPEAC’s Vision for the Future

A Brief History of Embodied Artificial Intelligence, and Its Future Outlook

Shape the Future of Computing

ACM encourages its members to take a direct hand in shaping the future of the association. There are more ways than ever to get involved.

Communications of the ACM (CACM) is now a fully Open Access publication.

By opening CACM to the world, we hope to increase engagement among the broader computer science community and encourage non-members to discover the rich resources ACM has to offer.

A new implementation of an algorithm for the optimal assignment problem: An improved version of Munkres' algorithm

• Published: September 1979
• Volume 19 , pages 418–424, ( 1979 )

Cite this article

• Jin Kue Wong 1   nAff2  

267 Accesses

14 Citations

Explore all metrics

Existing implementations of Munkres' algorithm for the optimal assignment problem are shown to require O ( n 4 ) time in the worst n × n case. A new implementation is presented which runs in worst-case time O ( n 3 ) and compares favorably in performance with the algorithm of Edmonds and Karp for this problem.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Price includes VAT (Russian Federation)

Instant access to the full article PDF.

Rent this article via DeepDyve

Institutional subscriptions

Similar content being viewed by others

Some results on an assignment problem variant

The assignment problem revisited

A Full Description of Polytopes Related to the Index of the Lowest Nonzero Row of an Assignment Matrix

J. Edmonds and R. M. Karp, Theoretical improvements in algorithmic efficiency for network flow problems , JACM 19:2 (April 1972), 248–264.

Article   Google Scholar  

L. R. Ford, Jr. and D. R. Fulkerson, Flows in Networks , Princeton University Press, (1962), 53–55.

L. R. Kerr, The effect of algebraic structure on the computational complexity of matrix multiplication , (Ph.D. thesis), Cornell Univ., June 1970.

J. Munkres, Algorithms for the assignment and transportation problems , J. SIAM 5:1 (March 1957), 32–38.

Google Scholar  

R. Silver, An algorithm for the assignment problem , Comm. ACM 3:11, (Nov. 1960), 605–606.

Download references

Author information

Jin Kue Wong

Present address: Department of Computer Science, University of Ottawa, Kin 6N5, Ottawa, Ontario, Canada

Authors and Affiliations

Department of Systems & Information Science, Vanderbilt University, 37235, Nashville, Tennessee, U.S.A.

You can also search for this author in PubMed   Google Scholar

Additional information

The results of this paper were obtained by the author while at the Department of Computer Science, Cornell University. This work was supported in part by a Vanderbilt University Research Council Grant.

Rights and permissions

Reprints and permissions

About this article

Wong, J.K. A new implementation of an algorithm for the optimal assignment problem: An improved version of Munkres' algorithm. BIT 19 , 418–424 (1979). https://doi.org/10.1007/BF01930994

Download citation

Received : 22 November 1978

Issue Date : September 1979

DOI : https://doi.org/10.1007/BF01930994

Share this article

Anyone you share the following link with will be able to read this content:

Sorry, a shareable link is not currently available for this article.

Provided by the Springer Nature SharedIt content-sharing initiative

Keywords and phrases

• Optimal assignment problem
• worst-case time
• analysis of algorithms

CR categories

• Find a journal
• Publish with us
• Track your research

• RcppArmadillo
• RcppExamples
• Dirk's Rcpp page
• Romain's Rcpp page
• Rcpp at CRAN
• Rcpp at GitHub
• Rcpp at R-Forge
• Rcpp-Devel list at Gmane
• StackOverflow on Rcpp

Munkres' Assignment Algorithm with RcppArmadillo

Lars Simon Zehnder — written Sep 24, 2013 — source

Munkres’ Assignment Algorithm ( Munkres (1957) , also known as hungarian algorithm ) is a well known algorithm in Operations Research solving the problem to optimally assign N jobs to N workers.

I needed to solve the Minimal Assignment Problem for a relabeling algorithm in MCMC sampling for finite mixture distributions, where I use a random permutation Gibbs sampler. For each sample an optimal labeling must be found, i.e. I have N parameter vectors and must assign each vector to one of the N components of the finite mixture under the restriction that each component gets a parameter vector. For the assignment of parameters to components [Stephens (1997b)] (http://www.isds.duke.edu/~scs/Courses/Stat376/Papers/Mixtures/LabelSwitchingStephensJRSSB.pdf) suggests an algorithm relying on the Minimal Assignment in regard to a loss matrix . The labeling with the smallest loss is then considered as optimal.

After an unsuccessful search for libraries implementing the algorithm easily for C++ or C, I made the decision to program it myself using RcppArmadillo for good performance. I found some guidance by the websites of Bob Pilgrim and [TopCoder] (http://community.topcoder.com/tc?module=Static&d1=tutorials&d2=hungarianAlgorithm). These websites offer excellent tutorials to understand the algorithm and to convert it to code. The order of this implementation of Munkres’ algorithm is of an order N to the power of 4. There exists also a version of order N to the power of 3, but an order of N to the power of 4 works very good for me and coding time is as usual a critical factor for me.

In the following I walk through the different steps of Munkres’ algorithm and explain the main parts and their functionality.

Let’s begin. The first step in Munkres’ algorithm is to subtract the minimal element of each row from each element in this row.

Note, that we use references for all function arguments. As we have to switch between the steps of the algorithm continously, we always must be able to determine which step should be chosen next. Therefore we give a mutable unsigned integer step as an argument to each step function of the algorithm.

Inside the function we can easily access a whole row by Armadillo’s row() method for matrices. In the second step, we then search for a zero in the modified cost matrix of step one.

Only the first zero in a row is taken. Then, the indicator matrix indM indicates this zero by setting the corresponding element at (r, c) to 1. A unique zero - the only or first one in a column and row - is called starred zero . In step 2 we find such a starred zero .

Note, that we use here Armadillo’s element access via the method at() , which makes no bound checks and improves performance.

Note Bene: This code is thoroughly debugged - never do this for fresh written code!

In step 3 we cover each column with a starred zero . If already N columns are covered all starred zeros describe a complete assignment - so, go to step 7 and finish. Otherwise go to step 4 .

We cover a column by looking for 1s in the indicator matrix indM (See step 2 for assuring that these are indeed only starred zeros ).

Step 4 finds noncovered zeros and primes them. If there are zeros in a row and none of them is starred , prime them. For this task we program a helper function to keep the code more readable and reusable. The helper function searches for noncovered zeros .

We can detect noncovered zeros by checking if the cost matrix contains at row r and column c a zero and row and column are not covered yet, i.e. rcov(r) == 0 , ccov(c) == 0 . This loop breaks, if we have found our first uncovered zero or no uncovered zero at all.

In step 4 , if no uncovered zero is found we go to step 6 . If instead an uncovered zero has been found, we set the indicator matrix at its position to 2. We then have to search for a starred zero in the row with the uncovered zero , uncover the column with the starred zero and cover the row with the starred zero . To indicate a starred zero in a row and to find it we create again two helper functions.

We know that starred zeros are indicated by the indicator matrix containing an element equal to 1. Now, step 4 .

Notice the rpath_0 and cpath_0 variables. These integer variables store the first vertex for an augmenting path in step 5 . If zeros could be primed we go further to step 5 .

Step 5 constructs a path beginning at an uncovered primed zero (this is actually graph theory - alternating and augmenting paths) and alternating between starred and primed zeros . This path is continued until a primed zero with no starred zero in its column is found. Then, all starred zeros in this path are unstarred and all primed zeros are starred . All primes in the indicator matrix are erased and all rows are uncovered . Then return to step 3 to cover again columns.

Step 5 needs several helper functions. First, we need a function to find starred zeros in columns.

Then we need a function to find a primed zero in a row. Note, that these tasks are easily performed by searching the indicator matrix indM .

In addition we need a function to augment the path, one to clear the covers from rows and one to erase the primed zeros from the indicator matrix indM .

The function to augment the path gets an integer matrix path of dimension 2 * N x 2. In it all vertices between rows and columns are stored row-wise. Now, we can set the complete step 5 :

Recall, if step 4 was successfull in uncovering all columns and covering all rows with a primed zero, it then calls step 6 . Step 6 takes the cover vectors rcov and ccov and looks in the uncovered region of the cost matrix for the smallest value. It then subtracts this value from each element in an uncovered column and adds it to each element in a covered row . After this transformation, the algorithm starts again at step 4 . Our last helper function searches for the smallest value in the uncovered region of the cost matrix.

Step 6 looks as follows:

At last, we must create a function that enables us to jump around the different steps of the algorithm. The following code shows the main function of the algorithm. It defines also the important variables to be passed to the different steps.

Note, this function takes the numeric cost matrix as an argument and returns the integer indicator matrix indM .

I chose to set the argument input_cost constant and copy it for reasons of reusability of the cost matrix in other C++ code. When working with rather huge cost matrices, it makes sense to make the argument mutable. Though, I used pass-by-reference for all the arguments in functions to avoid useless copying inside the functions.

To call the main function hungarian from R and to use our algorithm we construct an Rcpp Attribute :

If we want to provide this function also to other users we should probably ensure, that the matrix is square (There exists also an extension to rectangular matrices, see Burgeois and Lasalle (1971) ). This can be done easily with the exceptions provided by Rcpp passed over to R:

Note, that it is also possible to use for the attribute directly an Armadillo matrix, but following the recent discussion on the Rcpp-devel list , a pass-by-reference of arguments is not yet possible. Romain Francois’ proposals seem promising, so maybe we can expect in some of the next releases shallow copies allowing pass-by-reference in Rcpp Attributes .

Let us begin now with a very easy example that makes clear what is going on.

We can also compute a maximal assignment over a revenue matrix by simply considering the difference between a big value and this matrix as a cost matrix.

CoCost matrices containing negative values work as well:

Finally let us make some benchmarking. We load the rbenchmark package and take now a more realistic cost matrix.

But we also see, where the limitations of this algorithm lie

• huge matrices:

Some last notes on the structure of the code. I prefer to put the code of the algorithm in an header file, e.g. hungarian.h . And use an attributes.cpp ( attributes.cc ) file to program the Rcpp Attributes . With this, I can easily reuse the algorithm in C++ code by simple inclusion ( #include "hungarian.h" ) and have a complete overview on all the C++ functions I export to R.

tags: armadillo  

Related Articles

• Extending R with C++ and Fortran — Dirk Eddelbuettel and JBrandon Duck-Mayr
• Benchmarking Rcpp code with RcppClock — Zach DeBruine
• Simulation Smoother using RcppArmadillo — Tomasz Woźniak

Help Center Help Center

• Help Center
• Trial Software
• Product Updates
• Documentation

assignmunkres

Munkres global nearest neighbor assignment algorithm

Description

[ assignments , unassignedrows , unassignedcolumns ] = assignmunkres( costmatrix , costofnonassignment ) returns a table of assignments of detections to tracks using the Munkres algorithm. The Munkres algorithm obtains an optimal solution to the global nearest neighbor (GNN) assignment problem. An optimal solution minimizes the total cost of the assignments.

The cost of each potential assignment is contained in the cost matrix, costmatrix . Each matrix entry represents the cost of a possible assignments. Matrix rows represent tracks and columns represent detections. All possible assignments are represented in the cost matrix. The lower the cost, the more likely the assignment is to be made. Each track can be assigned to at most one detection and each detection can be assigned to at most one track. If the number of rows is greater than the number of columns, some tracks are unassigned. If the number of columns is greater than the number of rows, some detections are unassigned. You can set an entry of costmatrix to Inf to prohibit an assignment.

costofnonassignment represents the cost of leaving tracks or detections unassigned. Higher values increase the likelihood that every existing object is assigned.

The function returns a list of unassigned tracks, unassignedrows , and a list of unassigned detections, unassignedcolumns

collapse all

Assign Detections to Tracks Using Munkres Algorithm

Use assignMunkres to assign three detections to two tracks.

Start with two predicted track locations in x-y coordinates.

Assume three detections are received. At least one detection will not be assigned.

Construct a cost matrix by defining the cost of assigning a detection to a track as the Euclidean distance between them. Set the cost of non-assignment to 0.2.

Use the Auction algorithm to assign detections to tracks.

Display the assignments.

Show that there are no unassigned tracks.

Display the unassigned detections.

Plot detection to track assignments.

The track to detection assignments are:

Detection 1 is assigned to track 1.

Detection 2 is assigned to track 2.

Detection 3 is not assigned.

Input Arguments

Costmatrix — cost matrix real-valued m -by- n.

Cost matrix, specified as an M -by- N matrix. M is the number of tracks to be assigned and N is the number of detections to be assigned. Each entry in the cost matrix contains the cost of a track and detection assignment. The matrix may contain Inf entries to indicate that an assignment is prohibited. The cost matrix cannot be a sparse matrix.

Data Types: single | double

costofnonassignment — cost of non-assignment of tracks and detections scalar

Cost of non-assignment, specified as a scalar. The cost of non-assignment represents the cost of leaving tracks or detections unassigned. Higher values increase the likelihood that every object is assigned. The value cannot be set to Inf .

The costofnonassignment is half of the maximum cost that a successful assignment can have.

Output Arguments

Assignments — assignment of tracks to detections integer-valued l -by-2 matrix.

Assignment of detections to track, returned as an integer-valued L -by-2 matrix where L is the number of assignments. The first column of the matrix contains the assigned track indices and the second column contains the assigned detection indices.

Data Types: uint32

unassignedrows — Indices of unassigned tracks integer-valued P -by-1 column vector

Indices of unassigned tracks, returned as an integer-valued P -by-1 column vector.

unassignedcolumns — Indices of unassigned detections integer-valued Q -by-1 column vector

Indices of unassigned detections, returned as an integer-valued Q -by-1 column vector.

[1] Samuel S. Blackman and Popoli, R. Design and Analysis of Modern Tracking Systems . Artech House: Norwood, MA. 1999.

Extended Capabilities

C/c++ code generation generate c and c++ code using matlab® coder™., version history.

Introduced in R2018b

• assignauction | assignjv | assignkbest | assignkbestsd | assignsd | assignTOMHT | trackerTOMHT | trackerGNN

MATLAB Command

You clicked a link that corresponds to this MATLAB command:

Run the command by entering it in the MATLAB Command Window. Web browsers do not support MATLAB commands.

Select a Web Site

Choose a web site to get translated content where available and see local events and offers. Based on your location, we recommend that you select: .

• Switzerland (English)
• Switzerland (Deutsch)
• Switzerland (Français)
• 中国 (English)

You can also select a web site from the following list:

How to Get Best Site Performance

Select the China site (in Chinese or English) for best site performance. Other MathWorks country sites are not optimized for visits from your location.

• América Latina (Español)
• Canada (English)
• United States (English)
• Belgium (English)
• Denmark (English)
• Deutschland (Deutsch)
• España (Español)
• Finland (English)
• France (Français)
• Ireland (English)
• Italia (Italiano)
• Luxembourg (English)
• Netherlands (English)
• Norway (English)
• Österreich (Deutsch)
• Portugal (English)
• Sweden (English)
• United Kingdom (English)

Asia Pacific

• Australia (English)
• India (English)
• New Zealand (English)

Contact your local office

The blue social bookmark and publication sharing system.

Log in with your username.

I've lost my password.

Log in with your OpenID-Provider.

• Other OpenID-Provider

Munkres' Assignment Algorithm Modified for Rectangular Matrices

Http://216.249.163.93/bob.pilgrim/445/munkres.html, description.

in admob's case (e.g. a profit-maximization problem), the cost matrix prob should be modified so that minimization of the matrix elements results in maximizing the original cost values

• information
• programming

Comments and Reviews show / hide

BibSonomy is offered by the Data Science Chair of the University of Würzburg, the Information Processing and Analytics Group of the Humboldt-Unversität zu Berlin, the KDE Group of the University of Kassel, and the L3S Research Center .

AN EXTENSION OF THE MUNKRES ALGORITHM FOR THE ASSIGNMENT PROBLEM TO RECTANGULAR MATRICES

• CERN-DD-DH-71-1

Citations per year

• Submitted to Commun.ACM

use Algorithm::Munkres;

assign(\@mat,\@out_mat);

DESCRIPTION

Copyright and license.

Copyright (C) 2007-2008, Ted Pedersen and Anagha Kulkarni

This program is free software; you can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free Software Foundation; either version 2 of the License, or (at your option) any later version. This program is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details.

You should have received a copy of the GNU General Public License along with this program; if not, write to the Free Software Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.

1 POD Error

The following errors were encountered while parsing the POD:

Non-ASCII character seen before =encoding in 'François'. Assuming UTF-8

Module Install Instructions

To install Algorithm::Munkres, copy and paste the appropriate command in to your terminal.

For more information on module installation, please visit the detailed CPAN module installation guide .

Keyboard Shortcuts

Munkres' assignment algorithm

(algorithm)

Definition: Solve the assignment problem in polynomial time by marking and unmarking entries and covering and uncovering rows and columns.

Also known as Hungarian algorithm.

Author: PEB

Implementation

More information.

James Munkres , 1957.

If you have suggestions, corrections, or comments, please get in touch with Paul Black .

Entry modified 14 December 2020. HTML page formatted Mon Dec 14 10:59:03 2020.

Cite this as: Paul E. Black, "Munkres' assignment algorithm", in Dictionary of Algorithms and Data Structures [online], Paul E. Black, ed. 14 December 2020. (accessed TODAY) Available from: https://www.nist.gov/dads/HTML/munkresAssignment.html