process_cuts.hpp

Go to the documentation of this file.

/* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
#ifndef CMR_PROCESS_CUTS_H
#define CMR_PROCESS_CUTS_H

#include "datagroups.hpp"
#include "cc_lpcuts.hpp"
#include "graph.hpp"
#include "cut_structs.hpp"
#include "lp_util.hpp"
#include "util.hpp"

#include <memory>
#include <vector>
#include <limits>
#include <list>
#include <utility>



namespace CMR {
namespace Sep {

template<typename cut_rep>
class CutQueue {
public:
    CutQueue() : q_cap(std::numeric_limits<int>::max()) {}

    CutQueue(const int cap) : q_cap(cap) {}

    int q_capacity() const { return q_cap; }

    const cut_rep &peek_front() const { return cut_q.front(); }
    cut_rep &peek_front() { return cut_q.front(); }

    void push_front(const cut_rep &H)
        {
            cut_q.push_front(H);
            if(cut_q.size() > q_capacity()) cut_q.pop_back();
        }

    template <typename ...Args>
    void emplace_front(Args &&...args)
        {
            cut_q.emplace_front(std::forward<Args>(args)...);
            if (cut_q.size() > q_capacity()) cut_q.pop_back();
        }

    void push_back(const cut_rep &H)
        {
            if(cut_q.size() >= q_capacity()) cut_q.pop_back();
            cut_q.push_back(H);
        }

    template <typename ...Args>
    void emplace_back(Args &&...args)
        {
            if(cut_q.size() >= q_capacity()) cut_q.pop_back();
            cut_q.emplace_back(std::forward<Args>(args)...);
        }

    void pop_front() { cut_q.pop_front(); }  

    void splice(CutQueue<cut_rep> &Q){ cut_q.splice(cut_q.end(), Q.cut_q); }


    bool empty() const { return cut_q.empty(); }
    int size() const { return cut_q.size(); }

    void clear() { cut_q.clear(); } 

    using Itr = typename std::list<cut_rep>::iterator;
    using ConstItr = typename std::list<cut_rep>::const_iterator;

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

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

private:
    std::list<cut_rep> cut_q;
    int q_cap;
};


LP::SparseRow get_row(const CCtsp_lpcut_in &cc_cut,
                      const std::vector<int> &perm,
                      const Graph::CoreGraph &core_graph);

LP::SparseRow get_row(const dominoparity &dp_cut,
                      const std::vector<int> &tour_nodes,
                      const Graph::CoreGraph &core_graph);

LP::SparseRow get_row(const std::vector<int> &handle_delta,
                      const std::vector<std::vector<int>> &tooth_edges,
                      const Graph::CoreGraph &core_graph);

template<typename number_type>
double get_activity(const std::vector<number_type> &x,
                    const LP::SparseRow &R)
{
    double result = 0.0;
    for(auto i = 0; i < R.rmatind.size(); i++){
        int index = R.rmatind[i];
        result += x[index] * R.rmatval[i];
    }
    return result;
}


std::vector<int> teeth_inds(const ex_blossom &B,
                            const std::vector<double> &tour_edges,
                            const std::vector<double> &lp_vec,
                            const std::vector<Graph::Edge> &edges,
                            int ncount);

std::vector<int> teeth_inds(const ex_blossom &B,
                            const std::vector<double> &tour_edges,
                            const std::vector<double> &lp_vec,
                            const std::vector<Graph::Edge> &edges,
                            int ncount, const std::vector<int> &handle_delta);


bool bad_blossom(const ex_blossom &B,
                 const std::vector<double> &tour_edges,
                 const std::vector<double> &lp_vec,
                 const std::vector<Graph::Edge> &edges, int ncount);

}
}



#endif