f4c3@1031: #ifndef LEMON_OPT2_TSP_H
f4c3@1031: #define LEMON_OPT2_TSP_H
f4c3@1031: 
f4c3@1031: #include <vector>
f4c3@1031: #include <lemon/full_graph.h>
f4c3@1031: #include <lemon/path.h>
f4c3@1031: 
f4c3@1031: namespace lemon {
f4c3@1031:   
f4c3@1031:   namespace opt2_helper {
f4c3@1031:     template <class L>
f4c3@1031:     L vectorConvert(const std::vector<FullGraph::Node> &_path) {
f4c3@1031:       return L(_path.begin(), _path.end());
f4c3@1031:     }
f4c3@1031:   
f4c3@1031:     template <>
f4c3@1031:     std::vector<FullGraph::Node> vectorConvert(const std::vector<FullGraph::Node> &_path) {
f4c3@1031:       return _path;
f4c3@1031:     }
f4c3@1031:   }
f4c3@1031:   
f4c3@1031:   template <typename CM>
f4c3@1031:   class Opt2Tsp {
f4c3@1031:     private:
f4c3@1031:       GRAPH_TYPEDEFS(FullGraph);
f4c3@1031: 
f4c3@1031:     public:
f4c3@1031:       typedef CM CostMap;
f4c3@1031:       typedef typename CM::Value Cost;
f4c3@1031:       
f4c3@1031:     
f4c3@1031:       Opt2Tsp(const FullGraph &gr, const CostMap &cost) : _gr(gr), _cost(cost), 
f4c3@1031:             tmppath(_gr.nodeNum()*2) {
f4c3@1031:             
f4c3@1031:         for (int i=1; i<_gr.nodeNum()-1; ++i) {
f4c3@1031:           tmppath[2*i] = i-1;
f4c3@1031:           tmppath[2*i+1] = i+1;
f4c3@1031:         }
f4c3@1031:         tmppath[0] = _gr.nodeNum()-1;
f4c3@1031:         tmppath[1] = 1;
f4c3@1031:         tmppath[2*(_gr.nodeNum()-1)] = _gr.nodeNum()-2;
f4c3@1031:         tmppath[2*(_gr.nodeNum()-1)+1] = 0;
f4c3@1031:       }
f4c3@1031:       
f4c3@1031:       Opt2Tsp(const FullGraph &gr, const CostMap &cost, const std::vector<Node> &path) : 
f4c3@1031:               _gr(gr), _cost(cost), tmppath(_gr.nodeNum()*2) {
f4c3@1031: 
f4c3@1031:         for (unsigned int i=1; i<path.size()-1; ++i) {
f4c3@1031:           tmppath[2*_gr.id(path[i])] = _gr.id(path[i-1]);
f4c3@1031:           tmppath[2*_gr.id(path[i])+1] = _gr.id(path[i+1]);
f4c3@1031:         }
f4c3@1031:         
f4c3@1031:         tmppath[2*_gr.id(path[0])] = _gr.id(path.back());
f4c3@1031:         tmppath[2*_gr.id(path[0])+1] = _gr.id(path[1]);
f4c3@1031:         tmppath[2*_gr.id(path.back())] = _gr.id(path[path.size()-2]);
f4c3@1031:         tmppath[2*_gr.id(path.back())+1] = _gr.id(path.front());
f4c3@1031:       }
f4c3@1031: 
f4c3@1031:     private:
f4c3@1031:       Cost c(int u, int v) {
f4c3@1031:         return _cost[_gr.edge(_gr.nodeFromId(u), _gr.nodeFromId(v))];
f4c3@1031:       }
f4c3@1031:       
f4c3@1031:       class It {
f4c3@1031:         public:
f4c3@1031:           It(const std::vector<int> &path, int i=0) : tmppath(path), act(i), last(tmppath[2*act]) {}
f4c3@1031:           It(const std::vector<int> &path, int i, int l) : tmppath(path), act(i), last(l) {}
f4c3@1031: 
f4c3@1031:           int next_index() const {
f4c3@1031:             return (tmppath[2*act]==last)? 2*act+1 : 2*act;
f4c3@1031:           }
f4c3@1031:           
f4c3@1031:           int prev_index() const {
f4c3@1031:             return (tmppath[2*act]==last)? 2*act : 2*act+1;
f4c3@1031:           }
f4c3@1031:           
f4c3@1031:           int next() const {
f4c3@1031:             return tmppath[next_index()];
f4c3@1031:           }
f4c3@1031: 
f4c3@1031:           int prev() const {
f4c3@1031:             return tmppath[prev_index()];
f4c3@1031:           }
f4c3@1031:           
f4c3@1031:           It& operator++() {
f4c3@1031:             int tmp = act;
f4c3@1031:             act = next();
f4c3@1031:             last = tmp;
f4c3@1031:             return *this;
f4c3@1031:           }
f4c3@1031:           
f4c3@1031:           operator int() const {
f4c3@1031:             return act;
f4c3@1031:           }
f4c3@1031:           
f4c3@1031:         private:
f4c3@1031:           const std::vector<int> &tmppath;
f4c3@1031:           int act;
f4c3@1031:           int last;
f4c3@1031:       };
f4c3@1031: 
f4c3@1031:       bool check(std::vector<int> &path, It i, It j) {
f4c3@1031:         if (c(i, i.next()) + c(j, j.next()) > 
f4c3@1031:             c(i, j) + c(j.next(), i.next())) {
f4c3@1031: 
f4c3@1031:             path[ It(path, i.next(), i).prev_index() ] = j.next();
f4c3@1031:             path[ It(path, j.next(), j).prev_index() ] = i.next();
f4c3@1031: 
f4c3@1031:             path[i.next_index()] = j;
f4c3@1031:             path[j.next_index()] = i;
f4c3@1031: 
f4c3@1031:             return true;
f4c3@1031:         }
f4c3@1031:         return false;
f4c3@1031:       }
f4c3@1031:       
f4c3@1031:     public:
f4c3@1031:       
f4c3@1031:       Cost run() {
f4c3@1031:         _path.clear();
f4c3@1031: 
f4c3@1031:         if (_gr.nodeNum()>3) {
f4c3@1031: 
f4c3@1031: opt2_tsp_label:
f4c3@1031:           It i(tmppath);
f4c3@1031:           It j(tmppath, i, i.prev());
f4c3@1031:           ++j; ++j;
f4c3@1031:           for (; j.next()!=0; ++j) {
f4c3@1031:             if (check(tmppath, i, j))
f4c3@1031:               goto opt2_tsp_label;
f4c3@1031:           }
f4c3@1031:           
f4c3@1031:           for (++i; i.next()!=0; ++i) {
f4c3@1031:             It j(tmppath, i, i.prev());
f4c3@1031:             if (++j==0)
f4c3@1031:               break;
f4c3@1031:             if (++j==0)
f4c3@1031:               break;
f4c3@1031:             
f4c3@1031:             for (; j!=0; ++j) {
f4c3@1031:               if (check(tmppath, i, j))
f4c3@1031:                 goto opt2_tsp_label;
f4c3@1031:             }
f4c3@1031:           }
f4c3@1031:         }
f4c3@1031: 
f4c3@1031:         It k(tmppath);
f4c3@1031:         _path.push_back(_gr.nodeFromId(k));
f4c3@1031:         for (++k; k!=0; ++k)
f4c3@1031:           _path.push_back(_gr.nodeFromId(k));
f4c3@1031: 
f4c3@1031:         
f4c3@1031: 
f4c3@1031:         _sum = _cost[ _gr.edge(_path.back(), _path.front()) ];
f4c3@1031:         for (unsigned int i=0; i<_path.size()-1; ++i)
f4c3@1031:           _sum += _cost[ _gr.edge(_path[i], _path[i+1]) ];
f4c3@1031:         return _sum;
f4c3@1031:       }
f4c3@1031: 
f4c3@1031:       
f4c3@1031:       template <typename L>
f4c3@1031:       void tourNodes(L &container) {
f4c3@1031:         container(opt2_helper::vectorConvert<L>(_path));
f4c3@1031:       }
f4c3@1031:       
f4c3@1031:       template <template <typename> class L>
f4c3@1031:       L<Node> tourNodes() {
f4c3@1031:         return opt2_helper::vectorConvert<L<Node> >(_path);
f4c3@1031:       }
f4c3@1031: 
f4c3@1031:       const std::vector<Node>& tourNodes() {
f4c3@1031:         return _path;
f4c3@1031:       }
f4c3@1031:       
f4c3@1031:       Path<FullGraph> tour() {
f4c3@1031:         Path<FullGraph> p;
f4c3@1031:         if (_path.size()<2)
f4c3@1031:           return p;
f4c3@1031: 
f4c3@1031:         for (unsigned int i=0; i<_path.size()-1; ++i) {
f4c3@1031:           p.addBack(_gr.arc(_path[i], _path[i+1]));
f4c3@1031:         }
f4c3@1031:         p.addBack(_gr.arc(_path.back(), _path.front()));
f4c3@1031:         return p;
f4c3@1031:       }
f4c3@1031:       
f4c3@1031:       Cost tourCost() {
f4c3@1031:         return _sum;
f4c3@1031:       }
f4c3@1031:       
f4c3@1031: 
f4c3@1031:   private:
f4c3@1031:     const FullGraph &_gr;
f4c3@1031:     const CostMap &_cost;
f4c3@1031:     Cost _sum;
f4c3@1031:     std::vector<int> tmppath;
f4c3@1031:     std::vector<Node> _path;
f4c3@1031:   };
f4c3@1031: 
f4c3@1031: 
f4c3@1031: }; // namespace lemon
f4c3@1031: 
f4c3@1031: #endif