matthiasm@8: % MATCH - Solves the weighted bipartite matching (or assignment)
matthiasm@8: %         problem.
matthiasm@8: %
matthiasm@8: % Usage:  a = match(C);
matthiasm@8: %
matthiasm@8: % Arguments:   
matthiasm@8: %         C     - an m x n cost matrix; the sets are taken to be
matthiasm@8: %                 1:m and 1:n; C(i, j) gives the cost of matching
matthiasm@8: %                 items i (of the first set) and j (of the second set)
matthiasm@8: %
matthiasm@8: % Returns:
matthiasm@8: %
matthiasm@8: %         a     - an m x 1 assignment vector, which gives the
matthiasm@8: %                 minimum cost assignment.  a(i) is the index of
matthiasm@8: %                 the item of 1:n that was matched to item i of
matthiasm@8: %                 1:m.  If item i (of 1:m) was not matched to any 
matthiasm@8: %                 item of 1:n, then a(i) is zero.
matthiasm@8: 
matthiasm@8: % Copyright (C) 2002 Mark A. Paskin
matthiasm@8: %
matthiasm@8: % This program is free software; you can redistribute it and/or modify
matthiasm@8: % it under the terms of the GNU General Public License as published by
matthiasm@8: % the Free Software Foundation; either version 2 of the License, or
matthiasm@8: % (at your option) any later version.
matthiasm@8: %
matthiasm@8: % This program is distributed in the hope that it will be useful, but
matthiasm@8: % WITHOUT ANY WARRANTY; without even the implied warranty of
matthiasm@8: % MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
matthiasm@8: % General Public License for more details.
matthiasm@8: %
matthiasm@8: % You should have received a copy of the GNU General Public License
matthiasm@8: % along with this program; if not, write to the Free Software
matthiasm@8: % Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307
matthiasm@8: % USA.
matthiasm@8: %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
matthiasm@8: 
matthiasm@8: function [a] = optimalMatching(C)
matthiasm@8: 
matthiasm@8: % Trivial cases:
matthiasm@8: [p, q] = size(C);
matthiasm@8: if (p == 0)
matthiasm@8:   a = []; 
matthiasm@8:   return;
matthiasm@8: elseif (q == 0)
matthiasm@8:   a = zeros(p, 1);
matthiasm@8:   return;
matthiasm@8: end
matthiasm@8: 
matthiasm@8: 
matthiasm@8: if  0
matthiasm@8: % First, reduce the problem by making easy optimal matches.  If two
matthiasm@8: % elements agree that they are the best match, then match them up.
matthiasm@8: [x, a] = min(C, [], 2);
matthiasm@8: [y, b] = min(C, [], 1);
matthiasm@8: u = find(1:p ~= b(a(:)));
matthiasm@8: a(u) = 0;
matthiasm@8: v = find(1:q ~= a(b(:))');
matthiasm@8: C = C(u, v);
matthiasm@8: if (isempty(C)) return; end
matthiasm@8: end
matthiasm@8: 
matthiasm@8: % Get the (new) size of the two sets, u and v.
matthiasm@8: [m, n] = size(C);
matthiasm@8: 
matthiasm@8: %mx = realmax;
matthiasm@8: mx = 2*max(C(:));
matthiasm@8: mn = -2*min(C(:));
matthiasm@8: % Pad the affinity matrix to be square
matthiasm@8: if (m < n)
matthiasm@8:   C = [C; mx * ones(n - m, n)];
matthiasm@8: elseif (n < m)
matthiasm@8:   C = [C, mx * ones(m, m - n)];
matthiasm@8: end
matthiasm@8: 
matthiasm@8: % Run the Hungarian method.  First replace infinite values by the
matthiasm@8: % largest (or smallest) finite values.
matthiasm@8: C(find(isinf(C) & (C > 0))) = mx;
matthiasm@8: C(find(isinf(C) & (C < 0))) = mn;
matthiasm@8: %fprintf('running hungarian\n');
matthiasm@8: [b, cost] = hungarian(C');
matthiasm@8: 
matthiasm@8: % Extract only the real assignments
matthiasm@8: ap = b(1:m)';
matthiasm@8: ap(find(ap > n)) = 0;
matthiasm@8: 
matthiasm@8: a = ap; 
matthiasm@8: %% Incorporate this sub-assignment into the complete assignment
matthiasm@8: %  k = find(ap);
matthiasm@8: %  a(u(k)) = v(ap(k));
matthiasm@8: