star.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_STAR_HPP_
#define SRC_METHODS_STAR_HPP_

namespace ged {

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

public:

    virtual ~Star();

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

private:

    enum SortMethod_ {STD, COUNTING};

    class SortedNodeLabels_ {
    public:
        SortedNodeLabels_(const GEDGraph & g, SortMethod_ sort_method);

        SortedNodeLabels_();

        void operator=(const SortedNodeLabels_ & sorted_edge_labels);

        const std::vector<LabelID> & get_incident_labels(GEDGraph::NodeID) const;

    private:
        std::map<GEDGraph::NodeID, std::vector<LabelID>> sorted_node_labels_;
    };

    SortMethod_ sort_method_;

    std::map<GEDGraph::GraphID, SortedNodeLabels_> sorted_node_labels_;

    // Inherited member functions from LSAPEBasedMethod.

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

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

    virtual std::string lsape_valid_options_string_() const final;

    virtual void lsape_set_default_options_() final;

    virtual void lsape_init_graph_(const GEDGraph & graph) final;

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

    // Helper member functions.

    double compute_substitution_cost_(const GEDGraph & g, const GEDGraph & h, GEDGraph::NodeID i, GEDGraph::NodeID k,
            const SortedNodeLabels_ & sorted_node_labels_g, const SortedNodeLabels_ & sorted_node_labels_h) const;

    double compute_deletion_cost_(const GEDGraph & g, GEDGraph::NodeID i) const;

    double compute_insertion_cost_(const GEDGraph & h, GEDGraph::NodeID k) const;
};

}

#endif /* SRC_METHODS_STAR_HPP_ */