f4c3@1031: #ifndef LEMON_INSERTION_TSP_H
f4c3@1031: #define LEMON_INSERTION_TSP_H
f4c3@1031: 
f4c3@1031: #include <lemon/full_graph.h>
f4c3@1031: #include <lemon/path.h>
f4c3@1031: #include <lemon/maps.h>
f4c3@1031: #include <lemon/random.h>
f4c3@1031: #include <vector>
f4c3@1031: 
f4c3@1031: namespace lemon {
f4c3@1031: 
f4c3@1031:   namespace insertion_tsp_helper {
f4c3@1031:   
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(
f4c3@1031:         const std::vector<FullGraph::Node> &_path) {
f4c3@1031:       return _path;
f4c3@1031:     };
f4c3@1031:     
f4c3@1031:   };
f4c3@1031: 
f4c3@1031:   template <typename CM>
f4c3@1031:   class InsertionTsp {
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:       InsertionTsp(const FullGraph &gr, const CostMap &cost) : 
f4c3@1031:             _gr(gr), _cost(cost) {}
f4c3@1031:       
f4c3@1031:       enum InsertionMethod {
f4c3@1031:         INSERT_NEAREST,
f4c3@1031:         INSERT_FARTHEST,
f4c3@1031:         INSERT_CHEAPEST,
f4c3@1031:         INSERT_RANDOM
f4c3@1031:       };     
f4c3@1031:       
f4c3@1031:       Cost run(InsertionMethod method = INSERT_FARTHEST) {
f4c3@1031:         switch (method) {
f4c3@1031:           case INSERT_NEAREST:
f4c3@1031:             start<InitTour<true>, NearestSelection, DefaultInsert>();
f4c3@1031:             break;
f4c3@1031:           case INSERT_FARTHEST:
f4c3@1031:             start<InitTour<false>, FarthestSelection, DefaultInsert>();
f4c3@1031:             break;
f4c3@1031:           case INSERT_CHEAPEST:
f4c3@1031:             start<InitTour<true>, CheapestSelection, CheapestInsert>();
f4c3@1031:             break;
f4c3@1031:           case INSERT_RANDOM:
f4c3@1031:             start<InitTour<true>, RandomSelection, DefaultInsert>();
f4c3@1031:             break;
f4c3@1031:         }
f4c3@1031:         return sum;
f4c3@1031:       }
f4c3@1031: 
f4c3@1031:       template <typename L>
f4c3@1031:       void tourNodes(L &container) {
f4c3@1031:         container(insertion_tsp_helper::vectorConvert<L>(nodesPath));
f4c3@1031:       }
f4c3@1031:       
f4c3@1031:       template <template <typename> class L>
f4c3@1031:       L<Node> tourNodes() {
f4c3@1031:         return insertion_tsp_helper::vectorConvert<L<Node> >(nodesPath);
f4c3@1031:       }
f4c3@1031:       
f4c3@1031:       const std::vector<Node>& tourNodes() {
f4c3@1031:         return nodesPath;
f4c3@1031:       }
f4c3@1031:       
f4c3@1031:       Path<FullGraph> tour() {
f4c3@1031:         Path<FullGraph> p;
f4c3@1031:         if (nodesPath.size()<2)
f4c3@1031:           return p;
f4c3@1031:         
f4c3@1031:         for (unsigned int i=0; i<nodesPath.size()-1; ++i)
f4c3@1031:           p.addBack(_gr.arc(nodesPath[i], nodesPath[i+1]));
f4c3@1031:         
f4c3@1031:         p.addBack(_gr.arc(nodesPath.back(), nodesPath.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: 
f4c3@1031:       template <bool MIN>
f4c3@1031:       class InitTour {
f4c3@1031:         public:
f4c3@1031:           InitTour(const FullGraph &gr, const CostMap &cost,
f4c3@1031:                    std::vector<Node> &used, std::vector<Node> &notused,
f4c3@1031:                    Cost &fullcost) :
f4c3@1031:               _gr(gr), _cost(cost), _used(used), _notused(notused),
f4c3@1031:               _fullcost(fullcost) {}
f4c3@1031: 
f4c3@1031:           std::vector<Node> init() const {
f4c3@1031:             Edge min = (MIN) ? mapMin(_gr, _cost) : mapMax(_gr, _cost);
f4c3@1031:             std::vector<Node> path;
f4c3@1031:             path.push_back(_gr.u(min));
f4c3@1031:             path.push_back(_gr.v(min));
f4c3@1031:             
f4c3@1031:             _used.clear();
f4c3@1031:             _notused.clear();
f4c3@1031:             for (NodeIt n(_gr); n!=INVALID; ++n) {
f4c3@1031:               if (n != _gr.u(min) && n != _gr.v(min)) {
f4c3@1031:                 _notused.push_back(n);
f4c3@1031:               }
f4c3@1031:             }
f4c3@1031:             _used.push_back(_gr.u(min));
f4c3@1031:             _used.push_back(_gr.v(min));
f4c3@1031:             
f4c3@1031:             _fullcost = _cost[min]*2;
f4c3@1031:             return path;
f4c3@1031:           }
f4c3@1031: 
f4c3@1031:         private:
f4c3@1031:           const FullGraph &_gr;
f4c3@1031:           const CostMap &_cost;
f4c3@1031:           std::vector<Node> &_used;
f4c3@1031:           std::vector<Node> &_notused;
f4c3@1031:           Cost &_fullcost;
f4c3@1031:       };
f4c3@1031: 
f4c3@1031:       class NearestSelection {
f4c3@1031:         public:
f4c3@1031:           NearestSelection(const FullGraph &gr, const CostMap &cost,
f4c3@1031:                            std::vector<Node> &used, std::vector<Node> &notused) : 
f4c3@1031:               _gr(gr), _cost(cost), _used(used), _notused(notused) {}
f4c3@1031:       
f4c3@1031:           Node select() const {
f4c3@1031: 
f4c3@1031:             Cost insert_val =
f4c3@1031:               std::numeric_limits<Cost>::max();
f4c3@1031:             int insert_node = -1;
f4c3@1031:             
f4c3@1031:             for (unsigned int i=0; i<_notused.size(); ++i) {
f4c3@1031:               Cost min_val = _cost[_gr.edge(_notused[i], _used[0])];
f4c3@1031:               int min_node = 0;
f4c3@1031:             
f4c3@1031:               for (unsigned int j=1; j<_used.size(); ++j) {
f4c3@1031:                 if (min_val > _cost[_gr.edge(_notused[i], _used[j])]) {
f4c3@1031:                     min_val = _cost[_gr.edge(_notused[i], _used[j])];
f4c3@1031:                     min_node = j;
f4c3@1031:                 }
f4c3@1031:               }
f4c3@1031:               
f4c3@1031:               if (insert_val > min_val) {
f4c3@1031:                 insert_val = min_val;
f4c3@1031:                 insert_node = i;
f4c3@1031:               }
f4c3@1031:             }
f4c3@1031:             
f4c3@1031:             Node n = _notused[insert_node];
f4c3@1031:             _notused.erase(_notused.begin()+insert_node);
f4c3@1031:             
f4c3@1031:             return n;
f4c3@1031:           }
f4c3@1031:           
f4c3@1031:         private:
f4c3@1031:           const FullGraph &_gr;
f4c3@1031:           const CostMap &_cost;
f4c3@1031:           std::vector<Node> &_used;
f4c3@1031:           std::vector<Node> &_notused;
f4c3@1031:       };
f4c3@1031: 
f4c3@1031:       class FarthestSelection {
f4c3@1031:         public:
f4c3@1031:           FarthestSelection(const FullGraph &gr, const CostMap &cost,
f4c3@1031:                             std::vector<Node> &used, std::vector<Node> &notused) : 
f4c3@1031:               _gr(gr), _cost(cost), _used(used), _notused(notused) {}
f4c3@1031:       
f4c3@1031:           Node select() const {
f4c3@1031: 
f4c3@1031:             Cost insert_val =
f4c3@1031:               std::numeric_limits<Cost>::min();
f4c3@1031:             int insert_node = -1;
f4c3@1031:             
f4c3@1031:             for (unsigned int i=0; i<_notused.size(); ++i) {
f4c3@1031:               Cost min_val = _cost[_gr.edge(_notused[i], _used[0])];
f4c3@1031:               int min_node = 0;
f4c3@1031:               
f4c3@1031:               for (unsigned int j=1; j<_used.size(); ++j) {
f4c3@1031:                 if (min_val > _cost[_gr.edge(_notused[i], _used[j])]) {
f4c3@1031:                   min_val = _cost[_gr.edge(_notused[i], _used[j])];
f4c3@1031:                   min_node = j;
f4c3@1031:                 }
f4c3@1031:               }
f4c3@1031:               
f4c3@1031:               if (insert_val < min_val || insert_node == -1) {
f4c3@1031:                 insert_val = min_val;
f4c3@1031:                 insert_node = i;
f4c3@1031:               }
f4c3@1031:             }
f4c3@1031:             
f4c3@1031:             Node n = _notused[insert_node];
f4c3@1031:             _notused.erase(_notused.begin()+insert_node);
f4c3@1031:             
f4c3@1031:             return n;
f4c3@1031:           }
f4c3@1031:           
f4c3@1031:         private:
f4c3@1031:           const FullGraph &_gr;
f4c3@1031:           const CostMap &_cost;
f4c3@1031:           std::vector<Node> &_used;
f4c3@1031:           std::vector<Node> &_notused;
f4c3@1031:       };
f4c3@1031: 
f4c3@1031: 
f4c3@1031:       class CheapestSelection {
f4c3@1031:         private:
f4c3@1031:           Cost costDiff(Node u, Node v, Node w) const {
f4c3@1031:             return 
f4c3@1031:               _cost[_gr.edge(u, w)] +
f4c3@1031:               _cost[_gr.edge(v, w)] -
f4c3@1031:               _cost[_gr.edge(u, v)];
f4c3@1031:           }
f4c3@1031: 
f4c3@1031:         public:
f4c3@1031:           CheapestSelection(const FullGraph &gr, const CostMap &cost,
f4c3@1031:                             std::vector<Node> &used, std::vector<Node> &notused) : 
f4c3@1031:               _gr(gr), _cost(cost), _used(used), _notused(notused) {}
f4c3@1031:         
f4c3@1031:           Cost select() const {
f4c3@1031:             int insert_notused = -1;
f4c3@1031:             int best_insert_index = -1;
f4c3@1031:             Cost insert_val =
f4c3@1031:               std::numeric_limits<Cost>::max();
f4c3@1031:             
f4c3@1031:             for (unsigned int i=0; i<_notused.size(); ++i) {
f4c3@1031:               int min = i;
f4c3@1031:               int best_insert_tmp = 0;
f4c3@1031:               Cost min_val =
f4c3@1031:                 costDiff(_used.front(), _used.back(), _notused[i]);
f4c3@1031:               
f4c3@1031:               for (unsigned int j=1; j<_used.size(); ++j) {
f4c3@1031:                 Cost tmp =
f4c3@1031:                   costDiff(_used[j-1], _used[j], _notused[i]);
f4c3@1031: 
f4c3@1031:                 if (min_val > tmp) {
f4c3@1031:                   min = i;
f4c3@1031:                   min_val = tmp;
f4c3@1031:                   best_insert_tmp = j;
f4c3@1031:                 }
f4c3@1031:               }
f4c3@1031: 
f4c3@1031:               if (insert_val > min_val) {
f4c3@1031:                 insert_notused = min;
f4c3@1031:                 insert_val = min_val;
f4c3@1031:                 best_insert_index = best_insert_tmp;
f4c3@1031:               }
f4c3@1031:             }
f4c3@1031: 
f4c3@1031:             _used.insert(_used.begin()+best_insert_index, _notused[insert_notused]);
f4c3@1031:             _notused.erase(_notused.begin()+insert_notused);
f4c3@1031: 
f4c3@1031:             return insert_val;
f4c3@1031:           }
f4c3@1031:           
f4c3@1031:         private:
f4c3@1031:           const FullGraph &_gr;
f4c3@1031:           const CostMap &_cost;
f4c3@1031:           std::vector<Node> &_used;
f4c3@1031:           std::vector<Node> &_notused;
f4c3@1031:       };
f4c3@1031: 
f4c3@1031:       class RandomSelection {
f4c3@1031:         public:
f4c3@1031:           RandomSelection(const FullGraph &, const CostMap &,
f4c3@1031:                             std::vector<Node> &, std::vector<Node> &notused) : 
f4c3@1031:                            _notused(notused) {
f4c3@1031:             rnd.seedFromTime();
f4c3@1031:           }
f4c3@1031:           
f4c3@1031:           Node select() const {
f4c3@1031:             const int index = rnd[_notused.size()];
f4c3@1031:             Node n = _notused[index];
f4c3@1031:             _notused.erase(_notused.begin()+index);
f4c3@1031:             return n;
f4c3@1031:           }
f4c3@1031:         private:
f4c3@1031:           std::vector<Node> &_notused;
f4c3@1031:       };
f4c3@1031: 
f4c3@1031: 
f4c3@1031:       class DefaultInsert {
f4c3@1031:         private:
f4c3@1031:           Cost costDiff(Node u, Node v, Node w) const {
f4c3@1031:             return 
f4c3@1031:               _cost[_gr.edge(u, w)] +
f4c3@1031:               _cost[_gr.edge(v, w)] -
f4c3@1031:               _cost[_gr.edge(u, v)];
f4c3@1031:           }
f4c3@1031:   
f4c3@1031:         public:
f4c3@1031:           DefaultInsert(const FullGraph &gr, const CostMap &cost,
f4c3@1031:                         std::vector<Node> &path, Cost &fullcost) : 
f4c3@1031:             _gr(gr), _cost(cost), _path(path), _fullcost(fullcost) {}
f4c3@1031:           
f4c3@1031:           void insert(Node n) const {
f4c3@1031:             int min = 0;
f4c3@1031:             Cost min_val =
f4c3@1031:               costDiff(_path.front(), _path.back(), n);
f4c3@1031:             
f4c3@1031:             for (unsigned int i=1; i<_path.size(); ++i) {
f4c3@1031:               Cost tmp = costDiff(_path[i-1], _path[i], n);
f4c3@1031:               if (tmp < min_val) {
f4c3@1031:                 min = i;
f4c3@1031:                 min_val = tmp;
f4c3@1031:               }
f4c3@1031:             }
f4c3@1031:             
f4c3@1031:             _path.insert(_path.begin()+min, n);
f4c3@1031:             _fullcost += min_val;
f4c3@1031:           }
f4c3@1031:         
f4c3@1031:         private:
f4c3@1031:           const FullGraph &_gr;
f4c3@1031:           const CostMap &_cost;
f4c3@1031:           std::vector<Node> &_path;
f4c3@1031:           Cost &_fullcost;
f4c3@1031:       };
f4c3@1031:   
f4c3@1031:       class CheapestInsert {
f4c3@1031:         TEMPLATE_GRAPH_TYPEDEFS(FullGraph);
f4c3@1031:         public:
f4c3@1031:           CheapestInsert(const FullGraph &, const CostMap &,
f4c3@1031:                          std::vector<Node> &, Cost &fullcost) : 
f4c3@1031:             _fullcost(fullcost) {}
f4c3@1031:           
f4c3@1031:           void insert(Cost diff) const {
f4c3@1031:             _fullcost += diff;
f4c3@1031:           }
f4c3@1031: 
f4c3@1031:         private:
f4c3@1031:           Cost &_fullcost;
f4c3@1031:       };  
f4c3@1031:       
f4c3@1031:       
f4c3@1031:       template <class InitFunctor, class SelectionFunctor, class InsertFunctor>
f4c3@1031:       void start() {
f4c3@1031:         InitFunctor init(_gr, _cost, nodesPath, notused, sum);
f4c3@1031:         SelectionFunctor selectNode(_gr, _cost, nodesPath, notused);
f4c3@1031:         InsertFunctor insertNode(_gr, _cost, nodesPath, sum);
f4c3@1031:         
f4c3@1031:         nodesPath = init.init();
f4c3@1031:         
f4c3@1031:         for (int i=0; i<_gr.nodeNum()-2; ++i) {
f4c3@1031:           insertNode.insert(selectNode.select());
f4c3@1031:         }
f4c3@1031:         
f4c3@1031:         sum = _cost[ _gr.edge(nodesPath.front(), nodesPath.back()) ];
f4c3@1031:         for (unsigned int i=0; i<nodesPath.size()-1; ++i)
f4c3@1031:           sum += _cost[ _gr.edge(nodesPath[i], nodesPath[i+1]) ];
f4c3@1031:       }
f4c3@1031:     
f4c3@1031:       const FullGraph &_gr;
f4c3@1031:       const CostMap &_cost;
f4c3@1031:       std::vector<Node> notused;
f4c3@1031:       std::vector<Node> nodesPath;
f4c3@1031:       Cost sum;
f4c3@1031:   };
f4c3@1031:   
f4c3@1031: }; // namespace lemon
f4c3@1031: 
f4c3@1031: #endif