1.1 --- a/lemon/nearest_neighbor_tsp.h	Sat Jan 08 22:51:16 2011 +0100
     1.2 +++ b/lemon/nearest_neighbor_tsp.h	Sun Jan 09 00:56:52 2011 +0100
     1.3 @@ -24,12 +24,15 @@
     1.4  /// \brief Nearest neighbor algorithm for symmetric TSP
     1.5  
     1.6  #include <deque>
     1.7 +#include <vector>
     1.8  #include <limits>
     1.9  #include <lemon/full_graph.h>
    1.10  #include <lemon/maps.h>
    1.11  
    1.12  namespace lemon {
    1.13  
    1.14 +  /// \ingroup tsp
    1.15 +  ///
    1.16    /// \brief Nearest neighbor algorithm for symmetric TSP.
    1.17    ///
    1.18    /// NearestNeighborTsp implements the nearest neighbor heuristic for solving
    1.19 @@ -41,9 +44,8 @@
    1.20    /// Finally, it connects the two end points of the path to form a tour.
    1.21    ///
    1.22    /// This method runs in O(n<sup>2</sup>) time.
    1.23 -  /// It quickly finds an effectively short tour for most TSP
    1.24 -  /// instances, but in special cases, it could yield a really bad
    1.25 -  /// (or even the worst) solution.
    1.26 +  /// It quickly finds a short tour for most TSP instances, but in special
    1.27 +  /// cases, it could yield a really bad (or even the worst) solution.
    1.28    ///
    1.29    /// \tparam CM Type of the cost map.
    1.30    template <typename CM>
    1.31 @@ -63,7 +65,7 @@
    1.32        const FullGraph &_gr;
    1.33        const CostMap &_cost;
    1.34        Cost _sum;
    1.35 -      std::deque<Node> _path;
    1.36 +      std::vector<Node> _path;
    1.37  
    1.38      public:
    1.39  
    1.40 @@ -85,28 +87,30 @@
    1.41        /// \return The total cost of the found tour.
    1.42        Cost run() {
    1.43          _path.clear();
    1.44 -
    1.45 -        if (_gr.nodeNum() == 0) return _sum = 0;
    1.46 +        if (_gr.nodeNum() == 0) {
    1.47 +          return _sum = 0;
    1.48 +        }
    1.49          else if (_gr.nodeNum() == 1) {
    1.50            _path.push_back(_gr(0));
    1.51            return _sum = 0;
    1.52          }
    1.53  
    1.54 +        std::deque<Node> path_dq;
    1.55          Edge min_edge1 = INVALID,
    1.56               min_edge2 = INVALID;
    1.57  
    1.58          min_edge1 = mapMin(_gr, _cost);
    1.59          Node n1 = _gr.u(min_edge1),
    1.60               n2 = _gr.v(min_edge1);
    1.61 -        _path.push_back(n1);
    1.62 -        _path.push_back(n2);
    1.63 +        path_dq.push_back(n1);
    1.64 +        path_dq.push_back(n2);
    1.65  
    1.66          FullGraph::NodeMap<bool> used(_gr, false);
    1.67          used[n1] = true;
    1.68          used[n2] = true;
    1.69  
    1.70          min_edge1 = INVALID;
    1.71 -        while (int(_path.size()) != _gr.nodeNum()) {
    1.72 +        while (int(path_dq.size()) != _gr.nodeNum()) {
    1.73            if (min_edge1 == INVALID) {
    1.74              for (IncEdgeIt e(_gr, n1); e != INVALID; ++e) {
    1.75                if (!used[_gr.runningNode(e)] &&
    1.76 @@ -127,7 +131,7 @@
    1.77  
    1.78            if (_cost[min_edge1] < _cost[min_edge2]) {
    1.79              n1 = _gr.oppositeNode(n1, min_edge1);
    1.80 -            _path.push_front(n1);
    1.81 +            path_dq.push_front(n1);
    1.82  
    1.83              used[n1] = true;
    1.84              min_edge1 = INVALID;
    1.85 @@ -136,7 +140,7 @@
    1.86                min_edge2 = INVALID;
    1.87            } else {
    1.88              n2 = _gr.oppositeNode(n2, min_edge2);
    1.89 -            _path.push_back(n2);
    1.90 +            path_dq.push_back(n2);
    1.91  
    1.92              used[n2] = true;
    1.93              min_edge2 = INVALID;
    1.94 @@ -146,9 +150,15 @@
    1.95            }
    1.96          }
    1.97  
    1.98 -        _sum = _cost[_gr.edge(_path.back(), _path.front())];
    1.99 -        for (int i = 0; i < int(_path.size())-1; ++i) {
   1.100 -          _sum += _cost[_gr.edge(_path[i], _path[i+1])];
   1.101 +        n1 = path_dq.back();
   1.102 +        n2 = path_dq.front();
   1.103 +        _path.push_back(n2);
   1.104 +        _sum = _cost[_gr.edge(n1, n2)];
   1.105 +        for (int i = 1; i < int(path_dq.size()); ++i) {
   1.106 +          n1 = n2;
   1.107 +          n2 = path_dq[i];
   1.108 +          _path.push_back(n2);
   1.109 +          _sum += _cost[_gr.edge(n1, n2)];
   1.110          }
   1.111  
   1.112          return _sum;
   1.113 @@ -171,11 +181,11 @@
   1.114        /// \brief Returns a const reference to the node sequence of the
   1.115        /// found tour.
   1.116        ///
   1.117 -      /// This function returns a const reference to the internal structure
   1.118 +      /// This function returns a const reference to a vector
   1.119        /// that stores the node sequence of the found tour.
   1.120        ///
   1.121        /// \pre run() must be called before using this function.
   1.122 -      const std::deque<Node>& tourNodes() const {
   1.123 +      const std::vector<Node>& tourNodes() const {
   1.124          return _path;
   1.125        }
   1.126