lsape_based_method.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_METHODS_LSAPE_BASED_METHOD_HPP_
#define SRC_METHODS_LSAPE_BASED_METHOD_HPP_

namespace ged {

template<class UserNodeLabel, class UserEdgeLabel>
class LSAPEBasedMethod : public GEDMethod<UserNodeLabel, UserEdgeLabel> {

public:

    // Constructor and destructor.

    virtual ~LSAPEBasedMethod() = 0;

    LSAPEBasedMethod(const GEDData<UserNodeLabel, UserEdgeLabel> & ged_data);

    // Extension of interface provided by GEDMethod.

    void populate_instance_and_run_as_util(const GEDGraph & g, const GEDGraph & h, Result & result, DMatrix & lsape_instance);

    void populate_instance(const GEDGraph & g, const GEDGraph & h, DMatrix & lsape_instance);

protected:

    LSAPESolver::Model lsape_model_;

    LSAPESolver::GreedyMethod greedy_method_;

    bool compute_lower_bound_;

    bool solve_optimally_;

    std::size_t num_threads_;

private:

    enum CentralityMethod_ {NONE, DEGREE, EIGENVECTOR, PAGERANK};

    CentralityMethod_ centrality_method_;

    double centrality_weight_;

    std::map<GEDGraph::GraphID, std::vector<double>> centralities_;

    int max_num_solutions_;

    // Member functions inherited from GEDMethod.

    virtual void ged_init_() final;

    virtual void ged_run_(const GEDGraph & g, const GEDGraph & h, Result & result) final;

    virtual bool ged_parse_option_(const std::string & option, const std::string & arg) final;

    virtual std::string ged_valid_options_string_() const final;

    virtual void ged_set_default_options_() final;

    // Private helper member functions.

    void init_graph_(const GEDGraph & graph);

    void init_centralities_(const GEDGraph & graph);

    void add_centralities_(const GEDGraph & g, const GEDGraph & h, DMatrix & master_problem);

    void compute_eigenvector_with_largest_eigenvalue_(const DMatrix & symmetric_matrix, std::vector<double> & eigenvector, double & eigenvalue);

    // Virtual member functions to be overridden by derived classes.

    virtual void lsape_init_();

    virtual bool lsape_parse_option_(const std::string & option, const std::string & arg);

    virtual std::string lsape_valid_options_string_() const;

    virtual void lsape_set_default_options_();

    virtual void lsape_populate_instance_(const GEDGraph & g, const GEDGraph & h, DMatrix & lsape_instance);

    virtual void lsape_init_graph_(const GEDGraph & graph);

    virtual void lsape_pre_graph_init_(bool called_at_runtime);

    virtual void lsape_default_post_graph_init_();

    virtual double lsape_lower_bound_scaling_factor_(const GEDGraph & g, const GEDGraph & h);

};

}

#endif /* SRC_METHODS_LSAPE_BASED_METHOD_HPP_ */