2_local_search_components.hpp

Go to the documentation of this file.

//=======================================================================
// Copyright (c) 2013 Piotr Wygocki
//
// Distributed under the Boost Software License, Version 1.0. (See
// accompanying file LICENSE_1_0.txt or copy at
// http://www.boost.org/LICENSE_1_0.txt)
//=======================================================================
#ifndef PAAL_2_LOCAL_SEARCH_COMPONENTS_HPP
#define PAAL_2_LOCAL_SEARCH_COMPONENTS_HPP

#include "paal/data_structures/subset_iterator.hpp"

namespace paal {
namespace local_search {

template <typename Element> struct Swap {
    Swap(Element from, Element to) : m_from(from), m_to(to) {}

    Element get_from() const { return m_from; }

    Element get_to() const { return m_to; }

  private:
    Element m_from;
    Element m_to;
};

struct make_swap {
    template <typename Element>
    Swap<Element> operator()(Element from, Element to) const {
        return Swap<Element>(from, to);
    }
};

template <typename Metric> class gain_two_opt {
  public:
    gain_two_opt(const Metric &m) : m_metric(m) {}

    template <typename Solution, typename SolutionElement>
    int operator()(const Solution &, const Swap<SolutionElement> &swap) {
        auto from = swap.get_from();
        auto to = swap.get_to();
        return m_metric(from.first, from.second) +
               m_metric(to.first, to.second) - m_metric(from.first, to.first) -
               m_metric(from.second, to.second);
    }

  private:
    const Metric &m_metric;
};

struct two_local_search_commit {
    template <typename SolutionElement, typename Solution>
    bool operator()(Solution &s, const Swap<SolutionElement> &swap) {
        s.get_cycle().flip(swap.get_from().second, swap.get_to().first);
        return true;
    }
};

class two_local_searchget_moves {

    template <typename Solution> struct types_eval {
        using SolutionIter = decltype(std::declval<Solution>().begin());
        using Subset =
            data_structures::subsets_iterator<2, SolutionIter, make_swap>;
        using Range = boost::iterator_range<Subset>;
    };

  public:
    template <typename Solution>
    auto operator()(
        Solution &solution) const->typename types_eval<Solution>::Range {
        return data_structures::make_subsets_iterator_range<2>(
                solution.begin(), solution.end(), make_swap{});
    }
};

} 
} 

#endif // PAAL_2_LOCAL_SEARCH_COMPONENTS_HPP