HungarianAlg.cpp
Go to the documentation of this file.
1 // Based on https://github.com/Smorodov/Multitarget-tracker/tree/master/Tracker, GPLv3
2 // Refer to README.md in this directory.
3 
5 #include <limits>
6 
8 
10 
11 track_t AssignmentProblemSolver::Solve(const distMatrix_t& distMatrixIn, size_t nOfRows, size_t nOfColumns,
12  std::vector<int>& assignment, TMethod Method)
13 {
14  assignment.resize(nOfRows, -1);
15 
16  track_t cost = 0;
17 
18  switch (Method)
19  {
20  case optimal:
21  assignmentoptimal(assignment, cost, distMatrixIn, nOfRows, nOfColumns);
22  break;
23 
25  assignmentsuboptimal1(assignment, cost, distMatrixIn, nOfRows, nOfColumns);
26  break;
27 
29  assignmentsuboptimal2(assignment, cost, distMatrixIn, nOfRows, nOfColumns);
30  break;
31  }
32 
33  return cost;
34 }
35 // --------------------------------------------------------------------------
36 // Computes the optimal assignment (minimum overall costs) using Munkres algorithm.
37 // --------------------------------------------------------------------------
39  const distMatrix_t& distMatrixIn, size_t nOfRows, size_t nOfColumns)
40 {
41  // Generate distance cv::Matrix
42  // and check cv::Matrix elements positiveness :)
43 
44  // Total elements number
45  size_t nOfElements = nOfRows * nOfColumns;
46  // Memory allocation
47  track_t* distMatrix = (track_t*)malloc(nOfElements * sizeof(track_t));
48  // Pointer to last element
49  track_t* distMatrixEnd = distMatrix + nOfElements;
50 
51  for (size_t row = 0; row < nOfElements; row++)
52  {
53  track_t value = distMatrixIn[row];
54  assert(value >= 0);
55  distMatrix[row] = value;
56  }
57 
58  // Memory allocation
59  bool* coveredColumns = (bool*)calloc(nOfColumns, sizeof(bool));
60  bool* coveredRows = (bool*)calloc(nOfRows, sizeof(bool));
61  bool* starMatrix = (bool*)calloc(nOfElements, sizeof(bool));
62  bool* primeMatrix = (bool*)calloc(nOfElements, sizeof(bool));
63  bool* newStarMatrix = (bool*)calloc(nOfElements, sizeof(bool)); /* used in step4 */
64 
65  /* preliminary steps */
66  if (nOfRows <= nOfColumns)
67  {
68  for (size_t row = 0; row < nOfRows; row++)
69  {
70  /* find the smallest element in the row */
71  track_t* distMatrixTemp = distMatrix + row;
72  track_t minValue = *distMatrixTemp;
73  distMatrixTemp += nOfRows;
74  while (distMatrixTemp < distMatrixEnd)
75  {
76  track_t value = *distMatrixTemp;
77  if (value < minValue)
78  {
79  minValue = value;
80  }
81  distMatrixTemp += nOfRows;
82  }
83  /* subtract the smallest element from each element of the row */
84  distMatrixTemp = distMatrix + row;
85  while (distMatrixTemp < distMatrixEnd)
86  {
87  *distMatrixTemp -= minValue;
88  distMatrixTemp += nOfRows;
89  }
90  }
91  /* Steps 1 and 2a */
92  for (size_t row = 0; row < nOfRows; row++)
93  {
94  for (size_t col = 0; col < nOfColumns; col++)
95  {
96  if (distMatrix[row + nOfRows * col] == 0)
97  {
98  if (!coveredColumns[col])
99  {
100  starMatrix[row + nOfRows * col] = true;
101  coveredColumns[col] = true;
102  break;
103  }
104  }
105  }
106  }
107  }
108  else /* if(nOfRows > nOfColumns) */
109  {
110  for (size_t col = 0; col < nOfColumns; col++)
111  {
112  /* find the smallest element in the column */
113  track_t* distMatrixTemp = distMatrix + nOfRows * col;
114  track_t* columnEnd = distMatrixTemp + nOfRows;
115  track_t minValue = *distMatrixTemp++;
116  while (distMatrixTemp < columnEnd)
117  {
118  track_t value = *distMatrixTemp++;
119  if (value < minValue)
120  {
121  minValue = value;
122  }
123  }
124  /* subtract the smallest element from each element of the column */
125  distMatrixTemp = distMatrix + nOfRows * col;
126  while (distMatrixTemp < columnEnd)
127  {
128  *distMatrixTemp++ -= minValue;
129  }
130  }
131  /* Steps 1 and 2a */
132  for (size_t col = 0; col < nOfColumns; col++)
133  {
134  for (size_t row = 0; row < nOfRows; row++)
135  {
136  if (distMatrix[row + nOfRows * col] == 0)
137  {
138  if (!coveredRows[row])
139  {
140  starMatrix[row + nOfRows * col] = true;
141  coveredColumns[col] = true;
142  coveredRows[row] = true;
143  break;
144  }
145  }
146  }
147  }
148 
149  for (size_t row = 0; row < nOfRows; row++)
150  {
151  coveredRows[row] = false;
152  }
153  }
154  /* move to step 2b */
155  step2b(assignment, distMatrix, starMatrix, newStarMatrix, primeMatrix, coveredColumns, coveredRows, nOfRows,
156  nOfColumns, (nOfRows <= nOfColumns) ? nOfRows : nOfColumns);
157  /* compute cost and remove invalid assignments */
158  computeassignmentcost(assignment, cost, distMatrixIn, nOfRows);
159  /* free allocated memory */
160  free(distMatrix);
161  free(coveredColumns);
162  free(coveredRows);
163  free(starMatrix);
164  free(primeMatrix);
165  free(newStarMatrix);
166  return;
167 }
168 // --------------------------------------------------------------------------
169 //
170 // --------------------------------------------------------------------------
171 void AssignmentProblemSolver::buildassignmentvector(assignments_t& assignment, bool* starMatrix, size_t nOfRows,
172  size_t nOfColumns)
173 {
174  for (size_t row = 0; row < nOfRows; row++)
175  {
176  for (size_t col = 0; col < nOfColumns; col++)
177  {
178  if (starMatrix[row + nOfRows * col])
179  {
180  assignment[row] = static_cast<int>(col);
181  break;
182  }
183  }
184  }
185 }
186 // --------------------------------------------------------------------------
187 //
188 // --------------------------------------------------------------------------
190  const distMatrix_t& distMatrixIn, size_t nOfRows)
191 {
192  for (size_t row = 0; row < nOfRows; row++)
193  {
194  const int col = assignment[row];
195  if (col >= 0)
196  {
197  cost += distMatrixIn[row + nOfRows * col];
198  }
199  }
200 }
201 
202 // --------------------------------------------------------------------------
203 //
204 // --------------------------------------------------------------------------
205 void AssignmentProblemSolver::step2a(assignments_t& assignment, track_t* distMatrix, bool* starMatrix,
206  bool* newStarMatrix, bool* primeMatrix, bool* coveredColumns, bool* coveredRows,
207  size_t nOfRows, size_t nOfColumns, size_t minDim)
208 {
209  bool* starMatrixTemp, *columnEnd;
210  /* cover every column containing a starred zero */
211  for (size_t col = 0; col < nOfColumns; col++)
212  {
213  starMatrixTemp = starMatrix + nOfRows * col;
214  columnEnd = starMatrixTemp + nOfRows;
215  while (starMatrixTemp < columnEnd)
216  {
217  if (*starMatrixTemp++)
218  {
219  coveredColumns[col] = true;
220  break;
221  }
222  }
223  }
224  /* move to step 3 */
225  step2b(assignment, distMatrix, starMatrix, newStarMatrix, primeMatrix, coveredColumns, coveredRows, nOfRows,
226  nOfColumns, minDim);
227 }
228 
229 // --------------------------------------------------------------------------
230 //
231 // --------------------------------------------------------------------------
232 void AssignmentProblemSolver::step2b(assignments_t& assignment, track_t* distMatrix, bool* starMatrix,
233  bool* newStarMatrix, bool* primeMatrix, bool* coveredColumns, bool* coveredRows,
234  size_t nOfRows, size_t nOfColumns, size_t minDim)
235 {
236  /* count covered columns */
237  size_t nOfCoveredColumns = 0;
238  for (size_t col = 0; col < nOfColumns; col++)
239  {
240  if (coveredColumns[col])
241  {
242  nOfCoveredColumns++;
243  }
244  }
245  if (nOfCoveredColumns == minDim)
246  {
247  /* algorithm finished */
248  buildassignmentvector(assignment, starMatrix, nOfRows, nOfColumns);
249  }
250  else
251  {
252  /* move to step 3 */
253  step3(assignment, distMatrix, starMatrix, newStarMatrix, primeMatrix, coveredColumns, coveredRows, nOfRows,
254  nOfColumns, minDim);
255  }
256 }
257 
258 // --------------------------------------------------------------------------
259 //
260 // --------------------------------------------------------------------------
261 void AssignmentProblemSolver::step3(assignments_t& assignment, track_t* distMatrix, bool* starMatrix,
262  bool* newStarMatrix, bool* primeMatrix, bool* coveredColumns, bool* coveredRows,
263  size_t nOfRows, size_t nOfColumns, size_t minDim)
264 {
265  bool zerosFound = true;
266  while (zerosFound)
267  {
268  zerosFound = false;
269  for (size_t col = 0; col < nOfColumns; col++)
270  {
271  if (!coveredColumns[col])
272  {
273  for (size_t row = 0; row < nOfRows; row++)
274  {
275  if ((!coveredRows[row]) && (distMatrix[row + nOfRows * col] == 0))
276  {
277  /* prime zero */
278  primeMatrix[row + nOfRows * col] = true;
279  /* find starred zero in current row */
280  size_t starCol = 0;
281  for (; starCol < nOfColumns; starCol++)
282  {
283  if (starMatrix[row + nOfRows * starCol])
284  {
285  break;
286  }
287  }
288  if (starCol == nOfColumns) /* no starred zero found */
289  {
290  /* move to step 4 */
291  step4(assignment, distMatrix, starMatrix, newStarMatrix, primeMatrix, coveredColumns, coveredRows,
292  nOfRows, nOfColumns, minDim, row, col);
293  return;
294  }
295  else
296  {
297  coveredRows[row] = true;
298  coveredColumns[starCol] = false;
299  zerosFound = true;
300  break;
301  }
302  }
303  }
304  }
305  }
306  }
307  /* move to step 5 */
308  step5(assignment, distMatrix, starMatrix, newStarMatrix, primeMatrix, coveredColumns, coveredRows, nOfRows,
309  nOfColumns, minDim);
310 }
311 
312 // --------------------------------------------------------------------------
313 //
314 // --------------------------------------------------------------------------
315 void AssignmentProblemSolver::step4(assignments_t& assignment, track_t* distMatrix, bool* starMatrix,
316  bool* newStarMatrix, bool* primeMatrix, bool* coveredColumns, bool* coveredRows,
317  size_t nOfRows, size_t nOfColumns, size_t minDim, size_t row, size_t col)
318 {
319  const size_t nOfElements = nOfRows * nOfColumns;
320  /* generate temporary copy of starMatrix */
321  for (size_t n = 0; n < nOfElements; n++)
322  {
323  newStarMatrix[n] = starMatrix[n];
324  }
325  /* star current zero */
326  newStarMatrix[row + nOfRows * col] = true;
327  /* find starred zero in current column */
328  size_t starCol = col;
329  size_t starRow = 0;
330  for (; starRow < nOfRows; starRow++)
331  {
332  if (starMatrix[starRow + nOfRows * starCol])
333  {
334  break;
335  }
336  }
337  while (starRow < nOfRows)
338  {
339  /* unstar the starred zero */
340  newStarMatrix[starRow + nOfRows * starCol] = false;
341  /* find primed zero in current row */
342  size_t primeRow = starRow;
343  size_t primeCol = 0;
344  for (; primeCol < nOfColumns; primeCol++)
345  {
346  if (primeMatrix[primeRow + nOfRows * primeCol])
347  {
348  break;
349  }
350  }
351  /* star the primed zero */
352  newStarMatrix[primeRow + nOfRows * primeCol] = true;
353  /* find starred zero in current column */
354  starCol = primeCol;
355  for (starRow = 0; starRow < nOfRows; starRow++)
356  {
357  if (starMatrix[starRow + nOfRows * starCol])
358  {
359  break;
360  }
361  }
362  }
363  /* use temporary copy as new starMatrix */
364  /* delete all primes, uncover all rows */
365  for (size_t n = 0; n < nOfElements; n++)
366  {
367  primeMatrix[n] = false;
368  starMatrix[n] = newStarMatrix[n];
369  }
370  for (size_t n = 0; n < nOfRows; n++)
371  {
372  coveredRows[n] = false;
373  }
374  /* move to step 2a */
375  step2a(assignment, distMatrix, starMatrix, newStarMatrix, primeMatrix, coveredColumns, coveredRows, nOfRows,
376  nOfColumns, minDim);
377 }
378 
379 // --------------------------------------------------------------------------
380 //
381 // --------------------------------------------------------------------------
382 void AssignmentProblemSolver::step5(assignments_t& assignment, track_t* distMatrix, bool* starMatrix,
383  bool* newStarMatrix, bool* primeMatrix, bool* coveredColumns, bool* coveredRows,
384  size_t nOfRows, size_t nOfColumns, size_t minDim)
385 {
386  /* find smallest uncovered element h */
387  float h = std::numeric_limits<track_t>::max();
388  for (size_t row = 0; row < nOfRows; row++)
389  {
390  if (!coveredRows[row])
391  {
392  for (size_t col = 0; col < nOfColumns; col++)
393  {
394  if (!coveredColumns[col])
395  {
396  const float value = distMatrix[row + nOfRows * col];
397  if (value < h)
398  {
399  h = value;
400  }
401  }
402  }
403  }
404  }
405  /* add h to each covered row */
406  for (size_t row = 0; row < nOfRows; row++)
407  {
408  if (coveredRows[row])
409  {
410  for (size_t col = 0; col < nOfColumns; col++)
411  {
412  distMatrix[row + nOfRows * col] += h;
413  }
414  }
415  }
416  /* subtract h from each uncovered column */
417  for (size_t col = 0; col < nOfColumns; col++)
418  {
419  if (!coveredColumns[col])
420  {
421  for (size_t row = 0; row < nOfRows; row++)
422  {
423  distMatrix[row + nOfRows * col] -= h;
424  }
425  }
426  }
427  /* move to step 3 */
428  step3(assignment, distMatrix, starMatrix, newStarMatrix, primeMatrix, coveredColumns, coveredRows, nOfRows,
429  nOfColumns, minDim);
430 }
431 
432 // --------------------------------------------------------------------------
433 // Computes a suboptimal solution. Good for cases without forbidden assignments.
434 // --------------------------------------------------------------------------
436  const distMatrix_t& distMatrixIn, size_t nOfRows, size_t nOfColumns)
437 {
438  /* make working copy of distance Matrix */
439  const size_t nOfElements = nOfRows * nOfColumns;
440  float* distMatrix = (float*)malloc(nOfElements * sizeof(float));
441  for (size_t n = 0; n < nOfElements; n++)
442  {
443  distMatrix[n] = distMatrixIn[n];
444  }
445 
446  /* recursively search for the minimum element and do the assignment */
447  for (;;)
448  {
449  /* find minimum distance observation-to-track pair */
450  float minValue = std::numeric_limits<track_t>::max();
451  size_t tmpRow = 0;
452  size_t tmpCol = 0;
453  for (size_t row = 0; row < nOfRows; row++)
454  {
455  for (size_t col = 0; col < nOfColumns; col++)
456  {
457  const float value = distMatrix[row + nOfRows * col];
458  if (value != std::numeric_limits<track_t>::max() && (value < minValue))
459  {
460  minValue = value;
461  tmpRow = row;
462  tmpCol = col;
463  }
464  }
465  }
466 
467  if (minValue != std::numeric_limits<track_t>::max())
468  {
469  assignment[tmpRow] = static_cast<int>(tmpCol);
470  cost += minValue;
471  for (size_t n = 0; n < nOfRows; n++)
472  {
473  distMatrix[n + nOfRows * tmpCol] = std::numeric_limits<track_t>::max();
474  }
475  for (size_t n = 0; n < nOfColumns; n++)
476  {
477  distMatrix[tmpRow + nOfRows * n] = std::numeric_limits<track_t>::max();
478  }
479  }
480  else
481  {
482  break;
483  }
484  }
485 
486  free(distMatrix);
487 }
488 // --------------------------------------------------------------------------
489 // Computes a suboptimal solution. Good for cases with many forbidden assignments.
490 // --------------------------------------------------------------------------
492  const distMatrix_t& distMatrixIn, size_t nOfRows, size_t nOfColumns)
493 {
494  /* make working copy of distance Matrix */
495  const size_t nOfElements = nOfRows * nOfColumns;
496  float* distMatrix = (float*)malloc(nOfElements * sizeof(float));
497  for (size_t n = 0; n < nOfElements; n++)
498  {
499  distMatrix[n] = distMatrixIn[n];
500  }
501 
502  /* allocate memory */
503  int* nOfValidObservations = (int*)calloc(nOfRows, sizeof(int));
504  int* nOfValidTracks = (int*)calloc(nOfColumns, sizeof(int));
505 
506  /* compute number of validations */
507  bool infiniteValueFound = false;
508  bool finiteValueFound = false;
509  for (size_t row = 0; row < nOfRows; row++)
510  {
511  for (size_t col = 0; col < nOfColumns; col++)
512  {
513  if (distMatrix[row + nOfRows * col] != std::numeric_limits<track_t>::max())
514  {
515  nOfValidTracks[col] += 1;
516  nOfValidObservations[row] += 1;
517  finiteValueFound = true;
518  }
519  else
520  {
521  infiniteValueFound = true;
522  }
523  }
524  }
525 
526  if (infiniteValueFound)
527  {
528  if (!finiteValueFound)
529  {
530  return;
531  }
532  bool repeatSteps = true;
533 
534  while (repeatSteps)
535  {
536  repeatSteps = false;
537 
538  /* step 1: reject assignments of multiply validated tracks to singly validated observations */
539  for (size_t col = 0; col < nOfColumns; col++)
540  {
541  bool singleValidationFound = false;
542  for (size_t row = 0; row < nOfRows; row++)
543  {
544  if (distMatrix[row + nOfRows * col] != std::numeric_limits<track_t>::max() &&
545  (nOfValidObservations[row] == 1))
546  {
547  singleValidationFound = true;
548  break;
549  }
550 
551  if (singleValidationFound)
552  {
553  for (size_t row = 0; row < nOfRows; row++)
554  if ((nOfValidObservations[row] > 1) &&
555  distMatrix[row + nOfRows * col] != std::numeric_limits<track_t>::max())
556  {
557  distMatrix[row + nOfRows * col] = std::numeric_limits<track_t>::max();
558  nOfValidObservations[row] -= 1;
559  nOfValidTracks[col] -= 1;
560  repeatSteps = true;
561  }
562  }
563  }
564  }
565 
566  /* step 2: reject assignments of multiply validated observations to singly validated tracks */
567  if (nOfColumns > 1)
568  {
569  for (size_t row = 0; row < nOfRows; row++)
570  {
571  bool singleValidationFound = false;
572  for (size_t col = 0; col < nOfColumns; col++)
573  {
574  if (distMatrix[row + nOfRows * col] != std::numeric_limits<track_t>::max() && (nOfValidTracks[col] == 1))
575  {
576  singleValidationFound = true;
577  break;
578  }
579  }
580 
581  if (singleValidationFound)
582  {
583  for (size_t col = 0; col < nOfColumns; col++)
584  {
585  if ((nOfValidTracks[col] > 1) && distMatrix[row + nOfRows * col] != std::numeric_limits<track_t>::max())
586  {
587  distMatrix[row + nOfRows * col] = std::numeric_limits<track_t>::max();
588  nOfValidObservations[row] -= 1;
589  nOfValidTracks[col] -= 1;
590  repeatSteps = true;
591  }
592  }
593  }
594  }
595  }
596  } /* while(repeatSteps) */
597 
598  /* for each multiply validated track that validates only with singly validated */
599  /* observations, choose the observation with minimum distance */
600  for (size_t row = 0; row < nOfRows; row++)
601  {
602  if (nOfValidObservations[row] > 1)
603  {
604  bool allSinglyValidated = true;
605  float minValue = std::numeric_limits<track_t>::max();
606  size_t tmpCol = 0;
607  for (size_t col = 0; col < nOfColumns; col++)
608  {
609  const float value = distMatrix[row + nOfRows * col];
610  if (value != std::numeric_limits<track_t>::max())
611  {
612  if (nOfValidTracks[col] > 1)
613  {
614  allSinglyValidated = false;
615  break;
616  }
617  else if ((nOfValidTracks[col] == 1) && (value < minValue))
618  {
619  tmpCol = col;
620  minValue = value;
621  }
622  }
623  }
624 
625  if (allSinglyValidated)
626  {
627  assignment[row] = static_cast<int>(tmpCol);
628  cost += minValue;
629  for (size_t n = 0; n < nOfRows; n++)
630  {
631  distMatrix[n + nOfRows * tmpCol] = std::numeric_limits<track_t>::max();
632  }
633  for (size_t n = 0; n < nOfColumns; n++)
634  {
635  distMatrix[row + nOfRows * n] = std::numeric_limits<track_t>::max();
636  }
637  }
638  }
639  }
640 
641  // for each multiply validated observation that validates only with singly validated track, choose the track with
642  // minimum distance
643  for (size_t col = 0; col < nOfColumns; col++)
644  {
645  if (nOfValidTracks[col] > 1)
646  {
647  bool allSinglyValidated = true;
648  float minValue = std::numeric_limits<track_t>::max();
649  size_t tmpRow = 0;
650  for (size_t row = 0; row < nOfRows; row++)
651  {
652  const float value = distMatrix[row + nOfRows * col];
653  if (value != std::numeric_limits<track_t>::max())
654  {
655  if (nOfValidObservations[row] > 1)
656  {
657  allSinglyValidated = false;
658  break;
659  }
660  else if ((nOfValidObservations[row] == 1) && (value < minValue))
661  {
662  tmpRow = row;
663  minValue = value;
664  }
665  }
666  }
667 
668  if (allSinglyValidated)
669  {
670  assignment[tmpRow] = static_cast<int>(col);
671  cost += minValue;
672  for (size_t n = 0; n < nOfRows; n++)
673  {
674  distMatrix[n + nOfRows * col] = std::numeric_limits<track_t>::max();
675  }
676  for (size_t n = 0; n < nOfColumns; n++)
677  {
678  distMatrix[tmpRow + nOfRows * n] = std::numeric_limits<track_t>::max();
679  }
680  }
681  }
682  }
683  } /* if(infiniteValueFound) */
684 
685  /* now, recursively search for the minimum element and do the assignment */
686  for (;;)
687  {
688  /* find minimum distance observation-to-track pair */
689  float minValue = std::numeric_limits<track_t>::max();
690  size_t tmpRow = 0;
691  size_t tmpCol = 0;
692  for (size_t row = 0; row < nOfRows; row++)
693  {
694  for (size_t col = 0; col < nOfColumns; col++)
695  {
696  const float value = distMatrix[row + nOfRows * col];
697  if (value != std::numeric_limits<track_t>::max() && (value < minValue))
698  {
699  minValue = value;
700  tmpRow = row;
701  tmpCol = col;
702  }
703  }
704  }
705 
706  if (minValue != std::numeric_limits<track_t>::max())
707  {
708  assignment[tmpRow] = static_cast<int>(tmpCol);
709  cost += minValue;
710  for (size_t n = 0; n < nOfRows; n++)
711  {
712  distMatrix[n + nOfRows * tmpCol] = std::numeric_limits<track_t>::max();
713  }
714  for (size_t n = 0; n < nOfColumns; n++)
715  {
716  distMatrix[tmpRow + nOfRows * n] = std::numeric_limits<track_t>::max();
717  }
718  }
719  else
720  {
721  break;
722  }
723  }
724 
725  /* free allocated memory */
726  free(nOfValidObservations);
727  free(nOfValidTracks);
728  free(distMatrix);
729 }
void assignmentsuboptimal1(assignments_t &assignment, track_t &cost, const distMatrix_t &distMatrixIn, size_t nOfRows, size_t nOfColumns)
void assignmentoptimal(assignments_t &assignment, track_t &cost, const distMatrix_t &distMatrixIn, size_t nOfRows, size_t nOfColumns)
void buildassignmentvector(assignments_t &assignment, bool *starMatrix, size_t nOfRows, size_t nOfColumns)
void step2a(assignments_t &assignment, track_t *distMatrix, bool *starMatrix, bool *newStarMatrix, bool *primeMatrix, bool *coveredColumns, bool *coveredRows, size_t nOfRows, size_t nOfColumns, size_t minDim)
void computeassignmentcost(const assignments_t &assignment, track_t &cost, const distMatrix_t &distMatrixIn, size_t nOfRows)
std::vector< track_t > distMatrix_t
Definition: HungarianAlg.h:13
void assignmentsuboptimal2(assignments_t &assignment, track_t &cost, const distMatrix_t &distMatrixIn, size_t nOfRows, size_t nOfColumns)
void step2b(assignments_t &assignment, track_t *distMatrix, bool *starMatrix, bool *newStarMatrix, bool *primeMatrix, bool *coveredColumns, bool *coveredRows, size_t nOfRows, size_t nOfColumns, size_t minDim)
void step3(assignments_t &assignment, track_t *distMatrix, bool *starMatrix, bool *newStarMatrix, bool *primeMatrix, bool *coveredColumns, bool *coveredRows, size_t nOfRows, size_t nOfColumns, size_t minDim)
void step4(assignments_t &assignment, track_t *distMatrix, bool *starMatrix, bool *newStarMatrix, bool *primeMatrix, bool *coveredColumns, bool *coveredRows, size_t nOfRows, size_t nOfColumns, size_t minDim, size_t row, size_t col)
std::vector< int > assignments_t
Definition: HungarianAlg.h:12
float track_t
Definition: defines.h:7
void step5(assignments_t &assignment, track_t *distMatrix, bool *starMatrix, bool *newStarMatrix, bool *primeMatrix, bool *coveredColumns, bool *coveredRows, size_t nOfRows, size_t nOfColumns, size_t minDim)
track_t Solve(const distMatrix_t &distMatrixIn, size_t nOfRows, size_t nOfColumns, assignments_t &assignment, TMethod Method=optimal)


costmap_converter
Author(s): Christoph Rösmann , Franz Albers , Otniel Rinaldo
autogenerated on Fri Jun 7 2019 21:48:43