lemon/insertion_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_INSERTION_TSP_H
     2 #define LEMON_INSERTION_TSP_H
     3 
     4 #include <lemon/full_graph.h>
     5 #include <lemon/path.h>
     6 #include <lemon/maps.h>
     7 #include <lemon/random.h>
     8 #include <vector>
     9 
    10 namespace lemon {
    11 
    12   namespace insertion_tsp_helper {
    13   
    14     template <class L>
    15     L vectorConvert(const std::vector<FullGraph::Node> &_path) {
    16       return L(_path.begin(), _path.end());
    17     };
    18   
    19     template <>
    20     std::vector<FullGraph::Node> vectorConvert(
    21         const std::vector<FullGraph::Node> &_path) {
    22       return _path;
    23     };
    24     
    25   };
    26 
    27   template <typename CM>
    28   class InsertionTsp {
    29     private:
    30       GRAPH_TYPEDEFS(FullGraph);
    31 
    32     public:      
    33       typedef CM CostMap;
    34       typedef typename CM::Value Cost;
    35       
    36       InsertionTsp(const FullGraph &gr, const CostMap &cost) : 
    37             _gr(gr), _cost(cost) {}
    38       
    39       enum InsertionMethod {
    40         INSERT_NEAREST,
    41         INSERT_FARTHEST,
    42         INSERT_CHEAPEST,
    43         INSERT_RANDOM
    44       };     
    45       
    46       Cost run(InsertionMethod method = INSERT_FARTHEST) {
    47         switch (method) {
    48           case INSERT_NEAREST:
    49             start<InitTour<true>, NearestSelection, DefaultInsert>();
    50             break;
    51           case INSERT_FARTHEST:
    52             start<InitTour<false>, FarthestSelection, DefaultInsert>();
    53             break;
    54           case INSERT_CHEAPEST:
    55             start<InitTour<true>, CheapestSelection, CheapestInsert>();
    56             break;
    57           case INSERT_RANDOM:
    58             start<InitTour<true>, RandomSelection, DefaultInsert>();
    59             break;
    60         }
    61         return sum;
    62       }
    63 
    64       template <typename L>
    65       void tourNodes(L &container) {
    66         container(insertion_tsp_helper::vectorConvert<L>(nodesPath));
    67       }
    68       
    69       template <template <typename> class L>
    70       L<Node> tourNodes() {
    71         return insertion_tsp_helper::vectorConvert<L<Node> >(nodesPath);
    72       }
    73       
    74       const std::vector<Node>& tourNodes() {
    75         return nodesPath;
    76       }
    77       
    78       Path<FullGraph> tour() {
    79         Path<FullGraph> p;
    80         if (nodesPath.size()<2)
    81           return p;
    82         
    83         for (unsigned int i=0; i<nodesPath.size()-1; ++i)
    84           p.addBack(_gr.arc(nodesPath[i], nodesPath[i+1]));
    85         
    86         p.addBack(_gr.arc(nodesPath.back(), nodesPath.front()));
    87         return p;
    88       }
    89       
    90       Cost tourCost() {
    91         return sum;
    92       }
    93 
    94 
    95     private:
    96 
    97       template <bool MIN>
    98       class InitTour {
    99         public:
   100           InitTour(const FullGraph &gr, const CostMap &cost,
   101                    std::vector<Node> &used, std::vector<Node> &notused,
   102                    Cost &fullcost) :
   103               _gr(gr), _cost(cost), _used(used), _notused(notused),
   104               _fullcost(fullcost) {}
   105 
   106           std::vector<Node> init() const {
   107             Edge min = (MIN) ? mapMin(_gr, _cost) : mapMax(_gr, _cost);
   108             std::vector<Node> path;
   109             path.push_back(_gr.u(min));
   110             path.push_back(_gr.v(min));
   111             
   112             _used.clear();
   113             _notused.clear();
   114             for (NodeIt n(_gr); n!=INVALID; ++n) {
   115               if (n != _gr.u(min) && n != _gr.v(min)) {
   116                 _notused.push_back(n);
   117               }
   118             }
   119             _used.push_back(_gr.u(min));
   120             _used.push_back(_gr.v(min));
   121             
   122             _fullcost = _cost[min]*2;
   123             return path;
   124           }
   125 
   126         private:
   127           const FullGraph &_gr;
   128           const CostMap &_cost;
   129           std::vector<Node> &_used;
   130           std::vector<Node> &_notused;
   131           Cost &_fullcost;
   132       };
   133 
   134       class NearestSelection {
   135         public:
   136           NearestSelection(const FullGraph &gr, const CostMap &cost,
   137                            std::vector<Node> &used, std::vector<Node> &notused) : 
   138               _gr(gr), _cost(cost), _used(used), _notused(notused) {}
   139       
   140           Node select() const {
   141 
   142             Cost insert_val =
   143               std::numeric_limits<Cost>::max();
   144             int insert_node = -1;
   145             
   146             for (unsigned int i=0; i<_notused.size(); ++i) {
   147               Cost min_val = _cost[_gr.edge(_notused[i], _used[0])];
   148               int min_node = 0;
   149             
   150               for (unsigned int j=1; j<_used.size(); ++j) {
   151                 if (min_val > _cost[_gr.edge(_notused[i], _used[j])]) {
   152                     min_val = _cost[_gr.edge(_notused[i], _used[j])];
   153                     min_node = j;
   154                 }
   155               }
   156               
   157               if (insert_val > min_val) {
   158                 insert_val = min_val;
   159                 insert_node = i;
   160               }
   161             }
   162             
   163             Node n = _notused[insert_node];
   164             _notused.erase(_notused.begin()+insert_node);
   165             
   166             return n;
   167           }
   168           
   169         private:
   170           const FullGraph &_gr;
   171           const CostMap &_cost;
   172           std::vector<Node> &_used;
   173           std::vector<Node> &_notused;
   174       };
   175 
   176       class FarthestSelection {
   177         public:
   178           FarthestSelection(const FullGraph &gr, const CostMap &cost,
   179                             std::vector<Node> &used, std::vector<Node> &notused) : 
   180               _gr(gr), _cost(cost), _used(used), _notused(notused) {}
   181       
   182           Node select() const {
   183 
   184             Cost insert_val =
   185               std::numeric_limits<Cost>::min();
   186             int insert_node = -1;
   187             
   188             for (unsigned int i=0; i<_notused.size(); ++i) {
   189               Cost min_val = _cost[_gr.edge(_notused[i], _used[0])];
   190               int min_node = 0;
   191               
   192               for (unsigned int j=1; j<_used.size(); ++j) {
   193                 if (min_val > _cost[_gr.edge(_notused[i], _used[j])]) {
   194                   min_val = _cost[_gr.edge(_notused[i], _used[j])];
   195                   min_node = j;
   196                 }
   197               }
   198               
   199               if (insert_val < min_val || insert_node == -1) {
   200                 insert_val = min_val;
   201                 insert_node = i;
   202               }
   203             }
   204             
   205             Node n = _notused[insert_node];
   206             _notused.erase(_notused.begin()+insert_node);
   207             
   208             return n;
   209           }
   210           
   211         private:
   212           const FullGraph &_gr;
   213           const CostMap &_cost;
   214           std::vector<Node> &_used;
   215           std::vector<Node> &_notused;
   216       };
   217 
   218 
   219       class CheapestSelection {
   220         private:
   221           Cost costDiff(Node u, Node v, Node w) const {
   222             return 
   223               _cost[_gr.edge(u, w)] +
   224               _cost[_gr.edge(v, w)] -
   225               _cost[_gr.edge(u, v)];
   226           }
   227 
   228         public:
   229           CheapestSelection(const FullGraph &gr, const CostMap &cost,
   230                             std::vector<Node> &used, std::vector<Node> &notused) : 
   231               _gr(gr), _cost(cost), _used(used), _notused(notused) {}
   232         
   233           Cost select() const {
   234             int insert_notused = -1;
   235             int best_insert_index = -1;
   236             Cost insert_val =
   237               std::numeric_limits<Cost>::max();
   238             
   239             for (unsigned int i=0; i<_notused.size(); ++i) {
   240               int min = i;
   241               int best_insert_tmp = 0;
   242               Cost min_val =
   243                 costDiff(_used.front(), _used.back(), _notused[i]);
   244               
   245               for (unsigned int j=1; j<_used.size(); ++j) {
   246                 Cost tmp =
   247                   costDiff(_used[j-1], _used[j], _notused[i]);
   248 
   249                 if (min_val > tmp) {
   250                   min = i;
   251                   min_val = tmp;
   252                   best_insert_tmp = j;
   253                 }
   254               }
   255 
   256               if (insert_val > min_val) {
   257                 insert_notused = min;
   258                 insert_val = min_val;
   259                 best_insert_index = best_insert_tmp;
   260               }
   261             }
   262 
   263             _used.insert(_used.begin()+best_insert_index, _notused[insert_notused]);
   264             _notused.erase(_notused.begin()+insert_notused);
   265 
   266             return insert_val;
   267           }
   268           
   269         private:
   270           const FullGraph &_gr;
   271           const CostMap &_cost;
   272           std::vector<Node> &_used;
   273           std::vector<Node> &_notused;
   274       };
   275 
   276       class RandomSelection {
   277         public:
   278           RandomSelection(const FullGraph &, const CostMap &,
   279                             std::vector<Node> &, std::vector<Node> &notused) : 
   280                            _notused(notused) {
   281             rnd.seedFromTime();
   282           }
   283           
   284           Node select() const {
   285             const int index = rnd[_notused.size()];
   286             Node n = _notused[index];
   287             _notused.erase(_notused.begin()+index);
   288             return n;
   289           }
   290         private:
   291           std::vector<Node> &_notused;
   292       };
   293 
   294 
   295       class DefaultInsert {
   296         private:
   297           Cost costDiff(Node u, Node v, Node w) const {
   298             return 
   299               _cost[_gr.edge(u, w)] +
   300               _cost[_gr.edge(v, w)] -
   301               _cost[_gr.edge(u, v)];
   302           }
   303   
   304         public:
   305           DefaultInsert(const FullGraph &gr, const CostMap &cost,
   306                         std::vector<Node> &path, Cost &fullcost) : 
   307             _gr(gr), _cost(cost), _path(path), _fullcost(fullcost) {}
   308           
   309           void insert(Node n) const {
   310             int min = 0;
   311             Cost min_val =
   312               costDiff(_path.front(), _path.back(), n);
   313             
   314             for (unsigned int i=1; i<_path.size(); ++i) {
   315               Cost tmp = costDiff(_path[i-1], _path[i], n);
   316               if (tmp < min_val) {
   317                 min = i;
   318                 min_val = tmp;
   319               }
   320             }
   321             
   322             _path.insert(_path.begin()+min, n);
   323             _fullcost += min_val;
   324           }
   325         
   326         private:
   327           const FullGraph &_gr;
   328           const CostMap &_cost;
   329           std::vector<Node> &_path;
   330           Cost &_fullcost;
   331       };
   332   
   333       class CheapestInsert {
   334         TEMPLATE_GRAPH_TYPEDEFS(FullGraph);
   335         public:
   336           CheapestInsert(const FullGraph &, const CostMap &,
   337                          std::vector<Node> &, Cost &fullcost) : 
   338             _fullcost(fullcost) {}
   339           
   340           void insert(Cost diff) const {
   341             _fullcost += diff;
   342           }
   343 
   344         private:
   345           Cost &_fullcost;
   346       };  
   347       
   348       
   349       template <class InitFunctor, class SelectionFunctor, class InsertFunctor>
   350       void start() {
   351         InitFunctor init(_gr, _cost, nodesPath, notused, sum);
   352         SelectionFunctor selectNode(_gr, _cost, nodesPath, notused);
   353         InsertFunctor insertNode(_gr, _cost, nodesPath, sum);
   354         
   355         nodesPath = init.init();
   356         
   357         for (int i=0; i<_gr.nodeNum()-2; ++i) {
   358           insertNode.insert(selectNode.select());
   359         }
   360         
   361         sum = _cost[ _gr.edge(nodesPath.front(), nodesPath.back()) ];
   362         for (unsigned int i=0; i<nodesPath.size()-1; ++i)
   363           sum += _cost[ _gr.edge(nodesPath[i], nodesPath[i+1]) ];
   364       }
   365     
   366       const FullGraph &_gr;
   367       const CostMap &_cost;
   368       std::vector<Node> notused;
   369       std::vector<Node> nodesPath;
   370       Cost sum;
   371   };
   372   
   373 }; // namespace lemon
   374 
   375 #endif