Index: doc/CMakeLists.txt
===================================================================
--- doc/CMakeLists.txt	(revision 1135)
+++ doc/CMakeLists.txt	(revision 1206)
@@ -47,4 +47,5 @@
     COMMAND ${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} -r18 -sOutputFile=gen-images/planar.png ${CMAKE_CURRENT_SOURCE_DIR}/images/planar.eps
     COMMAND ${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} -r18 -sOutputFile=gen-images/strongly_connected_components.png ${CMAKE_CURRENT_SOURCE_DIR}/images/strongly_connected_components.eps
+    COMMAND ${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} -r18 -sOutputFile=gen-images/tsp.png ${CMAKE_CURRENT_SOURCE_DIR}/images/tsp.eps
     COMMAND ${CMAKE_COMMAND} -E remove_directory html
     COMMAND ${PYTHON_EXECUTABLE} ${PROJECT_SOURCE_DIR}/scripts/bib2dox.py ${CMAKE_CURRENT_SOURCE_DIR}/references.bib >references.dox
Index: doc/groups.dox
===================================================================
--- doc/groups.dox	(revision 1165)
+++ doc/groups.dox	(revision 1206)
@@ -559,4 +559,40 @@
 \image latex planar.eps "Plane graph" width=\textwidth
 */
+ 
+/**
+@defgroup tsp Traveling Salesman Problem
+@ingroup algs
+\brief Algorithms for the symmetric traveling salesman problem
+
+This group contains basic heuristic algorithms for the the symmetric
+\e traveling \e salesman \e problem (TSP).
+Given an \ref FullGraph "undirected full graph" with a cost map on its edges,
+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 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
+ - \ref GreedyTsp Greedy algorithm
+ - \ref InsertionTsp Insertion heuristic (with four selection methods)
+ - \ref ChristofidesTsp Christofides algorithm
+ - \ref Opt2Tsp 2-opt algorithm
+
+\ref NearestNeighborTsp, \ref GreedyTsp, and \ref InsertionTsp are the fastest
+solution methods. Furthermore, \ref InsertionTsp is usually quite effective.
+
+\ref ChristofidesTsp is somewhat slower, but it has the best guaranteed
+approximation factor: 3/2.
+
+\ref Opt2Tsp usually provides the best results in practice, but
+it is the slowest method. It can also be used to improve given tours,
+for example, the results of other algorithms.
+
+\image html tsp.png
+\image latex tsp.eps "Traveling salesman problem" width=\textwidth
+*/
 
 /**
Index: doc/images/tsp.eps
===================================================================
--- doc/images/tsp.eps	(revision 1200)
+++ doc/images/tsp.eps	(revision 1200)
@@ -0,0 +1,229 @@
+%!PS-Adobe-2.0 EPSF-2.0
+%%Creator: LEMON, graphToEps()
+%%CreationDate: Tue Jun 15 00:58:57 2010
+%%BoundingBox: 31 41 649 709
+%%EndComments
+/lb { setlinewidth setrgbcolor newpath moveto
+      4 2 roll 1 index 1 index curveto stroke } bind def
+/l { setlinewidth setrgbcolor newpath moveto lineto stroke } bind def
+/c { newpath dup 3 index add 2 index moveto 0 360 arc closepath } bind def
+/sq { newpath 2 index 1 index add 2 index 2 index add moveto
+      2 index 1 index sub 2 index 2 index add lineto
+      2 index 1 index sub 2 index 2 index sub lineto
+      2 index 1 index add 2 index 2 index sub lineto
+      closepath pop pop pop} bind def
+/di { newpath 2 index 1 index add 2 index moveto
+      2 index             2 index 2 index add lineto
+      2 index 1 index sub 2 index             lineto
+      2 index             2 index 2 index sub lineto
+      closepath pop pop pop} bind def
+/nc { 0 0 0 setrgbcolor 5 index 5 index 5 index c fill
+     setrgbcolor 1.1 div c fill
+   } bind def
+/nsq { 0 0 0 setrgbcolor 5 index 5 index 5 index sq fill
+     setrgbcolor 1.1 div sq fill
+   } bind def
+/ndi { 0 0 0 setrgbcolor 5 index 5 index 5 index di fill
+     setrgbcolor 1.1 div di fill
+   } bind def
+/nfemale { 0 0 0 setrgbcolor 3 index 0.0909091 1.5 mul mul setlinewidth
+  newpath 5 index 5 index moveto 5 index 5 index 5 index 3.01 mul sub
+  lineto 5 index 4 index .7 mul sub 5 index 5 index 2.2 mul sub moveto
+  5 index 4 index .7 mul add 5 index 5 index 2.2 mul sub lineto stroke
+  5 index 5 index 5 index c fill
+  setrgbcolor 1.1 div c fill
+  } bind def
+/nmale {
+  0 0 0 setrgbcolor 3 index 0.0909091 1.5 mul mul setlinewidth
+  newpath 5 index 5 index moveto
+  5 index 4 index 1 mul 1.5 mul add
+  5 index 5 index 3 sqrt 1.5 mul mul add
+  1 index 1 index lineto
+  1 index 1 index 7 index sub moveto
+  1 index 1 index lineto
+  exch 5 index 3 sqrt .5 mul mul sub exch 5 index .5 mul sub lineto
+  stroke
+  5 index 5 index 5 index c fill
+  setrgbcolor 1.1 div c fill
+  } bind def
+/arrl 1 def
+/arrw 0.3 def
+/lrl { 2 index mul exch 2 index mul exch rlineto pop} bind def
+/arr { setrgbcolor /y1 exch def /x1 exch def /dy exch def /dx exch def
+       /w exch def /len exch def
+       newpath x1 dy w 2 div mul add y1 dx w 2 div mul sub moveto
+       len w sub arrl sub dx dy lrl
+       arrw dy dx neg lrl
+       dx arrl w add mul dy w 2 div arrw add mul sub
+       dy arrl w add mul dx w 2 div arrw add mul add rlineto
+       dx arrl w add mul neg dy w 2 div arrw add mul sub
+       dy arrl w add mul neg dx w 2 div arrw add mul add rlineto
+       arrw dy dx neg lrl
+       len w sub arrl sub neg dx dy lrl
+       closepath fill } bind def
+/cshow { 2 index 2 index moveto dup stringwidth pop
+         neg 2 div fosi .35 mul neg rmoveto show pop pop} def
+
+gsave
+10 dup scale
+%Arcs:
+gsave
+27 68 37 69 0 0 1 0.513798 l
+37 69 27 68 0 0 1 0.513798 l
+8 52 5 64 0 0 1 0.513798 l
+5 64 8 52 0 0 1 0.513798 l
+16 57 25 55 0 0 1 0.513798 l
+25 55 16 57 0 0 1 0.513798 l
+43 67 37 69 0 0 1 0.513798 l
+37 69 43 67 0 0 1 0.513798 l
+42 57 43 67 0 0 1 0.513798 l
+43 67 42 57 0 0 1 0.513798 l
+62 42 61 33 0 0 1 0.513798 l
+61 33 62 42 0 0 1 0.513798 l
+62 42 58 48 0 0 1 0.513798 l
+58 48 62 42 0 0 1 0.513798 l
+58 27 61 33 0 0 1 0.513798 l
+61 33 58 27 0 0 1 0.513798 l
+57 58 62 63 0 0 1 0.513798 l
+62 63 57 58 0 0 1 0.513798 l
+13 13 21 10 0 0 1 0.513798 l
+21 10 13 13 0 0 1 0.513798 l
+13 13 5 6 0 0 1 0.513798 l
+5 6 13 13 0 0 1 0.513798 l
+17 33 7 38 0 0 1 0.513798 l
+7 38 17 33 0 0 1 0.513798 l
+46 10 59 15 0 0 1 0.513798 l
+59 15 46 10 0 0 1 0.513798 l
+46 10 39 10 0 0 1 0.513798 l
+39 10 46 10 0 0 1 0.513798 l
+27 23 21 10 0 0 1 0.513798 l
+21 10 27 23 0 0 1 0.513798 l
+52 41 56 37 0 0 1 0.513798 l
+56 37 52 41 0 0 1 0.513798 l
+62 63 63 69 0 0 1 0.513798 l
+63 69 62 63 0 0 1 0.513798 l
+36 16 39 10 0 0 1 0.513798 l
+39 10 36 16 0 0 1 0.513798 l
+36 16 30 15 0 0 1 0.513798 l
+30 15 36 16 0 0 1 0.513798 l
+12 42 7 38 0 0 1 0.513798 l
+7 38 12 42 0 0 1 0.513798 l
+12 42 8 52 0 0 1 0.513798 l
+8 52 12 42 0 0 1 0.513798 l
+32 22 30 15 0 0 1 0.513798 l
+30 15 32 22 0 0 1 0.513798 l
+5 25 10 17 0 0 1 0.513798 l
+10 17 5 25 0 0 1 0.513798 l
+5 25 17 33 0 0 1 0.513798 l
+17 33 5 25 0 0 1 0.513798 l
+45 35 48 28 0 0 1 0.513798 l
+48 28 45 35 0 0 1 0.513798 l
+31 32 25 32 0 0 1 0.513798 l
+25 32 31 32 0 0 1 0.513798 l
+31 32 32 39 0 0 1 0.513798 l
+32 39 31 32 0 0 1 0.513798 l
+42 41 38 46 0 0 1 0.513798 l
+38 46 42 41 0 0 1 0.513798 l
+42 41 52 41 0 0 1 0.513798 l
+52 41 42 41 0 0 1 0.513798 l
+5 6 10 17 0 0 1 0.513798 l
+10 17 5 6 0 0 1 0.513798 l
+51 21 59 15 0 0 1 0.513798 l
+59 15 51 21 0 0 1 0.513798 l
+51 21 58 27 0 0 1 0.513798 l
+58 27 51 21 0 0 1 0.513798 l
+52 33 56 37 0 0 1 0.513798 l
+56 37 52 33 0 0 1 0.513798 l
+52 33 48 28 0 0 1 0.513798 l
+48 28 52 33 0 0 1 0.513798 l
+31 62 25 55 0 0 1 0.513798 l
+25 55 31 62 0 0 1 0.513798 l
+31 62 27 68 0 0 1 0.513798 l
+27 68 31 62 0 0 1 0.513798 l
+17 63 5 64 0 0 1 0.513798 l
+5 64 17 63 0 0 1 0.513798 l
+17 63 16 57 0 0 1 0.513798 l
+16 57 17 63 0 0 1 0.513798 l
+21 47 30 40 0 0 1 0.513798 l
+30 40 21 47 0 0 1 0.513798 l
+21 47 30 48 0 0 1 0.513798 l
+30 48 21 47 0 0 1 0.513798 l
+40 30 45 35 0 0 1 0.513798 l
+45 35 40 30 0 0 1 0.513798 l
+40 30 32 22 0 0 1 0.513798 l
+32 22 40 30 0 0 1 0.513798 l
+32 39 30 40 0 0 1 0.513798 l
+30 40 32 39 0 0 1 0.513798 l
+20 26 25 32 0 0 1 0.513798 l
+25 32 20 26 0 0 1 0.513798 l
+20 26 27 23 0 0 1 0.513798 l
+27 23 20 26 0 0 1 0.513798 l
+52 64 63 69 0 0 1 0.513798 l
+63 69 52 64 0 0 1 0.513798 l
+52 64 42 57 0 0 1 0.513798 l
+42 57 52 64 0 0 1 0.513798 l
+49 49 58 48 0 0 1 0.513798 l
+58 48 49 49 0 0 1 0.513798 l
+49 49 57 58 0 0 1 0.513798 l
+57 58 49 49 0 0 1 0.513798 l
+37 52 38 46 0 0 1 0.513798 l
+38 46 37 52 0 0 1 0.513798 l
+37 52 30 48 0 0 1 0.513798 l
+30 48 37 52 0 0 1 0.513798 l
+grestore
+%Nodes:
+gsave
+30 40 0.856329 1 1 1 nc
+56 37 0.856329 1 1 1 nc
+48 28 0.856329 1 1 1 nc
+25 55 0.856329 1 1 1 nc
+25 32 0.856329 1 1 1 nc
+32 39 0.856329 1 1 1 nc
+39 10 0.856329 1 1 1 nc
+30 15 0.856329 1 1 1 nc
+5 64 0.856329 1 1 1 nc
+21 10 0.856329 1 1 1 nc
+10 17 0.856329 1 1 1 nc
+5 6 0.856329 1 1 1 nc
+59 15 0.856329 1 1 1 nc
+45 35 0.856329 1 1 1 nc
+32 22 0.856329 1 1 1 nc
+63 69 0.856329 1 1 1 nc
+62 63 0.856329 1 1 1 nc
+61 33 0.856329 1 1 1 nc
+46 10 0.856329 1 1 1 nc
+38 46 0.856329 1 1 1 nc
+37 69 0.856329 1 1 1 nc
+58 27 0.856329 1 1 1 nc
+58 48 0.856329 1 1 1 nc
+43 67 0.856329 1 1 1 nc
+30 48 0.856329 1 1 1 nc
+27 68 0.856329 1 1 1 nc
+7 38 0.856329 1 1 1 nc
+8 52 0.856329 1 1 1 nc
+16 57 0.856329 1 1 1 nc
+42 57 0.856329 1 1 1 nc
+62 42 0.856329 1 1 1 nc
+57 58 0.856329 1 1 1 nc
+13 13 0.856329 1 1 1 nc
+17 33 0.856329 1 1 1 nc
+27 23 0.856329 1 1 1 nc
+52 41 0.856329 1 1 1 nc
+36 16 0.856329 1 1 1 nc
+12 42 0.856329 1 1 1 nc
+5 25 0.856329 1 1 1 nc
+31 32 0.856329 1 1 1 nc
+42 41 0.856329 1 1 1 nc
+51 21 0.856329 1 1 1 nc
+52 33 0.856329 1 1 1 nc
+31 62 0.856329 1 1 1 nc
+17 63 0.856329 1 1 1 nc
+21 47 0.856329 1 1 1 nc
+40 30 0.856329 1 1 1 nc
+20 26 0.856329 1 1 1 nc
+52 64 0.856329 1 1 1 nc
+49 49 0.856329 1 1 1 nc
+37 52 0.856329 1 1 1 nc
+grestore
+grestore
+showpage
Index: lemon/christofides_tsp.h
===================================================================
--- lemon/christofides_tsp.h	(revision 1205)
+++ lemon/christofides_tsp.h	(revision 1205)
@@ -0,0 +1,254 @@
+/* -*- 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/kruskal.h>
+#include <lemon/matching.h>
+#include <lemon/euler.h>
+
+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
+  /// metric cost function.
+  /// It has a guaranteed approximation factor of 3/2 (i.e. it finds a tour
+  /// whose total cost is at most 3/2 of the optimum), but it usually
+  /// provides better solutions in practice.
+  /// 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 a signed number type.
+  template <typename CM>
+  class ChristofidesTsp
+  {
+    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;
+      std::vector<Node> _path;
+      Cost _sum;
+
+    public:
+
+      /// \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();
+
+        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])];
+          }
+        }
+        
+        // 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))]) );
+          }
+        }
+        
+        // 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 = _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;
+      }
+
+      /// @}
+      
+      /// \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 a vector
+      /// 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
+      /// an STL container through the given output iterator. The
+      /// <tt>value_type</tt> of the container must be <tt>FullGraph::Node</tt>.
+      /// For example,
+      /// \code
+      /// std::vector<FullGraph::Node> nodes(countNodes(graph));
+      /// tsp.tourNodes(nodes.begin());
+      /// \endcode
+      /// or
+      /// \code
+      /// std::list<FullGraph::Node> nodes;
+      /// tsp.tourNodes(std::back_inserter(nodes));
+      /// \endcode
+      ///
+      /// \pre run() must be called before using this function.
+      template <typename Iterator>
+      void tourNodes(Iterator out) const {
+        std::copy(_path.begin(), _path.end(), out);
+      }
+      
+      /// \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
+
+#endif
Index: lemon/greedy_tsp.h
===================================================================
--- lemon/greedy_tsp.h	(revision 1205)
+++ lemon/greedy_tsp.h	(revision 1205)
@@ -0,0 +1,251 @@
+/* -*- 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
+
+/// \ingroup tsp
+/// \file
+/// \brief Greedy algorithm for symmetric TSP
+
+#include <vector>
+#include <algorithm>
+#include <lemon/full_graph.h>
+#include <lemon/unionfind.h>
+
+namespace lemon {
+
+  /// \ingroup tsp
+  ///
+  /// \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>) time.
+  /// It quickly finds a relatively short tour for most TSP instances,
+  /// but it could also yield a really bad (or even the worst) solution
+  /// in special cases.
+  ///
+  /// \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:
+        EdgeComp(const CostMap &cost) : _cost(cost) {}
+
+        bool operator()(const Edge &a, const Edge &b) const {
+          return _cost[a] < _cost[b];
+        }
+      };
+
+    public:
+
+      /// \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() {
+        _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 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)
+          union_find.insert(n);
+
+        FullGraph::NodeMap<int> degree(_gr, 0);
+
+        int nodesNum = 0, i = 0;
+        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;
+            }
+          }
+        }
+
+        for (int i=0, n=-1; i<_gr.nodeNum()*2; ++i) {
+          if (plist[i] == -1) {
+            if (n==-1) {
+              n = i;
+            } else {
+              plist[n] = i/2;
+              plist[i] = n/2;
+              break;
+            }
+          }
+        }
+
+        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 = next;
+            next = plist[2*next+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;
+      }
+
+      /// @}
+
+      /// \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 a vector
+      /// 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
+      /// an STL container through the given output iterator. The
+      /// <tt>value_type</tt> of the container must be <tt>FullGraph::Node</tt>.
+      /// For example,
+      /// \code
+      /// std::vector<FullGraph::Node> nodes(countNodes(graph));
+      /// tsp.tourNodes(nodes.begin());
+      /// \endcode
+      /// or
+      /// \code
+      /// std::list<FullGraph::Node> nodes;
+      /// tsp.tourNodes(std::back_inserter(nodes));
+      /// \endcode
+      ///
+      /// \pre run() must be called before using this function.
+      template <typename Iterator>
+      void tourNodes(Iterator out) const {
+        std::copy(_path.begin(), _path.end(), out);
+      }
+
+      /// \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
+
+#endif
Index: lemon/insertion_tsp.h
===================================================================
--- lemon/insertion_tsp.h	(revision 1205)
+++ lemon/insertion_tsp.h	(revision 1205)
@@ -0,0 +1,533 @@
+/* -*- 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 <functional>
+#include <lemon/full_graph.h>
+#include <lemon/maps.h>
+#include <lemon/random.h>
+
+namespace lemon {
+
+  /// \ingroup tsp
+  ///
+  /// \brief Insertion algorithm for symmetric TSP.
+  ///
+  /// InsertionTsp implements the insertion heuristic for solving
+  /// symmetric \ref tsp "TSP".
+  ///
+  /// This is a fast and effective tour construction method 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 method is among the fastest TSP algorithms, and it typically
+  /// provides quite good solutions (usually much better than
+  /// \ref NearestNeighborTsp and \ref GreedyTsp).
+  ///
+  /// InsertionTsp implements four different node selection rules,
+  /// from which the most effective one (\e farthest \e node \e selection)
+  /// is used by default.
+  /// With this choice, the algorithm runs in O(n<sup>2</sup>) time.
+  /// For more information, see \ref SelectionRule.
+  ///
+  /// \tparam CM Type of the cost map.
+  template <typename CM>
+  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);
+
+      const FullGraph &_gr;
+      const CostMap &_cost;
+      std::vector<Node> _notused;
+      std::vector<Node> _tour;
+      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.
+      /// The FARTHEST method is one of the fastest selection rules, and
+      /// it is typically the most effective, thus it is the default
+      /// option. The RANDOM rule usually gives slightly worse results,
+      /// but it is more 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>2</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>2</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, but in most cases, it is almost as fast as
+        /// with other rules.
+        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) {
+        _tour.clear();
+
+        if (_gr.nodeNum() == 0) return _sum = 0;
+        else if (_gr.nodeNum() == 1) {
+          _tour.push_back(_gr(0));
+          return _sum = 0;
+        }
+
+        switch (rule) {
+          case NEAREST:
+            init(true);
+            start<ComparingSelection<std::less<Cost> >,
+                  DefaultInsertion>();
+            break;
+          case FARTHEST:
+            init(false);
+            start<ComparingSelection<std::greater<Cost> >,
+                  DefaultInsertion>();
+            break;
+          case CHEAPEST:
+            init(true);
+            start<CheapestSelection, CheapestInsertion>();
+            break;
+          case RANDOM:
+            init(true);
+            start<RandomSelection, DefaultInsertion>();
+            break;
+        }
+        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 a vector
+      /// 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 _tour;
+      }
+
+      /// \brief Gives back the node sequence of the found tour.
+      ///
+      /// This function copies the node sequence of the found tour into
+      /// an STL container through the given output iterator. The
+      /// <tt>value_type</tt> of the container must be <tt>FullGraph::Node</tt>.
+      /// For example,
+      /// \code
+      /// std::vector<FullGraph::Node> nodes(countNodes(graph));
+      /// tsp.tourNodes(nodes.begin());
+      /// \endcode
+      /// or
+      /// \code
+      /// std::list<FullGraph::Node> nodes;
+      /// tsp.tourNodes(std::back_inserter(nodes));
+      /// \endcode
+      ///
+      /// \pre run() must be called before using this function.
+      template <typename Iterator>
+      void tourNodes(Iterator out) const {
+        std::copy(_tour.begin(), _tour.end(), out);
+      }
+
+      /// \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(_tour.size()) - 1; ++i) {
+          path.addBack(_gr.arc(_tour[i], _tour[i+1]));
+        }
+        if (int(_tour.size()) >= 2) {
+          path.addBack(_gr.arc(_tour.back(), _tour.front()));
+        }
+      }
+
+      /// @}
+
+    private:
+
+      // Initializes the algorithm
+      void init(bool min) {
+        Edge min_edge = min ? mapMin(_gr, _cost) : mapMax(_gr, _cost);
+
+        _tour.clear();
+        _tour.push_back(_gr.u(min_edge));
+        _tour.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, _tour, _notused);
+        InsertionFunctor insertNode(_gr, _cost, _tour, _sum);
+
+        for (int i=0; i<_gr.nodeNum()-2; ++i) {
+          insertNode.insert(selectNode.select());
+        }
+
+        _sum = _cost[_gr.edge(_tour.back(), _tour.front())];
+        for (int i = 0; i < int(_tour.size())-1; ++i) {
+          _sum += _cost[_gr.edge(_tour[i], _tour[i+1])];
+        }
+      }
+
+
+      // Implementation of the nearest and farthest selection rule
+      template <typename Comparator>
+      class ComparingSelection {
+        public:
+          ComparingSelection(const FullGraph &gr, const CostMap &cost,
+                  std::vector<Node> &tour, std::vector<Node> &notused)
+            : _gr(gr), _cost(cost), _tour(tour), _notused(notused),
+              _dist(gr, 0), _compare()
+          {
+            // Compute initial distances for the unused nodes
+            for (unsigned int i=0; i<_notused.size(); ++i) {
+              Node u = _notused[i];
+              Cost min_dist = _cost[_gr.edge(u, _tour[0])];
+              for (unsigned int j=1; j<_tour.size(); ++j) {
+                Cost curr = _cost[_gr.edge(u, _tour[j])];
+                if (curr < min_dist) {
+                  min_dist = curr;
+                }
+              }
+              _dist[u] = min_dist;
+            }
+          }
+
+          Node select() {
+
+            // Select an used node with minimum distance
+            Cost ins_dist = 0;
+            int ins_node = -1;
+            for (unsigned int i=0; i<_notused.size(); ++i) {
+              Cost curr = _dist[_notused[i]];
+              if (_compare(curr, ins_dist) || ins_node == -1) {
+                ins_dist = curr;
+                ins_node = i;
+              }
+            }
+
+            // Remove the selected node from the unused vector
+            Node sn = _notused[ins_node];
+            _notused[ins_node] = _notused.back();
+            _notused.pop_back();
+
+            // Update the distances of the remaining nodes
+            for (unsigned int i=0; i<_notused.size(); ++i) {
+              Node u = _notused[i];
+              Cost nc = _cost[_gr.edge(sn, u)];
+              if (nc < _dist[u]) {
+                _dist[u] = nc;
+              }
+            }
+
+            return sn;
+          }
+
+        private:
+          const FullGraph &_gr;
+          const CostMap &_cost;
+          std::vector<Node> &_tour;
+          std::vector<Node> &_notused;
+          FullGraph::NodeMap<Cost> _dist;
+          Comparator _compare;
+      };
+
+      // Implementation of the cheapest selection rule
+      class CheapestSelection {
+        private:
+          Cost costDiff(Node u, Node v, Node w) const {
+            return
+              _cost[_gr.edge(u, w)] +
+              _cost[_gr.edge(v, w)] -
+              _cost[_gr.edge(u, v)];
+          }
+
+        public:
+          CheapestSelection(const FullGraph &gr, const CostMap &cost,
+                            std::vector<Node> &tour, std::vector<Node> &notused)
+            : _gr(gr), _cost(cost), _tour(tour), _notused(notused),
+              _ins_cost(gr, 0), _ins_pos(gr, -1)
+          {
+            // Compute insertion cost and position for the unused nodes
+            for (unsigned int i=0; i<_notused.size(); ++i) {
+              Node u = _notused[i];
+              Cost min_cost = costDiff(_tour.back(), _tour.front(), u);
+              int min_pos = 0;              
+              for (unsigned int j=1; j<_tour.size(); ++j) {
+                Cost curr_cost = costDiff(_tour[j-1], _tour[j], u);
+                if (curr_cost < min_cost) {
+                  min_cost = curr_cost;
+                  min_pos = j;
+                }
+              }
+              _ins_cost[u] = min_cost;
+              _ins_pos[u] = min_pos;
+            }
+          }
+
+          Cost select() {
+
+            // Select an used node with minimum insertion cost
+            Cost min_cost = 0;
+            int min_node = -1;
+            for (unsigned int i=0; i<_notused.size(); ++i) {
+              Cost curr_cost = _ins_cost[_notused[i]];
+              if (curr_cost < min_cost || min_node == -1) {
+                min_cost = curr_cost;
+                min_node = i;
+              }
+            }
+
+            // Remove the selected node from the unused vector
+            Node sn = _notused[min_node];
+            _notused[min_node] = _notused.back();
+            _notused.pop_back();
+            
+            // Insert the selected node into the tour
+            const int ipos = _ins_pos[sn];
+            _tour.insert(_tour.begin() + ipos, sn);
+
+            // Update the insertion cost and position of the remaining nodes
+            for (unsigned int i=0; i<_notused.size(); ++i) {
+              Node u = _notused[i];
+              Cost curr_cost = _ins_cost[u];
+              int curr_pos = _ins_pos[u];
+
+              int ipos_prev = ipos == 0 ? _tour.size()-1 : ipos-1;
+              int ipos_next = ipos == int(_tour.size())-1 ? 0 : ipos+1;
+              Cost nc1 = costDiff(_tour[ipos_prev], _tour[ipos], u);
+              Cost nc2 = costDiff(_tour[ipos], _tour[ipos_next], u);
+              
+              if (nc1 <= curr_cost || nc2 <= curr_cost) {
+                // A new position is better than the old one
+                if (nc1 <= nc2) {
+                  curr_cost = nc1;
+                  curr_pos = ipos;
+                } else {
+                  curr_cost = nc2;
+                  curr_pos = ipos_next;
+                }
+              }
+              else {
+                if (curr_pos == ipos) {
+                  // The minimum should be found again
+                  curr_cost = costDiff(_tour.back(), _tour.front(), u);
+                  curr_pos = 0;              
+                  for (unsigned int j=1; j<_tour.size(); ++j) {
+                    Cost tmp_cost = costDiff(_tour[j-1], _tour[j], u);
+                    if (tmp_cost < curr_cost) {
+                      curr_cost = tmp_cost;
+                      curr_pos = j;
+                    }
+                  }
+                }
+                else if (curr_pos > ipos) {
+                  ++curr_pos;
+                }
+              }
+              
+              _ins_cost[u] = curr_cost;
+              _ins_pos[u] = curr_pos;
+            }
+
+            return min_cost;
+          }
+
+        private:
+          const FullGraph &_gr;
+          const CostMap &_cost;
+          std::vector<Node> &_tour;
+          std::vector<Node> &_notused;
+          FullGraph::NodeMap<Cost> _ins_cost;
+          FullGraph::NodeMap<int> _ins_pos;
+      };
+
+      // Implementation of the random selection rule
+      class RandomSelection {
+        public:
+          RandomSelection(const FullGraph &, const CostMap &,
+                          std::vector<Node> &, std::vector<Node> &notused)
+            : _notused(notused) {}
+
+          Node select() const {
+            const int index = rnd[_notused.size()];
+            Node n = _notused[index];
+            _notused[index] = _notused.back();
+            _notused.pop_back();
+            return n;
+          }
+
+        private:
+          std::vector<Node> &_notused;
+      };
+
+
+      // Implementation of the default insertion method
+      class DefaultInsertion {
+        private:
+          Cost costDiff(Node u, Node v, Node w) const {
+            return
+              _cost[_gr.edge(u, w)] +
+              _cost[_gr.edge(v, w)] -
+              _cost[_gr.edge(u, v)];
+          }
+
+        public:
+          DefaultInsertion(const FullGraph &gr, const CostMap &cost,
+                           std::vector<Node> &tour, Cost &total_cost) :
+            _gr(gr), _cost(cost), _tour(tour), _total(total_cost) {}
+
+          void insert(Node n) const {
+            int min = 0;
+            Cost min_val =
+              costDiff(_tour.front(), _tour.back(), n);
+
+            for (unsigned int i=1; i<_tour.size(); ++i) {
+              Cost tmp = costDiff(_tour[i-1], _tour[i], n);
+              if (tmp < min_val) {
+                min = i;
+                min_val = tmp;
+              }
+            }
+
+            _tour.insert(_tour.begin()+min, n);
+            _total += min_val;
+          }
+
+        private:
+          const FullGraph &_gr;
+          const CostMap &_cost;
+          std::vector<Node> &_tour;
+          Cost &_total;
+      };
+
+      // Implementation of a special insertion method for the cheapest
+      // selection rule
+      class CheapestInsertion {
+        TEMPLATE_GRAPH_TYPEDEFS(FullGraph);
+        public:
+          CheapestInsertion(const FullGraph &, const CostMap &,
+                            std::vector<Node> &, Cost &total_cost) :
+            _total(total_cost) {}
+
+          void insert(Cost diff) const {
+            _total += diff;
+          }
+
+        private:
+          Cost &_total;
+      };
+
+  };
+
+}; // namespace lemon
+
+#endif
Index: lemon/nearest_neighbor_tsp.h
===================================================================
--- lemon/nearest_neighbor_tsp.h	(revision 1205)
+++ lemon/nearest_neighbor_tsp.h	(revision 1205)
@@ -0,0 +1,238 @@
+/* -*- 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 <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
+  /// 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 a relatively short tour for most TSP instances,
+  /// but it could also yield a really bad (or even the worst) solution
+  /// in special cases.
+  ///
+  /// \tparam CM Type of the cost map.
+  template <typename CM>
+  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::vector<Node> _path;
+
+    public:
+
+      /// \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;
+        }
+
+        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_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_dq.size()) != _gr.nodeNum()) {
+          if (min_edge1 == INVALID) {
+            for (IncEdgeIt e(_gr, n1); e != INVALID; ++e) {
+              if (!used[_gr.runningNode(e)] &&
+                  (_cost[e] < _cost[min_edge1] || min_edge1 == INVALID)) {
+                min_edge1 = e;
+              }
+            }
+          }
+
+          if (min_edge2 == INVALID) {
+            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.oppositeNode(n1, min_edge1);
+            path_dq.push_front(n1);
+
+            used[n1] = true;
+            min_edge1 = INVALID;
+
+            if (_gr.u(min_edge2) == n1 || _gr.v(min_edge2) == n1)
+              min_edge2 = INVALID;
+          } else {
+            n2 = _gr.oppositeNode(n2, min_edge2);
+            path_dq.push_back(n2);
+
+            used[n2] = true;
+            min_edge2 = INVALID;
+
+            if (_gr.u(min_edge1) == n2 || _gr.v(min_edge1) == n2)
+              min_edge1 = INVALID;
+          }
+        }
+
+        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;
+      }
+
+      /// @}
+
+      /// \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 a vector
+      /// 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
+      /// an STL container through the given output iterator. The
+      /// <tt>value_type</tt> of the container must be <tt>FullGraph::Node</tt>.
+      /// For example,
+      /// \code
+      /// std::vector<FullGraph::Node> nodes(countNodes(graph));
+      /// tsp.tourNodes(nodes.begin());
+      /// \endcode
+      /// or
+      /// \code
+      /// std::list<FullGraph::Node> nodes;
+      /// tsp.tourNodes(std::back_inserter(nodes));
+      /// \endcode
+      ///
+      /// \pre run() must be called before using this function.
+      template <typename Iterator>
+      void tourNodes(Iterator out) const {
+        std::copy(_path.begin(), _path.end(), out);
+      }
+
+      /// \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
+
+#endif
Index: lemon/opt2_tsp.h
===================================================================
--- lemon/opt2_tsp.h	(revision 1205)
+++ lemon/opt2_tsp.h	(revision 1205)
@@ -0,0 +1,367 @@
+/* -*- 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>
+
+namespace lemon {
+
+  /// \ingroup tsp
+  ///
+  /// \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 rather slow but effective method.
+  /// Its typical usage is the improvement of the result of a fast tour
+  /// construction heuristic (e.g. the InsertionTsp algorithm).
+  ///
+  /// \tparam CM Type of the cost map.
+  template <typename CM>
+  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:
+
+      /// \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 starting 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 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.
+      Cost run(const std::vector<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 std::vector<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 a vector
+      /// 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
+      /// an STL container through the given output iterator. The
+      /// <tt>value_type</tt> of the container must be <tt>FullGraph::Node</tt>.
+      /// For example,
+      /// \code
+      /// std::vector<FullGraph::Node> nodes(countNodes(graph));
+      /// tsp.tourNodes(nodes.begin());
+      /// \endcode
+      /// or
+      /// \code
+      /// std::list<FullGraph::Node> nodes;
+      /// tsp.tourNodes(std::back_inserter(nodes));
+      /// \endcode
+      ///
+      /// \pre run() must be called before using this function.
+      template <typename Iterator>
+      void tourNodes(Iterator out) const {
+        std::copy(_path.begin(), _path.end(), out);
+      }
+
+      /// \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:
+
+      // Iterator class for the linked list storage of the tour
+      class PathListIt {
+        public:
+          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 {
+            int x = (*plist)[2*act];
+            return x == last ? (*plist)[2*act+1] : x;
+          }
+
+          int prev() const {
+            return last;
+          }
+
+          PathListIt& operator++() {
+            int tmp = act;
+            act = next();
+            last = tmp;
+            return *this;
+          }
+
+          operator int() const {
+            return act;
+          }
+
+        private:
+          const std::vector<int> *plist;
+          int act;
+          int last;
+      };
+
+      // 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;
+     }
+
+      // 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;
+      }
+
+  };
+
+}; // namespace lemon
+
+#endif
Index: test/CMakeLists.txt
===================================================================
--- test/CMakeLists.txt	(revision 1198)
+++ test/CMakeLists.txt	(revision 1206)
@@ -53,4 +53,5 @@
   suurballe_test
   time_measure_test
+  tsp_test
   unionfind_test
 )
Index: test/tsp_test.cc
===================================================================
--- test/tsp_test.cc	(revision 1205)
+++ test/tsp_test.cc	(revision 1205)
@@ -0,0 +1,283 @@
+/* -*- 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.
+ *
+ */
+
+#include <iostream>
+
+#include <lemon/full_graph.h>
+#include <lemon/math.h>
+#include <lemon/maps.h>
+#include <lemon/random.h>
+#include <lemon/dim2.h>
+
+#include <lemon/nearest_neighbor_tsp.h>
+#include <lemon/greedy_tsp.h>
+#include <lemon/insertion_tsp.h>
+#include <lemon/christofides_tsp.h>
+#include <lemon/opt2_tsp.h>
+
+#include "test_tools.h"
+
+using namespace lemon;
+
+// // Tests checkMetricCost() function
+// void metricCostTest() {
+//   GRAPH_TYPEDEFS(FullGraph);
+//   FullGraph g(10);
+//   check(checkMetricCost(g, constMap<Edge>(0)), "Wrong checkMetricCost()");
+//   check(checkMetricCost(g, constMap<Edge>(1)), "Wrong checkMetricCost()");
+//   check(!checkMetricCost(g, constMap<Edge>(-1)), "Wrong checkMetricCost()");
+//   
+//   FullGraph::EdgeMap<float> cost(g);
+//   for (NodeIt u(g); u != INVALID; ++u) {
+//     for (NodeIt v(g); v != INVALID; ++v) {
+//       if (u == v) continue;
+//       float x1 = g.id(u), x2 = g.id(v);
+//       float y1 = x1 * x1, y2 = x2 * x2;
+//       cost[g.edge(u, v)] = std::sqrt((x2-x1)*(x2-x1) + (y2-y1)*(y2-y1));
+//     }
+//   }
+//   check(checkMetricCost(g, cost), "Wrong checkMetricCost()");
+//   float eps = Tolerance<float>::defaultEpsilon();
+//   cost[g.edge(g(0), g(9))] =
+//     cost[g.edge(g(0), g(8))] + cost[g.edge(g(8), g(9))] + eps * 2;
+//   check(!checkMetricCost(g, cost), "Wrong checkMetricCost()");
+//   check(checkMetricCost(g, cost, Tolerance<float>(eps * 4)),
+//     "Wrong checkMetricCost()");
+// }
+
+// Checks tour validity
+template <typename Container>
+bool checkTour(const FullGraph &gr, const Container &p) {
+  FullGraph::NodeMap<bool> used(gr, false);
+  
+  int node_cnt = 0;
+  for (typename Container::const_iterator it = p.begin(); it != p.end(); ++it) {
+    FullGraph::Node node = *it;
+    if (used[node]) return false;
+    used[node] = true;
+    ++node_cnt;
+  }
+  
+  return (node_cnt == gr.nodeNum());
+}
+
+// Checks tour validity
+bool checkTourPath(const FullGraph &gr, const Path<FullGraph> &p) {
+  FullGraph::NodeMap<bool> used(gr, false);
+  
+  if (!checkPath(gr, p)) return false;
+  if (gr.nodeNum() <= 1 && p.length() != 0) return false;
+  if (gr.nodeNum() > 1 && p.length() != gr.nodeNum()) return false;
+
+  for (int i = 0; i < p.length(); ++i) {
+    if (used[gr.target(p.nth(i))]) return false;
+    used[gr.target(p.nth(i))] = true;
+  }
+  return true;
+}
+
+// Checks tour cost
+template <typename CostMap>
+bool checkCost(const FullGraph &gr, const std::vector<FullGraph::Node> &p,
+               const CostMap &cost, typename CostMap::Value total)
+{
+  typedef typename CostMap::Value Cost;
+
+  Cost s = 0;
+  for (int i = 0; i < int(p.size()) - 1; ++i)
+    s += cost[gr.edge(p[i], p[i+1])];
+  if (int(p.size()) >= 2)
+    s += cost[gr.edge(p.back(), p.front())];
+
+  return !Tolerance<Cost>().different(s, total);
+}
+
+// Checks tour cost
+template <typename CostMap>
+bool checkCost(const FullGraph &, const Path<FullGraph> &p,
+               const CostMap &cost, typename CostMap::Value total)
+{
+  typedef typename CostMap::Value Cost;
+
+  Cost s = 0;
+  for (int i = 0; i < p.length(); ++i)
+    s += cost[p.nth(i)];
+
+  return !Tolerance<Cost>().different(s, total);
+}
+
+// Tests a TSP algorithm on small graphs
+template <typename TSP>
+void tspTestSmall(const std::string &alg_name) {
+  GRAPH_TYPEDEFS(FullGraph);
+
+  for (int n = 0; n <= 5; ++n) {
+    FullGraph g(n);
+    unsigned nsize = n;
+    int esize = n <= 1 ? 0 : n;
+
+    TSP alg(g, constMap<Edge, int>(1));
+
+    check(alg.run() == esize, alg_name + ": Wrong total cost");
+    check(alg.tourCost() == esize, alg_name + ": Wrong total cost");
+
+    std::list<Node> list1(nsize), list2;
+    std::vector<Node> vec1(nsize), vec2;
+    alg.tourNodes(list1.begin());
+    alg.tourNodes(vec1.begin());
+    alg.tourNodes(std::front_inserter(list2));
+    alg.tourNodes(std::back_inserter(vec2));
+    check(checkTour(g, alg.tourNodes()), alg_name + ": Wrong node sequence");
+    check(checkTour(g, list1), alg_name + ": Wrong node sequence");
+    check(checkTour(g, vec1), alg_name + ": Wrong node sequence");
+    check(checkTour(g, list2), alg_name + ": Wrong node sequence");
+    check(checkTour(g, vec2), alg_name + ": Wrong node sequence");
+    check(checkCost(g, vec1, constMap<Edge, int>(1), esize),
+      alg_name + ": Wrong tour cost");
+
+    SimplePath<FullGraph> path;
+    alg.tour(path);
+    check(path.length() == esize, alg_name + ": Wrong tour");
+    check(checkTourPath(g, path), alg_name + ": Wrong tour");
+    check(checkCost(g, path, constMap<Edge, int>(1), esize),
+      alg_name + ": Wrong tour cost");
+  }
+}
+
+// Tests a TSP algorithm on random graphs
+template <typename TSP>
+void tspTestRandom(const std::string &alg_name) {
+  GRAPH_TYPEDEFS(FullGraph);
+
+  FullGraph g(20);
+  FullGraph::NodeMap<dim2::Point<double> > pos(g);
+  DoubleEdgeMap cost(g);
+
+  TSP alg(g, cost);
+  Opt2Tsp<DoubleEdgeMap > opt2(g, cost);
+
+  for (int i = 1; i <= 3; i++) {
+    for (NodeIt u(g); u != INVALID; ++u) {
+      pos[u] = dim2::Point<double>(rnd(), rnd());
+    }
+    for (NodeIt u(g); u != INVALID; ++u) {
+      for (NodeIt v(g); v != INVALID; ++v) {
+        if (u == v) continue;
+        cost[g.edge(u, v)] = (pos[u] - pos[v]).normSquare();
+      }
+    }
+    
+    check(alg.run() > 0, alg_name + ": Wrong total cost");
+
+    std::vector<Node> vec;
+    alg.tourNodes(std::back_inserter(vec));
+    check(checkTour(g, vec), alg_name + ": Wrong node sequence");
+    check(checkCost(g, vec, cost, alg.tourCost()),
+      alg_name + ": Wrong tour cost");
+
+    SimplePath<FullGraph> path;
+    alg.tour(path);
+    check(checkTourPath(g, path), alg_name + ": Wrong tour");
+    check(checkCost(g, path, cost, alg.tourCost()),
+      alg_name + ": Wrong tour cost");
+    
+    check(!Tolerance<double>().less(alg.tourCost(), opt2.run(alg.tourNodes())),
+      "2-opt improvement: Wrong total cost");
+    check(checkTour(g, opt2.tourNodes()),
+      "2-opt improvement: Wrong node sequence");
+    check(checkCost(g, opt2.tourNodes(), cost, opt2.tourCost()),
+      "2-opt improvement: Wrong tour cost");
+    
+    check(!Tolerance<double>().less(alg.tourCost(), opt2.run(path)),
+      "2-opt improvement: Wrong total cost");
+    check(checkTour(g, opt2.tourNodes()),
+      "2-opt improvement: Wrong node sequence");
+    check(checkCost(g, opt2.tourNodes(), cost, opt2.tourCost()),
+      "2-opt improvement: Wrong tour cost");
+  }
+}
+
+// Algorithm class for Nearest Insertion 
+template <typename CM>
+class NearestInsertionTsp : public InsertionTsp<CM> {
+public:
+  NearestInsertionTsp(const FullGraph &gr, const CM &cost)
+    : InsertionTsp<CM>(gr, cost) {}
+  typename CM::Value run() {
+    return InsertionTsp<CM>::run(InsertionTsp<CM>::NEAREST);
+  }
+};
+
+// Algorithm class for Farthest Insertion 
+template <typename CM>
+class FarthestInsertionTsp : public InsertionTsp<CM> {
+public:
+  FarthestInsertionTsp(const FullGraph &gr, const CM &cost)
+    : InsertionTsp<CM>(gr, cost) {}
+  typename CM::Value run() {
+    return InsertionTsp<CM>::run(InsertionTsp<CM>::FARTHEST);
+  }
+};
+
+// Algorithm class for Cheapest Insertion 
+template <typename CM>
+class CheapestInsertionTsp : public InsertionTsp<CM> {
+public:
+  CheapestInsertionTsp(const FullGraph &gr, const CM &cost)
+    : InsertionTsp<CM>(gr, cost) {}
+  typename CM::Value run() {
+    return InsertionTsp<CM>::run(InsertionTsp<CM>::CHEAPEST);
+  }
+};
+
+// Algorithm class for Random Insertion 
+template <typename CM>
+class RandomInsertionTsp : public InsertionTsp<CM> {
+public:
+  RandomInsertionTsp(const FullGraph &gr, const CM &cost)
+    : InsertionTsp<CM>(gr, cost) {}
+  typename CM::Value run() {
+    return InsertionTsp<CM>::run(InsertionTsp<CM>::RANDOM);
+  }
+};
+
+int main() {
+  GRAPH_TYPEDEFS(FullGraph);
+
+  // metricCostTest();
+
+  tspTestSmall<NearestNeighborTsp<ConstMap<Edge, int> > >("Nearest Neighbor");
+  tspTestSmall<GreedyTsp<ConstMap<Edge, int> > >("Greedy");
+  tspTestSmall<NearestInsertionTsp<ConstMap<Edge, int> > >("Nearest Insertion");
+  tspTestSmall<FarthestInsertionTsp<ConstMap<Edge, int> > >("Farthest Insertion");
+  tspTestSmall<CheapestInsertionTsp<ConstMap<Edge, int> > >("Cheapest Insertion");
+  tspTestSmall<RandomInsertionTsp<ConstMap<Edge, int> > >("Random Insertion");
+  tspTestSmall<ChristofidesTsp<ConstMap<Edge, int> > >("Christofides");
+  tspTestSmall<Opt2Tsp<ConstMap<Edge, int> > >("2-opt");
+
+  tspTestRandom<NearestNeighborTsp<DoubleEdgeMap > >("Nearest Neighbor");
+  tspTestRandom<GreedyTsp<DoubleEdgeMap > >("Greedy");
+  tspTestRandom<NearestInsertionTsp<DoubleEdgeMap > >("Nearest Insertion");
+  tspTestRandom<FarthestInsertionTsp<DoubleEdgeMap > >("Farthest Insertion");
+  tspTestRandom<CheapestInsertionTsp<DoubleEdgeMap > >("Cheapest Insertion");
+  tspTestRandom<RandomInsertionTsp<DoubleEdgeMap > >("Random Insertion");
+  tspTestRandom<ChristofidesTsp<DoubleEdgeMap > >("Christofides");
+  tspTestRandom<Opt2Tsp<DoubleEdgeMap > >("2-opt");
+
+  return 0;
+}
