lsap_solver.hpp

Go to the documentation of this file.

/***************************************************************************
*                                                                          *
*   Copyright (C) 2018 by David B. Blumenthal                              *
*                                                                          *
*   This file is part of GEDLIB.                                           *
*                                                                          *
*   GEDLIB is free software: you can redistribute it and/or modify it      *
*   under the terms of the GNU Lesser General Public License as published  *
*   by the Free Software Foundation, either version 3 of the License, or   *
*   (at your option) any later version.                                    *
*                                                                          *
*   GEDLIB is distributed in the hope that it will be useful,              *
*   but WITHOUT ANY WARRANTY; without even the implied warranty of         *
*   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the           *
*   GNU Lesser General Public License for more details.                    *
*                                                                          *
*   You should have received a copy of the GNU Lesser General Public       *
*   License along with GEDLIB. If not, see <http://www.gnu.org/licenses/>. *
*                                                                          *
***************************************************************************/


#ifndef SRC_UTIL_LSAP_SOLVER_HPP_
#define SRC_UTIL_LSAP_SOLVER_HPP_

#include "../env/common_types.hpp"
#include "../env/matrix.hpp"

namespace ged {

class LSAPSolver {

public:

    enum GreedyMethod {
        BASIC=0,         
        REFINED=1,       
        LOSS=2,          
        BASIC_SORT=3,    
        INT_BASIC_SORT=4 
    };

    LSAPSolver(const DMatrix * cost_matrix);

    LSAPSolver();

    void solve(int num_solutions = 1);

    void set_problem(const DMatrix * cost_matrix);

    void set_greedy_method(const GreedyMethod & greedy_method);

    void set_hungarian_algorithm();

    void clear_solution();

    double minimal_cost() const;

    std::size_t get_assigned_col(std::size_t row, std::size_t solution_id = 0) const;

    std::size_t get_assigned_row(std::size_t col, std::size_t solution_id = 0) const;

    double get_slack(std::size_t row, std::size_t col) const;

    double get_dual_var_row(std::size_t row) const;

    double get_dual_var_col(std::size_t col) const;

    const DMatrix * cost_matrix() const;

    std::size_t num_rows() const;

    std::size_t num_cols() const;

    const std::vector<std::size_t> & row_to_col_assignment(std::size_t solution_id = 0) const;

    const std::vector<std::size_t> & col_to_row_assignment(std::size_t solution_id = 0) const;

    std::size_t num_solutions() const;

private:

    const DMatrix * cost_matrix_;

    GreedyMethod greedy_method_;

    bool solve_optimally_;

    double minimal_cost_;

    std::vector<std::vector<std::size_t>> row_to_col_assignments_;

    std::vector<std::vector<std::size_t>> col_to_row_assignments_;

    std::vector<double> dual_var_rows_;

    std::vector<double> dual_var_cols_;

    // Helper functions.

    std::vector<std::size_t> construct_col_to_row_asignment_(const std::vector<std::size_t> row_to_col_assignment) const;

    void compute_cost_from_assignments_();

    void compute_cost_from_dual_vars_();

};

}

#include "lsap_solver.ipp"

#endif /* SRC_UTIL_LSAP_SOLVER_HPP_ */