SHOGUN  3.2.1
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Groups Pages
munkres.cpp
Go to the documentation of this file.
1 /*
2  * Copyright (c) 2007 John Weaver
3  * 2012: ported to shogun by Chiyuan Zhang
4  *
5  * This program is free software; you can redistribute it and/or modify
6  * it under the terms of the GNU General Public License as published by
7  * the Free Software Foundation; either version 2 of the License, or
8  * (at your option) any later version.
9  *
10  * This program is distributed in the hope that it will be useful,
11  * but WITHOUT ANY WARRANTY; without even the implied warranty of
12  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
13  * GNU General Public License for more details.
14  *
15  * You should have received a copy of the GNU General Public License along
16  * with this program; if not, write to the Free Software Foundation, Inc.,
17  * 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.
18  */
19 
21 
22 #include <iostream>
23 #include <cmath>
24 
25 using namespace shogun;
26 
27 bool Munkres::find_uncovered_in_matrix(double item, int &row, int &col)
28 {
29  for (row=0; row < matrix.num_rows; row++)
30  if (!row_mask[row])
31  for (col=0; col < matrix.num_cols; col++)
32  if (!col_mask[col])
33  if (matrix(row,col) == item)
34  return true;
35 
36  return false;
37 }
38 
39 bool Munkres::pair_in_list(const std::pair<int,int> &needle, const std::list<std::pair<int,int> > &haystack)
40 {
41  for (std::list<std::pair<int,int> >::const_iterator i=haystack.begin(); i != haystack.end(); i++)
42  {
43  if ( needle == *i )
44  return true;
45  }
46 
47  return false;
48 }
49 
50 int Munkres::step1(void)
51 {
52  for (int row=0; row < matrix.num_rows; row++)
53  for (int col=0; col < matrix.num_cols; col++)
54  if (matrix(row,col) == 0)
55  {
56  bool isstarred=false;
57  for (int nrow=0; nrow < matrix.num_rows; nrow++)
58  if (mask_matrix(nrow,col) == STAR)
59  {
60  isstarred=true;
61  break;
62  }
63 
64  if (!isstarred)
65  {
66  for (int ncol=0; ncol < matrix.num_cols; ncol++)
67  if ( mask_matrix(row,ncol) == STAR )
68  {
69  isstarred=true;
70  break;
71  }
72  }
73 
74  if (!isstarred)
75  {
76  mask_matrix(row,col)=STAR;
77  }
78  }
79 
80  return 2;
81 }
82 
83 int Munkres::step2(void)
84 {
85  int rows=matrix.num_rows;
86  int cols=matrix.num_cols;
87  int covercount=0;
88  for (int row=0; row < rows; row++)
89  for (int col=0; col < cols; col++)
90  if (mask_matrix(row,col) == STAR)
91  {
92  col_mask[col]=true;
93  covercount++;
94  }
95 
96  int k=rows < cols ? rows : cols;
97 
98  if (covercount >= k)
99  {
100  return 0;
101  }
102 
103  return 3;
104 }
105 
106 int Munkres::step3(void)
107 {
108  /*
109  Main Zero Search
110 
111  1. Find an uncovered Z in the distance matrix and prime it. If no such zero exists, go to Step 5
112  2. If No Z* exists in the row of the Z', go to Step 4.
113  3. If a Z* exists, cover this row and uncover the column of the Z*. Return to Step 3.1 to find a new Z
114  */
115  if (find_uncovered_in_matrix(0, saverow, savecol))
116  {
117  mask_matrix(saverow,savecol)=PRIME; // prime it.
118  }
119  else
120  {
121  return 5;
122  }
123 
124  for (int ncol = 0; ncol < matrix.num_cols; ncol++)
125  if (mask_matrix(saverow,ncol) == STAR)
126  {
127  row_mask[saverow]=true; //cover this row and
128  col_mask[ncol]=false; // uncover the column containing the starred zero
129  return 3; // repeat
130  }
131 
132  return 4; // no starred zero in the row containing this primed zero
133 }
134 
135 int Munkres::step4(void)
136 {
137  int rows=matrix.num_rows;
138  int cols=matrix.num_cols;
139 
140  std::list<std::pair<int,int> > seq;
141  // use saverow, savecol from step 3.
142  std::pair<int,int> z0(saverow, savecol);
143  std::pair<int,int> z1(-1,-1);
144  std::pair<int,int> z2n(-1,-1);
145  seq.insert(seq.end(), z0);
146  int row, col=savecol;
147  /*
148  Increment Set of Starred Zeros
149 
150  1. Construct the ``alternating sequence'' of primed and starred zeros:
151 
152  Z0 : Unpaired Z' from Step 4.2
153  Z1 : The Z* in the column of Z0
154  Z[2N] : The Z' in the row of Z[2N-1], if such a zero exists
155  Z[2N+1] : The Z* in the column of Z[2N]
156 
157  The sequence eventually terminates with an unpaired Z' = Z[2N] for some N.
158  */
159  bool madepair;
160  do
161  {
162  madepair=false;
163  for (row=0; row < rows; row++)
164  if (mask_matrix(row,col) == STAR)
165  {
166  z1.first=row;
167  z1.second=col;
168  if (pair_in_list(z1, seq))
169  continue;
170 
171  madepair=true;
172  seq.insert(seq.end(), z1);
173  break;
174  }
175 
176  if (!madepair)
177  break;
178 
179  madepair=false;
180 
181  for (col = 0; col < cols; col++)
182  if (mask_matrix(row,col) == PRIME)
183  {
184  z2n.first=row;
185  z2n.second=col;
186  if (pair_in_list(z2n, seq))
187  continue;
188  madepair=true;
189  seq.insert(seq.end(), z2n);
190  break;
191  }
192  }
193  while (madepair);
194 
195  for (std::list<std::pair<int,int> >::iterator i=seq.begin();
196  i != seq.end();
197  i++)
198  {
199  // 2. Unstar each starred zero of the sequence.
200  if (mask_matrix(i->first,i->second) == STAR)
201  mask_matrix(i->first,i->second)=NORMAL;
202 
203  // 3. Star each primed zero of the sequence,
204  // thus increasing the number of starred zeros by one.
205  if (mask_matrix(i->first,i->second) == PRIME)
206  mask_matrix(i->first,i->second)=STAR;
207  }
208 
209  // 4. Erase all primes, uncover all columns and rows,
210  for (int rowi=0; rowi < mask_matrix.num_rows; rowi++)
211  {
212  for (int coli=0; coli < mask_matrix.num_cols; coli++)
213  {
214  if (mask_matrix(rowi,coli) == PRIME)
215  mask_matrix(rowi,coli) = NORMAL;
216  }
217  }
218 
219  for (int i=0; i < rows; i++)
220  row_mask[i]=false;
221 
222  for (int i=0; i < cols; i++)
223  col_mask[i]=false;
224 
225  // and return to Step 2.
226  return 2;
227 }
228 
229 int Munkres::step5(void)
230 {
231  int rows=matrix.num_rows;
232  int cols=matrix.num_cols;
233  /*
234  New Zero Manufactures
235 
236  1. Let h be the smallest uncovered entry in the (modified) distance matrix.
237  2. Add h to all covered rows.
238  3. Subtract h from all uncovered columns
239  4. Return to Step 3, without altering stars, primes, or covers.
240  */
241  double h=0;
242  for (int row=0; row < rows; row++)
243  {
244  if (!row_mask[row])
245  for (int col=0; col < cols; col++)
246  if (!col_mask[col])
247  if ((h > matrix(row,col) && matrix(row,col) != 0) || h == 0)
248  h = matrix(row,col);
249  }
250 
251  for (int row=0; row < rows; row++)
252  if (row_mask[row])
253  for (int col=0; col < cols; col++)
254  matrix(row,col)+=h;
255 
256  for (int col=0; col < cols; col++)
257  if (!col_mask[col])
258  for (int row=0; row < rows; row++)
259  matrix(row,col)-=h;
260 
261  return 3;
262 }
263 
265 {
266  // Linear assignment problem solution
267  // [modifies matrix in-place.]
268  // matrix(row,col): row major format assumed.
269 
270  // Assignments are remaining 0 values
271  // (extra 0 values are replaced with -1)
272 
273  double highValue=0;
274  for (int row=0; row < m.num_rows; row++)
275  {
276  for (int col=0; col < m.num_cols; col++)
277  {
278  if (m(row,col) != INFINITY && m(row,col) > highValue)
279  highValue = m(row,col);
280  }
281  }
282  highValue++;
283 
284  for (int row=0; row < m.num_rows; row++)
285  for (int col=0; col < m.num_cols; col++)
286  if (m(row,col) == INFINITY)
287  m(row,col)=highValue;
288 
289  bool notdone=true;
290  int step=1;
291 
292  mask_matrix.zero();
293  std::copy(m.matrix, m.matrix + m.num_cols*m.num_rows, matrix.matrix);
294  // STAR == 1 == starred, PRIME == 2 == primed
295 
296  row_mask=SG_MALLOC(bool, matrix.num_rows);
297  col_mask=SG_MALLOC(bool, matrix.num_cols);
298  for (int i=0; i < matrix.num_rows; i++)
299  row_mask[i] = false;
300 
301  for (int i=0; i < matrix.num_cols; i++)
302  col_mask[i] = false;
303 
304  while (notdone)
305  {
306  switch (step)
307  {
308  case 0:
309  notdone=false;
310  break;
311  case 1:
312  step=step1();
313  break;
314  case 2:
315  step=step2();
316  break;
317  case 3:
318  step=step3();
319  break;
320  case 4:
321  step=step4();
322  break;
323  case 5:
324  step=step5();
325  break;
326  }
327  }
328 
329  // Store results
330  for (int row=0; row < matrix.num_rows; row++)
331  for (int col=0; col < matrix.num_cols; col++)
332  if (mask_matrix(row,col) == STAR)
333  matrix(row,col)=0;
334  else
335  matrix(row,col)=-1;
336 
337  std::copy(matrix.matrix, matrix.matrix + m.num_cols*m.num_rows, m.matrix);
338 
339  SG_FREE(row_mask);
340  SG_FREE(col_mask);
341 }
342 

SHOGUN Machine Learning Toolbox - Documentation