munkres assignment algorithm c

Forgot password? New user? Sign up

Existing user? Log in

Hungarian Maximum Matching Algorithm

Already have an account? Log in here.

The Hungarian matching algorithm , also called the Kuhn-Munkres algorithm, is a $O\big(|V|^3\big)$ algorithm that can be used to find maximum-weight matchings in bipartite graphs , which is sometimes called the assignment problem . A bipartite graph can easily be represented by an adjacency matrix , where the weights of edges are the entries. Thinking about the graph in terms of an adjacency matrix is useful for the Hungarian algorithm.

A matching corresponds to a choice of 1s in the adjacency matrix, with at most one 1 in each row and in each column.

The Hungarian algorithm solves the following problem:

In a complete bipartite graph $G$, find the maximum-weight matching. (Recall that a maximum-weight matching is also a perfect matching.)

This can also be adapted to find the minimum-weight matching.

Say you are having a party and you want a musician to perform, a chef to prepare food, and a cleaning service to help clean up after the party. There are three companies that provide each of these three services, but one company can only provide one service at a time (i.e. Company B cannot provide both the cleaners and the chef). You are deciding which company you should purchase each service from in order to minimize the cost of the party. You realize that is an example of the assignment problem, and set out to make a graph out of the following information: $\quad$ Company$\quad$ $\quad$ Cost for Musician$\quad$ $\quad$ Cost for Chef$\quad$ $\quad$ Cost for Cleaners$\quad$ $\quad$ Company A$\quad$ $\quad$ $108$\quad$ $\quad$ $125$\quad$ $\quad$ $150$\quad$ $\quad$ Company B$\quad$ $\quad$ $150$\quad$ $\quad$ $135$\quad$ $\quad$ $175$\quad$ $\quad$ Company C$\quad$ $\quad$ $122$\quad$ $\quad$ $148$\quad$ $\quad$ $250$\quad$ Can you model this table as a graph? What are the nodes? What are the edges? Show Answer The nodes are the companies and the services. The edges are weighted by the price.

What are some ways to solve the problem above? Since the table above can be thought of as a $3 \times 3$ matrix, one could certainly solve this problem using brute force, checking every combination and seeing what yields the lowest price. However, there are $n!$ combinations to check, and for large $n$, this method becomes very inefficient very quickly.

The Hungarian Algorithm Using an Adjacency Matrix

The hungarian algorithm using a graph.

With the cost matrix from the example above in mind, the Hungarian algorithm operates on this key idea: if a number is added to or subtracted from all of the entries of any one row or column of a cost matrix, then an optimal assignment for the resulting cost matrix is also an optimal assignment for the original cost matrix.

The Hungarian Method [1] Subtract the smallest entry in each row from all the other entries in the row. This will make the smallest entry in the row now equal to 0. Subtract the smallest entry in each column from all the other entries in the column. This will make the smallest entry in the column now equal to 0. Draw lines through the row and columns that have the 0 entries such that the fewest lines possible are drawn. If there are $n$ lines drawn, an optimal assignment of zeros is possible and the algorithm is finished. If the number of lines is less than $n$, then the optimal number of zeroes is not yet reached. Go to the next step. Find the smallest entry not covered by any line. Subtract this entry from each row that isn’t crossed out, and then add it to each column that is crossed out. Then, go back to Step 3.

Solve for the optimal solution for the example in the introduction using the Hungarian algorithm described above. Here is the initial adjacency matrix: Subtract the smallest value in each row from the other values in the row: Now, subtract the smallest value in each column from all other values in the column: Draw lines through the row and columns that have the 0 entries such that the fewest possible lines are drawn: There are 2 lines drawn, and 2 is less than 3, so there is not yet the optimal number of zeroes. Find the smallest entry not covered by any line. Subtract this entry from each row that isn’t crossed out, and then add it to each column that is crossed out. Then, go back to Step 3. 2 is the smallest entry. First, subtract from the uncovered rows: Now add to the covered columns: Now go back to step 3, drawing lines through the rows and columns that have 0 entries: There are 3 lines (which is $n$), so we are done. The assignment will be where the 0's are in the matrix such that only one 0 per row and column is part of the assignment. Replace the original values: The Hungarian algorithm tells us that it is cheapest to go with the musician from company C, the chef from company B, and the cleaners from company A. We can verify this by brute force. 108 + 135 + 250 = 493 108 + 148 + 175 = 431 150 + 125 + 250 = 525 150 + 148 + 150 = 448 122 + 125 + 175 = 422 122 + 135 + 150 = 407. We can see that 407 is the lowest price and matches the assignment the Hungarian algorithm determined. $_\square$

The Hungarian algorithm can also be executed by manipulating the weights of the bipartite graph in order to find a stable, maximum (or minimum) weight matching. This can be done by finding a feasible labeling of a graph that is perfectly matched, where a perfect matching is denoted as every vertex having exactly one edge of the matching.

How do we know that this creates a maximum-weight matching?

A feasible labeling on a perfect match returns a maximum-weighted matching. Suppose each edge $e$ in the graph $G$ connects two vertices, and every vertex $v$ is covered exactly once. With this, we have the following inequality: \[w(M’) = \sum_{e\ \epsilon\ E} w(e) \leq \sum_{e\ \epsilon\ E } \big(l(e_x) + l(e_y)\big) = \sum_{v\ \epsilon\ V} l(v),\] where $M’$ is any perfect matching in $G$ created by a random assignment of vertices, and $l(x)$ is a numeric label to node $x$. This means that $\sum_{v\ \epsilon\ V}\ l(v)$ is an upper bound on the cost of any perfect matching. Now let $M$ be a perfect match in $G$, then \[w(M) = \sum_{e\ \epsilon\ E} w(e) = \sum_{v\ \epsilon\ V}\ l(v).\] So $w(M’) \leq w(M)$ and $M$ is optimal. $_\square$

Start the algorithm by assigning any weight to each individual node in order to form a feasible labeling of the graph $G$. This labeling will be improved upon by finding augmenting paths for the assignment until the optimal one is found.

A feasible labeling is a labeling such that

$l(x) + l(y) \geq w(x,y)\ \forall x \in X, y \in Y$, where $X$ is the set of nodes on one side of the bipartite graph, $Y$ is the other set of nodes, $l(x)$ is the label of $x$, etc., and $w(x,y)$ is the weight of the edge between $x$ and $y$.

A simple feasible labeling is just to label a node with the number of the largest weight from an edge going into the node. This is certain to be a feasible labeling because if $A$ is a node connected to $B$, the label of $A$ plus the label of $B$ is greater than or equal to the weight $w(x,y)$ for all $y$ and $x$.

A feasible labeling of nodes, where labels are in red [2] .

Imagine there are four soccer players and each can play a few positions in the field. The team manager has quantified their skill level playing each position to make assignments easier.

How can players be assigned to positions in order to maximize the amount of skill points they provide?

The algorithm starts by labeling all nodes on one side of the graph with the maximum weight. This can be done by finding the maximum-weighted edge and labeling the adjacent node with it. Additionally, match the graph with those edges. If a node has two maximum edges, don’t connect them.

Although Eva is the best suited to play defense, she can't play defense and mid at the same time!

If the matching is perfect, the algorithm is done as there is a perfect matching of maximum weights. Otherwise, there will be two nodes that are not connected to any other node, like Tom and Defense. If this is the case, begin iterating.

Improve the labeling by finding the non-zero label vertex without a match, and try to find the best assignment for it. Formally, the Hungarian matching algorithm can be executed as defined below:

The Hungarian Algorithm for Graphs [3] Given: the labeling $l$, an equality graph $G_l = (V, E_l)$, an initial matching $M$ in $G_l$, and an unmatched vertex $u \in V$ and $u \notin M$ Augmenting the matching A path is augmenting for $M$ in $G_l$ if it alternates between edges in the matching and edges not in the matching, and the first and last vertices are free vertices , or unmatched, in $M$. We will keep track of a candidate augmenting path starting at the vertex $u$. If the algorithm finds an unmatched vertex $v$, add on to the existing augmenting path $p$ by adding the $u$ to $v$ segment. Flip the matching by replacing the edges in $M$ with the edges in the augmenting path that are not in $M$ $($in other words, the edges in $E_l - M).$ Improving the labeling $S \subseteq X$ and $T \subseteq Y,$ where $S$ and $T$ represent the candidate augmenting alternating path between the matching and the edges not in the matching. Let $N_l(S)$ be the neighbors to each node that is in $S$ along edges in $E_l$ such that $N_l(S) = \{v|\forall u \in S: (u,v) \in E_l\}$. If $N_l(S) = T$, then we cannot increase the size of the alternating path (and therefore can't further augment), so we need to improve the labeling. Let $\delta_l$ be the minimum of $l(u) + l(v) - w(u,v)$ over all of the $u \in S$ and $v \notin T$. Improve the labeling $l$ to $l'$: If $r \in S,$ then $l'(r) = l(r) - \delta_l,$ If $r \in T,$ then $l'(r) = l(r) + \delta_l.$ If $r \notin S$ and $r \notin T,$ then $l'(r) = l(r).$ $l'$ is a valid labeling and $E_l \subset E_{l'}.$ Putting it all together: The Hungarian Algorithm Start with some matching $M$, a valid labeling $l$, where $l$ is defined as the labelling $\forall x \in X, y \in Y| l(y) = 0, l(x) = \text{ max}_{y \in Y}(w\big(x, y)\big)$. Do these steps until a perfect matching is found $($when $M$ is perfect$):$ (a) Look for an augmenting path in $M.$ (b) If an augmenting path does not exist, improve the labeling and then go back to step (a).

Each step will increase the size of the matching $M$ or it will increase the size of the set of labeled edges, $E_l$. This means that the process will eventually terminate since there are only so many edges in the graph $G$. [4]

When the process terminates, $M$ will be a perfect matching. By the Kuhn-Munkres theorem , this means that the matching is a maximum-weight matching.

The algorithm defined above can be implemented in the soccer scenario. First, the conflicting node is identified, implying that there is an alternating tree that must be reconfigured.

There is an alternating path between defense, Eva, mid, and Tom.

To find the best appropriate node, find the minimum $\delta_l$, as defined in step 4 above, where $l_u$ is the label for player $u,$ $l_v$ is the label for position $v,$ and $w_{u, v}$ is the weight on that edge.

The $\delta_l$ of each unmatched node is computed, where the minimum is found to be a value of 2, between Tom playing mid $(8 + 0 – 6 = 2).$

The labels are then augmented and the new edges are graphed in the example. Notice that defense and mid went down by 2 points, whereas Eva’s skillset got back two points. However, this is expected as Eva can't play in both positions at once.

Augmenting path leads to relabeling of nodes, which gives rise to the maximum-weighted path.

These new edges complete the perfect matching of the graph, which implies that a maximum-weighted graph has been found and the algorithm can terminate.

The complexity of the algorithm will be analyzed using the graph-based technique as a reference, yet the result is the same as for the matrix-based one.

Algorithm analysis [3] At each $a$ or $b$ step, the algorithm adds one edge to the matching and this happens $O\big(|V|\big)$ times. It takes $O\big(|V|\big)$ time to find the right vertex for the augmenting (if there is one at all), and it is $O\big(|V|\big)$ time to flip the matching. Improving the labeling takes $O\big(|V|\big)$ time to find $\delta_l$ and to update the labelling accordingly. We might have to improve the labeling up to $O\big(|V|\big)$ times if there is no augmenting path. This makes for a total of $O\big(|V|^2\big)$ time. In all, there are $O\big(|V|\big)$ iterations each taking $O\big(|V|\big)$ work, leading to a total running time of $O\big(|V|^3\big)$.

Matching Algorithms
Bruff, D. The Assignment Problem and the Hungarian Method . Retrieved June 26, 2016, from http://www.math.harvard.edu/archive/20_spring_05/handouts/assignment_overheads.pdf
Golin, M. Bipartite Matching &amp; the Hungarian Method . Retrieved Retrieved June 26th, 2016, from http://www.cse.ust.hk/~golin/COMP572/Notes/Matching.pdf
Grinman, A. The Hungarian Algorithm for Weighted Bipartite Graphs . Retrieved June 26, 2016, from http://math.mit.edu/~rpeng/18434/hungarianAlgorithm.pdf
Golin, M. Bipartite Matching & the Hungarian Method . Retrieved June 26, 2016, from http://www.cse.ust.hk/~golin/COMP572/Notes/Matching.pdf

Problem Loading...

Note Loading...

Set Loading...

Data Structures
Linked List
Binary Tree
Binary Search Tree
Segment Tree
Disjoint Set Union
Fenwick Tree
Red-Black Tree
Advanced Data Structures
Solve Coding Problems
Hungarian Algorithm for Assignment Problem | Set 1 (Introduction)
Count of nodes with maximum connection in an undirected graph
Erdos Renyl Model (for generating Random Graphs)
Types of Graphs with Examples
Clustering Coefficient in Graph Theory
Maximum number of edges in Bipartite graph
Find node having maximum number of common nodes with a given node K
Convert the undirected graph into directed graph such that there is no path of length greater than 1
Count of Disjoint Groups by grouping points that are at most K distance apart
Maximize count of nodes disconnected from all other nodes in a Graph
Program to find the number of region in Planar Graph
Cost of painting n * m grid
Ways to Remove Edges from a Complete Graph to make Odd Edges
Number of Simple Graph with N Vertices and M Edges
Balance pans using given weights that are powers of a number
Chiliagon Number
Sum of all the numbers in the Nth parenthesis
Shortest path in a graph from a source S to destination D with exactly K edges for multiple Queries
Find if two given Quadratic equations have common roots or not

Hungarian Algorithm for Assignment Problem | Set 2 (Implementation)

Given a 2D array , arr of size N*N where arr[i][j] denotes the cost to complete the j th job by the i th worker. Any worker can be assigned to perform any job. The task is to assign the jobs such that exactly one worker can perform exactly one job in such a way that the total cost of the assignment is minimized.

Input: arr[][] = {{3, 5}, {10, 1}} Output: 4 Explanation: The optimal assignment is to assign job 1 to the 1st worker, job 2 to the 2nd worker. Hence, the optimal cost is 3 + 1 = 4. Input: arr[][] = {{2500, 4000, 3500}, {4000, 6000, 3500}, {2000, 4000, 2500}} Output: 4 Explanation: The optimal assignment is to assign job 2 to the 1st worker, job 3 to the 2nd worker and job 1 to the 3rd worker. Hence, the optimal cost is 4000 + 3500 + 2000 = 9500.

Different approaches to solve this problem are discussed in this article .

Approach: The idea is to use the Hungarian Algorithm to solve this problem. The algorithm is as follows:

For each row of the matrix, find the smallest element and subtract it from every element in its row.
Repeat the step 1 for all columns.
Cover all zeros in the matrix using the minimum number of horizontal and vertical lines.
Test for Optimality : If the minimum number of covering lines is N , an optimal assignment is possible. Else if lines are lesser than N , an optimal assignment is not found and must proceed to step 5.
Determine the smallest entry not covered by any line. Subtract this entry from each uncovered row, and then add it to each covered column. Return to step 3.

Consider an example to understand the approach:

Let the 2D array be: 2500 4000 3500 4000 6000 3500 2000 4000 2500 Step 1: Subtract minimum of every row. 2500, 3500 and 2000 are subtracted from rows 1, 2 and 3 respectively. 0 1500 1000 500 2500 0 0 2000 500 Step 2: Subtract minimum of every column. 0, 1500 and 0 are subtracted from columns 1, 2 and 3 respectively. 0 0 1000 500 1000 0 0 500 500 Step 3: Cover all zeroes with minimum number of horizontal and vertical lines. Step 4: Since we need 3 lines to cover all zeroes, the optimal assignment is found. 2500 4000 3500 4000 6000 3500 2000 4000 2500 So the optimal cost is 4000 + 3500 + 2000 = 9500

For implementing the above algorithm, the idea is to use the max_cost_assignment() function defined in the dlib library . This function is an implementation of the Hungarian algorithm (also known as the Kuhn-Munkres algorithm) which runs in O(N 3 ) time. It solves the optimal assignment problem.

Below is the implementation of the above approach:

Time Complexity: O(N 3 ) Auxiliary Space: O(N 2 )

Please Login to comment...

Mathematical
WhatsApp To Launch New App Lock Feature
Top Design Resources for Icons
Node.js 21 is here: What’s new
Zoom: World’s Most Innovative Companies of 2024
30 OOPs Interview Questions and Answers (2024)

Improve your Coding Skills with Practice

What kind of Experience do you want to share?

Introduction.

The Munkres algorithm described here aims to find an optimal solution which minimizes the total cost of the assignments .

For example, it can be used to match tracked (red) and detected (green) image points:

The following example also available in tutorial-munkres-assignment.cpp shows how to use Munkres algorithm:

The tutorial starts with 10 random image points (red) which represent our tracked points:

Then, by clicking on the image, the user is able to simulate the detected points (green):

Once the "fake" detection are selected, a cost matrix is built by defining the cost of assigning a track to a detection point as the Euclidean distance between them:

Finally, Munkres is ran to assign tracked points with the detected points (blue lines):

Munkres Assignment Algorithm

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

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

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

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

Kuhn-Munkres (Hungarian) Algorithm in C++

saebyn/munkres-cpp

Folders and files, repository files navigation, munkres-cpp.

An implementation of the Kuhn–Munkres algorithm.

Requirements

C++ compiler with C++11 support.

For development:

GCC (tested on 4.6.3, 4.8);
CMake (2.8.12);
the test suite requires the Google C++ Test Framework ;
microbenchmarking requires Benchmark , Celero , Hayai and gprof ;
code coverage requires gcov and lcov;
static code analyzer requires cppcheck .

Portability

The project is developed under the GNU/Linux OS with the gcc compiler and usually not tested under other OSs and compilers. But the project does not use OS or compiler specific features (types, attributes, etc) so it's expected that the project will be normally work under other platforms.

These steps are the easiest way to get started:

download: $ git clone https://github.com/saebyn/munkres-cpp.git && cd munkres-cpp
build: $ mkdir build && cd build && cmake .. && make
install: $ make install

Development

For development purpose, the project implements a variety of build targets. All of them help to continuously check correctness of algorithm implementation, performance, memory management, etc. Pass the -DMUNKRESCPP_DEVEL_MODE=ON option to CMake to enable development mode.

Running unit tests:

Build and execute the test suite with these commands:

Running code coverage analyzer:

You must compile unit tests in debug mode to get a correct code coverage report.

Running the memory profiler:

Since the unit tests call all functions which implement the algorithm, using valgrind on the unit test runner is an appropriate way to check memory management.

Running the microbenchmarks:

First, build them:

To get comparable results it's required to generate the data set wich will be used for all benchmarks:

Where every dim_x parameter generates a square matrix with dim_x dimension. To launch microbenchmarks, perform the following commands:

Getting performance profiling:

Running the static code analyzer:, running the code formatter:, bug reporting and work to be done.

Check the issues list at GitHub .

Contributors 4

CMake 15.3%

R news and tutorials contributed by hundreds of R bloggers

Munkres’ assignment algorithm with rcpparmadillo.

Posted on September 24, 2013 by Rcpp Gallery in R bloggers | 0 Comments

[social4i size="small" align="align-left"] --> [This article was first published on Rcpp Gallery , and kindly contributed to R-bloggers ]. (You can report issue about the content on this page here ) Want to share your content on R-bloggers? click here if you have a blog, or here if you don't.

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) 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 . 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.