HungarianAlg.h
Go to the documentation of this file.
00001 // Based on https://github.com/Smorodov/Multitarget-tracker/tree/master/Tracker, GPLv3
00002 // Refer to README.md in this directory.
00003 
00004 #include <vector>
00005 #include <iostream>
00006 #include <limits>
00007 #include <time.h>
00008 #include "defines.h"
00009 
00010 // http://community.topcoder.com/tc?module=Static&d1=tutorials&d2=hungarianAlgorithm
00011 
00012 typedef std::vector<int> assignments_t;
00013 typedef std::vector<track_t> distMatrix_t;
00014 
00015 class AssignmentProblemSolver
00016 {
00017 private:
00018   // --------------------------------------------------------------------------
00019   // Computes the optimal assignment (minimum overall costs) using Munkres algorithm.
00020   // --------------------------------------------------------------------------
00021   void assignmentoptimal(assignments_t& assignment, track_t& cost, const distMatrix_t& distMatrixIn, size_t nOfRows,
00022                          size_t nOfColumns);
00023   void buildassignmentvector(assignments_t& assignment, bool* starMatrix, size_t nOfRows, size_t nOfColumns);
00024   void computeassignmentcost(const assignments_t& assignment, track_t& cost, const distMatrix_t& distMatrixIn,
00025                              size_t nOfRows);
00026   void step2a(assignments_t& assignment, track_t* distMatrix, bool* starMatrix, bool* newStarMatrix, bool* primeMatrix,
00027               bool* coveredColumns, bool* coveredRows, size_t nOfRows, size_t nOfColumns, size_t minDim);
00028   void step2b(assignments_t& assignment, track_t* distMatrix, bool* starMatrix, bool* newStarMatrix, bool* primeMatrix,
00029               bool* coveredColumns, bool* coveredRows, size_t nOfRows, size_t nOfColumns, size_t minDim);
00030   void step3(assignments_t& assignment, track_t* distMatrix, bool* starMatrix, bool* newStarMatrix, bool* primeMatrix,
00031              bool* coveredColumns, bool* coveredRows, size_t nOfRows, size_t nOfColumns, size_t minDim);
00032   void step4(assignments_t& assignment, track_t* distMatrix, bool* starMatrix, bool* newStarMatrix, bool* primeMatrix,
00033              bool* coveredColumns, bool* coveredRows, size_t nOfRows, size_t nOfColumns, size_t minDim, size_t row,
00034              size_t col);
00035   void step5(assignments_t& assignment, track_t* distMatrix, bool* starMatrix, bool* newStarMatrix, bool* primeMatrix,
00036              bool* coveredColumns, bool* coveredRows, size_t nOfRows, size_t nOfColumns, size_t minDim);
00037   // --------------------------------------------------------------------------
00038   // Computes a suboptimal solution. Good for cases with many forbidden assignments.
00039   // --------------------------------------------------------------------------
00040   void assignmentsuboptimal1(assignments_t& assignment, track_t& cost, const distMatrix_t& distMatrixIn, size_t nOfRows,
00041                              size_t nOfColumns);
00042   // --------------------------------------------------------------------------
00043   // Computes a suboptimal solution. Good for cases with many forbidden assignments.
00044   // --------------------------------------------------------------------------
00045   void assignmentsuboptimal2(assignments_t& assignment, track_t& cost, const distMatrix_t& distMatrixIn, size_t nOfRows,
00046                              size_t nOfColumns);
00047 
00048 public:
00049   enum TMethod
00050   {
00051     optimal,
00052     many_forbidden_assignments,
00053     without_forbidden_assignments
00054   };
00055 
00056   AssignmentProblemSolver();
00057   ~AssignmentProblemSolver();
00058   track_t Solve(const distMatrix_t& distMatrixIn, size_t nOfRows, size_t nOfColumns, assignments_t& assignment,
00059                 TMethod Method = optimal);
00060 };


costmap_converter
Author(s): Christoph Rösmann , Franz Albers , Otniel Rinaldo
autogenerated on Sat Jun 8 2019 20:53:15