Munkres Yi Cao.m

function [assignment,cost] = Munkres_Yi_Cao(costMat)
% MUNKRES   Munkres (Hungarian) Algorithm for Linear Assignment Problem. 
%
% [ASSIGN,COST] = munkres(COSTMAT) returns the optimal column indices,
% ASSIGN assigned to each row and the minimum COST based on the assignment
% problem represented by the COSTMAT, where the (i,j)th element represents the cost to assign the jth
% job to the ith worker.
%
% Partial assignment: This code can identify a partial assignment is a full
% assignment is not feasible. For a partial assignment, there are some
% zero elements in the returning assignment vector, which indicate
% un-assigned tasks. The cost returned only contains the cost of partially
% assigned tasks.
% This is vectorized implementation of the algorithm. It is the fastest
% among all Matlab implementations of the algorithm.
% Examples
% Example 1: a 5 x 5 example
%{ [assignment,cost] = munkres(magic(5));
%   disp(assignment); % 3 2 1 5 4
%   disp(cost); %15
%}
% Example 2: 400 x 400 random data
%{
  n=400;
  A=rand(n);
  tic
  [a,b]=munkres(A);
  toc                 % about 2 seconds 
%}
% Example 3: rectangular assignment with inf costs
%{
  A=rand(10,7);
  A(A>0.7)=Inf;
  [a,b]=munkres(A);
%}
% Example 4: an example of partial assignment
%{
  A = [1 3 Inf; Inf Inf 5; Inf Inf 0.5]; 
  [a,b]=munkres(A)
%}
% a = [1 0 3]
% b = 1.5
% Reference:
% "Munkres' Assignment Algorithm, Modified for Rectangular Matrices", 
% http://csclab.murraystate.edu/bob.pilgrim/445/munkres.html

% version 2.3 by Yi Cao at Cranfield University on 11th September 2011