munkre.h

Go to the documentation of this file.

#ifndef MUNKRE_H
#define MUNKRE_H

#include <opencv2/core/core.hpp>



namespace tuw {
class Munkre {
public:
    static std::vector<std::pair<size_t, size_t>> find_minimum_assignment ( const cv::Mat_<double> costmatrix );

private:
    enum Zero {
        UNDEF = 0,
        STAR = 1,
        PRIME = 2,
    };

    static void step_0 (const cv::Mat_<double> costmatrix, cv::Mat_<double> &C, bool &transpose, size_t &k, size_t &step);

    static void step_1 (cv::Mat_<double> &C, size_t &step);

    static void step_2 (const cv::Mat_<double> C, cv::Mat_<Zero> &M, std::vector<bool> &row_cover, std::vector<bool> &col_cover, size_t &step);

    static void step_3 (const cv::Mat_<Zero> M, std::vector<bool> &col_cover, const size_t k, size_t &step);

    static void step_4 (const cv::Mat_<double> C, cv::Mat_<Zero> &M, std::vector<bool> &row_cover, std::vector<bool> &col_cover, std::vector<std::pair<size_t, size_t>> &path, size_t &step);

    static void step_5 (cv::Mat_<Zero> M, std::vector<bool> &row_cover, std::vector<bool> &col_cover, std::vector<std::pair<size_t, size_t>> &path, size_t &step);

    static void step_6 (cv::Mat_<double> C, const std::vector<bool> row_cover, const std::vector<bool> col_cover, size_t &step);

    static void step_7 (const cv::Mat_<Zero> M, const bool transpose, std::vector<std::pair<size_t, size_t>> &result, size_t &k, size_t &step);

    static void find_uncovered_zero (const cv::Mat_<double> C, const std::vector<bool> row_cover, const std::vector<bool> col_cover, int &row, int &col);

    static int find_zero_in_row (const cv::Mat_<Zero> M, const size_t row, const Zero type);

    static int find_zero_in_col (const cv::Mat_<Zero> M, const size_t col, const Zero type);

    static void print (const cv::Mat_<double> C, const cv::Mat_<Zero> M, const std::vector<bool> row_cover, const std::vector<bool> col_cover, const size_t step);
};
};

#endif // MUNKRE_H