cliq.hpp

Go to the documentation of this file.

/* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
#ifndef CMR_CLIQ_H
#define CMR_CLIQ_H

#include "cut_structs.hpp"
#include "util.hpp"

#include <array>
#include <memory>
#include <unordered_map>
#include <utility>
#include <vector>

extern "C" {
#include <concorde/INCLUDE/tsp.h>
}

namespace CMR {
namespace Sep {

class Clique {
public:
    Clique() = default; 

    Clique(const CCtsp_lpclique &cc_cliq,
           const std::vector<int> &saved_tour,
           const std::vector<int> &saved_perm,
           const std::vector<int> &current_tour);

    Clique(int start, int end,
           const std::vector<int> &saved_tour,
           const std::vector<int> &saved_perm,
           const std::vector<int> & current_tour);

    Clique(const std::vector<int> &nodes, const std::vector<int> &perm,
           bool peserve_order);

    using Ptr = std::shared_ptr<Clique>; 

    int seg_count() const { return seglist.size(); }

    const std::vector<Segment> &seg_list() const { return seglist; }

    std::vector<int> node_list(const std::vector<int> &saved_tour) const;

    bool operator==(const Clique &rhs) const
        { return seglist == rhs.seglist; } 

    bool contains(const int index) const {
        for (const Segment &seg : seglist)
            if (seg.contains(index))
                return true;
        return false;
    }

private:
    std::vector<Segment> seglist;
};

class Tooth {
public:
    Tooth() = default; 

    Tooth(const SimpleTooth &T,
          const std::vector<int> &saved_tour,
          const std::vector<int> &saved_perm,
          const std::vector<int> &current_tour);

    const std::array<Clique, 2> &set_pair() const { return sets; }

    using Ptr = std::shared_ptr<Tooth>; 

    bool operator==(const Tooth &rhs) const
        { return sets == rhs.sets; } 

private:
    std::array<Clique, 2> sets;
};


}
}

namespace std {

template<>
struct hash<CMR::Sep::Clique> {
    size_t operator()(const CMR::Sep::Clique &clq) const
        {
            size_t val = 0;

            for (const CMR::Segment &seg : clq.seg_list())
                val = (val * 65537) + (seg.start * 4099) + seg.end;

            return val;
        }
};

template<>
struct hash<CMR::Sep::Tooth> {
    size_t operator()(const CMR::Sep::Tooth &T) const
        {
            size_t val = 0;

            for (const CMR::Sep::Clique &clq : T.set_pair())
                for (const CMR::Segment &seg : clq.seg_list())
                    val = (val * 65537) + (seg.start * 4099) + seg.end;

            return val;
        }
};

}

namespace CMR {
namespace Sep {

class CliqueBank {
public:
    CliqueBank(const std::vector<int> &tour, const std::vector<int> &perm);

    Clique::Ptr add_clique(const Clique &clq);

    Clique::Ptr add_clique(const CCtsp_lpclique &cc_cliq,
                           const std::vector<int> &tour);

    Clique::Ptr add_clique(int start, int end,
                           const std::vector<int> &tour);

    Clique::Ptr add_clique(const std::vector<int> &nodes);

    Clique::Ptr add_tour_clique(const std::vector<int> &tour_nodes);

    void steal_clique(Clique::Ptr &clq_ptr, CliqueBank &from_bank);

    void del_clique(Clique::Ptr &clq_ptr);

    int size() const
        { return bank.size(); } 

    using CliqueHash = std::unordered_map<Clique, Clique::Ptr>;

    using Itr = CliqueHash::iterator;
    using ConstItr = CliqueHash::const_iterator;

    Itr begin() { return bank.begin(); }
    Itr end() { return bank.end(); }

    ConstItr begin() const { return bank.begin(); }
    ConstItr end() const { return bank.end(); }

    const std::vector<int> &ref_tour() const { return saved_tour; }
    const std::vector<int> &ref_perm() const { return saved_perm; }


private:
    const std::vector<int> saved_tour; 
    const std::vector<int> saved_perm; 
    CliqueHash bank; 
};


class ToothBank {
public:
    ToothBank(const std::vector<int> &tour, const std::vector<int> &perm);

    ToothBank(const CliqueBank &cbank);

    Tooth::Ptr add_tooth(const SimpleTooth &T,
                         const std::vector<int> &tour);

    void del_tooth(Tooth::Ptr &T_ptr);

    int size() const
        { return bank.size(); } 

    using ToothHash = std::unordered_map<Tooth, Tooth::Ptr>;

    using Itr = ToothHash::iterator; 
    using ConstItr = ToothHash::const_iterator; 

    Itr begin()
        { return bank.begin(); } 

    ConstItr begin() const
        { return bank.begin(); } 

    Itr end()
        { return bank.end(); } 

    ConstItr end() const
        { return bank.end(); } 

    const std::vector<int> &ref_tour() const
        { return saved_tour; } 

    const std::vector<int> &ref_perm() const
        { return saved_perm; } 

private:
    const std::vector<int> saved_tour; 
    const std::vector<int> saved_perm; 
    ToothHash bank; 
};

}
}

#endif