|
wolffd@0
|
1 % MATCH - Solves the weighted bipartite matching (or assignment)
|
|
wolffd@0
|
2 % problem.
|
|
wolffd@0
|
3 %
|
|
wolffd@0
|
4 % Usage: a = match(C);
|
|
wolffd@0
|
5 %
|
|
wolffd@0
|
6 % Arguments:
|
|
wolffd@0
|
7 % C - an m x n cost matrix; the sets are taken to be
|
|
wolffd@0
|
8 % 1:m and 1:n; C(i, j) gives the cost of matching
|
|
wolffd@0
|
9 % items i (of the first set) and j (of the second set)
|
|
wolffd@0
|
10 %
|
|
wolffd@0
|
11 % Returns:
|
|
wolffd@0
|
12 %
|
|
wolffd@0
|
13 % a - an m x 1 assignment vector, which gives the
|
|
wolffd@0
|
14 % minimum cost assignment. a(i) is the index of
|
|
wolffd@0
|
15 % the item of 1:n that was matched to item i of
|
|
wolffd@0
|
16 % 1:m. If item i (of 1:m) was not matched to any
|
|
wolffd@0
|
17 % item of 1:n, then a(i) is zero.
|
|
wolffd@0
|
18
|
|
wolffd@0
|
19 % Copyright (C) 2002 Mark A. Paskin
|
|
wolffd@0
|
20 %
|
|
wolffd@0
|
21 % This program is free software; you can redistribute it and/or modify
|
|
wolffd@0
|
22 % it under the terms of the GNU General Public License as published by
|
|
wolffd@0
|
23 % the Free Software Foundation; either version 2 of the License, or
|
|
wolffd@0
|
24 % (at your option) any later version.
|
|
wolffd@0
|
25 %
|
|
wolffd@0
|
26 % This program is distributed in the hope that it will be useful, but
|
|
wolffd@0
|
27 % WITHOUT ANY WARRANTY; without even the implied warranty of
|
|
wolffd@0
|
28 % MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
|
|
wolffd@0
|
29 % General Public License for more details.
|
|
wolffd@0
|
30 %
|
|
wolffd@0
|
31 % You should have received a copy of the GNU General Public License
|
|
wolffd@0
|
32 % along with this program; if not, write to the Free Software
|
|
wolffd@0
|
33 % Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307
|
|
wolffd@0
|
34 % USA.
|
|
wolffd@0
|
35 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
|
|
wolffd@0
|
36
|
|
wolffd@0
|
37 function [a] = optimalMatching(C)
|
|
wolffd@0
|
38
|
|
wolffd@0
|
39 % Trivial cases:
|
|
wolffd@0
|
40 [p, q] = size(C);
|
|
wolffd@0
|
41 if (p == 0)
|
|
wolffd@0
|
42 a = [];
|
|
wolffd@0
|
43 return;
|
|
wolffd@0
|
44 elseif (q == 0)
|
|
wolffd@0
|
45 a = zeros(p, 1);
|
|
wolffd@0
|
46 return;
|
|
wolffd@0
|
47 end
|
|
wolffd@0
|
48
|
|
wolffd@0
|
49
|
|
wolffd@0
|
50 if 0
|
|
wolffd@0
|
51 % First, reduce the problem by making easy optimal matches. If two
|
|
wolffd@0
|
52 % elements agree that they are the best match, then match them up.
|
|
wolffd@0
|
53 [x, a] = min(C, [], 2);
|
|
wolffd@0
|
54 [y, b] = min(C, [], 1);
|
|
wolffd@0
|
55 u = find(1:p ~= b(a(:)));
|
|
wolffd@0
|
56 a(u) = 0;
|
|
wolffd@0
|
57 v = find(1:q ~= a(b(:))');
|
|
wolffd@0
|
58 C = C(u, v);
|
|
wolffd@0
|
59 if (isempty(C)) return; end
|
|
wolffd@0
|
60 end
|
|
wolffd@0
|
61
|
|
wolffd@0
|
62 % Get the (new) size of the two sets, u and v.
|
|
wolffd@0
|
63 [m, n] = size(C);
|
|
wolffd@0
|
64
|
|
wolffd@0
|
65 %mx = realmax;
|
|
wolffd@0
|
66 mx = 2*max(C(:));
|
|
wolffd@0
|
67 mn = -2*min(C(:));
|
|
wolffd@0
|
68 % Pad the affinity matrix to be square
|
|
wolffd@0
|
69 if (m < n)
|
|
wolffd@0
|
70 C = [C; mx * ones(n - m, n)];
|
|
wolffd@0
|
71 elseif (n < m)
|
|
wolffd@0
|
72 C = [C, mx * ones(m, m - n)];
|
|
wolffd@0
|
73 end
|
|
wolffd@0
|
74
|
|
wolffd@0
|
75 % Run the Hungarian method. First replace infinite values by the
|
|
wolffd@0
|
76 % largest (or smallest) finite values.
|
|
wolffd@0
|
77 C(find(isinf(C) & (C > 0))) = mx;
|
|
wolffd@0
|
78 C(find(isinf(C) & (C < 0))) = mn;
|
|
wolffd@0
|
79 %fprintf('running hungarian\n');
|
|
wolffd@0
|
80 [b, cost] = hungarian(C');
|
|
wolffd@0
|
81
|
|
wolffd@0
|
82 % Extract only the real assignments
|
|
wolffd@0
|
83 ap = b(1:m)';
|
|
wolffd@0
|
84 ap(find(ap > n)) = 0;
|
|
wolffd@0
|
85
|
|
wolffd@0
|
86 a = ap;
|
|
wolffd@0
|
87 %% Incorporate this sub-assignment into the complete assignment
|
|
wolffd@0
|
88 % k = find(ap);
|
|
wolffd@0
|
89 % a(u(k)) = v(ap(k));
|
|
wolffd@0
|
90
|
