# HG changeset patch
# User Peter Kovacs <kpeter@inf.elte.hu>
# Date 1294531012 -3600
# Node ID ef200e268af2e361f17337a8535e52dc90a035fe
# Parent  9a51db0382284a09f447b6d148d29e681cb23e98
Unifications and improvements in TSP algorithms (#386)

diff -r 9a51db038228 -r ef200e268af2 doc/groups.dox
--- a/doc/groups.dox	Sat Jan 08 22:51:16 2011 +0100
+++ b/doc/groups.dox	Sun Jan 09 00:56:52 2011 +0100
@@ -561,8 +561,9 @@
 the problem is to find a shortest possible tour that visits each node exactly
 once (i.e. the minimum cost Hamiltonian cycle).
 
-These TSP algorithms should be used with a
-metric cost function. Otherwise, they could yield worse results.
+These TSP algorithms are intended to be used with a \e metric \e cost
+\e function, i.e. the edge costs should satisfy the triangle inequality.
+Otherwise the algorithms could yield worse results.
 
 LEMON provides five well-known heuristics for solving symmetric TSP:
  - \ref NearestNeighborTsp Neareast neighbor algorithm
diff -r 9a51db038228 -r ef200e268af2 lemon/christofides_tsp.h
--- a/lemon/christofides_tsp.h	Sat Jan 08 22:51:16 2011 +0100
+++ b/lemon/christofides_tsp.h	Sun Jan 09 00:56:52 2011 +0100
@@ -31,13 +31,15 @@
 
 namespace lemon {
   
+  /// \ingroup tsp
+  ///
   /// \brief Christofides algorithm for symmetric TSP.
   ///
   /// ChristofidesTsp implements Christofides' heuristic for solving
   /// symmetric \ref tsp "TSP".
   ///
   /// This a well-known approximation method for the TSP problem with
-  /// \ref checkMetricCost() "metric cost function".
+  /// metric cost function.
   /// It yields a tour whose total cost is at most 3/2 of the optimum,
   /// but it is usually much better.
   /// This implementation runs in O(n<sup>3</sup>log(n)) time.
@@ -54,7 +56,7 @@
   ///
   /// \tparam CM Type of the cost map.
   ///
-  /// \warning \& CM::Value must be signed type.
+  /// \warning CM::Value must be a signed number type.
   template <typename CM>
   class ChristofidesTsp
   {
@@ -195,7 +197,7 @@
       /// \brief Returns a const reference to the node sequence of the
       /// 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.
diff -r 9a51db038228 -r ef200e268af2 lemon/greedy_tsp.h
--- a/lemon/greedy_tsp.h	Sat Jan 08 22:51:16 2011 +0100
+++ b/lemon/greedy_tsp.h	Sun Jan 09 00:56:52 2011 +0100
@@ -30,6 +30,8 @@
 
 namespace lemon {
 
+  /// \ingroup tsp
+  ///
   /// \brief Greedy algorithm for symmetric TSP.
   ///
   /// GreedyTsp implements the greedy heuristic for solving
@@ -42,9 +44,8 @@
   /// not increase the degree of any node above two.
   ///
   /// This method runs in O(n<sup>2</sup>log(n)) 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.
   template <typename CM>
@@ -193,7 +194,7 @@
       /// \brief Returns a const reference to the node sequence of the
       /// 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.
diff -r 9a51db038228 -r ef200e268af2 lemon/insertion_tsp.h
--- a/lemon/insertion_tsp.h	Sat Jan 08 22:51:16 2011 +0100
+++ b/lemon/insertion_tsp.h	Sun Jan 09 00:56:52 2011 +0100
@@ -30,6 +30,8 @@
 
 namespace lemon {
 
+  /// \ingroup tsp
+  ///
   /// \brief Insertion algorithm for symmetric TSP.
   ///
   /// InsertionTsp implements the insertion heuristic for solving
@@ -74,9 +76,9 @@
       ///
       /// During the algorithm, nodes are selected for addition to the current
       /// subtour according to the applied rule.
-      /// In general, the FARTHEST yields the best tours, thus it is the
-      /// default option. RANDOM usually gives somewhat worse results, but
-      /// it is much faster than the others and it is the most robust.
+      /// In general, the FARTHEST method yields the best tours, thus it is the
+      /// default option. The RANDOM rule usually gives somewhat worse results,
+      /// but it is much faster than the others and it is the most robust.
       ///
       /// The desired selection rule can be specified as a parameter of the
       /// \ref run() function.
@@ -178,7 +180,7 @@
       /// \brief Returns a const reference to the node sequence of the
       /// 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.
diff -r 9a51db038228 -r ef200e268af2 lemon/nearest_neighbor_tsp.h
--- a/lemon/nearest_neighbor_tsp.h	Sat Jan 08 22:51:16 2011 +0100
+++ b/lemon/nearest_neighbor_tsp.h	Sun Jan 09 00:56:52 2011 +0100
@@ -24,12 +24,15 @@
 /// \brief Nearest neighbor algorithm for symmetric TSP
 
 #include <deque>
+#include <vector>
 #include <limits>
 #include <lemon/full_graph.h>
 #include <lemon/maps.h>
 
 namespace lemon {
 
+  /// \ingroup tsp
+  ///
   /// \brief Nearest neighbor algorithm for symmetric TSP.
   ///
   /// NearestNeighborTsp implements the nearest neighbor heuristic for solving
@@ -41,9 +44,8 @@
   /// Finally, it connects the two end points of the path to form a tour.
   ///
   /// 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.
   template <typename CM>
@@ -63,7 +65,7 @@
       const FullGraph &_gr;
       const CostMap &_cost;
       Cost _sum;
-      std::deque<Node> _path;
+      std::vector<Node> _path;
 
     public:
 
@@ -85,28 +87,30 @@
       /// \return The total cost of the found tour.
       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));
           return _sum = 0;
         }
 
+        std::deque<Node> path_dq;
         Edge min_edge1 = INVALID,
              min_edge2 = INVALID;
 
         min_edge1 = mapMin(_gr, _cost);
         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);
         used[n1] = true;
         used[n2] = true;
 
         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) {
               if (!used[_gr.runningNode(e)] &&
@@ -127,7 +131,7 @@
 
           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;
             min_edge1 = INVALID;
@@ -136,7 +140,7 @@
               min_edge2 = INVALID;
           } else {
             n2 = _gr.oppositeNode(n2, min_edge2);
-            _path.push_back(n2);
+            path_dq.push_back(n2);
 
             used[n2] = true;
             min_edge2 = INVALID;
@@ -146,9 +150,15 @@
           }
         }
 
-        _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)];
         }
 
         return _sum;
@@ -171,11 +181,11 @@
       /// \brief Returns a const reference to the node sequence of the
       /// 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;
       }
 
diff -r 9a51db038228 -r ef200e268af2 lemon/opt2_tsp.h
--- a/lemon/opt2_tsp.h	Sat Jan 08 22:51:16 2011 +0100
+++ b/lemon/opt2_tsp.h	Sun Jan 09 00:56:52 2011 +0100
@@ -21,13 +21,15 @@
 
 /// \ingroup tsp
 /// \file
-/// \brief 2-opt algorithm for symmetric TSP
+/// \brief 2-opt algorithm for symmetric TSP.
 
 #include <vector>
 #include <lemon/full_graph.h>
 
 namespace lemon {
 
+  /// \ingroup tsp
+  ///
   /// \brief 2-opt algorithm for symmetric TSP.
   ///
   /// Opt2Tsp implements the 2-opt heuristic for solving
@@ -114,7 +116,7 @@
         return start();
       }
 
-      /// \brief Runs the algorithm from the given tour.
+      /// \brief Runs the algorithm starting from the given tour.
       ///
       /// This function runs the algorithm starting from the given tour.
       ///
@@ -156,16 +158,16 @@
         return start();
       }
 
-      /// \brief Runs the algorithm from the given tour.
+      /// \brief Runs the algorithm starting from the given tour.
       ///
-      /// This function runs the algorithm starting from the given tour.
+      /// This function runs the algorithm starting from the given tour
+      /// (node sequence).
       ///
-      /// \param tour The tour as a node sequence. It must be a standard
-      /// sequence container storing all <tt>Node</tt>s in the desired order.
+      /// \param tour A vector that stores all <tt>Node</tt>s of the graph
+      /// in the desired order.
       ///
       /// \return The total cost of the found tour.
-      template <template <typename> class Container>
-      Cost run(const Container<Node>& tour) {
+      Cost run(const std::vector<Node>& tour) {
         _path.clear();
 
         if (_gr.nodeNum() == 0) return _sum = 0;
@@ -180,7 +182,7 @@
         }
 
         _plist.resize(2*_gr.nodeNum());
-        typename Container<Node>::const_iterator it = tour.begin();
+        typename std::vector<Node>::const_iterator it = tour.begin();
         int first = _gr.id(*it),
             prev = first,
             curr = _gr.id(*(++it)),
@@ -217,7 +219,7 @@
       /// \brief Returns a const reference to the node sequence of the
       /// 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.