HungarianAlg.h
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 
4 #include <vector>
5 #include <iostream>
6 #include <limits>
7 #include <time.h>
8 #include "defines.h"
9 
10 // http://community.topcoder.com/tc?module=Static&d1=tutorials&d2=hungarianAlgorithm
11 
12 typedef std::vector<int> assignments_t;
13 typedef std::vector<track_t> distMatrix_t;
14 
16 {
17 private:
18  // --------------------------------------------------------------------------
19  // Computes the optimal assignment (minimum overall costs) using Munkres algorithm.
20  // --------------------------------------------------------------------------
21  void assignmentoptimal(assignments_t& assignment, track_t& cost, const distMatrix_t& distMatrixIn, size_t nOfRows,
22  size_t nOfColumns);
23  void buildassignmentvector(assignments_t& assignment, bool* starMatrix, size_t nOfRows, size_t nOfColumns);
24  void computeassignmentcost(const assignments_t& assignment, track_t& cost, const distMatrix_t& distMatrixIn,
25  size_t nOfRows);
26  void step2a(assignments_t& assignment, track_t* distMatrix, bool* starMatrix, bool* newStarMatrix, bool* primeMatrix,
27  bool* coveredColumns, bool* coveredRows, size_t nOfRows, size_t nOfColumns, size_t minDim);
28  void step2b(assignments_t& assignment, track_t* distMatrix, bool* starMatrix, bool* newStarMatrix, bool* primeMatrix,
29  bool* coveredColumns, bool* coveredRows, size_t nOfRows, size_t nOfColumns, size_t minDim);
30  void step3(assignments_t& assignment, track_t* distMatrix, bool* starMatrix, bool* newStarMatrix, bool* primeMatrix,
31  bool* coveredColumns, bool* coveredRows, size_t nOfRows, size_t nOfColumns, size_t minDim);
32  void step4(assignments_t& assignment, track_t* distMatrix, bool* starMatrix, bool* newStarMatrix, bool* primeMatrix,
33  bool* coveredColumns, bool* coveredRows, size_t nOfRows, size_t nOfColumns, size_t minDim, size_t row,
34  size_t col);
35  void step5(assignments_t& assignment, track_t* distMatrix, bool* starMatrix, bool* newStarMatrix, bool* primeMatrix,
36  bool* coveredColumns, bool* coveredRows, size_t nOfRows, size_t nOfColumns, size_t minDim);
37  // --------------------------------------------------------------------------
38  // Computes a suboptimal solution. Good for cases with many forbidden assignments.
39  // --------------------------------------------------------------------------
40  void assignmentsuboptimal1(assignments_t& assignment, track_t& cost, const distMatrix_t& distMatrixIn, size_t nOfRows,
41  size_t nOfColumns);
42  // --------------------------------------------------------------------------
43  // Computes a suboptimal solution. Good for cases with many forbidden assignments.
44  // --------------------------------------------------------------------------
45  void assignmentsuboptimal2(assignments_t& assignment, track_t& cost, const distMatrix_t& distMatrixIn, size_t nOfRows,
46  size_t nOfColumns);
47 
48 public:
49  enum TMethod
50  {
54  };
55 
58  track_t Solve(const distMatrix_t& distMatrixIn, size_t nOfRows, size_t nOfColumns, assignments_t& assignment,
59  TMethod Method = optimal);
60 };
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