lemon/opt2_tsp.h
author Peter Kovacs <kpeter@inf.elte.hu>
Sat, 08 Jan 2011 22:49:09 +0100
changeset 1032 62ba43576f85
child 1033 9a51db038228
permissions -rw-r--r--
Doc group for TSP algorithms (#386)
     1 #ifndef LEMON_OPT2_TSP_H
     2 #define LEMON_OPT2_TSP_H
     3 
     4 #include <vector>
     5 #include <lemon/full_graph.h>
     6 #include <lemon/path.h>
     7 
     8 namespace lemon {
     9   
    10   namespace opt2_helper {
    11     template <class L>
    12     L vectorConvert(const std::vector<FullGraph::Node> &_path) {
    13       return L(_path.begin(), _path.end());
    14     }
    15   
    16     template <>
    17     std::vector<FullGraph::Node> vectorConvert(const std::vector<FullGraph::Node> &_path) {
    18       return _path;
    19     }
    20   }
    21   
    22   template <typename CM>
    23   class Opt2Tsp {
    24     private:
    25       GRAPH_TYPEDEFS(FullGraph);
    26 
    27     public:
    28       typedef CM CostMap;
    29       typedef typename CM::Value Cost;
    30       
    31     
    32       Opt2Tsp(const FullGraph &gr, const CostMap &cost) : _gr(gr), _cost(cost), 
    33             tmppath(_gr.nodeNum()*2) {
    34             
    35         for (int i=1; i<_gr.nodeNum()-1; ++i) {
    36           tmppath[2*i] = i-1;
    37           tmppath[2*i+1] = i+1;
    38         }
    39         tmppath[0] = _gr.nodeNum()-1;
    40         tmppath[1] = 1;
    41         tmppath[2*(_gr.nodeNum()-1)] = _gr.nodeNum()-2;
    42         tmppath[2*(_gr.nodeNum()-1)+1] = 0;
    43       }
    44       
    45       Opt2Tsp(const FullGraph &gr, const CostMap &cost, const std::vector<Node> &path) : 
    46               _gr(gr), _cost(cost), tmppath(_gr.nodeNum()*2) {
    47 
    48         for (unsigned int i=1; i<path.size()-1; ++i) {
    49           tmppath[2*_gr.id(path[i])] = _gr.id(path[i-1]);
    50           tmppath[2*_gr.id(path[i])+1] = _gr.id(path[i+1]);
    51         }
    52         
    53         tmppath[2*_gr.id(path[0])] = _gr.id(path.back());
    54         tmppath[2*_gr.id(path[0])+1] = _gr.id(path[1]);
    55         tmppath[2*_gr.id(path.back())] = _gr.id(path[path.size()-2]);
    56         tmppath[2*_gr.id(path.back())+1] = _gr.id(path.front());
    57       }
    58 
    59     private:
    60       Cost c(int u, int v) {
    61         return _cost[_gr.edge(_gr.nodeFromId(u), _gr.nodeFromId(v))];
    62       }
    63       
    64       class It {
    65         public:
    66           It(const std::vector<int> &path, int i=0) : tmppath(path), act(i), last(tmppath[2*act]) {}
    67           It(const std::vector<int> &path, int i, int l) : tmppath(path), act(i), last(l) {}
    68 
    69           int next_index() const {
    70             return (tmppath[2*act]==last)? 2*act+1 : 2*act;
    71           }
    72           
    73           int prev_index() const {
    74             return (tmppath[2*act]==last)? 2*act : 2*act+1;
    75           }
    76           
    77           int next() const {
    78             return tmppath[next_index()];
    79           }
    80 
    81           int prev() const {
    82             return tmppath[prev_index()];
    83           }
    84           
    85           It& operator++() {
    86             int tmp = act;
    87             act = next();
    88             last = tmp;
    89             return *this;
    90           }
    91           
    92           operator int() const {
    93             return act;
    94           }
    95           
    96         private:
    97           const std::vector<int> &tmppath;
    98           int act;
    99           int last;
   100       };
   101 
   102       bool check(std::vector<int> &path, It i, It j) {
   103         if (c(i, i.next()) + c(j, j.next()) > 
   104             c(i, j) + c(j.next(), i.next())) {
   105 
   106             path[ It(path, i.next(), i).prev_index() ] = j.next();
   107             path[ It(path, j.next(), j).prev_index() ] = i.next();
   108 
   109             path[i.next_index()] = j;
   110             path[j.next_index()] = i;
   111 
   112             return true;
   113         }
   114         return false;
   115       }
   116       
   117     public:
   118       
   119       Cost run() {
   120         _path.clear();
   121 
   122         if (_gr.nodeNum()>3) {
   123 
   124 opt2_tsp_label:
   125           It i(tmppath);
   126           It j(tmppath, i, i.prev());
   127           ++j; ++j;
   128           for (; j.next()!=0; ++j) {
   129             if (check(tmppath, i, j))
   130               goto opt2_tsp_label;
   131           }
   132           
   133           for (++i; i.next()!=0; ++i) {
   134             It j(tmppath, i, i.prev());
   135             if (++j==0)
   136               break;
   137             if (++j==0)
   138               break;
   139             
   140             for (; j!=0; ++j) {
   141               if (check(tmppath, i, j))
   142                 goto opt2_tsp_label;
   143             }
   144           }
   145         }
   146 
   147         It k(tmppath);
   148         _path.push_back(_gr.nodeFromId(k));
   149         for (++k; k!=0; ++k)
   150           _path.push_back(_gr.nodeFromId(k));
   151 
   152         
   153 
   154         _sum = _cost[ _gr.edge(_path.back(), _path.front()) ];
   155         for (unsigned int i=0; i<_path.size()-1; ++i)
   156           _sum += _cost[ _gr.edge(_path[i], _path[i+1]) ];
   157         return _sum;
   158       }
   159 
   160       
   161       template <typename L>
   162       void tourNodes(L &container) {
   163         container(opt2_helper::vectorConvert<L>(_path));
   164       }
   165       
   166       template <template <typename> class L>
   167       L<Node> tourNodes() {
   168         return opt2_helper::vectorConvert<L<Node> >(_path);
   169       }
   170 
   171       const std::vector<Node>& tourNodes() {
   172         return _path;
   173       }
   174       
   175       Path<FullGraph> tour() {
   176         Path<FullGraph> p;
   177         if (_path.size()<2)
   178           return p;
   179 
   180         for (unsigned int i=0; i<_path.size()-1; ++i) {
   181           p.addBack(_gr.arc(_path[i], _path[i+1]));
   182         }
   183         p.addBack(_gr.arc(_path.back(), _path.front()));
   184         return p;
   185       }
   186       
   187       Cost tourCost() {
   188         return _sum;
   189       }
   190       
   191 
   192   private:
   193     const FullGraph &_gr;
   194     const CostMap &_cost;
   195     Cost _sum;
   196     std::vector<int> tmppath;
   197     std::vector<Node> _path;
   198   };
   199 
   200 
   201 }; // namespace lemon
   202 
   203 #endif