lsape_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 LSAPE_SOLVER_HPP
#define LSAPE_SOLVER_HPP 1

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

namespace ged {

class LSAPESolver {

public:

    enum Model {
        ECBP=0, 
        FLWC=1, 
        EBP=2,  
        FLCC=3, 
        FBP=4,  
        FBP0=5, 
        SFBP=6  
    };

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

    LSAPESolver(const DMatrix * cost_matrix);

    LSAPESolver();

    void set_problem(const DMatrix * cost_matrix);

    void clear_solution();

    void set_model(const Model & model);

    void set_greedy_method(const GreedyMethod & greedy_method);

    void solve(int num_solutions = 1);

    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;

    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_rows() const;

    std::size_t num_cols() const;

    std::size_t total_num_rows() const;

    std::size_t total_num_cols() const;

    std::size_t num_solutions() const;


private:

    const DMatrix * cost_matrix_;

    Model model_;

    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 "lsape_solver.ipp"

#endif