-
Notifications
You must be signed in to change notification settings - Fork 0
/
munkres.m
86 lines (72 loc) · 1.85 KB
/
munkres.m
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
function [assignment,cost] = munkres(costMat)
assignment = false(size(costMat));
cost = 0;
costMat(costMat~=costMat)=Inf;
validMat = costMat<Inf;
validCol = any(validMat);
validRow = any(validMat,2);
nRows = sum(validRow);
nCols = sum(validCol);
n = max(nRows,nCols);
if ~n
return
end
dMat = zeros(n);
dMat(1:nRows,1:nCols) = costMat(validRow,validCol);
dMat = bsxfun(@minus, dMat, min(dMat,[],2));
zP = ~dMat;
starZ = false(n);
while any(zP(:))
[r,c]=find(zP,1);
starZ(r,c)=true;
zP(r,:)=false;
zP(:,c)=false;
end
while 1
primeZ = false(n);
coverColumn = any(starZ);
if ~any(~coverColumn)
break
end
coverRow = false(n,1);
while 1
zP(:) = false;
zP(~coverRow,~coverColumn) = ~dMat(~coverRow,~coverColumn);
Step = 6;
while any(any(zP(~coverRow,~coverColumn)))
[uZr,uZc] = find(zP,1);
primeZ(uZr,uZc) = true;
stz = starZ(uZr,:);
if ~any(stz)
Step = 5;
break;
end
coverRow(uZr) = true;
coverColumn(stz) = false;
zP(uZr,:) = false;
zP(~coverRow,stz) = ~dMat(~coverRow,stz);
end
if Step == 6
M=dMat(~coverRow,~coverColumn);
minval=min(min(M));
if minval==inf
return
end
dMat(coverRow,coverColumn)=dMat(coverRow,coverColumn)+minval;
dMat(~coverRow,~coverColumn)=M-minval;
else
break
end
end
rowZ1 = starZ(:,uZc);
starZ(uZr,uZc)=true;
while any(rowZ1)
starZ(rowZ1,uZc)=false;
uZc = primeZ(rowZ1,:);
uZr = rowZ1;
rowZ1 = starZ(:,uZc);
starZ(uZr,uZc)=true;
end
end
assignment(validRow,validCol) = starZ(1:nRows,1:nCols);
cost = sum(costMat(assignment));