hungarian.m

function [MatchingCost] = Hungarian（Perf）
% 
% [MATCHINGCOST] = Hungarian_New（WEIGHTS）
%
% A function for finding a minimum edge weight matching given a MxN Edge
% weight matrix WEIGHTS using the Hungarian Algorithm.
%
% An edge weight of Inf indicates that the pair of vertices given by its
% position have no adjacent edge.
%
% MATCHING return a MxN matrix with ones in the place of the matchings and
% zeros elsewhere.
% 
% COST returns the cost of the minimum matching

% Written by: Alex Melin 30 June 2006


 % Initialize Variables
 Matching = zeros（size（Perf））;

% Condense the Performance Matrix by removing any unconnected vertices to
% increase the speed of the algorithm

  % Find the number in each column that are connected
    num_y = sum（~isinf（Perf）1）;
  % Find the number in each row that are connected
    num_x = sum（~isinf（Perf）2）;
    
  % Find the columns（vertices） and rows（vertices） that are isolated
    x_con = find（num_x~=0）;
    y_con = find（num_y~=0）;
    
  % Assemble Condensed Performance Matrix
    P_size = max（length（x_con）length（y_con））;
    P_cond = zeros（P_size）;
    P_cond（1:length（x_con）1:length（y_con）） = Perf（x_cony_con）;
    if isempty（P_cond）
      Cost = 0;
      return
    end

    % Ensure that a perfect matching exists
      % Calculate a form of the Edge Matrix
      Edge = P_cond;
      Edge（P_cond~=Inf） = 0;
      % Find the deficiency（CNUM） in the Edge Matrix
      cnum = min_line_cover（Edge）;
    
      % Project additional vertices and edges so that a perfect matching
      % exists
      Pmax = max（max（P_cond（P_cond~=Inf）））;
      P_size = length（P_cond）+cnum;
      P_cond = ones（P_size）*Pmax;
      P_cond（1:length（x_con）1:length（y_con）） = Perf（x_cony_con）;
     
   
%*************************************************
% MAIN PROGRAM: CONTROLS WHICH STEP IS EXECUTED
%*************************************************
  exit_flag = 1;
  stepnum = 1;
  while exit_flag
    switch stepnum
      case 1
        [P_condstepnum] = step1（P_cond）;
      case 2
        [r_covc_covMstepnum] = step2（P_cond）;
      case 3
        [c_covstepnum] = step3（MP_size）;
      case 4
        [Mr_covc_covZ_rZ_cstepnum] = step4（P_condr_covc_covM）;
      case 5
        [Mr_covc_covstepnum] = step5（MZ_rZ_cr_covc_cov）;
      case 6
        [P_condstepnum] = step6（P_condr_covc_cov）;
      case 7
        exit_flag = 0;
    end
  end

% Remove all the virtual satellites and targets and uncondense the
% Matching to the size of the original performance matrix.
Matching（x_cony_con） = M（1:length（x_con）1:length（y_con））;
Cost = sum（sum（Perf（Matching==1）））;

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%   STEP 1: Find the smallest number of zeros in each row
%           and subtract that minimum from its row
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

function [P_condstepnum] = step1（P_cond）