Changeset 1033:9a51db038228 in lemon-main for lemon

Timestamp:

01/08/11 22:51:16 (13 years ago)

Author:

Peter Kovacs <kpeter@…>

Branch:

default

Phase:

public

Message:

Document and greatly improve TSP algorithms (#386)

• Add LEMON headers.
• Add Doxygen doc for all classes and their members.
• Clarify and unify the public API of the algorithms.
• Various small improvements in the implementations to make them clearer and faster.
• Avoid using adaptors in ChristofidesTsp?.

Location:

lemon

Files:

• christofides_tsp.h (modified) (1 diff)
• greedy_tsp.h (modified) (2 diffs)
• insertion_tsp.h (modified) (8 diffs)
• nearest_neighbor_tsp.h (modified) (4 diffs)
• opt2_tsp.h (modified) (2 diffs)

lemon/christofides_tsp.h

@@ +1 @@
+/* -*- mode: C++; indent-tabs-mode: nil; -*-
+ *
+ * This file is a part of LEMON, a generic C++ optimization library.
+ *
+ * Copyright (C) 2003-2010
+ * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
+ * (Egervary Research Group on Combinatorial Optimization, EGRES).
+ *
+ * Permission to use, modify and distribute this software is granted
+ * provided that this copyright notice appears in all copies. For
+ * precise terms see the accompanying LICENSE file.
+ *
+ * This software is provided "AS IS" with no warranty of any kind,
+ * express or implied, and with no claim as to its suitability for any
+ * purpose.
+ *
+ */
+
 #ifndef LEMON_CHRISTOFIDES_TSP_H
 #define LEMON_CHRISTOFIDES_TSP_H
 
+/// \ingroup tsp
+/// \file
+/// \brief Christofides algorithm for symmetric TSP
+
 #include <lemon/full_graph.h>
 #include <lemon/smart_graph.h>
-#include <lemon/path.h>
 #include <lemon/kruskal.h>
 #include <lemon/matching.h>
-#include <lemon/adaptors.h>
-#include <lemon/maps.h>
 #include <lemon/euler.h>
 
 namespace lemon {
   
-  namespace christofides_helper {
-    template <class L>
-    L vectorConvert(const std::vector<FullGraph::Node> &_path) {
-      return L(_path.begin(), _path.end());
-    }
-  
-    template <>
-    std::vector<FullGraph::Node> vectorConvert(const std::vector<FullGraph::Node> &_path) {
-      return _path;
-    }
-  }
-  
+  /// \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".
+  /// 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.
+  ///
+  /// The algorithm starts with a \ref spantree "minimum cost spanning tree" and
+  /// finds a \ref MaxWeightedPerfectMatching "minimum cost perfect matching"
+  /// in the subgraph induced by the nodes that have odd degree in the
+  /// spanning tree.
+  /// Finally, it constructs the tour from the \ref EulerIt "Euler traversal"
+  /// of the union of the spanning tree and the matching.
+  /// During this last step, the algorithm simply skips the visited nodes
+  /// (i.e. creates shortcuts) assuming that the triangle inequality holds
+  /// for the cost function.
+  ///
+  /// \tparam CM Type of the cost map.
+  ///
+  /// \warning \& CM::Value must be signed type.
   template <typename CM>
-  class ChristofidesTsp {
+  class ChristofidesTsp
+  {
+    public:
+
+      /// Type of the cost map
+      typedef CM CostMap;
+      /// Type of the edge costs
+      typedef typename CM::Value Cost;
+
     private:
-      GRAPH_TYPEDEFS(SmartGraph);
+
+      GRAPH_TYPEDEFS(FullGraph);
+
+      const FullGraph &_gr;
+      const CostMap &_cost;
+      std::vector<Node> _path;
+      Cost _sum;
 
     public:
-      typedef typename CM::Value Cost;
-      typedef SmartGraph::EdgeMap<Cost> CostMap;
-    
-      ChristofidesTsp(const FullGraph &gr, const CM &cost) : _cost(_gr), fullg(gr), fullcost(cost), nr(_gr) {
-        graphCopy(gr, _gr).nodeCrossRef(nr).edgeMap(cost, _cost).run();
-      }
-
+
+      /// \brief Constructor
+      ///
+      /// Constructor.
+      /// \param gr The \ref FullGraph "full graph" the algorithm runs on.
+      /// \param cost The cost map.
+      ChristofidesTsp(const FullGraph &gr, const CostMap &cost)
+        : _gr(gr), _cost(cost) {}
+
+      /// \name Execution Control
+      /// @{
+
+      /// \brief Runs the algorithm.
+      ///
+      /// This function runs the algorithm.
+      ///
+      /// \return The total cost of the found tour.
       Cost run() {
         _path.clear();
-        
-        SmartGraph::EdgeMap<bool> tree(_gr);
-        kruskal(_gr, _cost, tree);
-        
-        FilterEdges<SmartGraph> treefiltered(_gr, tree);
-        InDegMap<FilterEdges<SmartGraph> > deg(treefiltered);
-        
-        SmartGraph::NodeMap<bool> oddfilter(_gr, false);
-        FilterNodes<SmartGraph> oddNodes(_gr, oddfilter);
-        
-        for (NodeIt n(_gr); n!=INVALID; ++n) {
-          if (deg[n]%2 == 1) {
-            oddNodes.enable(n);
+
+        if (_gr.nodeNum() == 0) return _sum = 0;
+        else if (_gr.nodeNum() == 1) {
+          _path.push_back(_gr(0));
+          return _sum = 0;
+        }
+        else if (_gr.nodeNum() == 2) {
+          _path.push_back(_gr(0));
+          _path.push_back(_gr(1));
+          return _sum = 2 * _cost[_gr.edge(_gr(0), _gr(1))];
+        }
+        
+        // Compute min. cost spanning tree
+        std::vector<Edge> tree;
+        kruskal(_gr, _cost, std::back_inserter(tree));
+        
+        FullGraph::NodeMap<int> deg(_gr, 0);
+        for (int i = 0; i != int(tree.size()); ++i) {
+          Edge e = tree[i];
+          ++deg[_gr.u(e)];
+          ++deg[_gr.v(e)];
+        }
+
+        // Copy the induced subgraph of odd nodes
+        std::vector<Node> odd_nodes;
+        for (NodeIt u(_gr); u != INVALID; ++u) {
+          if (deg[u] % 2 == 1) odd_nodes.push_back(u);
+        }
+  
+        SmartGraph sgr;
+        SmartGraph::EdgeMap<Cost> scost(sgr);
+        for (int i = 0; i != int(odd_nodes.size()); ++i) {
+          sgr.addNode();
+        }
+        for (int i = 0; i != int(odd_nodes.size()); ++i) {
+          for (int j = 0; j != int(odd_nodes.size()); ++j) {
+            if (j == i) continue;
+            SmartGraph::Edge e =
+              sgr.addEdge(sgr.nodeFromId(i), sgr.nodeFromId(j));
+            scost[e] = -_cost[_gr.edge(odd_nodes[i], odd_nodes[j])];
           }
         }
         
-        NegMap<CostMap> negmap(_cost);
-        MaxWeightedPerfectMatching<FilterNodes<SmartGraph>,
-                  NegMap<CostMap> > perfmatch(oddNodes, negmap);
-        perfmatch.run();
-        
-        for (FilterNodes<SmartGraph>::EdgeIt e(oddNodes); e!=INVALID; ++e) {
-          if (perfmatch.matching(e)) {
-            treefiltered.enable(_gr.addEdge(_gr.u(e), _gr.v(e)));
+        // Compute min. cost perfect matching
+        MaxWeightedPerfectMatching<SmartGraph, SmartGraph::EdgeMap<Cost> >
+          mwpm(sgr, scost);
+        mwpm.run();
+        
+        for (SmartGraph::EdgeIt e(sgr); e != INVALID; ++e) {
+          if (mwpm.matching(e)) {
+            tree.push_back( _gr.edge(odd_nodes[sgr.id(sgr.u(e))],
+                                     odd_nodes[sgr.id(sgr.v(e))]) );
           }
         }
         
-        FilterEdges<SmartGraph>::NodeMap<bool> seen(treefiltered, false);
-        for (EulerIt<FilterEdges<SmartGraph> > e(treefiltered); e!=INVALID; ++e) {
-          if (seen[treefiltered.target(e)]==false) {
-            _path.push_back(nr[treefiltered.target(e)]);
-            seen[treefiltered.target(e)] = true;
+        // Join the spanning tree and the matching        
+        sgr.clear();
+        for (int i = 0; i != _gr.nodeNum(); ++i) {
+          sgr.addNode();
+        }
+        for (int i = 0; i != int(tree.size()); ++i) {
+          int ui = _gr.id(_gr.u(tree[i])),
+              vi = _gr.id(_gr.v(tree[i]));
+          sgr.addEdge(sgr.nodeFromId(ui), sgr.nodeFromId(vi));
+        }
+
+        // Compute the tour from the Euler traversal
+        SmartGraph::NodeMap<bool> visited(sgr, false);
+        for (EulerIt<SmartGraph> e(sgr); e != INVALID; ++e) {
+          SmartGraph::Node n = sgr.target(e);
+          if (!visited[n]) {
+            _path.push_back(_gr(sgr.id(n)));
+            visited[n] = true;
           }
         }
 
-        _sum = fullcost[ fullg.edge(_path.back(), _path.front()) ];
-        for (unsigned int i=0; i<_path.size()-1; ++i)
-          _sum += fullcost[ fullg.edge(_path[i], _path[i+1]) ];
+        _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])];
+        }
 
         return _sum;
       }
 
-      template <typename L>
-      void tourNodes(L &container) {
-        container(christofides_helper::vectorConvert<L>(_path));
-      }
-      
-      template <template <typename> class L>
-      L<FullGraph::Node> tourNodes() {
-        return christofides_helper::vectorConvert<L<FullGraph::Node> >(_path);
-      }
-
-      const std::vector<Node>& tourNodes() {
+      /// @}
+      
+      /// \name Query Functions
+      /// @{
+      
+      /// \brief The total cost of the found tour.
+      ///
+      /// This function returns the total cost of the found tour.
+      ///
+      /// \pre run() must be called before using this function.
+      Cost tourCost() const {
+        return _sum;
+      }
+      
+      /// \brief Returns a const reference to the node sequence of the
+      /// found tour.
+      ///
+      /// This function returns a const reference to the internal structure
+      /// that stores the node sequence of the found tour.
+      ///
+      /// \pre run() must be called before using this function.
+      const std::vector<Node>& tourNodes() const {
         return _path;
       }
-      
-      Path<FullGraph> tour() {
-        Path<FullGraph> p;
-        if (_path.size()<2)
-          return p;
-
-        for (unsigned int i=0; i<_path.size()-1; ++i) {
-          p.addBack(fullg.arc(_path[i], _path[i+1]));
-        }
-        p.addBack(fullg.arc(_path.back(), _path.front()));
-        
-        return p;
-      }
-      
-      Cost tourCost() {
-        return _sum;
-      }
-      
-
-  private:
-    SmartGraph _gr;
-    CostMap _cost;
-    Cost _sum;
-    const FullGraph &fullg;
-    const CM &fullcost;
-    std::vector<FullGraph::Node> _path;
-    SmartGraph::NodeMap<FullGraph::Node> nr;
+
+      /// \brief Gives back the node sequence of the found tour.
+      ///
+      /// This function copies the node sequence of the found tour into
+      /// the given standard container.
+      ///
+      /// \pre run() must be called before using this function.
+      template <typename Container>
+      void tourNodes(Container &container) const {
+        container.assign(_path.begin(), _path.end());
+      }
+      
+      /// \brief Gives back the found tour as a path.
+      ///
+      /// This function copies the found tour as a list of arcs/edges into
+      /// the given \ref concept::Path "path structure".
+      ///
+      /// \pre run() must be called before using this function.
+      template <typename Path>
+      void tour(Path &path) const {
+        path.clear();
+        for (int i = 0; i < int(_path.size()) - 1; ++i) {
+          path.addBack(_gr.arc(_path[i], _path[i+1]));
+        }
+        if (int(_path.size()) >= 2) {
+          path.addBack(_gr.arc(_path.back(), _path.front()));
+        }
+      }
+      
+      /// @}
+      
   };
 
-
 }; // namespace lemon
 

lemon/greedy_tsp.h

@@ +1 @@
+/* -*- mode: C++; indent-tabs-mode: nil; -*-
+ *
+ * This file is a part of LEMON, a generic C++ optimization library.
+ *
+ * Copyright (C) 2003-2010
+ * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
+ * (Egervary Research Group on Combinatorial Optimization, EGRES).
+ *
+ * Permission to use, modify and distribute this software is granted
+ * provided that this copyright notice appears in all copies. For
+ * precise terms see the accompanying LICENSE file.
+ *
+ * This software is provided "AS IS" with no warranty of any kind,
+ * express or implied, and with no claim as to its suitability for any
+ * purpose.
+ *
+ */
+
 #ifndef LEMON_GREEDY_TSP_H
 #define LEMON_GREEDY_TSP_H
 
-#include <lemon/path.h>
+/// \ingroup tsp
+/// \file
+/// \brief Greedy algorithm for symmetric TSP
+
+#include <vector>
+#include <algorithm>
 #include <lemon/full_graph.h>
 #include <lemon/unionfind.h>
-#include <algorithm>
 
 namespace lemon {
 
-  namespace greedy_tsp_helper {
-
-    template <typename CostMap>
-    class KeyComp {
-      typedef typename CostMap::Key Key;
-      const CostMap &cost;
+  /// \brief Greedy algorithm for symmetric TSP.
+  ///
+  /// GreedyTsp implements the greedy heuristic for solving
+  /// symmetric \ref tsp "TSP".
+  ///
+  /// This algorithm is quite similar to the \ref NearestNeighborTsp
+  /// "nearest neighbor" heuristic, but it maintains a set of disjoint paths.
+  /// At each step, the shortest possible edge is added to these paths
+  /// as long as it does not create a cycle of less than n edges and it does
+  /// 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.
+  ///
+  /// \tparam CM Type of the cost map.
+  template <typename CM>
+  class GreedyTsp
+  {
+    public:
+
+      /// Type of the cost map
+      typedef CM CostMap;
+      /// Type of the edge costs
+      typedef typename CM::Value Cost;
+
+    private:
+
+      GRAPH_TYPEDEFS(FullGraph);
+
+      const FullGraph &_gr;
+      const CostMap &_cost;
+      Cost _sum;
+      std::vector<Node> _path;
       
+    private:
+    
+      // Functor class to compare edges by their costs
+      class EdgeComp {
+      private:
+        const CostMap &_cost;
+
       public:
-        KeyComp(const CostMap &_cost) : cost(_cost) {}
-      
-        bool operator() (const Key &a, const Key &b) const {
-          return cost[a] < cost[b];
-        }
-    };
-
-  
-    template <class L>
-    L vectorConvert(const std::vector<FullGraph::Node> &_path) {
-      return L(_path.begin(), _path.end());
-    }
-  
-    template <>
-    std::vector<FullGraph::Node> vectorConvert(const std::vector<FullGraph::Node> &_path) {
-      return _path;
-    }
-    
-  }
-
-
-  template <typename CM>
-  class GreedyTsp {
-    private:
-      GRAPH_TYPEDEFS(FullGraph);
-    
+        EdgeComp(const CostMap &cost) : _cost(cost) {}
+
+        bool operator()(const Edge &a, const Edge &b) const {
+          return _cost[a] < _cost[b];
+        }
+      };
+
     public:
-      typedef CM CostMap;
-      typedef typename CM::Value Cost;
-      
-      GreedyTsp(const FullGraph &gr, const CostMap &cost) : _gr(gr), _cost(cost) {}  
-
+
+      /// \brief Constructor
+      ///
+      /// Constructor.
+      /// \param gr The \ref FullGraph "full graph" the algorithm runs on.
+      /// \param cost The cost map.
+      GreedyTsp(const FullGraph &gr, const CostMap &cost)
+        : _gr(gr), _cost(cost) {}
+
+      /// \name Execution Control
+      /// @{
+
+      /// \brief Runs the algorithm.
+      ///
+      /// This function runs the algorithm.
+      ///
+      /// \return The total cost of the found tour.
       Cost run() {
-        typedef UnionFind<FullGraph::NodeMap<int> > Union;
-        _nodes.clear();
-        
-        std::vector<int> path;
-        path.resize(_gr.nodeNum()*2, -1);
-        
-        std::vector<typename CostMap::Key> sorted_edges;
+        _path.clear();
+
+        if (_gr.nodeNum() == 0) return _sum = 0;
+        else if (_gr.nodeNum() == 1) {
+          _path.push_back(_gr(0));
+          return _sum = 0;
+        }
+
+        std::vector<int> plist;
+        plist.resize(_gr.nodeNum()*2, -1);
+
+        std::vector<Edge> sorted_edges;
         sorted_edges.reserve(_gr.edgeNum());
-        for (EdgeIt n(_gr); n != INVALID; ++n)
-          sorted_edges.push_back(n);
-
-        std::sort(sorted_edges.begin(), sorted_edges.end(), greedy_tsp_helper::KeyComp<CostMap>(_cost));
-
-        FullGraph::NodeMap<int> nodemap(_gr);
-        Union unionfind(nodemap);
-
+        for (EdgeIt e(_gr); e != INVALID; ++e)
+          sorted_edges.push_back(e);
+        std::sort(sorted_edges.begin(), sorted_edges.end(), EdgeComp(_cost));
+
+        FullGraph::NodeMap<int> item_int_map(_gr);
+        UnionFind<FullGraph::NodeMap<int> > union_find(item_int_map);
         for (NodeIt n(_gr); n != INVALID; ++n)
-          unionfind.insert(n);
-        
+          union_find.insert(n);
+
         FullGraph::NodeMap<int> degree(_gr, 0);
 
         int nodesNum = 0, i = 0;
-
-        while ( nodesNum != _gr.nodeNum()-1 ) {
-          const Edge &e = sorted_edges[i];
-          
-          const Node u = _gr.u(e),
-                     v = _gr.v(e);
-          
-          if (degree[u]<=1 && degree[v]<=1) {
-            if (unionfind.join(u, v)) {
+        while (nodesNum != _gr.nodeNum()-1) {
+          Edge e = sorted_edges[i++];
+          Node u = _gr.u(e),
+               v = _gr.v(e);
+
+          if (degree[u] <= 1 && degree[v] <= 1) {
+            if (union_find.join(u, v)) {
+              const int uid = _gr.id(u),
+                        vid = _gr.id(v);
+
+              plist[uid*2 + degree[u]] = vid;
+              plist[vid*2 + degree[v]] = uid;
+
               ++degree[u];
               ++degree[v];
               ++nodesNum;
-              
-              const int uid = _gr.id(u),
-                        vid = _gr.id(v);
-              
-              
-              path[uid*2 + (path[uid*2]==-1 ? 0 : 1)] = vid;
-              path[vid*2 + (path[vid*2]==-1 ? 0 : 1)] = uid;
             }
           }
-
-          ++i;
-        }
-
+        }
 
         for (int i=0, n=-1; i<_gr.nodeNum()*2; ++i) {
-          if (path[i] == -1) {
+          if (plist[i] == -1) {
             if (n==-1) {
               n = i;
             } else {
-              path[n] = i/2;
-              path[i] = n/2;
+              plist[n] = i/2;
+              plist[i] = n/2;
               break;
             }
@@ -110 +158 @@
         }
 
-
-        for (int i=0, j=0, last=-1; i!=_gr.nodeNum(); ++i) {
-          _nodes.push_back(_gr.nodeFromId(j));
-          
-          if (path[2*j] != last) {
-            last = j;
-            j = path[2*j];
+        for (int i=0, next=0, last=-1; i!=_gr.nodeNum(); ++i) {
+          _path.push_back(_gr.nodeFromId(next));
+          if (plist[2*next] != last) {
+            last = next;
+            next = plist[2*next];
           } else {
-            last = j;
-            j = path[2*j+1];
+            last = next;
+            next = plist[2*next+1];
           }
         }
 
-        _sum = _cost[_gr.edge(_nodes.back(), _nodes.front())];
-        for (unsigned int i=0; i<_nodes.size()-1; ++i)
-          _sum += _cost[_gr.edge(_nodes[i], _nodes[i+1])];
+        _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])];
+        }
 
         return _sum;
       }
 
-
-
-      template <typename L>
-      void tourNodes(L &container) {
-        container(greedy_tsp_helper::vectorConvert<L>(_nodes));
-      }
-      
-      template <template <typename> class L>
-      L<Node> tourNodes() {
-        return greedy_tsp_helper::vectorConvert<L<Node> >(_nodes);
-      }
-      
-      const std::vector<Node>& tourNodes() {
-        return _nodes;
-      }
-      
-      Path<FullGraph> tour() {
-        Path<FullGraph> p;
-        if (_nodes.size()<2)
-          return p;
-        
-        for (unsigned int i=0; i<_nodes.size()-1; ++i) {
-          p.addBack(_gr.arc(_nodes[i], _nodes[i+1]));
-        }
-        
-        p.addBack(_gr.arc(_nodes.back(), _nodes.front()));
-        
-        return p;
-      }
-      
-      Cost tourCost() {
+      /// @}
+
+      /// \name Query Functions
+      /// @{
+
+      /// \brief The total cost of the found tour.
+      ///
+      /// This function returns the total cost of the found tour.
+      ///
+      /// \pre run() must be called before using this function.
+      Cost tourCost() const {
         return _sum;
       }
-      
-
-    private:
-      const FullGraph &_gr;
-      const CostMap &_cost;
-      Cost _sum;
-      std::vector<Node> _nodes;
+
+      /// \brief Returns a const reference to the node sequence of the
+      /// found tour.
+      ///
+      /// This function returns a const reference to the internal structure
+      /// that stores the node sequence of the found tour.
+      ///
+      /// \pre run() must be called before using this function.
+      const std::vector<Node>& tourNodes() const {
+        return _path;
+      }
+
+      /// \brief Gives back the node sequence of the found tour.
+      ///
+      /// This function copies the node sequence of the found tour into
+      /// the given standard container.
+      ///
+      /// \pre run() must be called before using this function.
+      template <typename Container>
+      void tourNodes(Container &container) const {
+        container.assign(_path.begin(), _path.end());
+      }
+
+      /// \brief Gives back the found tour as a path.
+      ///
+      /// This function copies the found tour as a list of arcs/edges into
+      /// the given \ref concept::Path "path structure".
+      ///
+      /// \pre run() must be called before using this function.
+      template <typename Path>
+      void tour(Path &path) const {
+        path.clear();
+        for (int i = 0; i < int(_path.size()) - 1; ++i) {
+          path.addBack(_gr.arc(_path[i], _path[i+1]));
+        }
+        if (int(_path.size()) >= 2) {
+          path.addBack(_gr.arc(_path.back(), _path.front()));
+        }
+      }
+
+      /// @}
+
   };
 

lemon/insertion_tsp.h

@@ +1 @@
+/* -*- mode: C++; indent-tabs-mode: nil; -*-
+ *
+ * This file is a part of LEMON, a generic C++ optimization library.
+ *
+ * Copyright (C) 2003-2010
+ * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
+ * (Egervary Research Group on Combinatorial Optimization, EGRES).
+ *
+ * Permission to use, modify and distribute this software is granted
+ * provided that this copyright notice appears in all copies. For
+ * precise terms see the accompanying LICENSE file.
+ *
+ * This software is provided "AS IS" with no warranty of any kind,
+ * express or implied, and with no claim as to its suitability for any
+ * purpose.
+ *
+ */
+
 #ifndef LEMON_INSERTION_TSP_H
 #define LEMON_INSERTION_TSP_H
 
+/// \ingroup tsp
+/// \file
+/// \brief Insertion algorithm for symmetric TSP
+
+#include <vector>
 #include <lemon/full_graph.h>
-#include <lemon/path.h>
 #include <lemon/maps.h>
 #include <lemon/random.h>
-#include <vector>
 
 namespace lemon {
 
-  namespace insertion_tsp_helper {
-  
-    template <class L>
-    L vectorConvert(const std::vector<FullGraph::Node> &_path) {
-      return L(_path.begin(), _path.end());
-    };
-  
-    template <>
-    std::vector<FullGraph::Node> vectorConvert(
-        const std::vector<FullGraph::Node> &_path) {
-      return _path;
-    };
-    
-  };
-
+  /// \brief Insertion algorithm for symmetric TSP.
+  ///
+  /// InsertionTsp implements the insertion heuristic for solving
+  /// symmetric \ref tsp "TSP".
+  ///
+  /// This is a basic TSP heuristic that has many variants.
+  /// It starts with a subtour containing a few nodes of the graph and it
+  /// iteratively inserts the other nodes into this subtour according to a
+  /// certain node selection rule.
+  ///
+  /// This implementation provides four different node selection rules,
+  /// from which the most powerful one is used by default.
+  /// For more information, see \ref SelectionRule.
+  ///
+  /// \tparam CM Type of the cost map.
   template <typename CM>
-  class InsertionTsp {
+  class InsertionTsp
+  {
+    public:
+
+      /// Type of the cost map
+      typedef CM CostMap;
+      /// Type of the edge costs
+      typedef typename CM::Value Cost;
+
     private:
+
       GRAPH_TYPEDEFS(FullGraph);
 
-    public:      
-      typedef CM CostMap;
-      typedef typename CM::Value Cost;
-      
-      InsertionTsp(const FullGraph &gr, const CostMap &cost) : 
-            _gr(gr), _cost(cost) {}
-      
-      enum InsertionMethod {
-        INSERT_NEAREST,
-        INSERT_FARTHEST,
-        INSERT_CHEAPEST,
-        INSERT_RANDOM
-      };     
-      
-      Cost run(InsertionMethod method = INSERT_FARTHEST) {
-        switch (method) {
-          case INSERT_NEAREST:
-            start<InitTour<true>, NearestSelection, DefaultInsert>();
+      const FullGraph &_gr;
+      const CostMap &_cost;
+      std::vector<Node> _notused;
+      std::vector<Node> _path;
+      Cost _sum;
+
+    public:
+
+      /// \brief Constants for specifying the node selection rule.
+      ///
+      /// Enum type containing constants for specifying the node selection
+      /// rule for the \ref run() function.
+      ///
+      /// 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.
+      ///
+      /// The desired selection rule can be specified as a parameter of the
+      /// \ref run() function.
+      enum SelectionRule {
+
+        /// An unvisited node having minimum distance from the current
+        /// subtour is selected at each step.
+        /// The algorithm runs in O(n<sup>3</sup>) time using this
+        /// selection rule.
+        NEAREST,
+
+        /// An unvisited node having maximum distance from the current
+        /// subtour is selected at each step.
+        /// The algorithm runs in O(n<sup>3</sup>) time using this
+        /// selection rule.
+        FARTHEST,
+
+        /// An unvisited node whose insertion results in the least
+        /// increase of the subtour's total cost is selected at each step.
+        /// The algorithm runs in O(n<sup>3</sup>) time using this
+        /// selection rule.
+        CHEAPEST,
+
+        /// An unvisited node is selected randomly without any evaluation
+        /// at each step.
+        /// The global \ref rnd "random number generator instance" is used.
+        /// You can seed it before executing the algorithm, if you
+        /// would like to.
+        /// The algorithm runs in O(n<sup>2</sup>) time using this
+        /// selection rule.
+        RANDOM
+      };
+
+    public:
+
+      /// \brief Constructor
+      ///
+      /// Constructor.
+      /// \param gr The \ref FullGraph "full graph" the algorithm runs on.
+      /// \param cost The cost map.
+      InsertionTsp(const FullGraph &gr, const CostMap &cost)
+        : _gr(gr), _cost(cost) {}
+
+      /// \name Execution Control
+      /// @{
+
+      /// \brief Runs the algorithm.
+      ///
+      /// This function runs the algorithm.
+      ///
+      /// \param rule The node selection rule. For more information, see
+      /// \ref SelectionRule.
+      ///
+      /// \return The total cost of the found tour.
+      Cost run(SelectionRule rule = FARTHEST) {
+        _path.clear();
+
+        if (_gr.nodeNum() == 0) return _sum = 0;
+        else if (_gr.nodeNum() == 1) {
+          _path.push_back(_gr(0));
+          return _sum = 0;
+        }
+
+        switch (rule) {
+          case NEAREST:
+            init(true);
+            start<NearestSelection, DefaultInsertion>();
             break;
-          case INSERT_FARTHEST:
-            start<InitTour<false>, FarthestSelection, DefaultInsert>();
+          case FARTHEST:
+            init(false);
+            start<FarthestSelection, DefaultInsertion>();
             break;
-          case INSERT_CHEAPEST:
-            start<InitTour<true>, CheapestSelection, CheapestInsert>();
+          case CHEAPEST:
+            init(true);
+            start<CheapestSelection, CheapestInsertion>();
             break;
-          case INSERT_RANDOM:
-            start<InitTour<true>, RandomSelection, DefaultInsert>();
+          case RANDOM:
+            init(true);
+            start<RandomSelection, DefaultInsertion>();
             break;
         }
-        return sum;
-      }
-
-      template <typename L>
-      void tourNodes(L &container) {
-        container(insertion_tsp_helper::vectorConvert<L>(nodesPath));
-      }
-      
-      template <template <typename> class L>
-      L<Node> tourNodes() {
-        return insertion_tsp_helper::vectorConvert<L<Node> >(nodesPath);
-      }
-      
-      const std::vector<Node>& tourNodes() {
-        return nodesPath;
-      }
-      
-      Path<FullGraph> tour() {
-        Path<FullGraph> p;
-        if (nodesPath.size()<2)
-          return p;
-        
-        for (unsigned int i=0; i<nodesPath.size()-1; ++i)
-          p.addBack(_gr.arc(nodesPath[i], nodesPath[i+1]));
-        
-        p.addBack(_gr.arc(nodesPath.back(), nodesPath.front()));
-        return p;
-      }
-      
-      Cost tourCost() {
-        return sum;
-      }
-
+        return _sum;
+      }
+
+      /// @}
+
+      /// \name Query Functions
+      /// @{
+
+      /// \brief The total cost of the found tour.
+      ///
+      /// This function returns the total cost of the found tour.
+      ///
+      /// \pre run() must be called before using this function.
+      Cost tourCost() const {
+        return _sum;
+      }
+
+      /// \brief Returns a const reference to the node sequence of the
+      /// found tour.
+      ///
+      /// This function returns a const reference to the internal structure
+      /// that stores the node sequence of the found tour.
+      ///
+      /// \pre run() must be called before using this function.
+      const std::vector<Node>& tourNodes() const {
+        return _path;
+      }
+
+      /// \brief Gives back the node sequence of the found tour.
+      ///
+      /// This function copies the node sequence of the found tour into
+      /// the given standard container.
+      ///
+      /// \pre run() must be called before using this function.
+      template <typename Container>
+      void tourNodes(Container &container) const {
+        container.assign(_path.begin(), _path.end());
+      }
+
+      /// \brief Gives back the found tour as a path.
+      ///
+      /// This function copies the found tour as a list of arcs/edges into
+      /// the given \ref concept::Path "path structure".
+      ///
+      /// \pre run() must be called before using this function.
+      template <typename Path>
+      void tour(Path &path) const {
+        path.clear();
+        for (int i = 0; i < int(_path.size()) - 1; ++i) {
+          path.addBack(_gr.arc(_path[i], _path[i+1]));
+        }
+        if (int(_path.size()) >= 2) {
+          path.addBack(_gr.arc(_path.back(), _path.front()));
+        }
+      }
+
+      /// @}
 
     private:
 
-      template <bool MIN>
-      class InitTour {
-        public:
-          InitTour(const FullGraph &gr, const CostMap &cost,
-                   std::vector<Node> &used, std::vector<Node> &notused,
-                   Cost &fullcost) :
-              _gr(gr), _cost(cost), _used(used), _notused(notused),
-              _fullcost(fullcost) {}
-
-          std::vector<Node> init() const {
-            Edge min = (MIN) ? mapMin(_gr, _cost) : mapMax(_gr, _cost);
-            std::vector<Node> path;
-            path.push_back(_gr.u(min));
-            path.push_back(_gr.v(min));
-            
-            _used.clear();
-            _notused.clear();
-            for (NodeIt n(_gr); n!=INVALID; ++n) {
-              if (n != _gr.u(min) && n != _gr.v(min)) {
-                _notused.push_back(n);
+      // Initializes the algorithm
+      void init(bool min) {
+        Edge min_edge = min ? mapMin(_gr, _cost) : mapMax(_gr, _cost);
+
+        _path.clear();
+        _path.push_back(_gr.u(min_edge));
+        _path.push_back(_gr.v(min_edge));
+
+        _notused.clear();
+        for (NodeIt n(_gr); n!=INVALID; ++n) {
+          if (n != _gr.u(min_edge) && n != _gr.v(min_edge)) {
+            _notused.push_back(n);
+          }
+        }
+
+        _sum = _cost[min_edge] * 2;
+      }
+
+      // Executes the algorithm
+      template <class SelectionFunctor, class InsertionFunctor>
+      void start() {
+        SelectionFunctor selectNode(_gr, _cost, _path, _notused);
+        InsertionFunctor insertNode(_gr, _cost, _path, _sum);
+
+        for (int i=0; i<_gr.nodeNum()-2; ++i) {
+          insertNode.insert(selectNode.select());
+        }
+
+        _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])];
+        }
+      }
+
+
+      // Implementation of the nearest selection rule
+      class NearestSelection {
+        public:
+          NearestSelection(const FullGraph &gr, const CostMap &cost,
+                           std::vector<Node> &path, std::vector<Node> &notused)
+            : _gr(gr), _cost(cost), _path(path), _notused(notused) {}
+
+          Node select() const {
+            Cost insert_val = 0;
+            int insert_node = -1;
+
+            for (unsigned int i=0; i<_notused.size(); ++i) {
+              Cost min_val = _cost[_gr.edge(_notused[i], _path[0])];
+              int min_node = 0;
+
+              for (unsigned int j=1; j<_path.size(); ++j) {
+                Cost curr = _cost[_gr.edge(_notused[i], _path[j])];
+                if (min_val > curr) {
+                    min_val = curr;
+                    min_node = j;
+                }
+              }
+
+              if (insert_val > min_val || insert_node == -1) {
+                insert_val = min_val;
+                insert_node = i;
               }
             }
-            _used.push_back(_gr.u(min));
-            _used.push_back(_gr.v(min));
-            
-            _fullcost = _cost[min]*2;
-            return path;
+
+            Node n = _notused[insert_node];
+            _notused.erase(_notused.begin()+insert_node);
+
+            return n;
           }
 
@@ -127 +292 @@
           const FullGraph &_gr;
           const CostMap &_cost;
-          std::vector<Node> &_used;
+          std::vector<Node> &_path;
           std::vector<Node> &_notused;
-          Cost &_fullcost;
-      };
-
-      class NearestSelection {
-        public:
-          NearestSelection(const FullGraph &gr, const CostMap &cost,
-                           std::vector<Node> &used, std::vector<Node> &notused) : 
-              _gr(gr), _cost(cost), _used(used), _notused(notused) {}
-      
+      };
+
+
+      // Implementation of the farthest selection rule
+      class FarthestSelection {
+        public:
+          FarthestSelection(const FullGraph &gr, const CostMap &cost,
+                            std::vector<Node> &path, std::vector<Node> &notused)
+            : _gr(gr), _cost(cost), _path(path), _notused(notused) {}
+
           Node select() const {
-
-            Cost insert_val =
-              std::numeric_limits<Cost>::max();
+            Cost insert_val = 0;
             int insert_node = -1;
-            
+
             for (unsigned int i=0; i<_notused.size(); ++i) {
-              Cost min_val = _cost[_gr.edge(_notused[i], _used[0])];
+              Cost min_val = _cost[_gr.edge(_notused[i], _path[0])];
               int min_node = 0;
-            
-              for (unsigned int j=1; j<_used.size(); ++j) {
-                if (min_val > _cost[_gr.edge(_notused[i], _used[j])]) {
-                    min_val = _cost[_gr.edge(_notused[i], _used[j])];
-                    min_node = j;
-                }
-              }
-              
-              if (insert_val > min_val) {
-                insert_val = min_val;
-                insert_node = i;
-              }
-            }
-            
-            Node n = _notused[insert_node];
-            _notused.erase(_notused.begin()+insert_node);
-            
-            return n;
-          }
-          
-        private:
-          const FullGraph &_gr;
-          const CostMap &_cost;
-          std::vector<Node> &_used;
-          std::vector<Node> &_notused;
-      };
-
-      class FarthestSelection {
-        public:
-          FarthestSelection(const FullGraph &gr, const CostMap &cost,
-                            std::vector<Node> &used, std::vector<Node> &notused) : 
-              _gr(gr), _cost(cost), _used(used), _notused(notused) {}
-      
-          Node select() const {
-
-            Cost insert_val =
-              std::numeric_limits<Cost>::min();
-            int insert_node = -1;
-            
-            for (unsigned int i=0; i<_notused.size(); ++i) {
-              Cost min_val = _cost[_gr.edge(_notused[i], _used[0])];
-              int min_node = 0;
-              
-              for (unsigned int j=1; j<_used.size(); ++j) {
-                if (min_val > _cost[_gr.edge(_notused[i], _used[j])]) {
-                  min_val = _cost[_gr.edge(_notused[i], _used[j])];
+
+              for (unsigned int j=1; j<_path.size(); ++j) {
+                Cost curr = _cost[_gr.edge(_notused[i], _path[j])];
+                if (min_val > curr) {
+                  min_val = curr;
                   min_node = j;
                 }
               }
-              
+
               if (insert_val < min_val || insert_node == -1) {
                 insert_val = min_val;
@@ -202 +325 @@
               }
             }
-            
+
             Node n = _notused[insert_node];
             _notused.erase(_notused.begin()+insert_node);
-            
+
             return n;
           }
-          
+
         private:
           const FullGraph &_gr;
           const CostMap &_cost;
-          std::vector<Node> &_used;
+          std::vector<Node> &_path;
           std::vector<Node> &_notused;
       };
 
 
+      // Implementation of the cheapest selection rule
       class CheapestSelection {
         private:
           Cost costDiff(Node u, Node v, Node w) const {
-            return 
+            return
               _cost[_gr.edge(u, w)] +
               _cost[_gr.edge(v, w)] -
@@ -228 +352 @@
         public:
           CheapestSelection(const FullGraph &gr, const CostMap &cost,
-                            std::vector<Node> &used, std::vector<Node> &notused) : 
-              _gr(gr), _cost(cost), _used(used), _notused(notused) {}
-        
+                            std::vector<Node> &path, std::vector<Node> &notused)
+            : _gr(gr), _cost(cost), _path(path), _notused(notused) {}
+
           Cost select() const {
             int insert_notused = -1;
             int best_insert_index = -1;
-            Cost insert_val =
-              std::numeric_limits<Cost>::max();
-            
+            Cost insert_val = 0;
+
             for (unsigned int i=0; i<_notused.size(); ++i) {
               int min = i;
               int best_insert_tmp = 0;
               Cost min_val =
-                costDiff(_used.front(), _used.back(), _notused[i]);
-              
-              for (unsigned int j=1; j<_used.size(); ++j) {
+                costDiff(_path.front(), _path.back(), _notused[i]);
+
+              for (unsigned int j=1; j<_path.size(); ++j) {
                 Cost tmp =
-                  costDiff(_used[j-1], _used[j], _notused[i]);
+                  costDiff(_path[j-1], _path[j], _notused[i]);
 
                 if (min_val > tmp) {
@@ -254 +377 @@
               }
 
-              if (insert_val > min_val) {
+              if (insert_val > min_val || insert_notused == -1) {
                 insert_notused = min;
                 insert_val = min_val;
@@ -261 +384 @@
             }
 
-            _used.insert(_used.begin()+best_insert_index, _notused[insert_notused]);
+            _path.insert(_path.begin()+best_insert_index,
+                         _notused[insert_notused]);
             _notused.erase(_notused.begin()+insert_notused);
 
             return insert_val;
           }
-          
+
         private:
           const FullGraph &_gr;
           const CostMap &_cost;
-          std::vector<Node> &_used;
+          std::vector<Node> &_path;
           std::vector<Node> &_notused;
       };
 
+      // Implementation of the random selection rule
       class RandomSelection {
         public:
           RandomSelection(const FullGraph &, const CostMap &,
-                            std::vector<Node> &, std::vector<Node> &notused) : 
-                           _notused(notused) {
-            rnd.seedFromTime();
-          }
-          
+                          std::vector<Node> &, std::vector<Node> &notused)
+            : _notused(notused) {}
+
           Node select() const {
             const int index = rnd[_notused.size()];
@@ -293 +416 @@
 
 
-      class DefaultInsert {
+      // Implementation of the default insertion method
+      class DefaultInsertion {
         private:
           Cost costDiff(Node u, Node v, Node w) const {
-            return 
+            return
               _cost[_gr.edge(u, w)] +
               _cost[_gr.edge(v, w)] -
               _cost[_gr.edge(u, v)];
           }
-  
-        public:
-          DefaultInsert(const FullGraph &gr, const CostMap &cost,
-                        std::vector<Node> &path, Cost &fullcost) : 
-            _gr(gr), _cost(cost), _path(path), _fullcost(fullcost) {}
-          
+
+        public:
+          DefaultInsertion(const FullGraph &gr, const CostMap &cost,
+                           std::vector<Node> &path, Cost &total_cost) :
+            _gr(gr), _cost(cost), _path(path), _total(total_cost) {}
+
           void insert(Node n) const {
             int min = 0;
             Cost min_val =
               costDiff(_path.front(), _path.back(), n);
-            
+
             for (unsigned int i=1; i<_path.size(); ++i) {
               Cost tmp = costDiff(_path[i-1], _path[i], n);
@@ -319 +443 @@
               }
             }
-            
+
             _path.insert(_path.begin()+min, n);
-            _fullcost += min_val;
-          }
-        
+            _total += min_val;
+          }
+
         private:
           const FullGraph &_gr;
           const CostMap &_cost;
           std::vector<Node> &_path;
-          Cost &_fullcost;
-      };
-  
-      class CheapestInsert {
+          Cost &_total;
+      };
+
+      // Implementation of a special insertion method for the cheapest
+      // selection rule
+      class CheapestInsertion {
         TEMPLATE_GRAPH_TYPEDEFS(FullGraph);
         public:
-          CheapestInsert(const FullGraph &, const CostMap &,
-                         std::vector<Node> &, Cost &fullcost) : 
-            _fullcost(fullcost) {}
-          
+          CheapestInsertion(const FullGraph &, const CostMap &,
+                            std::vector<Node> &, Cost &total_cost) :
+            _total(total_cost) {}
+
           void insert(Cost diff) const {
-            _fullcost += diff;
-          }
-
-        private:
-          Cost &_fullcost;
-      };  
-      
-      
-      template <class InitFunctor, class SelectionFunctor, class InsertFunctor>
-      void start() {
-        InitFunctor init(_gr, _cost, nodesPath, notused, sum);
-        SelectionFunctor selectNode(_gr, _cost, nodesPath, notused);
-        InsertFunctor insertNode(_gr, _cost, nodesPath, sum);
-        
-        nodesPath = init.init();
-        
-        for (int i=0; i<_gr.nodeNum()-2; ++i) {
-          insertNode.insert(selectNode.select());
-        }
-        
-        sum = _cost[ _gr.edge(nodesPath.front(), nodesPath.back()) ];
-        for (unsigned int i=0; i<nodesPath.size()-1; ++i)
-          sum += _cost[ _gr.edge(nodesPath[i], nodesPath[i+1]) ];
-      }
-    
-      const FullGraph &_gr;
-      const CostMap &_cost;
-      std::vector<Node> notused;
-      std::vector<Node> nodesPath;
-      Cost sum;
+            _total += diff;
+          }
+
+        private:
+          Cost &_total;
+      };
+
   };
-  
+
 }; // namespace lemon
 

lemon/nearest_neighbor_tsp.h

@@ +1 @@
+/* -*- mode: C++; indent-tabs-mode: nil; -*-
+ *
+ * This file is a part of LEMON, a generic C++ optimization library.
+ *
+ * Copyright (C) 2003-2010
+ * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
+ * (Egervary Research Group on Combinatorial Optimization, EGRES).
+ *
+ * Permission to use, modify and distribute this software is granted
+ * provided that this copyright notice appears in all copies. For
+ * precise terms see the accompanying LICENSE file.
+ *
+ * This software is provided "AS IS" with no warranty of any kind,
+ * express or implied, and with no claim as to its suitability for any
+ * purpose.
+ *
+ */
+
 #ifndef LEMON_NEAREST_NEIGHBOUR_TSP_H
 #define LEMON_NEAREST_NEIGHBOUR_TSP_H
 
+/// \ingroup tsp
+/// \file
+/// \brief Nearest neighbor algorithm for symmetric TSP
+
 #include <deque>
+#include <limits>
 #include <lemon/full_graph.h>
-#include <lemon/path.h>
 #include <lemon/maps.h>
 
 namespace lemon {
-  
-  namespace nn_helper {
-    template <class L>
-    L dequeConvert(const std::deque<FullGraph::Node> &_path) {
-      return L(_path.begin(), _path.end());
-    }
-
-    template <>
-    std::deque<FullGraph::Node> dequeConvert(const std::deque<FullGraph::Node> &_path) {
-      return _path;
-    }
-  }
-  
+
+  /// \brief Nearest neighbor algorithm for symmetric TSP.
+  ///
+  /// NearestNeighborTsp implements the nearest neighbor heuristic for solving
+  /// symmetric \ref tsp "TSP".
+  ///
+  /// This is probably the simplest TSP heuristic.
+  /// It starts with a minimum cost edge and at each step, it connects the
+  /// nearest unvisited node to the current path.
+  /// 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.
+  ///
+  /// \tparam CM Type of the cost map.
   template <typename CM>
-  class NearestNeighborTsp {
+  class NearestNeighborTsp
+  {
+    public:
+
+      /// Type of the cost map
+      typedef CM CostMap;
+      /// Type of the edge costs
+      typedef typename CM::Value Cost;
+
     private:
+
       GRAPH_TYPEDEFS(FullGraph);
 
+      const FullGraph &_gr;
+      const CostMap &_cost;
+      Cost _sum;
+      std::deque<Node> _path;
+
     public:
-      typedef CM CostMap;
-      typedef typename CM::Value Cost;
-    
-      NearestNeighborTsp(const FullGraph &gr, const CostMap &cost) : _gr(gr), _cost(cost) {}
-
+
+      /// \brief Constructor
+      ///
+      /// Constructor.
+      /// \param gr The \ref FullGraph "full graph" the algorithm runs on.
+      /// \param cost The cost map.
+      NearestNeighborTsp(const FullGraph &gr, const CostMap &cost)
+        : _gr(gr), _cost(cost) {}
+
+      /// \name Execution Control
+      /// @{
+
+      /// \brief Runs the algorithm.
+      ///
+      /// This function runs the algorithm.
+      ///
+      /// \return The total cost of the found tour.
       Cost run() {
         _path.clear();
 
+        if (_gr.nodeNum() == 0) return _sum = 0;
+        else if (_gr.nodeNum() == 1) {
+          _path.push_back(_gr(0));
+          return _sum = 0;
+        }
+
         Edge min_edge1 = INVALID,
              min_edge2 = INVALID;
-        
+
         min_edge1 = mapMin(_gr, _cost);
-
-        FullGraph::NodeMap<bool> used(_gr, false);
-
-        Node n1 = _gr.u(min_edge1), 
+        Node n1 = _gr.u(min_edge1),
              n2 = _gr.v(min_edge1);
-        
         _path.push_back(n1);
         _path.push_back(n2);
 
+        FullGraph::NodeMap<bool> used(_gr, false);
         used[n1] = true;
         used[n2] = true;
 
         min_edge1 = INVALID;
-
         while (int(_path.size()) != _gr.nodeNum()) {
           if (min_edge1 == INVALID) {
-            for (IncEdgeIt e(_gr, n1); e!=INVALID; ++e) {
-              if (!used[_gr.runningNode(e)]) {
-                if (min_edge1==INVALID || _cost[min_edge1] > _cost[e])
-                  min_edge1 = e;
+            for (IncEdgeIt e(_gr, n1); e != INVALID; ++e) {
+              if (!used[_gr.runningNode(e)] &&
+                  (_cost[e] < _cost[min_edge1] || min_edge1 == INVALID)) {
+                min_edge1 = e;
               }
             }
@@ -64 +118 @@
 
           if (min_edge2 == INVALID) {
-            for (IncEdgeIt e(_gr, n2); e!=INVALID; ++e) {
-              if (!used[_gr.runningNode(e)]) {
-                if (min_edge2==INVALID || _cost[min_edge2] > _cost[e])
-                  min_edge2 = e;
+            for (IncEdgeIt e(_gr, n2); e != INVALID; ++e) {
+              if (!used[_gr.runningNode(e)] &&
+                  (_cost[e] < _cost[min_edge2] || min_edge2 == INVALID)) {
+                min_edge2 = e;
               }
             }
           }
 
-          if ( _cost[min_edge1] < _cost[min_edge2] ) {
-            n1 = (_gr.u(min_edge1) == n1) ? _gr.v(min_edge1) : _gr.u(min_edge1);
+          if (_cost[min_edge1] < _cost[min_edge2]) {
+            n1 = _gr.oppositeNode(n1, min_edge1);
             _path.push_front(n1);
 
@@ -79 +133 @@
             min_edge1 = INVALID;
 
-            if (_gr.u(min_edge2)==n1 || _gr.v(min_edge2)==n1)
+            if (_gr.u(min_edge2) == n1 || _gr.v(min_edge2) == n1)
               min_edge2 = INVALID;
           } else {
-            n2 = (_gr.u(min_edge2) == n2) ? _gr.v(min_edge2) : _gr.u(min_edge2);
+            n2 = _gr.oppositeNode(n2, min_edge2);
             _path.push_back(n2);
 
@@ -88 +142 @@
             min_edge2 = INVALID;
 
-            if (_gr.u(min_edge1)==n2 || _gr.v(min_edge1)==n2)
+            if (_gr.u(min_edge1) == n2 || _gr.v(min_edge1) == n2)
               min_edge1 = INVALID;
           }
         }
 
-        _sum = _cost[ _gr.edge(_path.back(), _path.front()) ];
-        for (unsigned int i=0; i<_path.size()-1; ++i)
-          _sum += _cost[ _gr.edge(_path[i], _path[i+1]) ];
+        _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])];
+        }
 
         return _sum;
       }
 
-      
-      template <typename L>
-      void tourNodes(L &container) {
-        container(nn_helper::dequeConvert<L>(_path));
-      }
-      
-      template <template <typename> class L>
-      L<Node> tourNodes() {
-        return nn_helper::dequeConvert<L<Node> >(_path);
-      }      
-
-      const std::deque<Node>& tourNodes() {
+      /// @}
+
+      /// \name Query Functions
+      /// @{
+
+      /// \brief The total cost of the found tour.
+      ///
+      /// This function returns the total cost of the found tour.
+      ///
+      /// \pre run() must be called before using this function.
+      Cost tourCost() const {
+        return _sum;
+      }
+
+      /// \brief Returns a const reference to the node sequence of the
+      /// found tour.
+      ///
+      /// This function returns a const reference to the internal structure
+      /// that stores the node sequence of the found tour.
+      ///
+      /// \pre run() must be called before using this function.
+      const std::deque<Node>& tourNodes() const {
         return _path;
       }
-      
-      Path<FullGraph> tour() {
-        Path<FullGraph> p;
-        if (_path.size()<2)
-          return p;
-        
-        for (unsigned int i=0; i<_path.size()-1; ++i) {
-          p.addBack(_gr.arc(_path[i], _path[i+1]));
-        }
-        p.addBack(_gr.arc(_path.back(), _path.front()));
-        
-        return p;
-      }
-      
-      Cost tourCost() {
-        return _sum;
-      }
-      
-
-  private:
-    const FullGraph &_gr;
-    const CostMap &_cost;
-    Cost _sum;
-    std::deque<Node> _path;
+
+      /// \brief Gives back the node sequence of the found tour.
+      ///
+      /// This function copies the node sequence of the found tour into
+      /// the given standard container.
+      ///
+      /// \pre run() must be called before using this function.
+      template <typename Container>
+      void tourNodes(Container &container) const {
+        container.assign(_path.begin(), _path.end());
+      }
+
+      /// \brief Gives back the found tour as a path.
+      ///
+      /// This function copies the found tour as a list of arcs/edges into
+      /// the given \ref concept::Path "path structure".
+      ///
+      /// \pre run() must be called before using this function.
+      template <typename Path>
+      void tour(Path &path) const {
+        path.clear();
+        for (int i = 0; i < int(_path.size()) - 1; ++i) {
+          path.addBack(_gr.arc(_path[i], _path[i+1]));
+        }
+        if (int(_path.size()) >= 2) {
+          path.addBack(_gr.arc(_path.back(), _path.front()));
+        }
+      }
+
+      /// @}
+
   };
 
-
 }; // namespace lemon
 

lemon/opt2_tsp.h

@@ +1 @@
+/* -*- mode: C++; indent-tabs-mode: nil; -*-
+ *
+ * This file is a part of LEMON, a generic C++ optimization library.
+ *
+ * Copyright (C) 2003-2010
+ * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
+ * (Egervary Research Group on Combinatorial Optimization, EGRES).
+ *
+ * Permission to use, modify and distribute this software is granted
+ * provided that this copyright notice appears in all copies. For
+ * precise terms see the accompanying LICENSE file.
+ *
+ * This software is provided "AS IS" with no warranty of any kind,
+ * express or implied, and with no claim as to its suitability for any
+ * purpose.
+ *
+ */
+
 #ifndef LEMON_OPT2_TSP_H
 #define LEMON_OPT2_TSP_H
 
+/// \ingroup tsp
+/// \file
+/// \brief 2-opt algorithm for symmetric TSP
+
 #include <vector>
 #include <lemon/full_graph.h>
-#include <lemon/path.h>
 
 namespace lemon {
-  
-  namespace opt2_helper {
-    template <class L>
-    L vectorConvert(const std::vector<FullGraph::Node> &_path) {
-      return L(_path.begin(), _path.end());
-    }
-  
-    template <>
-    std::vector<FullGraph::Node> vectorConvert(const std::vector<FullGraph::Node> &_path) {
-      return _path;
-    }
-  }
-  
+
+  /// \brief 2-opt algorithm for symmetric TSP.
+  ///
+  /// Opt2Tsp implements the 2-opt heuristic for solving
+  /// symmetric \ref tsp "TSP".
+  ///
+  /// This algorithm starts with an initial tour and iteratively improves it.
+  /// At each step, it removes two edges and the reconnects the created two
+  /// paths in the other way if the resulting tour is shorter.
+  /// The algorithm finishes when no such 2-opt move can be applied, and so
+  /// the tour is 2-optimal.
+  ///
+  /// If no starting tour is given to the \ref run() function, then the
+  /// algorithm uses the node sequence determined by the node IDs.
+  /// Oherwise, it starts with the given tour.
+  ///
+  /// This is a relatively slow but powerful method. 
+  /// A typical usage of it is the improvement of a solution that is resulted
+  /// by a fast tour construction heuristic (e.g. the InsertionTsp algorithm).
+  ///
+  /// \tparam CM Type of the cost map.
   template <typename CM>
-  class Opt2Tsp {
+  class Opt2Tsp
+  {
+    public:
+
+      /// Type of the cost map
+      typedef CM CostMap;
+      /// Type of the edge costs
+      typedef typename CM::Value Cost;
+
     private:
+
       GRAPH_TYPEDEFS(FullGraph);
 
+      const FullGraph &_gr;
+      const CostMap &_cost;
+      Cost _sum;
+      std::vector<int> _plist;
+      std::vector<Node> _path;
+
     public:
-      typedef CM CostMap;
-      typedef typename CM::Value Cost;
-      
-    
-      Opt2Tsp(const FullGraph &gr, const CostMap &cost) : _gr(gr), _cost(cost), 
-            tmppath(_gr.nodeNum()*2) {
-            
-        for (int i=1; i<_gr.nodeNum()-1; ++i) {
-          tmppath[2*i] = i-1;
-          tmppath[2*i+1] = i+1;
-        }
-        tmppath[0] = _gr.nodeNum()-1;
-        tmppath[1] = 1;
-        tmppath[2*(_gr.nodeNum()-1)] = _gr.nodeNum()-2;
-        tmppath[2*(_gr.nodeNum()-1)+1] = 0;
-      }
-      
-      Opt2Tsp(const FullGraph &gr, const CostMap &cost, const std::vector<Node> &path) : 
-              _gr(gr), _cost(cost), tmppath(_gr.nodeNum()*2) {
-
-        for (unsigned int i=1; i<path.size()-1; ++i) {
-          tmppath[2*_gr.id(path[i])] = _gr.id(path[i-1]);
-          tmppath[2*_gr.id(path[i])+1] = _gr.id(path[i+1]);
-        }
-        
-        tmppath[2*_gr.id(path[0])] = _gr.id(path.back());
-        tmppath[2*_gr.id(path[0])+1] = _gr.id(path[1]);
-        tmppath[2*_gr.id(path.back())] = _gr.id(path[path.size()-2]);
-        tmppath[2*_gr.id(path.back())+1] = _gr.id(path.front());
-      }
+
+      /// \brief Constructor
+      ///
+      /// Constructor.
+      /// \param gr The \ref FullGraph "full graph" the algorithm runs on.
+      /// \param cost The cost map.
+      Opt2Tsp(const FullGraph &gr, const CostMap &cost)
+        : _gr(gr), _cost(cost) {}
+
+      /// \name Execution Control
+      /// @{
+
+      /// \brief Runs the algorithm from scratch.
+      ///
+      /// This function runs the algorithm starting from the tour that is
+      /// determined by the node ID sequence.
+      ///
+      /// \return The total cost of the found tour.
+      Cost run() {
+        _path.clear();
+
+        if (_gr.nodeNum() == 0) return _sum = 0;
+        else if (_gr.nodeNum() == 1) {
+          _path.push_back(_gr(0));
+          return _sum = 0;
+        }
+        else if (_gr.nodeNum() == 2) {
+          _path.push_back(_gr(0));
+          _path.push_back(_gr(1));
+          return _sum = 2 * _cost[_gr.edge(_gr(0), _gr(1))];
+        }
+
+        _plist.resize(2*_gr.nodeNum());
+        for (int i = 1; i < _gr.nodeNum()-1; ++i) {
+          _plist[2*i] = i-1;
+          _plist[2*i+1] = i+1;
+        }
+        _plist[0] = _gr.nodeNum()-1;
+        _plist[1] = 1;
+        _plist[2*_gr.nodeNum()-2] = _gr.nodeNum()-2;
+        _plist[2*_gr.nodeNum()-1] = 0;
+
+        return start();
+      }
+
+      /// \brief Runs the algorithm from the given tour.
+      ///
+      /// This function runs the algorithm starting from the given tour.
+      ///
+      /// \param tour The tour as a path structure. It must be a
+      /// \ref checkPath() "valid path" containing excactly n arcs.
+      ///
+      /// \return The total cost of the found tour.
+      template <typename Path>
+      Cost run(const Path& tour) {
+        _path.clear();
+
+        if (_gr.nodeNum() == 0) return _sum = 0;
+        else if (_gr.nodeNum() == 1) {
+          _path.push_back(_gr(0));
+          return _sum = 0;
+        }
+        else if (_gr.nodeNum() == 2) {
+          _path.push_back(_gr(0));
+          _path.push_back(_gr(1));
+          return _sum = 2 * _cost[_gr.edge(_gr(0), _gr(1))];
+        }
+
+        _plist.resize(2*_gr.nodeNum());
+        typename Path::ArcIt it(tour);
+        int first = _gr.id(_gr.source(it)),
+            prev = first,
+            curr = _gr.id(_gr.target(it)),
+            next = -1;
+        _plist[2*first+1] = curr;
+        for (++it; it != INVALID; ++it) {
+          next = _gr.id(_gr.target(it));
+          _plist[2*curr] = prev;
+          _plist[2*curr+1] = next;
+          prev = curr;
+          curr = next;
+        }
+        _plist[2*first] = prev;
+
+        return start();
+      }
+
+      /// \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.
+      ///
+      /// \return The total cost of the found tour.
+      template <template <typename> class Container>
+      Cost run(const Container<Node>& tour) {
+        _path.clear();
+
+        if (_gr.nodeNum() == 0) return _sum = 0;
+        else if (_gr.nodeNum() == 1) {
+          _path.push_back(_gr(0));
+          return _sum = 0;
+        }
+        else if (_gr.nodeNum() == 2) {
+          _path.push_back(_gr(0));
+          _path.push_back(_gr(1));
+          return _sum = 2 * _cost[_gr.edge(_gr(0), _gr(1))];
+        }
+
+        _plist.resize(2*_gr.nodeNum());
+        typename Container<Node>::const_iterator it = tour.begin();
+        int first = _gr.id(*it),
+            prev = first,
+            curr = _gr.id(*(++it)),
+            next = -1;
+        _plist[2*first+1] = curr;
+        for (++it; it != tour.end(); ++it) {
+          next = _gr.id(*it);
+          _plist[2*curr] = prev;
+          _plist[2*curr+1] = next;
+          prev = curr;
+          curr = next;
+        }
+        _plist[2*first] = curr;
+        _plist[2*curr] = prev;
+        _plist[2*curr+1] = first;
+
+        return start();
+      }
+
+      /// @}
+
+      /// \name Query Functions
+      /// @{
+
+      /// \brief The total cost of the found tour.
+      ///
+      /// This function returns the total cost of the found tour.
+      ///
+      /// \pre run() must be called before using this function.
+      Cost tourCost() const {
+        return _sum;
+      }
+
+      /// \brief Returns a const reference to the node sequence of the
+      /// found tour.
+      ///
+      /// This function returns a const reference to the internal structure
+      /// that stores the node sequence of the found tour.
+      ///
+      /// \pre run() must be called before using this function.
+      const std::vector<Node>& tourNodes() const {
+        return _path;
+      }
+
+      /// \brief Gives back the node sequence of the found tour.
+      ///
+      /// This function copies the node sequence of the found tour into
+      /// the given standard container.
+      ///
+      /// \pre run() must be called before using this function.
+      template <typename Container>
+      void tourNodes(Container &container) const {
+        container.assign(_path.begin(), _path.end());
+      }
+
+      /// \brief Gives back the found tour as a path.
+      ///
+      /// This function copies the found tour as a list of arcs/edges into
+      /// the given \ref concept::Path "path structure".
+      ///
+      /// \pre run() must be called before using this function.
+      template <typename Path>
+      void tour(Path &path) const {
+        path.clear();
+        for (int i = 0; i < int(_path.size()) - 1; ++i) {
+          path.addBack(_gr.arc(_path[i], _path[i+1]));
+        }
+        if (int(_path.size()) >= 2) {
+          path.addBack(_gr.arc(_path.back(), _path.front()));
+        }
+      }
+
+      /// @}
 
     private:
-      Cost c(int u, int v) {
-        return _cost[_gr.edge(_gr.nodeFromId(u), _gr.nodeFromId(v))];
-      }
-      
-      class It {
+
+      // Iterator class for the linked list storage of the tour
+      class PathListIt {
         public:
-          It(const std::vector<int> &path, int i=0) : tmppath(path), act(i), last(tmppath[2*act]) {}
-          It(const std::vector<int> &path, int i, int l) : tmppath(path), act(i), last(l) {}
-
-          int next_index() const {
-            return (tmppath[2*act]==last)? 2*act+1 : 2*act;
-          }
-          
-          int prev_index() const {
-            return (tmppath[2*act]==last)? 2*act : 2*act+1;
-          }
-          
+          PathListIt(const std::vector<int> &pl, int i=0)
+            : plist(&pl), act(i), last(pl[2*act]) {}
+          PathListIt(const std::vector<int> &pl, int i, int l)
+            : plist(&pl), act(i), last(l) {}
+
+          int nextIndex() const {
+            return (*plist)[2*act] == last ? 2*act+1 : 2*act;
+          }
+
+          int prevIndex() const {
+            return (*plist)[2*act] == last ? 2*act : 2*act+1;
+          }
+
           int next() const {
-            return tmppath[next_index()];
+            int x = (*plist)[2*act];
+            return x == last ? (*plist)[2*act+1] : x;
           }
 
           int prev() const {
-            return tmppath[prev_index()];
-          }
-          
-          It& operator++() {
+            return last;
+          }
+
+          PathListIt& operator++() {
             int tmp = act;
             act = next();
@@ -89 +289 @@
             return *this;
           }
-          
+
           operator int() const {
             return act;
           }
-          
+
         private:
-          const std::vector<int> &tmppath;
+          const std::vector<int> *plist;
           int act;
           int last;
       };
 
-      bool check(std::vector<int> &path, It i, It j) {
-        if (c(i, i.next()) + c(j, j.next()) > 
-            c(i, j) + c(j.next(), i.next())) {
-
-            path[ It(path, i.next(), i).prev_index() ] = j.next();
-            path[ It(path, j.next(), j).prev_index() ] = i.next();
-
-            path[i.next_index()] = j;
-            path[j.next_index()] = i;
-
-            return true;
-        }
+      // Checks and applies 2-opt move (if it improves the tour)
+      bool checkOpt2(const PathListIt& i, const PathListIt& j) {
+        Node u  = _gr.nodeFromId(i),
+             un = _gr.nodeFromId(i.next()),
+             v  = _gr.nodeFromId(j),
+             vn = _gr.nodeFromId(j.next());
+
+        if (_cost[_gr.edge(u, un)] + _cost[_gr.edge(v, vn)] >
+            _cost[_gr.edge(u, v)] + _cost[_gr.edge(un, vn)])
+        {
+          _plist[PathListIt(_plist, i.next(), i).prevIndex()] = j.next();
+          _plist[PathListIt(_plist, j.next(), j).prevIndex()] = i.next();
+
+          _plist[i.nextIndex()] = j;
+          _plist[j.nextIndex()] = i;
+
+          return true;
+        }
+
         return false;
-      }
-      
-    public:
-      
-      Cost run() {
-        _path.clear();
-
-        if (_gr.nodeNum()>3) {
-
-opt2_tsp_label:
-          It i(tmppath);
-          It j(tmppath, i, i.prev());
-          ++j; ++j;
-          for (; j.next()!=0; ++j) {
-            if (check(tmppath, i, j))
-              goto opt2_tsp_label;
-          }
-          
-          for (++i; i.next()!=0; ++i) {
-            It j(tmppath, i, i.prev());
-            if (++j==0)
-              break;
-            if (++j==0)
-              break;
-            
-            for (; j!=0; ++j) {
-              if (check(tmppath, i, j))
-                goto opt2_tsp_label;
-            }
-          }
-        }
-
-        It k(tmppath);
-        _path.push_back(_gr.nodeFromId(k));
-        for (++k; k!=0; ++k)
-          _path.push_back(_gr.nodeFromId(k));
-
-        
-
-        _sum = _cost[ _gr.edge(_path.back(), _path.front()) ];
-        for (unsigned int i=0; i<_path.size()-1; ++i)
-          _sum += _cost[ _gr.edge(_path[i], _path[i+1]) ];
+     }
+
+      // Executes the algorithm from the initial tour
+      Cost start() {
+
+      restart_search:
+        for (PathListIt i(_plist); true; ++i) {
+          PathListIt j = i;
+          if (++j == 0 || ++j == 0) break;
+          for (; j != 0 && j != i.prev(); ++j) {
+            if (checkOpt2(i, j))
+              goto restart_search;
+          }
+        }
+
+        PathListIt i(_plist);
+        _path.push_back(_gr.nodeFromId(i));
+        for (++i; i != 0; ++i)
+          _path.push_back(_gr.nodeFromId(i));
+
+        _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])];
+        }
+
         return _sum;
       }
 
-      
-      template <typename L>
-      void tourNodes(L &container) {
-        container(opt2_helper::vectorConvert<L>(_path));
-      }
-      
-      template <template <typename> class L>
-      L<Node> tourNodes() {
-        return opt2_helper::vectorConvert<L<Node> >(_path);
-      }
-
-      const std::vector<Node>& tourNodes() {
-        return _path;
-      }
-      
-      Path<FullGraph> tour() {
-        Path<FullGraph> p;
-        if (_path.size()<2)
-          return p;
-
-        for (unsigned int i=0; i<_path.size()-1; ++i) {
-          p.addBack(_gr.arc(_path[i], _path[i+1]));
-        }
-        p.addBack(_gr.arc(_path.back(), _path.front()));
-        return p;
-      }
-      
-      Cost tourCost() {
-        return _sum;
-      }
-      
-
-  private:
-    const FullGraph &_gr;
-    const CostMap &_cost;
-    Cost _sum;
-    std::vector<int> tmppath;
-    std::vector<Node> _path;
   };
 
-
 }; // namespace lemon