Changeset 1202:ef200e268af2 in lemon

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)

Files:

• doc/groups.dox (modified) (1 diff)
• lemon/christofides_tsp.h (modified) (4 diffs)
• lemon/greedy_tsp.h (modified) (3 diffs)
• lemon/insertion_tsp.h (modified) (3 diffs)
• lemon/nearest_neighbor_tsp.h (modified) (12 diffs)
• lemon/opt2_tsp.h (modified) (6 diffs)

doc/groups.dox

@@ -562 +562 @@
 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:

lemon/christofides_tsp.h

@@ -32 +32 @@
 namespace lemon {
   
+  /// \ingroup tsp
+  ///
   /// \brief Christofides algorithm for symmetric TSP.
   ///
@@ -38 +40 @@
   ///
   /// 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.
@@ -55 +57 @@
   /// \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
@@ -196 +198 @@
       /// 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.
       ///

lemon/greedy_tsp.h

@@ -31 +31 @@
 namespace lemon {
 
+  /// \ingroup tsp
+  ///
   /// \brief Greedy algorithm for symmetric TSP.
   ///
@@ -43 +45 @@
   ///
   /// 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.
@@ -194 +195 @@
       /// 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.
       ///

lemon/insertion_tsp.h

@@ -31 +31 @@
 namespace lemon {
 
+  /// \ingroup tsp
+  ///
   /// \brief Insertion algorithm for symmetric TSP.
   ///
@@ -75 +77 @@
       /// 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
@@ -179 +181 @@
       /// 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.
       ///

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;
       }

lemon/opt2_tsp.h

@@ -22 +22 @@
 /// \ingroup tsp
 /// \file
-/// \brief 2-opt algorithm for symmetric TSP
+/// \brief 2-opt algorithm for symmetric TSP.
 
 #include <vector>
@@ -29 +29 @@
 namespace lemon {
 
+  /// \ingroup tsp
+  ///
   /// \brief 2-opt algorithm for symmetric TSP.
   ///
@@ -115 +117 @@
       }
 
-      /// \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.
@@ -157 +159 @@
       }
 
-      /// \brief Runs the algorithm from the given tour.
-      ///
-      /// This function runs the algorithm starting from the given tour.
-      ///
-      /// \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.
+      /// \brief Runs the algorithm starting from the given tour.
+      ///
+      /// This function runs the algorithm starting from the given tour
+      /// (node sequence).
+      ///
+      /// \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();
 
@@ -181 +183 @@
 
         _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,
@@ -218 +220 @@
       /// 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.
       ///