kpeter@1033: /* -*- mode: C++; indent-tabs-mode: nil; -*-
kpeter@1033:  *
kpeter@1033:  * This file is a part of LEMON, a generic C++ optimization library.
kpeter@1033:  *
alpar@1092:  * Copyright (C) 2003-2013
kpeter@1033:  * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
kpeter@1033:  * (Egervary Research Group on Combinatorial Optimization, EGRES).
kpeter@1033:  *
kpeter@1033:  * Permission to use, modify and distribute this software is granted
kpeter@1033:  * provided that this copyright notice appears in all copies. For
kpeter@1033:  * precise terms see the accompanying LICENSE file.
kpeter@1033:  *
kpeter@1033:  * This software is provided "AS IS" with no warranty of any kind,
kpeter@1033:  * express or implied, and with no claim as to its suitability for any
kpeter@1033:  * purpose.
kpeter@1033:  *
kpeter@1033:  */
kpeter@1033: 
f4c3@1031: #ifndef LEMON_INSERTION_TSP_H
f4c3@1031: #define LEMON_INSERTION_TSP_H
f4c3@1031: 
kpeter@1033: /// \ingroup tsp
kpeter@1033: /// \file
kpeter@1033: /// \brief Insertion algorithm for symmetric TSP
kpeter@1033: 
kpeter@1033: #include <vector>
kpeter@1036: #include <functional>
f4c3@1031: #include <lemon/full_graph.h>
f4c3@1031: #include <lemon/maps.h>
f4c3@1031: #include <lemon/random.h>
f4c3@1031: 
f4c3@1031: namespace lemon {
f4c3@1031: 
kpeter@1034:   /// \ingroup tsp
kpeter@1034:   ///
kpeter@1033:   /// \brief Insertion algorithm for symmetric TSP.
kpeter@1033:   ///
kpeter@1033:   /// InsertionTsp implements the insertion heuristic for solving
kpeter@1033:   /// symmetric \ref tsp "TSP".
kpeter@1033:   ///
kpeter@1036:   /// This is a fast and effective tour construction method that has
kpeter@1036:   /// many variants.
kpeter@1033:   /// It starts with a subtour containing a few nodes of the graph and it
kpeter@1033:   /// iteratively inserts the other nodes into this subtour according to a
kpeter@1033:   /// certain node selection rule.
kpeter@1033:   ///
kpeter@1036:   /// This method is among the fastest TSP algorithms, and it typically
kpeter@1036:   /// provides quite good solutions (usually much better than
kpeter@1036:   /// \ref NearestNeighborTsp and \ref GreedyTsp).
kpeter@1036:   ///
kpeter@1036:   /// InsertionTsp implements four different node selection rules,
kpeter@1036:   /// from which the most effective one (\e farthest \e node \e selection)
kpeter@1036:   /// is used by default.
kpeter@1036:   /// With this choice, the algorithm runs in O(n<sup>2</sup>) time.
kpeter@1033:   /// For more information, see \ref SelectionRule.
kpeter@1033:   ///
kpeter@1033:   /// \tparam CM Type of the cost map.
kpeter@1033:   template <typename CM>
kpeter@1033:   class InsertionTsp
kpeter@1033:   {
kpeter@1033:     public:
f4c3@1031: 
kpeter@1033:       /// Type of the cost map
f4c3@1031:       typedef CM CostMap;
kpeter@1033:       /// Type of the edge costs
f4c3@1031:       typedef typename CM::Value Cost;
f4c3@1031: 
f4c3@1031:     private:
f4c3@1031: 
kpeter@1033:       GRAPH_TYPEDEFS(FullGraph);
kpeter@1033: 
kpeter@1033:       const FullGraph &_gr;
kpeter@1033:       const CostMap &_cost;
kpeter@1033:       std::vector<Node> _notused;
kpeter@1036:       std::vector<Node> _tour;
kpeter@1033:       Cost _sum;
kpeter@1033: 
kpeter@1033:     public:
kpeter@1033: 
kpeter@1033:       /// \brief Constants for specifying the node selection rule.
kpeter@1033:       ///
kpeter@1033:       /// Enum type containing constants for specifying the node selection
kpeter@1033:       /// rule for the \ref run() function.
kpeter@1033:       ///
kpeter@1033:       /// During the algorithm, nodes are selected for addition to the current
kpeter@1033:       /// subtour according to the applied rule.
kpeter@1036:       /// The FARTHEST method is one of the fastest selection rules, and
kpeter@1036:       /// it is typically the most effective, thus it is the default
kpeter@1036:       /// option. The RANDOM rule usually gives slightly worse results,
kpeter@1036:       /// but it is more robust.
kpeter@1033:       ///
kpeter@1033:       /// The desired selection rule can be specified as a parameter of the
kpeter@1033:       /// \ref run() function.
kpeter@1033:       enum SelectionRule {
kpeter@1033: 
kpeter@1033:         /// An unvisited node having minimum distance from the current
kpeter@1033:         /// subtour is selected at each step.
kpeter@1036:         /// The algorithm runs in O(n<sup>2</sup>) time using this
kpeter@1033:         /// selection rule.
kpeter@1033:         NEAREST,
kpeter@1033: 
kpeter@1033:         /// An unvisited node having maximum distance from the current
kpeter@1033:         /// subtour is selected at each step.
kpeter@1036:         /// The algorithm runs in O(n<sup>2</sup>) time using this
kpeter@1033:         /// selection rule.
kpeter@1033:         FARTHEST,
kpeter@1033: 
kpeter@1033:         /// An unvisited node whose insertion results in the least
kpeter@1033:         /// increase of the subtour's total cost is selected at each step.
kpeter@1033:         /// The algorithm runs in O(n<sup>3</sup>) time using this
kpeter@1036:         /// selection rule, but in most cases, it is almost as fast as
kpeter@1036:         /// with other rules.
kpeter@1033:         CHEAPEST,
kpeter@1033: 
kpeter@1033:         /// An unvisited node is selected randomly without any evaluation
kpeter@1033:         /// at each step.
kpeter@1033:         /// The global \ref rnd "random number generator instance" is used.
kpeter@1033:         /// You can seed it before executing the algorithm, if you
kpeter@1033:         /// would like to.
kpeter@1033:         /// The algorithm runs in O(n<sup>2</sup>) time using this
kpeter@1033:         /// selection rule.
kpeter@1033:         RANDOM
kpeter@1033:       };
kpeter@1033: 
kpeter@1033:     public:
kpeter@1033: 
kpeter@1033:       /// \brief Constructor
kpeter@1033:       ///
kpeter@1033:       /// Constructor.
kpeter@1033:       /// \param gr The \ref FullGraph "full graph" the algorithm runs on.
kpeter@1033:       /// \param cost The cost map.
kpeter@1033:       InsertionTsp(const FullGraph &gr, const CostMap &cost)
kpeter@1033:         : _gr(gr), _cost(cost) {}
kpeter@1033: 
kpeter@1033:       /// \name Execution Control
kpeter@1033:       /// @{
kpeter@1033: 
kpeter@1033:       /// \brief Runs the algorithm.
kpeter@1033:       ///
kpeter@1033:       /// This function runs the algorithm.
kpeter@1033:       ///
kpeter@1033:       /// \param rule The node selection rule. For more information, see
kpeter@1033:       /// \ref SelectionRule.
kpeter@1033:       ///
kpeter@1033:       /// \return The total cost of the found tour.
kpeter@1033:       Cost run(SelectionRule rule = FARTHEST) {
kpeter@1036:         _tour.clear();
kpeter@1033: 
kpeter@1033:         if (_gr.nodeNum() == 0) return _sum = 0;
kpeter@1033:         else if (_gr.nodeNum() == 1) {
kpeter@1036:           _tour.push_back(_gr(0));
kpeter@1033:           return _sum = 0;
kpeter@1033:         }
kpeter@1033: 
kpeter@1033:         switch (rule) {
kpeter@1033:           case NEAREST:
kpeter@1033:             init(true);
kpeter@1036:             start<ComparingSelection<std::less<Cost> >,
kpeter@1036:                   DefaultInsertion>();
kpeter@1033:             break;
kpeter@1033:           case FARTHEST:
kpeter@1033:             init(false);
kpeter@1036:             start<ComparingSelection<std::greater<Cost> >,
kpeter@1036:                   DefaultInsertion>();
kpeter@1033:             break;
kpeter@1033:           case CHEAPEST:
kpeter@1033:             init(true);
kpeter@1033:             start<CheapestSelection, CheapestInsertion>();
kpeter@1033:             break;
kpeter@1033:           case RANDOM:
kpeter@1033:             init(true);
kpeter@1033:             start<RandomSelection, DefaultInsertion>();
kpeter@1033:             break;
kpeter@1033:         }
kpeter@1033:         return _sum;
kpeter@1033:       }
kpeter@1033: 
kpeter@1033:       /// @}
kpeter@1033: 
kpeter@1033:       /// \name Query Functions
kpeter@1033:       /// @{
kpeter@1033: 
kpeter@1033:       /// \brief The total cost of the found tour.
kpeter@1033:       ///
kpeter@1033:       /// This function returns the total cost of the found tour.
kpeter@1033:       ///
kpeter@1033:       /// \pre run() must be called before using this function.
kpeter@1033:       Cost tourCost() const {
kpeter@1033:         return _sum;
kpeter@1033:       }
kpeter@1033: 
kpeter@1033:       /// \brief Returns a const reference to the node sequence of the
kpeter@1033:       /// found tour.
kpeter@1033:       ///
kpeter@1034:       /// This function returns a const reference to a vector
kpeter@1033:       /// that stores the node sequence of the found tour.
kpeter@1033:       ///
kpeter@1033:       /// \pre run() must be called before using this function.
kpeter@1033:       const std::vector<Node>& tourNodes() const {
kpeter@1036:         return _tour;
kpeter@1033:       }
kpeter@1033: 
kpeter@1033:       /// \brief Gives back the node sequence of the found tour.
kpeter@1033:       ///
kpeter@1033:       /// This function copies the node sequence of the found tour into
kpeter@1037:       /// an STL container through the given output iterator. The
kpeter@1037:       /// <tt>value_type</tt> of the container must be <tt>FullGraph::Node</tt>.
kpeter@1037:       /// For example,
kpeter@1037:       /// \code
kpeter@1037:       /// std::vector<FullGraph::Node> nodes(countNodes(graph));
kpeter@1037:       /// tsp.tourNodes(nodes.begin());
kpeter@1037:       /// \endcode
kpeter@1037:       /// or
kpeter@1037:       /// \code
kpeter@1037:       /// std::list<FullGraph::Node> nodes;
kpeter@1037:       /// tsp.tourNodes(std::back_inserter(nodes));
kpeter@1037:       /// \endcode
kpeter@1033:       ///
kpeter@1033:       /// \pre run() must be called before using this function.
kpeter@1037:       template <typename Iterator>
kpeter@1037:       void tourNodes(Iterator out) const {
kpeter@1037:         std::copy(_tour.begin(), _tour.end(), out);
kpeter@1033:       }
kpeter@1033: 
kpeter@1033:       /// \brief Gives back the found tour as a path.
kpeter@1033:       ///
kpeter@1033:       /// This function copies the found tour as a list of arcs/edges into
alpar@1076:       /// the given \ref lemon::concepts::Path "path structure".
kpeter@1033:       ///
kpeter@1033:       /// \pre run() must be called before using this function.
kpeter@1033:       template <typename Path>
kpeter@1033:       void tour(Path &path) const {
kpeter@1033:         path.clear();
kpeter@1036:         for (int i = 0; i < int(_tour.size()) - 1; ++i) {
kpeter@1036:           path.addBack(_gr.arc(_tour[i], _tour[i+1]));
kpeter@1033:         }
kpeter@1036:         if (int(_tour.size()) >= 2) {
kpeter@1036:           path.addBack(_gr.arc(_tour.back(), _tour.front()));
kpeter@1033:         }
kpeter@1033:       }
kpeter@1033: 
kpeter@1033:       /// @}
kpeter@1033: 
kpeter@1033:     private:
kpeter@1033: 
kpeter@1033:       // Initializes the algorithm
kpeter@1033:       void init(bool min) {
kpeter@1033:         Edge min_edge = min ? mapMin(_gr, _cost) : mapMax(_gr, _cost);
kpeter@1033: 
kpeter@1036:         _tour.clear();
kpeter@1036:         _tour.push_back(_gr.u(min_edge));
kpeter@1036:         _tour.push_back(_gr.v(min_edge));
kpeter@1033: 
kpeter@1033:         _notused.clear();
kpeter@1033:         for (NodeIt n(_gr); n!=INVALID; ++n) {
kpeter@1033:           if (n != _gr.u(min_edge) && n != _gr.v(min_edge)) {
kpeter@1033:             _notused.push_back(n);
kpeter@1033:           }
kpeter@1033:         }
kpeter@1033: 
kpeter@1033:         _sum = _cost[min_edge] * 2;
kpeter@1033:       }
kpeter@1033: 
kpeter@1033:       // Executes the algorithm
kpeter@1033:       template <class SelectionFunctor, class InsertionFunctor>
kpeter@1033:       void start() {
kpeter@1036:         SelectionFunctor selectNode(_gr, _cost, _tour, _notused);
kpeter@1036:         InsertionFunctor insertNode(_gr, _cost, _tour, _sum);
kpeter@1033: 
kpeter@1033:         for (int i=0; i<_gr.nodeNum()-2; ++i) {
kpeter@1033:           insertNode.insert(selectNode.select());
kpeter@1033:         }
kpeter@1033: 
kpeter@1036:         _sum = _cost[_gr.edge(_tour.back(), _tour.front())];
kpeter@1036:         for (int i = 0; i < int(_tour.size())-1; ++i) {
kpeter@1036:           _sum += _cost[_gr.edge(_tour[i], _tour[i+1])];
kpeter@1033:         }
kpeter@1033:       }
kpeter@1033: 
kpeter@1033: 
kpeter@1036:       // Implementation of the nearest and farthest selection rule
kpeter@1036:       template <typename Comparator>
kpeter@1036:       class ComparingSelection {
f4c3@1031:         public:
kpeter@1036:           ComparingSelection(const FullGraph &gr, const CostMap &cost,
kpeter@1036:                   std::vector<Node> &tour, std::vector<Node> &notused)
kpeter@1036:             : _gr(gr), _cost(cost), _tour(tour), _notused(notused),
kpeter@1036:               _dist(gr, 0), _compare()
kpeter@1036:           {
kpeter@1036:             // Compute initial distances for the unused nodes
kpeter@1033:             for (unsigned int i=0; i<_notused.size(); ++i) {
kpeter@1036:               Node u = _notused[i];
kpeter@1036:               Cost min_dist = _cost[_gr.edge(u, _tour[0])];
kpeter@1036:               for (unsigned int j=1; j<_tour.size(); ++j) {
kpeter@1036:                 Cost curr = _cost[_gr.edge(u, _tour[j])];
kpeter@1036:                 if (curr < min_dist) {
kpeter@1036:                   min_dist = curr;
kpeter@1033:                 }
kpeter@1033:               }
kpeter@1036:               _dist[u] = min_dist;
kpeter@1036:             }
kpeter@1036:           }
kpeter@1033: 
kpeter@1036:           Node select() {
kpeter@1036: 
kpeter@1036:             // Select an used node with minimum distance
kpeter@1036:             Cost ins_dist = 0;
kpeter@1036:             int ins_node = -1;
kpeter@1036:             for (unsigned int i=0; i<_notused.size(); ++i) {
kpeter@1036:               Cost curr = _dist[_notused[i]];
kpeter@1036:               if (_compare(curr, ins_dist) || ins_node == -1) {
kpeter@1036:                 ins_dist = curr;
kpeter@1036:                 ins_node = i;
f4c3@1031:               }
f4c3@1031:             }
kpeter@1033: 
kpeter@1036:             // Remove the selected node from the unused vector
kpeter@1036:             Node sn = _notused[ins_node];
kpeter@1036:             _notused[ins_node] = _notused.back();
kpeter@1036:             _notused.pop_back();
kpeter@1033: 
kpeter@1036:             // Update the distances of the remaining nodes
kpeter@1036:             for (unsigned int i=0; i<_notused.size(); ++i) {
kpeter@1036:               Node u = _notused[i];
kpeter@1036:               Cost nc = _cost[_gr.edge(sn, u)];
kpeter@1036:               if (nc < _dist[u]) {
kpeter@1036:                 _dist[u] = nc;
kpeter@1036:               }
kpeter@1036:             }
kpeter@1036: 
kpeter@1036:             return sn;
f4c3@1031:           }
f4c3@1031: 
f4c3@1031:         private:
f4c3@1031:           const FullGraph &_gr;
f4c3@1031:           const CostMap &_cost;
kpeter@1036:           std::vector<Node> &_tour;
f4c3@1031:           std::vector<Node> &_notused;
kpeter@1036:           FullGraph::NodeMap<Cost> _dist;
kpeter@1036:           Comparator _compare;
f4c3@1031:       };
f4c3@1031: 
kpeter@1033:       // Implementation of the cheapest selection rule
f4c3@1031:       class CheapestSelection {
f4c3@1031:         private:
f4c3@1031:           Cost costDiff(Node u, Node v, Node w) const {
kpeter@1033:             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,
kpeter@1036:                             std::vector<Node> &tour, std::vector<Node> &notused)
kpeter@1036:             : _gr(gr), _cost(cost), _tour(tour), _notused(notused),
kpeter@1036:               _ins_cost(gr, 0), _ins_pos(gr, -1)
kpeter@1036:           {
kpeter@1036:             // Compute insertion cost and position for the unused nodes
f4c3@1031:             for (unsigned int i=0; i<_notused.size(); ++i) {
kpeter@1036:               Node u = _notused[i];
kpeter@1036:               Cost min_cost = costDiff(_tour.back(), _tour.front(), u);
alpar@1092:               int min_pos = 0;
kpeter@1036:               for (unsigned int j=1; j<_tour.size(); ++j) {
kpeter@1036:                 Cost curr_cost = costDiff(_tour[j-1], _tour[j], u);
kpeter@1036:                 if (curr_cost < min_cost) {
kpeter@1036:                   min_cost = curr_cost;
kpeter@1036:                   min_pos = j;
f4c3@1031:                 }
f4c3@1031:               }
kpeter@1036:               _ins_cost[u] = min_cost;
kpeter@1036:               _ins_pos[u] = min_pos;
kpeter@1036:             }
kpeter@1036:           }
f4c3@1031: 
kpeter@1036:           Cost select() {
kpeter@1036: 
kpeter@1036:             // Select an used node with minimum insertion cost
kpeter@1036:             Cost min_cost = 0;
kpeter@1036:             int min_node = -1;
kpeter@1036:             for (unsigned int i=0; i<_notused.size(); ++i) {
kpeter@1036:               Cost curr_cost = _ins_cost[_notused[i]];
kpeter@1036:               if (curr_cost < min_cost || min_node == -1) {
kpeter@1036:                 min_cost = curr_cost;
kpeter@1036:                 min_node = i;
f4c3@1031:               }
f4c3@1031:             }
f4c3@1031: 
kpeter@1036:             // Remove the selected node from the unused vector
kpeter@1036:             Node sn = _notused[min_node];
kpeter@1036:             _notused[min_node] = _notused.back();
kpeter@1036:             _notused.pop_back();
alpar@1092: 
kpeter@1036:             // Insert the selected node into the tour
kpeter@1036:             const int ipos = _ins_pos[sn];
kpeter@1036:             _tour.insert(_tour.begin() + ipos, sn);
f4c3@1031: 
kpeter@1036:             // Update the insertion cost and position of the remaining nodes
kpeter@1036:             for (unsigned int i=0; i<_notused.size(); ++i) {
kpeter@1036:               Node u = _notused[i];
kpeter@1036:               Cost curr_cost = _ins_cost[u];
kpeter@1036:               int curr_pos = _ins_pos[u];
kpeter@1036: 
kpeter@1036:               int ipos_prev = ipos == 0 ? _tour.size()-1 : ipos-1;
kpeter@1036:               int ipos_next = ipos == int(_tour.size())-1 ? 0 : ipos+1;
kpeter@1036:               Cost nc1 = costDiff(_tour[ipos_prev], _tour[ipos], u);
kpeter@1036:               Cost nc2 = costDiff(_tour[ipos], _tour[ipos_next], u);
alpar@1092: 
kpeter@1036:               if (nc1 <= curr_cost || nc2 <= curr_cost) {
kpeter@1036:                 // A new position is better than the old one
kpeter@1036:                 if (nc1 <= nc2) {
kpeter@1036:                   curr_cost = nc1;
kpeter@1036:                   curr_pos = ipos;
kpeter@1036:                 } else {
kpeter@1036:                   curr_cost = nc2;
kpeter@1036:                   curr_pos = ipos_next;
kpeter@1036:                 }
kpeter@1036:               }
kpeter@1036:               else {
kpeter@1036:                 if (curr_pos == ipos) {
kpeter@1036:                   // The minimum should be found again
kpeter@1036:                   curr_cost = costDiff(_tour.back(), _tour.front(), u);
alpar@1092:                   curr_pos = 0;
kpeter@1036:                   for (unsigned int j=1; j<_tour.size(); ++j) {
kpeter@1036:                     Cost tmp_cost = costDiff(_tour[j-1], _tour[j], u);
kpeter@1036:                     if (tmp_cost < curr_cost) {
kpeter@1036:                       curr_cost = tmp_cost;
kpeter@1036:                       curr_pos = j;
kpeter@1036:                     }
kpeter@1036:                   }
kpeter@1036:                 }
kpeter@1036:                 else if (curr_pos > ipos) {
kpeter@1036:                   ++curr_pos;
kpeter@1036:                 }
kpeter@1036:               }
alpar@1092: 
kpeter@1036:               _ins_cost[u] = curr_cost;
kpeter@1036:               _ins_pos[u] = curr_pos;
kpeter@1036:             }
kpeter@1036: 
kpeter@1036:             return min_cost;
f4c3@1031:           }
kpeter@1033: 
f4c3@1031:         private:
f4c3@1031:           const FullGraph &_gr;
f4c3@1031:           const CostMap &_cost;
kpeter@1036:           std::vector<Node> &_tour;
f4c3@1031:           std::vector<Node> &_notused;
kpeter@1036:           FullGraph::NodeMap<Cost> _ins_cost;
kpeter@1036:           FullGraph::NodeMap<int> _ins_pos;
f4c3@1031:       };
f4c3@1031: 
kpeter@1033:       // Implementation of the random selection rule
f4c3@1031:       class RandomSelection {
f4c3@1031:         public:
f4c3@1031:           RandomSelection(const FullGraph &, const CostMap &,
kpeter@1033:                           std::vector<Node> &, std::vector<Node> &notused)
kpeter@1033:             : _notused(notused) {}
kpeter@1033: 
f4c3@1031:           Node select() const {
f4c3@1031:             const int index = rnd[_notused.size()];
f4c3@1031:             Node n = _notused[index];
kpeter@1036:             _notused[index] = _notused.back();
kpeter@1036:             _notused.pop_back();
f4c3@1031:             return n;
f4c3@1031:           }
kpeter@1036: 
f4c3@1031:         private:
f4c3@1031:           std::vector<Node> &_notused;
f4c3@1031:       };
f4c3@1031: 
f4c3@1031: 
kpeter@1033:       // Implementation of the default insertion method
kpeter@1033:       class DefaultInsertion {
f4c3@1031:         private:
f4c3@1031:           Cost costDiff(Node u, Node v, Node w) const {
kpeter@1033:             return
f4c3@1031:               _cost[_gr.edge(u, w)] +
f4c3@1031:               _cost[_gr.edge(v, w)] -
f4c3@1031:               _cost[_gr.edge(u, v)];
f4c3@1031:           }
kpeter@1033: 
f4c3@1031:         public:
kpeter@1033:           DefaultInsertion(const FullGraph &gr, const CostMap &cost,
kpeter@1036:                            std::vector<Node> &tour, Cost &total_cost) :
kpeter@1036:             _gr(gr), _cost(cost), _tour(tour), _total(total_cost) {}
kpeter@1033: 
f4c3@1031:           void insert(Node n) const {
f4c3@1031:             int min = 0;
f4c3@1031:             Cost min_val =
kpeter@1036:               costDiff(_tour.front(), _tour.back(), n);
kpeter@1033: 
kpeter@1036:             for (unsigned int i=1; i<_tour.size(); ++i) {
kpeter@1036:               Cost tmp = costDiff(_tour[i-1], _tour[i], n);
f4c3@1031:               if (tmp < min_val) {
f4c3@1031:                 min = i;
f4c3@1031:                 min_val = tmp;
f4c3@1031:               }
f4c3@1031:             }
kpeter@1033: 
kpeter@1036:             _tour.insert(_tour.begin()+min, n);
kpeter@1033:             _total += min_val;
f4c3@1031:           }
kpeter@1033: 
f4c3@1031:         private:
f4c3@1031:           const FullGraph &_gr;
f4c3@1031:           const CostMap &_cost;
kpeter@1036:           std::vector<Node> &_tour;
kpeter@1033:           Cost &_total;
f4c3@1031:       };
kpeter@1033: 
kpeter@1033:       // Implementation of a special insertion method for the cheapest
kpeter@1033:       // selection rule
kpeter@1033:       class CheapestInsertion {
f4c3@1031:         TEMPLATE_GRAPH_TYPEDEFS(FullGraph);
f4c3@1031:         public:
kpeter@1033:           CheapestInsertion(const FullGraph &, const CostMap &,
kpeter@1033:                             std::vector<Node> &, Cost &total_cost) :
kpeter@1033:             _total(total_cost) {}
kpeter@1033: 
f4c3@1031:           void insert(Cost diff) const {
kpeter@1033:             _total += diff;
f4c3@1031:           }
f4c3@1031: 
f4c3@1031:         private:
kpeter@1033:           Cost &_total;
kpeter@1033:       };
kpeter@1033: 
f4c3@1031:   };
kpeter@1033: 
f4c3@1031: }; // namespace lemon
f4c3@1031: 
f4c3@1031: #endif