Changeset 1202:ef200e268af2 in lemon for lemon/nearest_neighbor_tsp.h

Timestamp:

01/09/11 00:56:52 (13 years ago)

Author:

Peter Kovacs <kpeter@…>

Branch:

default

Phase:

public

Message:

Unifications and improvements in TSP algorithms (#386)

File:

• lemon/nearest_neighbor_tsp.h (modified) (12 diffs)

lemon/nearest_neighbor_tsp.h

@@ -25 +25 @@
 
 #include <deque>
+#include <vector>
 #include <limits>
 #include <lemon/full_graph.h>
@@ -31 +32 @@
 namespace lemon {
 
+  /// \ingroup tsp
+  ///
   /// \brief Nearest neighbor algorithm for symmetric TSP.
   ///
@@ -42 +45 @@
   ///
   /// This method runs in O(n<sup>2</sup>) time.
-  /// It quickly finds an effectively short tour for most TSP
-  /// instances, but in special cases, it could yield a really bad
-  /// (or even the worst) solution.
+  /// It quickly finds a short tour for most TSP instances, but in special
+  /// cases, it could yield a really bad (or even the worst) solution.
   ///
   /// \tparam CM Type of the cost map.
@@ -64 +66 @@
       const CostMap &_cost;
       Cost _sum;
-      std::deque<Node> _path;
+      std::vector<Node> _path;
 
     public:
@@ -86 +88 @@
       Cost run() {
         _path.clear();
-
-        if (_gr.nodeNum() == 0) return _sum = 0;
+        if (_gr.nodeNum() == 0) {
+          return _sum = 0;
+        }
         else if (_gr.nodeNum() == 1) {
           _path.push_back(_gr(0));
@@ -93 +96 @@
         }
 
+        std::deque<Node> path_dq;
         Edge min_edge1 = INVALID,
              min_edge2 = INVALID;
@@ -99 +103 @@
         Node n1 = _gr.u(min_edge1),
              n2 = _gr.v(min_edge1);
-        _path.push_back(n1);
-        _path.push_back(n2);
+        path_dq.push_back(n1);
+        path_dq.push_back(n2);
 
         FullGraph::NodeMap<bool> used(_gr, false);
@@ -107 +111 @@
 
         min_edge1 = INVALID;
-        while (int(_path.size()) != _gr.nodeNum()) {
+        while (int(path_dq.size()) != _gr.nodeNum()) {
           if (min_edge1 == INVALID) {
             for (IncEdgeIt e(_gr, n1); e != INVALID; ++e) {
@@ -128 +132 @@
           if (_cost[min_edge1] < _cost[min_edge2]) {
             n1 = _gr.oppositeNode(n1, min_edge1);
-            _path.push_front(n1);
+            path_dq.push_front(n1);
 
             used[n1] = true;
@@ -137 +141 @@
           } else {
             n2 = _gr.oppositeNode(n2, min_edge2);
-            _path.push_back(n2);
+            path_dq.push_back(n2);
 
             used[n2] = true;
@@ -147 +151 @@
         }
 
-        _sum = _cost[_gr.edge(_path.back(), _path.front())];
-        for (int i = 0; i < int(_path.size())-1; ++i) {
-          _sum += _cost[_gr.edge(_path[i], _path[i+1])];
+        n1 = path_dq.back();
+        n2 = path_dq.front();
+        _path.push_back(n2);
+        _sum = _cost[_gr.edge(n1, n2)];
+        for (int i = 1; i < int(path_dq.size()); ++i) {
+          n1 = n2;
+          n2 = path_dq[i];
+          _path.push_back(n2);
+          _sum += _cost[_gr.edge(n1, n2)];
         }
 
@@ -172 +182 @@
       /// found tour.
       ///
-      /// This function returns a const reference to the internal structure
+      /// This function returns a const reference to a vector
       /// that stores the node sequence of the found tour.
       ///
       /// \pre run() must be called before using this function.
-      const std::deque<Node>& tourNodes() const {
+      const std::vector<Node>& tourNodes() const {
         return _path;
       }