Merge #386
authorAlpar Juttner <alpar@cs.elte.hu>
Fri, 01 Mar 2013 17:59:08 +0100
changeset 1038a2d142bb5d3c
parent 1030 4936be66d2f5
parent 1037 d3dcc49e6403
child 1041 0b0327c9b3ef
Merge #386
doc/CMakeLists.txt
doc/groups.dox
test/CMakeLists.txt
     1.1 --- a/doc/CMakeLists.txt	Tue Feb 12 07:15:52 2013 +0100
     1.2 +++ b/doc/CMakeLists.txt	Fri Mar 01 17:59:08 2013 +0100
     1.3 @@ -46,6 +46,7 @@
     1.4      COMMAND ${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} -r18 -sOutputFile=gen-images/nodeshape_4.png ${CMAKE_CURRENT_SOURCE_DIR}/images/nodeshape_4.eps
     1.5      COMMAND ${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} -r18 -sOutputFile=gen-images/planar.png ${CMAKE_CURRENT_SOURCE_DIR}/images/planar.eps
     1.6      COMMAND ${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} -r18 -sOutputFile=gen-images/strongly_connected_components.png ${CMAKE_CURRENT_SOURCE_DIR}/images/strongly_connected_components.eps
     1.7 +    COMMAND ${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} -r18 -sOutputFile=gen-images/tsp.png ${CMAKE_CURRENT_SOURCE_DIR}/images/tsp.eps
     1.8      COMMAND ${CMAKE_COMMAND} -E remove_directory html
     1.9      COMMAND ${PYTHON_EXECUTABLE} ${PROJECT_SOURCE_DIR}/scripts/bib2dox.py ${CMAKE_CURRENT_SOURCE_DIR}/references.bib >references.dox
    1.10      COMMAND ${DOXYGEN_EXECUTABLE} Doxyfile
     2.1 --- a/doc/groups.dox	Tue Feb 12 07:15:52 2013 +0100
     2.2 +++ b/doc/groups.dox	Fri Mar 01 17:59:08 2013 +0100
     2.3 @@ -558,6 +558,42 @@
     2.4  \image html planar.png
     2.5  \image latex planar.eps "Plane graph" width=\textwidth
     2.6  */
     2.7 + 
     2.8 +/**
     2.9 +@defgroup tsp Traveling Salesman Problem
    2.10 +@ingroup algs
    2.11 +\brief Algorithms for the symmetric traveling salesman problem
    2.12 +
    2.13 +This group contains basic heuristic algorithms for the the symmetric
    2.14 +\e traveling \e salesman \e problem (TSP).
    2.15 +Given an \ref FullGraph "undirected full graph" with a cost map on its edges,
    2.16 +the problem is to find a shortest possible tour that visits each node exactly
    2.17 +once (i.e. the minimum cost Hamiltonian cycle).
    2.18 +
    2.19 +These TSP algorithms are intended to be used with a \e metric \e cost
    2.20 +\e function, i.e. the edge costs should satisfy the triangle inequality.
    2.21 +Otherwise the algorithms could yield worse results.
    2.22 +
    2.23 +LEMON provides five well-known heuristics for solving symmetric TSP:
    2.24 + - \ref NearestNeighborTsp Neareast neighbor algorithm
    2.25 + - \ref GreedyTsp Greedy algorithm
    2.26 + - \ref InsertionTsp Insertion heuristic (with four selection methods)
    2.27 + - \ref ChristofidesTsp Christofides algorithm
    2.28 + - \ref Opt2Tsp 2-opt algorithm
    2.29 +
    2.30 +\ref NearestNeighborTsp, \ref GreedyTsp, and \ref InsertionTsp are the fastest
    2.31 +solution methods. Furthermore, \ref InsertionTsp is usually quite effective.
    2.32 +
    2.33 +\ref ChristofidesTsp is somewhat slower, but it has the best guaranteed
    2.34 +approximation factor: 3/2.
    2.35 +
    2.36 +\ref Opt2Tsp usually provides the best results in practice, but
    2.37 +it is the slowest method. It can also be used to improve given tours,
    2.38 +for example, the results of other algorithms.
    2.39 +
    2.40 +\image html tsp.png
    2.41 +\image latex tsp.eps "Traveling salesman problem" width=\textwidth
    2.42 +*/
    2.43  
    2.44  /**
    2.45  @defgroup approx_algs Approximation Algorithms
     3.1 --- /dev/null	Thu Jan 01 00:00:00 1970 +0000
     3.2 +++ b/doc/images/tsp.eps	Fri Mar 01 17:59:08 2013 +0100
     3.3 @@ -0,0 +1,229 @@
     3.4 +%!PS-Adobe-2.0 EPSF-2.0
     3.5 +%%Creator: LEMON, graphToEps()
     3.6 +%%CreationDate: Tue Jun 15 00:58:57 2010
     3.7 +%%BoundingBox: 31 41 649 709
     3.8 +%%EndComments
     3.9 +/lb { setlinewidth setrgbcolor newpath moveto
    3.10 +      4 2 roll 1 index 1 index curveto stroke } bind def
    3.11 +/l { setlinewidth setrgbcolor newpath moveto lineto stroke } bind def
    3.12 +/c { newpath dup 3 index add 2 index moveto 0 360 arc closepath } bind def
    3.13 +/sq { newpath 2 index 1 index add 2 index 2 index add moveto
    3.14 +      2 index 1 index sub 2 index 2 index add lineto
    3.15 +      2 index 1 index sub 2 index 2 index sub lineto
    3.16 +      2 index 1 index add 2 index 2 index sub lineto
    3.17 +      closepath pop pop pop} bind def
    3.18 +/di { newpath 2 index 1 index add 2 index moveto
    3.19 +      2 index             2 index 2 index add lineto
    3.20 +      2 index 1 index sub 2 index             lineto
    3.21 +      2 index             2 index 2 index sub lineto
    3.22 +      closepath pop pop pop} bind def
    3.23 +/nc { 0 0 0 setrgbcolor 5 index 5 index 5 index c fill
    3.24 +     setrgbcolor 1.1 div c fill
    3.25 +   } bind def
    3.26 +/nsq { 0 0 0 setrgbcolor 5 index 5 index 5 index sq fill
    3.27 +     setrgbcolor 1.1 div sq fill
    3.28 +   } bind def
    3.29 +/ndi { 0 0 0 setrgbcolor 5 index 5 index 5 index di fill
    3.30 +     setrgbcolor 1.1 div di fill
    3.31 +   } bind def
    3.32 +/nfemale { 0 0 0 setrgbcolor 3 index 0.0909091 1.5 mul mul setlinewidth
    3.33 +  newpath 5 index 5 index moveto 5 index 5 index 5 index 3.01 mul sub
    3.34 +  lineto 5 index 4 index .7 mul sub 5 index 5 index 2.2 mul sub moveto
    3.35 +  5 index 4 index .7 mul add 5 index 5 index 2.2 mul sub lineto stroke
    3.36 +  5 index 5 index 5 index c fill
    3.37 +  setrgbcolor 1.1 div c fill
    3.38 +  } bind def
    3.39 +/nmale {
    3.40 +  0 0 0 setrgbcolor 3 index 0.0909091 1.5 mul mul setlinewidth
    3.41 +  newpath 5 index 5 index moveto
    3.42 +  5 index 4 index 1 mul 1.5 mul add
    3.43 +  5 index 5 index 3 sqrt 1.5 mul mul add
    3.44 +  1 index 1 index lineto
    3.45 +  1 index 1 index 7 index sub moveto
    3.46 +  1 index 1 index lineto
    3.47 +  exch 5 index 3 sqrt .5 mul mul sub exch 5 index .5 mul sub lineto
    3.48 +  stroke
    3.49 +  5 index 5 index 5 index c fill
    3.50 +  setrgbcolor 1.1 div c fill
    3.51 +  } bind def
    3.52 +/arrl 1 def
    3.53 +/arrw 0.3 def
    3.54 +/lrl { 2 index mul exch 2 index mul exch rlineto pop} bind def
    3.55 +/arr { setrgbcolor /y1 exch def /x1 exch def /dy exch def /dx exch def
    3.56 +       /w exch def /len exch def
    3.57 +       newpath x1 dy w 2 div mul add y1 dx w 2 div mul sub moveto
    3.58 +       len w sub arrl sub dx dy lrl
    3.59 +       arrw dy dx neg lrl
    3.60 +       dx arrl w add mul dy w 2 div arrw add mul sub
    3.61 +       dy arrl w add mul dx w 2 div arrw add mul add rlineto
    3.62 +       dx arrl w add mul neg dy w 2 div arrw add mul sub
    3.63 +       dy arrl w add mul neg dx w 2 div arrw add mul add rlineto
    3.64 +       arrw dy dx neg lrl
    3.65 +       len w sub arrl sub neg dx dy lrl
    3.66 +       closepath fill } bind def
    3.67 +/cshow { 2 index 2 index moveto dup stringwidth pop
    3.68 +         neg 2 div fosi .35 mul neg rmoveto show pop pop} def
    3.69 +
    3.70 +gsave
    3.71 +10 dup scale
    3.72 +%Arcs:
    3.73 +gsave
    3.74 +27 68 37 69 0 0 1 0.513798 l
    3.75 +37 69 27 68 0 0 1 0.513798 l
    3.76 +8 52 5 64 0 0 1 0.513798 l
    3.77 +5 64 8 52 0 0 1 0.513798 l
    3.78 +16 57 25 55 0 0 1 0.513798 l
    3.79 +25 55 16 57 0 0 1 0.513798 l
    3.80 +43 67 37 69 0 0 1 0.513798 l
    3.81 +37 69 43 67 0 0 1 0.513798 l
    3.82 +42 57 43 67 0 0 1 0.513798 l
    3.83 +43 67 42 57 0 0 1 0.513798 l
    3.84 +62 42 61 33 0 0 1 0.513798 l
    3.85 +61 33 62 42 0 0 1 0.513798 l
    3.86 +62 42 58 48 0 0 1 0.513798 l
    3.87 +58 48 62 42 0 0 1 0.513798 l
    3.88 +58 27 61 33 0 0 1 0.513798 l
    3.89 +61 33 58 27 0 0 1 0.513798 l
    3.90 +57 58 62 63 0 0 1 0.513798 l
    3.91 +62 63 57 58 0 0 1 0.513798 l
    3.92 +13 13 21 10 0 0 1 0.513798 l
    3.93 +21 10 13 13 0 0 1 0.513798 l
    3.94 +13 13 5 6 0 0 1 0.513798 l
    3.95 +5 6 13 13 0 0 1 0.513798 l
    3.96 +17 33 7 38 0 0 1 0.513798 l
    3.97 +7 38 17 33 0 0 1 0.513798 l
    3.98 +46 10 59 15 0 0 1 0.513798 l
    3.99 +59 15 46 10 0 0 1 0.513798 l
   3.100 +46 10 39 10 0 0 1 0.513798 l
   3.101 +39 10 46 10 0 0 1 0.513798 l
   3.102 +27 23 21 10 0 0 1 0.513798 l
   3.103 +21 10 27 23 0 0 1 0.513798 l
   3.104 +52 41 56 37 0 0 1 0.513798 l
   3.105 +56 37 52 41 0 0 1 0.513798 l
   3.106 +62 63 63 69 0 0 1 0.513798 l
   3.107 +63 69 62 63 0 0 1 0.513798 l
   3.108 +36 16 39 10 0 0 1 0.513798 l
   3.109 +39 10 36 16 0 0 1 0.513798 l
   3.110 +36 16 30 15 0 0 1 0.513798 l
   3.111 +30 15 36 16 0 0 1 0.513798 l
   3.112 +12 42 7 38 0 0 1 0.513798 l
   3.113 +7 38 12 42 0 0 1 0.513798 l
   3.114 +12 42 8 52 0 0 1 0.513798 l
   3.115 +8 52 12 42 0 0 1 0.513798 l
   3.116 +32 22 30 15 0 0 1 0.513798 l
   3.117 +30 15 32 22 0 0 1 0.513798 l
   3.118 +5 25 10 17 0 0 1 0.513798 l
   3.119 +10 17 5 25 0 0 1 0.513798 l
   3.120 +5 25 17 33 0 0 1 0.513798 l
   3.121 +17 33 5 25 0 0 1 0.513798 l
   3.122 +45 35 48 28 0 0 1 0.513798 l
   3.123 +48 28 45 35 0 0 1 0.513798 l
   3.124 +31 32 25 32 0 0 1 0.513798 l
   3.125 +25 32 31 32 0 0 1 0.513798 l
   3.126 +31 32 32 39 0 0 1 0.513798 l
   3.127 +32 39 31 32 0 0 1 0.513798 l
   3.128 +42 41 38 46 0 0 1 0.513798 l
   3.129 +38 46 42 41 0 0 1 0.513798 l
   3.130 +42 41 52 41 0 0 1 0.513798 l
   3.131 +52 41 42 41 0 0 1 0.513798 l
   3.132 +5 6 10 17 0 0 1 0.513798 l
   3.133 +10 17 5 6 0 0 1 0.513798 l
   3.134 +51 21 59 15 0 0 1 0.513798 l
   3.135 +59 15 51 21 0 0 1 0.513798 l
   3.136 +51 21 58 27 0 0 1 0.513798 l
   3.137 +58 27 51 21 0 0 1 0.513798 l
   3.138 +52 33 56 37 0 0 1 0.513798 l
   3.139 +56 37 52 33 0 0 1 0.513798 l
   3.140 +52 33 48 28 0 0 1 0.513798 l
   3.141 +48 28 52 33 0 0 1 0.513798 l
   3.142 +31 62 25 55 0 0 1 0.513798 l
   3.143 +25 55 31 62 0 0 1 0.513798 l
   3.144 +31 62 27 68 0 0 1 0.513798 l
   3.145 +27 68 31 62 0 0 1 0.513798 l
   3.146 +17 63 5 64 0 0 1 0.513798 l
   3.147 +5 64 17 63 0 0 1 0.513798 l
   3.148 +17 63 16 57 0 0 1 0.513798 l
   3.149 +16 57 17 63 0 0 1 0.513798 l
   3.150 +21 47 30 40 0 0 1 0.513798 l
   3.151 +30 40 21 47 0 0 1 0.513798 l
   3.152 +21 47 30 48 0 0 1 0.513798 l
   3.153 +30 48 21 47 0 0 1 0.513798 l
   3.154 +40 30 45 35 0 0 1 0.513798 l
   3.155 +45 35 40 30 0 0 1 0.513798 l
   3.156 +40 30 32 22 0 0 1 0.513798 l
   3.157 +32 22 40 30 0 0 1 0.513798 l
   3.158 +32 39 30 40 0 0 1 0.513798 l
   3.159 +30 40 32 39 0 0 1 0.513798 l
   3.160 +20 26 25 32 0 0 1 0.513798 l
   3.161 +25 32 20 26 0 0 1 0.513798 l
   3.162 +20 26 27 23 0 0 1 0.513798 l
   3.163 +27 23 20 26 0 0 1 0.513798 l
   3.164 +52 64 63 69 0 0 1 0.513798 l
   3.165 +63 69 52 64 0 0 1 0.513798 l
   3.166 +52 64 42 57 0 0 1 0.513798 l
   3.167 +42 57 52 64 0 0 1 0.513798 l
   3.168 +49 49 58 48 0 0 1 0.513798 l
   3.169 +58 48 49 49 0 0 1 0.513798 l
   3.170 +49 49 57 58 0 0 1 0.513798 l
   3.171 +57 58 49 49 0 0 1 0.513798 l
   3.172 +37 52 38 46 0 0 1 0.513798 l
   3.173 +38 46 37 52 0 0 1 0.513798 l
   3.174 +37 52 30 48 0 0 1 0.513798 l
   3.175 +30 48 37 52 0 0 1 0.513798 l
   3.176 +grestore
   3.177 +%Nodes:
   3.178 +gsave
   3.179 +30 40 0.856329 1 1 1 nc
   3.180 +56 37 0.856329 1 1 1 nc
   3.181 +48 28 0.856329 1 1 1 nc
   3.182 +25 55 0.856329 1 1 1 nc
   3.183 +25 32 0.856329 1 1 1 nc
   3.184 +32 39 0.856329 1 1 1 nc
   3.185 +39 10 0.856329 1 1 1 nc
   3.186 +30 15 0.856329 1 1 1 nc
   3.187 +5 64 0.856329 1 1 1 nc
   3.188 +21 10 0.856329 1 1 1 nc
   3.189 +10 17 0.856329 1 1 1 nc
   3.190 +5 6 0.856329 1 1 1 nc
   3.191 +59 15 0.856329 1 1 1 nc
   3.192 +45 35 0.856329 1 1 1 nc
   3.193 +32 22 0.856329 1 1 1 nc
   3.194 +63 69 0.856329 1 1 1 nc
   3.195 +62 63 0.856329 1 1 1 nc
   3.196 +61 33 0.856329 1 1 1 nc
   3.197 +46 10 0.856329 1 1 1 nc
   3.198 +38 46 0.856329 1 1 1 nc
   3.199 +37 69 0.856329 1 1 1 nc
   3.200 +58 27 0.856329 1 1 1 nc
   3.201 +58 48 0.856329 1 1 1 nc
   3.202 +43 67 0.856329 1 1 1 nc
   3.203 +30 48 0.856329 1 1 1 nc
   3.204 +27 68 0.856329 1 1 1 nc
   3.205 +7 38 0.856329 1 1 1 nc
   3.206 +8 52 0.856329 1 1 1 nc
   3.207 +16 57 0.856329 1 1 1 nc
   3.208 +42 57 0.856329 1 1 1 nc
   3.209 +62 42 0.856329 1 1 1 nc
   3.210 +57 58 0.856329 1 1 1 nc
   3.211 +13 13 0.856329 1 1 1 nc
   3.212 +17 33 0.856329 1 1 1 nc
   3.213 +27 23 0.856329 1 1 1 nc
   3.214 +52 41 0.856329 1 1 1 nc
   3.215 +36 16 0.856329 1 1 1 nc
   3.216 +12 42 0.856329 1 1 1 nc
   3.217 +5 25 0.856329 1 1 1 nc
   3.218 +31 32 0.856329 1 1 1 nc
   3.219 +42 41 0.856329 1 1 1 nc
   3.220 +51 21 0.856329 1 1 1 nc
   3.221 +52 33 0.856329 1 1 1 nc
   3.222 +31 62 0.856329 1 1 1 nc
   3.223 +17 63 0.856329 1 1 1 nc
   3.224 +21 47 0.856329 1 1 1 nc
   3.225 +40 30 0.856329 1 1 1 nc
   3.226 +20 26 0.856329 1 1 1 nc
   3.227 +52 64 0.856329 1 1 1 nc
   3.228 +49 49 0.856329 1 1 1 nc
   3.229 +37 52 0.856329 1 1 1 nc
   3.230 +grestore
   3.231 +grestore
   3.232 +showpage
     4.1 --- /dev/null	Thu Jan 01 00:00:00 1970 +0000
     4.2 +++ b/lemon/christofides_tsp.h	Fri Mar 01 17:59:08 2013 +0100
     4.3 @@ -0,0 +1,254 @@
     4.4 +/* -*- mode: C++; indent-tabs-mode: nil; -*-
     4.5 + *
     4.6 + * This file is a part of LEMON, a generic C++ optimization library.
     4.7 + *
     4.8 + * Copyright (C) 2003-2010
     4.9 + * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    4.10 + * (Egervary Research Group on Combinatorial Optimization, EGRES).
    4.11 + *
    4.12 + * Permission to use, modify and distribute this software is granted
    4.13 + * provided that this copyright notice appears in all copies. For
    4.14 + * precise terms see the accompanying LICENSE file.
    4.15 + *
    4.16 + * This software is provided "AS IS" with no warranty of any kind,
    4.17 + * express or implied, and with no claim as to its suitability for any
    4.18 + * purpose.
    4.19 + *
    4.20 + */
    4.21 +
    4.22 +#ifndef LEMON_CHRISTOFIDES_TSP_H
    4.23 +#define LEMON_CHRISTOFIDES_TSP_H
    4.24 +
    4.25 +/// \ingroup tsp
    4.26 +/// \file
    4.27 +/// \brief Christofides algorithm for symmetric TSP
    4.28 +
    4.29 +#include <lemon/full_graph.h>
    4.30 +#include <lemon/smart_graph.h>
    4.31 +#include <lemon/kruskal.h>
    4.32 +#include <lemon/matching.h>
    4.33 +#include <lemon/euler.h>
    4.34 +
    4.35 +namespace lemon {
    4.36 +  
    4.37 +  /// \ingroup tsp
    4.38 +  ///
    4.39 +  /// \brief Christofides algorithm for symmetric TSP.
    4.40 +  ///
    4.41 +  /// ChristofidesTsp implements Christofides' heuristic for solving
    4.42 +  /// symmetric \ref tsp "TSP".
    4.43 +  ///
    4.44 +  /// This a well-known approximation method for the TSP problem with
    4.45 +  /// metric cost function.
    4.46 +  /// It has a guaranteed approximation factor of 3/2 (i.e. it finds a tour
    4.47 +  /// whose total cost is at most 3/2 of the optimum), but it usually
    4.48 +  /// provides better solutions in practice.
    4.49 +  /// This implementation runs in O(n<sup>3</sup>log(n)) time.
    4.50 +  ///
    4.51 +  /// The algorithm starts with a \ref spantree "minimum cost spanning tree" and
    4.52 +  /// finds a \ref MaxWeightedPerfectMatching "minimum cost perfect matching"
    4.53 +  /// in the subgraph induced by the nodes that have odd degree in the
    4.54 +  /// spanning tree.
    4.55 +  /// Finally, it constructs the tour from the \ref EulerIt "Euler traversal"
    4.56 +  /// of the union of the spanning tree and the matching.
    4.57 +  /// During this last step, the algorithm simply skips the visited nodes
    4.58 +  /// (i.e. creates shortcuts) assuming that the triangle inequality holds
    4.59 +  /// for the cost function.
    4.60 +  ///
    4.61 +  /// \tparam CM Type of the cost map.
    4.62 +  ///
    4.63 +  /// \warning CM::Value must be a signed number type.
    4.64 +  template <typename CM>
    4.65 +  class ChristofidesTsp
    4.66 +  {
    4.67 +    public:
    4.68 +
    4.69 +      /// Type of the cost map
    4.70 +      typedef CM CostMap;
    4.71 +      /// Type of the edge costs
    4.72 +      typedef typename CM::Value Cost;
    4.73 +
    4.74 +    private:
    4.75 +
    4.76 +      GRAPH_TYPEDEFS(FullGraph);
    4.77 +
    4.78 +      const FullGraph &_gr;
    4.79 +      const CostMap &_cost;
    4.80 +      std::vector<Node> _path;
    4.81 +      Cost _sum;
    4.82 +
    4.83 +    public:
    4.84 +
    4.85 +      /// \brief Constructor
    4.86 +      ///
    4.87 +      /// Constructor.
    4.88 +      /// \param gr The \ref FullGraph "full graph" the algorithm runs on.
    4.89 +      /// \param cost The cost map.
    4.90 +      ChristofidesTsp(const FullGraph &gr, const CostMap &cost)
    4.91 +        : _gr(gr), _cost(cost) {}
    4.92 +
    4.93 +      /// \name Execution Control
    4.94 +      /// @{
    4.95 +
    4.96 +      /// \brief Runs the algorithm.
    4.97 +      ///
    4.98 +      /// This function runs the algorithm.
    4.99 +      ///
   4.100 +      /// \return The total cost of the found tour.
   4.101 +      Cost run() {
   4.102 +        _path.clear();
   4.103 +
   4.104 +        if (_gr.nodeNum() == 0) return _sum = 0;
   4.105 +        else if (_gr.nodeNum() == 1) {
   4.106 +          _path.push_back(_gr(0));
   4.107 +          return _sum = 0;
   4.108 +        }
   4.109 +        else if (_gr.nodeNum() == 2) {
   4.110 +          _path.push_back(_gr(0));
   4.111 +          _path.push_back(_gr(1));
   4.112 +          return _sum = 2 * _cost[_gr.edge(_gr(0), _gr(1))];
   4.113 +        }
   4.114 +        
   4.115 +        // Compute min. cost spanning tree
   4.116 +        std::vector<Edge> tree;
   4.117 +        kruskal(_gr, _cost, std::back_inserter(tree));
   4.118 +        
   4.119 +        FullGraph::NodeMap<int> deg(_gr, 0);
   4.120 +        for (int i = 0; i != int(tree.size()); ++i) {
   4.121 +          Edge e = tree[i];
   4.122 +          ++deg[_gr.u(e)];
   4.123 +          ++deg[_gr.v(e)];
   4.124 +        }
   4.125 +
   4.126 +        // Copy the induced subgraph of odd nodes
   4.127 +        std::vector<Node> odd_nodes;
   4.128 +        for (NodeIt u(_gr); u != INVALID; ++u) {
   4.129 +          if (deg[u] % 2 == 1) odd_nodes.push_back(u);
   4.130 +        }
   4.131 +  
   4.132 +        SmartGraph sgr;
   4.133 +        SmartGraph::EdgeMap<Cost> scost(sgr);
   4.134 +        for (int i = 0; i != int(odd_nodes.size()); ++i) {
   4.135 +          sgr.addNode();
   4.136 +        }
   4.137 +        for (int i = 0; i != int(odd_nodes.size()); ++i) {
   4.138 +          for (int j = 0; j != int(odd_nodes.size()); ++j) {
   4.139 +            if (j == i) continue;
   4.140 +            SmartGraph::Edge e =
   4.141 +              sgr.addEdge(sgr.nodeFromId(i), sgr.nodeFromId(j));
   4.142 +            scost[e] = -_cost[_gr.edge(odd_nodes[i], odd_nodes[j])];
   4.143 +          }
   4.144 +        }
   4.145 +        
   4.146 +        // Compute min. cost perfect matching
   4.147 +        MaxWeightedPerfectMatching<SmartGraph, SmartGraph::EdgeMap<Cost> >
   4.148 +          mwpm(sgr, scost);
   4.149 +        mwpm.run();
   4.150 +        
   4.151 +        for (SmartGraph::EdgeIt e(sgr); e != INVALID; ++e) {
   4.152 +          if (mwpm.matching(e)) {
   4.153 +            tree.push_back( _gr.edge(odd_nodes[sgr.id(sgr.u(e))],
   4.154 +                                     odd_nodes[sgr.id(sgr.v(e))]) );
   4.155 +          }
   4.156 +        }
   4.157 +        
   4.158 +        // Join the spanning tree and the matching        
   4.159 +        sgr.clear();
   4.160 +        for (int i = 0; i != _gr.nodeNum(); ++i) {
   4.161 +          sgr.addNode();
   4.162 +        }
   4.163 +        for (int i = 0; i != int(tree.size()); ++i) {
   4.164 +          int ui = _gr.id(_gr.u(tree[i])),
   4.165 +              vi = _gr.id(_gr.v(tree[i]));
   4.166 +          sgr.addEdge(sgr.nodeFromId(ui), sgr.nodeFromId(vi));
   4.167 +        }
   4.168 +
   4.169 +        // Compute the tour from the Euler traversal
   4.170 +        SmartGraph::NodeMap<bool> visited(sgr, false);
   4.171 +        for (EulerIt<SmartGraph> e(sgr); e != INVALID; ++e) {
   4.172 +          SmartGraph::Node n = sgr.target(e);
   4.173 +          if (!visited[n]) {
   4.174 +            _path.push_back(_gr(sgr.id(n)));
   4.175 +            visited[n] = true;
   4.176 +          }
   4.177 +        }
   4.178 +
   4.179 +        _sum = _cost[_gr.edge(_path.back(), _path.front())];
   4.180 +        for (int i = 0; i < int(_path.size())-1; ++i) {
   4.181 +          _sum += _cost[_gr.edge(_path[i], _path[i+1])];
   4.182 +        }
   4.183 +
   4.184 +        return _sum;
   4.185 +      }
   4.186 +
   4.187 +      /// @}
   4.188 +      
   4.189 +      /// \name Query Functions
   4.190 +      /// @{
   4.191 +      
   4.192 +      /// \brief The total cost of the found tour.
   4.193 +      ///
   4.194 +      /// This function returns the total cost of the found tour.
   4.195 +      ///
   4.196 +      /// \pre run() must be called before using this function.
   4.197 +      Cost tourCost() const {
   4.198 +        return _sum;
   4.199 +      }
   4.200 +      
   4.201 +      /// \brief Returns a const reference to the node sequence of the
   4.202 +      /// found tour.
   4.203 +      ///
   4.204 +      /// This function returns a const reference to a vector
   4.205 +      /// that stores the node sequence of the found tour.
   4.206 +      ///
   4.207 +      /// \pre run() must be called before using this function.
   4.208 +      const std::vector<Node>& tourNodes() const {
   4.209 +        return _path;
   4.210 +      }
   4.211 +
   4.212 +      /// \brief Gives back the node sequence of the found tour.
   4.213 +      ///
   4.214 +      /// This function copies the node sequence of the found tour into
   4.215 +      /// an STL container through the given output iterator. The
   4.216 +      /// <tt>value_type</tt> of the container must be <tt>FullGraph::Node</tt>.
   4.217 +      /// For example,
   4.218 +      /// \code
   4.219 +      /// std::vector<FullGraph::Node> nodes(countNodes(graph));
   4.220 +      /// tsp.tourNodes(nodes.begin());
   4.221 +      /// \endcode
   4.222 +      /// or
   4.223 +      /// \code
   4.224 +      /// std::list<FullGraph::Node> nodes;
   4.225 +      /// tsp.tourNodes(std::back_inserter(nodes));
   4.226 +      /// \endcode
   4.227 +      ///
   4.228 +      /// \pre run() must be called before using this function.
   4.229 +      template <typename Iterator>
   4.230 +      void tourNodes(Iterator out) const {
   4.231 +        std::copy(_path.begin(), _path.end(), out);
   4.232 +      }
   4.233 +      
   4.234 +      /// \brief Gives back the found tour as a path.
   4.235 +      ///
   4.236 +      /// This function copies the found tour as a list of arcs/edges into
   4.237 +      /// the given \ref concept::Path "path structure".
   4.238 +      ///
   4.239 +      /// \pre run() must be called before using this function.
   4.240 +      template <typename Path>
   4.241 +      void tour(Path &path) const {
   4.242 +        path.clear();
   4.243 +        for (int i = 0; i < int(_path.size()) - 1; ++i) {
   4.244 +          path.addBack(_gr.arc(_path[i], _path[i+1]));
   4.245 +        }
   4.246 +        if (int(_path.size()) >= 2) {
   4.247 +          path.addBack(_gr.arc(_path.back(), _path.front()));
   4.248 +        }
   4.249 +      }
   4.250 +      
   4.251 +      /// @}
   4.252 +      
   4.253 +  };
   4.254 +
   4.255 +}; // namespace lemon
   4.256 +
   4.257 +#endif
     5.1 --- /dev/null	Thu Jan 01 00:00:00 1970 +0000
     5.2 +++ b/lemon/greedy_tsp.h	Fri Mar 01 17:59:08 2013 +0100
     5.3 @@ -0,0 +1,251 @@
     5.4 +/* -*- mode: C++; indent-tabs-mode: nil; -*-
     5.5 + *
     5.6 + * This file is a part of LEMON, a generic C++ optimization library.
     5.7 + *
     5.8 + * Copyright (C) 2003-2010
     5.9 + * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    5.10 + * (Egervary Research Group on Combinatorial Optimization, EGRES).
    5.11 + *
    5.12 + * Permission to use, modify and distribute this software is granted
    5.13 + * provided that this copyright notice appears in all copies. For
    5.14 + * precise terms see the accompanying LICENSE file.
    5.15 + *
    5.16 + * This software is provided "AS IS" with no warranty of any kind,
    5.17 + * express or implied, and with no claim as to its suitability for any
    5.18 + * purpose.
    5.19 + *
    5.20 + */
    5.21 +
    5.22 +#ifndef LEMON_GREEDY_TSP_H
    5.23 +#define LEMON_GREEDY_TSP_H
    5.24 +
    5.25 +/// \ingroup tsp
    5.26 +/// \file
    5.27 +/// \brief Greedy algorithm for symmetric TSP
    5.28 +
    5.29 +#include <vector>
    5.30 +#include <algorithm>
    5.31 +#include <lemon/full_graph.h>
    5.32 +#include <lemon/unionfind.h>
    5.33 +
    5.34 +namespace lemon {
    5.35 +
    5.36 +  /// \ingroup tsp
    5.37 +  ///
    5.38 +  /// \brief Greedy algorithm for symmetric TSP.
    5.39 +  ///
    5.40 +  /// GreedyTsp implements the greedy heuristic for solving
    5.41 +  /// symmetric \ref tsp "TSP".
    5.42 +  ///
    5.43 +  /// This algorithm is quite similar to the \ref NearestNeighborTsp
    5.44 +  /// "nearest neighbor" heuristic, but it maintains a set of disjoint paths.
    5.45 +  /// At each step, the shortest possible edge is added to these paths
    5.46 +  /// as long as it does not create a cycle of less than n edges and it does
    5.47 +  /// not increase the degree of any node above two.
    5.48 +  ///
    5.49 +  /// This method runs in O(n<sup>2</sup>) time.
    5.50 +  /// It quickly finds a relatively short tour for most TSP instances,
    5.51 +  /// but it could also yield a really bad (or even the worst) solution
    5.52 +  /// in special cases.
    5.53 +  ///
    5.54 +  /// \tparam CM Type of the cost map.
    5.55 +  template <typename CM>
    5.56 +  class GreedyTsp
    5.57 +  {
    5.58 +    public:
    5.59 +
    5.60 +      /// Type of the cost map
    5.61 +      typedef CM CostMap;
    5.62 +      /// Type of the edge costs
    5.63 +      typedef typename CM::Value Cost;
    5.64 +
    5.65 +    private:
    5.66 +
    5.67 +      GRAPH_TYPEDEFS(FullGraph);
    5.68 +
    5.69 +      const FullGraph &_gr;
    5.70 +      const CostMap &_cost;
    5.71 +      Cost _sum;
    5.72 +      std::vector<Node> _path;
    5.73 +      
    5.74 +    private:
    5.75 +    
    5.76 +      // Functor class to compare edges by their costs
    5.77 +      class EdgeComp {
    5.78 +      private:
    5.79 +        const CostMap &_cost;
    5.80 +
    5.81 +      public:
    5.82 +        EdgeComp(const CostMap &cost) : _cost(cost) {}
    5.83 +
    5.84 +        bool operator()(const Edge &a, const Edge &b) const {
    5.85 +          return _cost[a] < _cost[b];
    5.86 +        }
    5.87 +      };
    5.88 +
    5.89 +    public:
    5.90 +
    5.91 +      /// \brief Constructor
    5.92 +      ///
    5.93 +      /// Constructor.
    5.94 +      /// \param gr The \ref FullGraph "full graph" the algorithm runs on.
    5.95 +      /// \param cost The cost map.
    5.96 +      GreedyTsp(const FullGraph &gr, const CostMap &cost)
    5.97 +        : _gr(gr), _cost(cost) {}
    5.98 +
    5.99 +      /// \name Execution Control
   5.100 +      /// @{
   5.101 +
   5.102 +      /// \brief Runs the algorithm.
   5.103 +      ///
   5.104 +      /// This function runs the algorithm.
   5.105 +      ///
   5.106 +      /// \return The total cost of the found tour.
   5.107 +      Cost run() {
   5.108 +        _path.clear();
   5.109 +
   5.110 +        if (_gr.nodeNum() == 0) return _sum = 0;
   5.111 +        else if (_gr.nodeNum() == 1) {
   5.112 +          _path.push_back(_gr(0));
   5.113 +          return _sum = 0;
   5.114 +        }
   5.115 +
   5.116 +        std::vector<int> plist;
   5.117 +        plist.resize(_gr.nodeNum()*2, -1);
   5.118 +
   5.119 +        std::vector<Edge> sorted_edges;
   5.120 +        sorted_edges.reserve(_gr.edgeNum());
   5.121 +        for (EdgeIt e(_gr); e != INVALID; ++e)
   5.122 +          sorted_edges.push_back(e);
   5.123 +        std::sort(sorted_edges.begin(), sorted_edges.end(), EdgeComp(_cost));
   5.124 +
   5.125 +        FullGraph::NodeMap<int> item_int_map(_gr);
   5.126 +        UnionFind<FullGraph::NodeMap<int> > union_find(item_int_map);
   5.127 +        for (NodeIt n(_gr); n != INVALID; ++n)
   5.128 +          union_find.insert(n);
   5.129 +
   5.130 +        FullGraph::NodeMap<int> degree(_gr, 0);
   5.131 +
   5.132 +        int nodesNum = 0, i = 0;
   5.133 +        while (nodesNum != _gr.nodeNum()-1) {
   5.134 +          Edge e = sorted_edges[i++];
   5.135 +          Node u = _gr.u(e),
   5.136 +               v = _gr.v(e);
   5.137 +
   5.138 +          if (degree[u] <= 1 && degree[v] <= 1) {
   5.139 +            if (union_find.join(u, v)) {
   5.140 +              const int uid = _gr.id(u),
   5.141 +                        vid = _gr.id(v);
   5.142 +
   5.143 +              plist[uid*2 + degree[u]] = vid;
   5.144 +              plist[vid*2 + degree[v]] = uid;
   5.145 +
   5.146 +              ++degree[u];
   5.147 +              ++degree[v];
   5.148 +              ++nodesNum;
   5.149 +            }
   5.150 +          }
   5.151 +        }
   5.152 +
   5.153 +        for (int i=0, n=-1; i<_gr.nodeNum()*2; ++i) {
   5.154 +          if (plist[i] == -1) {
   5.155 +            if (n==-1) {
   5.156 +              n = i;
   5.157 +            } else {
   5.158 +              plist[n] = i/2;
   5.159 +              plist[i] = n/2;
   5.160 +              break;
   5.161 +            }
   5.162 +          }
   5.163 +        }
   5.164 +
   5.165 +        for (int i=0, next=0, last=-1; i!=_gr.nodeNum(); ++i) {
   5.166 +          _path.push_back(_gr.nodeFromId(next));
   5.167 +          if (plist[2*next] != last) {
   5.168 +            last = next;
   5.169 +            next = plist[2*next];
   5.170 +          } else {
   5.171 +            last = next;
   5.172 +            next = plist[2*next+1];
   5.173 +          }
   5.174 +        }
   5.175 +
   5.176 +        _sum = _cost[_gr.edge(_path.back(), _path.front())];
   5.177 +        for (int i = 0; i < int(_path.size())-1; ++i) {
   5.178 +          _sum += _cost[_gr.edge(_path[i], _path[i+1])];
   5.179 +        }
   5.180 +
   5.181 +        return _sum;
   5.182 +      }
   5.183 +
   5.184 +      /// @}
   5.185 +
   5.186 +      /// \name Query Functions
   5.187 +      /// @{
   5.188 +
   5.189 +      /// \brief The total cost of the found tour.
   5.190 +      ///
   5.191 +      /// This function returns the total cost of the found tour.
   5.192 +      ///
   5.193 +      /// \pre run() must be called before using this function.
   5.194 +      Cost tourCost() const {
   5.195 +        return _sum;
   5.196 +      }
   5.197 +
   5.198 +      /// \brief Returns a const reference to the node sequence of the
   5.199 +      /// found tour.
   5.200 +      ///
   5.201 +      /// This function returns a const reference to a vector
   5.202 +      /// that stores the node sequence of the found tour.
   5.203 +      ///
   5.204 +      /// \pre run() must be called before using this function.
   5.205 +      const std::vector<Node>& tourNodes() const {
   5.206 +        return _path;
   5.207 +      }
   5.208 +
   5.209 +      /// \brief Gives back the node sequence of the found tour.
   5.210 +      ///
   5.211 +      /// This function copies the node sequence of the found tour into
   5.212 +      /// an STL container through the given output iterator. The
   5.213 +      /// <tt>value_type</tt> of the container must be <tt>FullGraph::Node</tt>.
   5.214 +      /// For example,
   5.215 +      /// \code
   5.216 +      /// std::vector<FullGraph::Node> nodes(countNodes(graph));
   5.217 +      /// tsp.tourNodes(nodes.begin());
   5.218 +      /// \endcode
   5.219 +      /// or
   5.220 +      /// \code
   5.221 +      /// std::list<FullGraph::Node> nodes;
   5.222 +      /// tsp.tourNodes(std::back_inserter(nodes));
   5.223 +      /// \endcode
   5.224 +      ///
   5.225 +      /// \pre run() must be called before using this function.
   5.226 +      template <typename Iterator>
   5.227 +      void tourNodes(Iterator out) const {
   5.228 +        std::copy(_path.begin(), _path.end(), out);
   5.229 +      }
   5.230 +
   5.231 +      /// \brief Gives back the found tour as a path.
   5.232 +      ///
   5.233 +      /// This function copies the found tour as a list of arcs/edges into
   5.234 +      /// the given \ref concept::Path "path structure".
   5.235 +      ///
   5.236 +      /// \pre run() must be called before using this function.
   5.237 +      template <typename Path>
   5.238 +      void tour(Path &path) const {
   5.239 +        path.clear();
   5.240 +        for (int i = 0; i < int(_path.size()) - 1; ++i) {
   5.241 +          path.addBack(_gr.arc(_path[i], _path[i+1]));
   5.242 +        }
   5.243 +        if (int(_path.size()) >= 2) {
   5.244 +          path.addBack(_gr.arc(_path.back(), _path.front()));
   5.245 +        }
   5.246 +      }
   5.247 +
   5.248 +      /// @}
   5.249 +
   5.250 +  };
   5.251 +
   5.252 +}; // namespace lemon
   5.253 +
   5.254 +#endif
     6.1 --- /dev/null	Thu Jan 01 00:00:00 1970 +0000
     6.2 +++ b/lemon/insertion_tsp.h	Fri Mar 01 17:59:08 2013 +0100
     6.3 @@ -0,0 +1,533 @@
     6.4 +/* -*- mode: C++; indent-tabs-mode: nil; -*-
     6.5 + *
     6.6 + * This file is a part of LEMON, a generic C++ optimization library.
     6.7 + *
     6.8 + * Copyright (C) 2003-2010
     6.9 + * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    6.10 + * (Egervary Research Group on Combinatorial Optimization, EGRES).
    6.11 + *
    6.12 + * Permission to use, modify and distribute this software is granted
    6.13 + * provided that this copyright notice appears in all copies. For
    6.14 + * precise terms see the accompanying LICENSE file.
    6.15 + *
    6.16 + * This software is provided "AS IS" with no warranty of any kind,
    6.17 + * express or implied, and with no claim as to its suitability for any
    6.18 + * purpose.
    6.19 + *
    6.20 + */
    6.21 +
    6.22 +#ifndef LEMON_INSERTION_TSP_H
    6.23 +#define LEMON_INSERTION_TSP_H
    6.24 +
    6.25 +/// \ingroup tsp
    6.26 +/// \file
    6.27 +/// \brief Insertion algorithm for symmetric TSP
    6.28 +
    6.29 +#include <vector>
    6.30 +#include <functional>
    6.31 +#include <lemon/full_graph.h>
    6.32 +#include <lemon/maps.h>
    6.33 +#include <lemon/random.h>
    6.34 +
    6.35 +namespace lemon {
    6.36 +
    6.37 +  /// \ingroup tsp
    6.38 +  ///
    6.39 +  /// \brief Insertion algorithm for symmetric TSP.
    6.40 +  ///
    6.41 +  /// InsertionTsp implements the insertion heuristic for solving
    6.42 +  /// symmetric \ref tsp "TSP".
    6.43 +  ///
    6.44 +  /// This is a fast and effective tour construction method that has
    6.45 +  /// many variants.
    6.46 +  /// It starts with a subtour containing a few nodes of the graph and it
    6.47 +  /// iteratively inserts the other nodes into this subtour according to a
    6.48 +  /// certain node selection rule.
    6.49 +  ///
    6.50 +  /// This method is among the fastest TSP algorithms, and it typically
    6.51 +  /// provides quite good solutions (usually much better than
    6.52 +  /// \ref NearestNeighborTsp and \ref GreedyTsp).
    6.53 +  ///
    6.54 +  /// InsertionTsp implements four different node selection rules,
    6.55 +  /// from which the most effective one (\e farthest \e node \e selection)
    6.56 +  /// is used by default.
    6.57 +  /// With this choice, the algorithm runs in O(n<sup>2</sup>) time.
    6.58 +  /// For more information, see \ref SelectionRule.
    6.59 +  ///
    6.60 +  /// \tparam CM Type of the cost map.
    6.61 +  template <typename CM>
    6.62 +  class InsertionTsp
    6.63 +  {
    6.64 +    public:
    6.65 +
    6.66 +      /// Type of the cost map
    6.67 +      typedef CM CostMap;
    6.68 +      /// Type of the edge costs
    6.69 +      typedef typename CM::Value Cost;
    6.70 +
    6.71 +    private:
    6.72 +
    6.73 +      GRAPH_TYPEDEFS(FullGraph);
    6.74 +
    6.75 +      const FullGraph &_gr;
    6.76 +      const CostMap &_cost;
    6.77 +      std::vector<Node> _notused;
    6.78 +      std::vector<Node> _tour;
    6.79 +      Cost _sum;
    6.80 +
    6.81 +    public:
    6.82 +
    6.83 +      /// \brief Constants for specifying the node selection rule.
    6.84 +      ///
    6.85 +      /// Enum type containing constants for specifying the node selection
    6.86 +      /// rule for the \ref run() function.
    6.87 +      ///
    6.88 +      /// During the algorithm, nodes are selected for addition to the current
    6.89 +      /// subtour according to the applied rule.
    6.90 +      /// The FARTHEST method is one of the fastest selection rules, and
    6.91 +      /// it is typically the most effective, thus it is the default
    6.92 +      /// option. The RANDOM rule usually gives slightly worse results,
    6.93 +      /// but it is more robust.
    6.94 +      ///
    6.95 +      /// The desired selection rule can be specified as a parameter of the
    6.96 +      /// \ref run() function.
    6.97 +      enum SelectionRule {
    6.98 +
    6.99 +        /// An unvisited node having minimum distance from the current
   6.100 +        /// subtour is selected at each step.
   6.101 +        /// The algorithm runs in O(n<sup>2</sup>) time using this
   6.102 +        /// selection rule.
   6.103 +        NEAREST,
   6.104 +
   6.105 +        /// An unvisited node having maximum distance from the current
   6.106 +        /// subtour is selected at each step.
   6.107 +        /// The algorithm runs in O(n<sup>2</sup>) time using this
   6.108 +        /// selection rule.
   6.109 +        FARTHEST,
   6.110 +
   6.111 +        /// An unvisited node whose insertion results in the least
   6.112 +        /// increase of the subtour's total cost is selected at each step.
   6.113 +        /// The algorithm runs in O(n<sup>3</sup>) time using this
   6.114 +        /// selection rule, but in most cases, it is almost as fast as
   6.115 +        /// with other rules.
   6.116 +        CHEAPEST,
   6.117 +
   6.118 +        /// An unvisited node is selected randomly without any evaluation
   6.119 +        /// at each step.
   6.120 +        /// The global \ref rnd "random number generator instance" is used.
   6.121 +        /// You can seed it before executing the algorithm, if you
   6.122 +        /// would like to.
   6.123 +        /// The algorithm runs in O(n<sup>2</sup>) time using this
   6.124 +        /// selection rule.
   6.125 +        RANDOM
   6.126 +      };
   6.127 +
   6.128 +    public:
   6.129 +
   6.130 +      /// \brief Constructor
   6.131 +      ///
   6.132 +      /// Constructor.
   6.133 +      /// \param gr The \ref FullGraph "full graph" the algorithm runs on.
   6.134 +      /// \param cost The cost map.
   6.135 +      InsertionTsp(const FullGraph &gr, const CostMap &cost)
   6.136 +        : _gr(gr), _cost(cost) {}
   6.137 +
   6.138 +      /// \name Execution Control
   6.139 +      /// @{
   6.140 +
   6.141 +      /// \brief Runs the algorithm.
   6.142 +      ///
   6.143 +      /// This function runs the algorithm.
   6.144 +      ///
   6.145 +      /// \param rule The node selection rule. For more information, see
   6.146 +      /// \ref SelectionRule.
   6.147 +      ///
   6.148 +      /// \return The total cost of the found tour.
   6.149 +      Cost run(SelectionRule rule = FARTHEST) {
   6.150 +        _tour.clear();
   6.151 +
   6.152 +        if (_gr.nodeNum() == 0) return _sum = 0;
   6.153 +        else if (_gr.nodeNum() == 1) {
   6.154 +          _tour.push_back(_gr(0));
   6.155 +          return _sum = 0;
   6.156 +        }
   6.157 +
   6.158 +        switch (rule) {
   6.159 +          case NEAREST:
   6.160 +            init(true);
   6.161 +            start<ComparingSelection<std::less<Cost> >,
   6.162 +                  DefaultInsertion>();
   6.163 +            break;
   6.164 +          case FARTHEST:
   6.165 +            init(false);
   6.166 +            start<ComparingSelection<std::greater<Cost> >,
   6.167 +                  DefaultInsertion>();
   6.168 +            break;
   6.169 +          case CHEAPEST:
   6.170 +            init(true);
   6.171 +            start<CheapestSelection, CheapestInsertion>();
   6.172 +            break;
   6.173 +          case RANDOM:
   6.174 +            init(true);
   6.175 +            start<RandomSelection, DefaultInsertion>();
   6.176 +            break;
   6.177 +        }
   6.178 +        return _sum;
   6.179 +      }
   6.180 +
   6.181 +      /// @}
   6.182 +
   6.183 +      /// \name Query Functions
   6.184 +      /// @{
   6.185 +
   6.186 +      /// \brief The total cost of the found tour.
   6.187 +      ///
   6.188 +      /// This function returns the total cost of the found tour.
   6.189 +      ///
   6.190 +      /// \pre run() must be called before using this function.
   6.191 +      Cost tourCost() const {
   6.192 +        return _sum;
   6.193 +      }
   6.194 +
   6.195 +      /// \brief Returns a const reference to the node sequence of the
   6.196 +      /// found tour.
   6.197 +      ///
   6.198 +      /// This function returns a const reference to a vector
   6.199 +      /// that stores the node sequence of the found tour.
   6.200 +      ///
   6.201 +      /// \pre run() must be called before using this function.
   6.202 +      const std::vector<Node>& tourNodes() const {
   6.203 +        return _tour;
   6.204 +      }
   6.205 +
   6.206 +      /// \brief Gives back the node sequence of the found tour.
   6.207 +      ///
   6.208 +      /// This function copies the node sequence of the found tour into
   6.209 +      /// an STL container through the given output iterator. The
   6.210 +      /// <tt>value_type</tt> of the container must be <tt>FullGraph::Node</tt>.
   6.211 +      /// For example,
   6.212 +      /// \code
   6.213 +      /// std::vector<FullGraph::Node> nodes(countNodes(graph));
   6.214 +      /// tsp.tourNodes(nodes.begin());
   6.215 +      /// \endcode
   6.216 +      /// or
   6.217 +      /// \code
   6.218 +      /// std::list<FullGraph::Node> nodes;
   6.219 +      /// tsp.tourNodes(std::back_inserter(nodes));
   6.220 +      /// \endcode
   6.221 +      ///
   6.222 +      /// \pre run() must be called before using this function.
   6.223 +      template <typename Iterator>
   6.224 +      void tourNodes(Iterator out) const {
   6.225 +        std::copy(_tour.begin(), _tour.end(), out);
   6.226 +      }
   6.227 +
   6.228 +      /// \brief Gives back the found tour as a path.
   6.229 +      ///
   6.230 +      /// This function copies the found tour as a list of arcs/edges into
   6.231 +      /// the given \ref concept::Path "path structure".
   6.232 +      ///
   6.233 +      /// \pre run() must be called before using this function.
   6.234 +      template <typename Path>
   6.235 +      void tour(Path &path) const {
   6.236 +        path.clear();
   6.237 +        for (int i = 0; i < int(_tour.size()) - 1; ++i) {
   6.238 +          path.addBack(_gr.arc(_tour[i], _tour[i+1]));
   6.239 +        }
   6.240 +        if (int(_tour.size()) >= 2) {
   6.241 +          path.addBack(_gr.arc(_tour.back(), _tour.front()));
   6.242 +        }
   6.243 +      }
   6.244 +
   6.245 +      /// @}
   6.246 +
   6.247 +    private:
   6.248 +
   6.249 +      // Initializes the algorithm
   6.250 +      void init(bool min) {
   6.251 +        Edge min_edge = min ? mapMin(_gr, _cost) : mapMax(_gr, _cost);
   6.252 +
   6.253 +        _tour.clear();
   6.254 +        _tour.push_back(_gr.u(min_edge));
   6.255 +        _tour.push_back(_gr.v(min_edge));
   6.256 +
   6.257 +        _notused.clear();
   6.258 +        for (NodeIt n(_gr); n!=INVALID; ++n) {
   6.259 +          if (n != _gr.u(min_edge) && n != _gr.v(min_edge)) {
   6.260 +            _notused.push_back(n);
   6.261 +          }
   6.262 +        }
   6.263 +
   6.264 +        _sum = _cost[min_edge] * 2;
   6.265 +      }
   6.266 +
   6.267 +      // Executes the algorithm
   6.268 +      template <class SelectionFunctor, class InsertionFunctor>
   6.269 +      void start() {
   6.270 +        SelectionFunctor selectNode(_gr, _cost, _tour, _notused);
   6.271 +        InsertionFunctor insertNode(_gr, _cost, _tour, _sum);
   6.272 +
   6.273 +        for (int i=0; i<_gr.nodeNum()-2; ++i) {
   6.274 +          insertNode.insert(selectNode.select());
   6.275 +        }
   6.276 +
   6.277 +        _sum = _cost[_gr.edge(_tour.back(), _tour.front())];
   6.278 +        for (int i = 0; i < int(_tour.size())-1; ++i) {
   6.279 +          _sum += _cost[_gr.edge(_tour[i], _tour[i+1])];
   6.280 +        }
   6.281 +      }
   6.282 +
   6.283 +
   6.284 +      // Implementation of the nearest and farthest selection rule
   6.285 +      template <typename Comparator>
   6.286 +      class ComparingSelection {
   6.287 +        public:
   6.288 +          ComparingSelection(const FullGraph &gr, const CostMap &cost,
   6.289 +                  std::vector<Node> &tour, std::vector<Node> &notused)
   6.290 +            : _gr(gr), _cost(cost), _tour(tour), _notused(notused),
   6.291 +              _dist(gr, 0), _compare()
   6.292 +          {
   6.293 +            // Compute initial distances for the unused nodes
   6.294 +            for (unsigned int i=0; i<_notused.size(); ++i) {
   6.295 +              Node u = _notused[i];
   6.296 +              Cost min_dist = _cost[_gr.edge(u, _tour[0])];
   6.297 +              for (unsigned int j=1; j<_tour.size(); ++j) {
   6.298 +                Cost curr = _cost[_gr.edge(u, _tour[j])];
   6.299 +                if (curr < min_dist) {
   6.300 +                  min_dist = curr;
   6.301 +                }
   6.302 +              }
   6.303 +              _dist[u] = min_dist;
   6.304 +            }
   6.305 +          }
   6.306 +
   6.307 +          Node select() {
   6.308 +
   6.309 +            // Select an used node with minimum distance
   6.310 +            Cost ins_dist = 0;
   6.311 +            int ins_node = -1;
   6.312 +            for (unsigned int i=0; i<_notused.size(); ++i) {
   6.313 +              Cost curr = _dist[_notused[i]];
   6.314 +              if (_compare(curr, ins_dist) || ins_node == -1) {
   6.315 +                ins_dist = curr;
   6.316 +                ins_node = i;
   6.317 +              }
   6.318 +            }
   6.319 +
   6.320 +            // Remove the selected node from the unused vector
   6.321 +            Node sn = _notused[ins_node];
   6.322 +            _notused[ins_node] = _notused.back();
   6.323 +            _notused.pop_back();
   6.324 +
   6.325 +            // Update the distances of the remaining nodes
   6.326 +            for (unsigned int i=0; i<_notused.size(); ++i) {
   6.327 +              Node u = _notused[i];
   6.328 +              Cost nc = _cost[_gr.edge(sn, u)];
   6.329 +              if (nc < _dist[u]) {
   6.330 +                _dist[u] = nc;
   6.331 +              }
   6.332 +            }
   6.333 +
   6.334 +            return sn;
   6.335 +          }
   6.336 +
   6.337 +        private:
   6.338 +          const FullGraph &_gr;
   6.339 +          const CostMap &_cost;
   6.340 +          std::vector<Node> &_tour;
   6.341 +          std::vector<Node> &_notused;
   6.342 +          FullGraph::NodeMap<Cost> _dist;
   6.343 +          Comparator _compare;
   6.344 +      };
   6.345 +
   6.346 +      // Implementation of the cheapest selection rule
   6.347 +      class CheapestSelection {
   6.348 +        private:
   6.349 +          Cost costDiff(Node u, Node v, Node w) const {
   6.350 +            return
   6.351 +              _cost[_gr.edge(u, w)] +
   6.352 +              _cost[_gr.edge(v, w)] -
   6.353 +              _cost[_gr.edge(u, v)];
   6.354 +          }
   6.355 +
   6.356 +        public:
   6.357 +          CheapestSelection(const FullGraph &gr, const CostMap &cost,
   6.358 +                            std::vector<Node> &tour, std::vector<Node> &notused)
   6.359 +            : _gr(gr), _cost(cost), _tour(tour), _notused(notused),
   6.360 +              _ins_cost(gr, 0), _ins_pos(gr, -1)
   6.361 +          {
   6.362 +            // Compute insertion cost and position for the unused nodes
   6.363 +            for (unsigned int i=0; i<_notused.size(); ++i) {
   6.364 +              Node u = _notused[i];
   6.365 +              Cost min_cost = costDiff(_tour.back(), _tour.front(), u);
   6.366 +              int min_pos = 0;              
   6.367 +              for (unsigned int j=1; j<_tour.size(); ++j) {
   6.368 +                Cost curr_cost = costDiff(_tour[j-1], _tour[j], u);
   6.369 +                if (curr_cost < min_cost) {
   6.370 +                  min_cost = curr_cost;
   6.371 +                  min_pos = j;
   6.372 +                }
   6.373 +              }
   6.374 +              _ins_cost[u] = min_cost;
   6.375 +              _ins_pos[u] = min_pos;
   6.376 +            }
   6.377 +          }
   6.378 +
   6.379 +          Cost select() {
   6.380 +
   6.381 +            // Select an used node with minimum insertion cost
   6.382 +            Cost min_cost = 0;
   6.383 +            int min_node = -1;
   6.384 +            for (unsigned int i=0; i<_notused.size(); ++i) {
   6.385 +              Cost curr_cost = _ins_cost[_notused[i]];
   6.386 +              if (curr_cost < min_cost || min_node == -1) {
   6.387 +                min_cost = curr_cost;
   6.388 +                min_node = i;
   6.389 +              }
   6.390 +            }
   6.391 +
   6.392 +            // Remove the selected node from the unused vector
   6.393 +            Node sn = _notused[min_node];
   6.394 +            _notused[min_node] = _notused.back();
   6.395 +            _notused.pop_back();
   6.396 +            
   6.397 +            // Insert the selected node into the tour
   6.398 +            const int ipos = _ins_pos[sn];
   6.399 +            _tour.insert(_tour.begin() + ipos, sn);
   6.400 +
   6.401 +            // Update the insertion cost and position of the remaining nodes
   6.402 +            for (unsigned int i=0; i<_notused.size(); ++i) {
   6.403 +              Node u = _notused[i];
   6.404 +              Cost curr_cost = _ins_cost[u];
   6.405 +              int curr_pos = _ins_pos[u];
   6.406 +
   6.407 +              int ipos_prev = ipos == 0 ? _tour.size()-1 : ipos-1;
   6.408 +              int ipos_next = ipos == int(_tour.size())-1 ? 0 : ipos+1;
   6.409 +              Cost nc1 = costDiff(_tour[ipos_prev], _tour[ipos], u);
   6.410 +              Cost nc2 = costDiff(_tour[ipos], _tour[ipos_next], u);
   6.411 +              
   6.412 +              if (nc1 <= curr_cost || nc2 <= curr_cost) {
   6.413 +                // A new position is better than the old one
   6.414 +                if (nc1 <= nc2) {
   6.415 +                  curr_cost = nc1;
   6.416 +                  curr_pos = ipos;
   6.417 +                } else {
   6.418 +                  curr_cost = nc2;
   6.419 +                  curr_pos = ipos_next;
   6.420 +                }
   6.421 +              }
   6.422 +              else {
   6.423 +                if (curr_pos == ipos) {
   6.424 +                  // The minimum should be found again
   6.425 +                  curr_cost = costDiff(_tour.back(), _tour.front(), u);
   6.426 +                  curr_pos = 0;              
   6.427 +                  for (unsigned int j=1; j<_tour.size(); ++j) {
   6.428 +                    Cost tmp_cost = costDiff(_tour[j-1], _tour[j], u);
   6.429 +                    if (tmp_cost < curr_cost) {
   6.430 +                      curr_cost = tmp_cost;
   6.431 +                      curr_pos = j;
   6.432 +                    }
   6.433 +                  }
   6.434 +                }
   6.435 +                else if (curr_pos > ipos) {
   6.436 +                  ++curr_pos;
   6.437 +                }
   6.438 +              }
   6.439 +              
   6.440 +              _ins_cost[u] = curr_cost;
   6.441 +              _ins_pos[u] = curr_pos;
   6.442 +            }
   6.443 +
   6.444 +            return min_cost;
   6.445 +          }
   6.446 +
   6.447 +        private:
   6.448 +          const FullGraph &_gr;
   6.449 +          const CostMap &_cost;
   6.450 +          std::vector<Node> &_tour;
   6.451 +          std::vector<Node> &_notused;
   6.452 +          FullGraph::NodeMap<Cost> _ins_cost;
   6.453 +          FullGraph::NodeMap<int> _ins_pos;
   6.454 +      };
   6.455 +
   6.456 +      // Implementation of the random selection rule
   6.457 +      class RandomSelection {
   6.458 +        public:
   6.459 +          RandomSelection(const FullGraph &, const CostMap &,
   6.460 +                          std::vector<Node> &, std::vector<Node> &notused)
   6.461 +            : _notused(notused) {}
   6.462 +
   6.463 +          Node select() const {
   6.464 +            const int index = rnd[_notused.size()];
   6.465 +            Node n = _notused[index];
   6.466 +            _notused[index] = _notused.back();
   6.467 +            _notused.pop_back();
   6.468 +            return n;
   6.469 +          }
   6.470 +
   6.471 +        private:
   6.472 +          std::vector<Node> &_notused;
   6.473 +      };
   6.474 +
   6.475 +
   6.476 +      // Implementation of the default insertion method
   6.477 +      class DefaultInsertion {
   6.478 +        private:
   6.479 +          Cost costDiff(Node u, Node v, Node w) const {
   6.480 +            return
   6.481 +              _cost[_gr.edge(u, w)] +
   6.482 +              _cost[_gr.edge(v, w)] -
   6.483 +              _cost[_gr.edge(u, v)];
   6.484 +          }
   6.485 +
   6.486 +        public:
   6.487 +          DefaultInsertion(const FullGraph &gr, const CostMap &cost,
   6.488 +                           std::vector<Node> &tour, Cost &total_cost) :
   6.489 +            _gr(gr), _cost(cost), _tour(tour), _total(total_cost) {}
   6.490 +
   6.491 +          void insert(Node n) const {
   6.492 +            int min = 0;
   6.493 +            Cost min_val =
   6.494 +              costDiff(_tour.front(), _tour.back(), n);
   6.495 +
   6.496 +            for (unsigned int i=1; i<_tour.size(); ++i) {
   6.497 +              Cost tmp = costDiff(_tour[i-1], _tour[i], n);
   6.498 +              if (tmp < min_val) {
   6.499 +                min = i;
   6.500 +                min_val = tmp;
   6.501 +              }
   6.502 +            }
   6.503 +
   6.504 +            _tour.insert(_tour.begin()+min, n);
   6.505 +            _total += min_val;
   6.506 +          }
   6.507 +
   6.508 +        private:
   6.509 +          const FullGraph &_gr;
   6.510 +          const CostMap &_cost;
   6.511 +          std::vector<Node> &_tour;
   6.512 +          Cost &_total;
   6.513 +      };
   6.514 +
   6.515 +      // Implementation of a special insertion method for the cheapest
   6.516 +      // selection rule
   6.517 +      class CheapestInsertion {
   6.518 +        TEMPLATE_GRAPH_TYPEDEFS(FullGraph);
   6.519 +        public:
   6.520 +          CheapestInsertion(const FullGraph &, const CostMap &,
   6.521 +                            std::vector<Node> &, Cost &total_cost) :
   6.522 +            _total(total_cost) {}
   6.523 +
   6.524 +          void insert(Cost diff) const {
   6.525 +            _total += diff;
   6.526 +          }
   6.527 +
   6.528 +        private:
   6.529 +          Cost &_total;
   6.530 +      };
   6.531 +
   6.532 +  };
   6.533 +
   6.534 +}; // namespace lemon
   6.535 +
   6.536 +#endif
     7.1 --- /dev/null	Thu Jan 01 00:00:00 1970 +0000
     7.2 +++ b/lemon/nearest_neighbor_tsp.h	Fri Mar 01 17:59:08 2013 +0100
     7.3 @@ -0,0 +1,238 @@
     7.4 +/* -*- mode: C++; indent-tabs-mode: nil; -*-
     7.5 + *
     7.6 + * This file is a part of LEMON, a generic C++ optimization library.
     7.7 + *
     7.8 + * Copyright (C) 2003-2010
     7.9 + * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    7.10 + * (Egervary Research Group on Combinatorial Optimization, EGRES).
    7.11 + *
    7.12 + * Permission to use, modify and distribute this software is granted
    7.13 + * provided that this copyright notice appears in all copies. For
    7.14 + * precise terms see the accompanying LICENSE file.
    7.15 + *
    7.16 + * This software is provided "AS IS" with no warranty of any kind,
    7.17 + * express or implied, and with no claim as to its suitability for any
    7.18 + * purpose.
    7.19 + *
    7.20 + */
    7.21 +
    7.22 +#ifndef LEMON_NEAREST_NEIGHBOUR_TSP_H
    7.23 +#define LEMON_NEAREST_NEIGHBOUR_TSP_H
    7.24 +
    7.25 +/// \ingroup tsp
    7.26 +/// \file
    7.27 +/// \brief Nearest neighbor algorithm for symmetric TSP
    7.28 +
    7.29 +#include <deque>
    7.30 +#include <vector>
    7.31 +#include <limits>
    7.32 +#include <lemon/full_graph.h>
    7.33 +#include <lemon/maps.h>
    7.34 +
    7.35 +namespace lemon {
    7.36 +
    7.37 +  /// \ingroup tsp
    7.38 +  ///
    7.39 +  /// \brief Nearest neighbor algorithm for symmetric TSP.
    7.40 +  ///
    7.41 +  /// NearestNeighborTsp implements the nearest neighbor heuristic for solving
    7.42 +  /// symmetric \ref tsp "TSP".
    7.43 +  ///
    7.44 +  /// This is probably the simplest TSP heuristic.
    7.45 +  /// It starts with a minimum cost edge and at each step, it connects the
    7.46 +  /// nearest unvisited node to the current path.
    7.47 +  /// Finally, it connects the two end points of the path to form a tour.
    7.48 +  ///
    7.49 +  /// This method runs in O(n<sup>2</sup>) time.
    7.50 +  /// It quickly finds a relatively short tour for most TSP instances,
    7.51 +  /// but it could also yield a really bad (or even the worst) solution
    7.52 +  /// in special cases.
    7.53 +  ///
    7.54 +  /// \tparam CM Type of the cost map.
    7.55 +  template <typename CM>
    7.56 +  class NearestNeighborTsp
    7.57 +  {
    7.58 +    public:
    7.59 +
    7.60 +      /// Type of the cost map
    7.61 +      typedef CM CostMap;
    7.62 +      /// Type of the edge costs
    7.63 +      typedef typename CM::Value Cost;
    7.64 +
    7.65 +    private:
    7.66 +
    7.67 +      GRAPH_TYPEDEFS(FullGraph);
    7.68 +
    7.69 +      const FullGraph &_gr;
    7.70 +      const CostMap &_cost;
    7.71 +      Cost _sum;
    7.72 +      std::vector<Node> _path;
    7.73 +
    7.74 +    public:
    7.75 +
    7.76 +      /// \brief Constructor
    7.77 +      ///
    7.78 +      /// Constructor.
    7.79 +      /// \param gr The \ref FullGraph "full graph" the algorithm runs on.
    7.80 +      /// \param cost The cost map.
    7.81 +      NearestNeighborTsp(const FullGraph &gr, const CostMap &cost)
    7.82 +        : _gr(gr), _cost(cost) {}
    7.83 +
    7.84 +      /// \name Execution Control
    7.85 +      /// @{
    7.86 +
    7.87 +      /// \brief Runs the algorithm.
    7.88 +      ///
    7.89 +      /// This function runs the algorithm.
    7.90 +      ///
    7.91 +      /// \return The total cost of the found tour.
    7.92 +      Cost run() {
    7.93 +        _path.clear();
    7.94 +        if (_gr.nodeNum() == 0) {
    7.95 +          return _sum = 0;
    7.96 +        }
    7.97 +        else if (_gr.nodeNum() == 1) {
    7.98 +          _path.push_back(_gr(0));
    7.99 +          return _sum = 0;
   7.100 +        }
   7.101 +
   7.102 +        std::deque<Node> path_dq;
   7.103 +        Edge min_edge1 = INVALID,
   7.104 +             min_edge2 = INVALID;
   7.105 +
   7.106 +        min_edge1 = mapMin(_gr, _cost);
   7.107 +        Node n1 = _gr.u(min_edge1),
   7.108 +             n2 = _gr.v(min_edge1);
   7.109 +        path_dq.push_back(n1);
   7.110 +        path_dq.push_back(n2);
   7.111 +
   7.112 +        FullGraph::NodeMap<bool> used(_gr, false);
   7.113 +        used[n1] = true;
   7.114 +        used[n2] = true;
   7.115 +
   7.116 +        min_edge1 = INVALID;
   7.117 +        while (int(path_dq.size()) != _gr.nodeNum()) {
   7.118 +          if (min_edge1 == INVALID) {
   7.119 +            for (IncEdgeIt e(_gr, n1); e != INVALID; ++e) {
   7.120 +              if (!used[_gr.runningNode(e)] &&
   7.121 +                  (_cost[e] < _cost[min_edge1] || min_edge1 == INVALID)) {
   7.122 +                min_edge1 = e;
   7.123 +              }
   7.124 +            }
   7.125 +          }
   7.126 +
   7.127 +          if (min_edge2 == INVALID) {
   7.128 +            for (IncEdgeIt e(_gr, n2); e != INVALID; ++e) {
   7.129 +              if (!used[_gr.runningNode(e)] &&
   7.130 +                  (_cost[e] < _cost[min_edge2] || min_edge2 == INVALID)) {
   7.131 +                min_edge2 = e;
   7.132 +              }
   7.133 +            }
   7.134 +          }
   7.135 +
   7.136 +          if (_cost[min_edge1] < _cost[min_edge2]) {
   7.137 +            n1 = _gr.oppositeNode(n1, min_edge1);
   7.138 +            path_dq.push_front(n1);
   7.139 +
   7.140 +            used[n1] = true;
   7.141 +            min_edge1 = INVALID;
   7.142 +
   7.143 +            if (_gr.u(min_edge2) == n1 || _gr.v(min_edge2) == n1)
   7.144 +              min_edge2 = INVALID;
   7.145 +          } else {
   7.146 +            n2 = _gr.oppositeNode(n2, min_edge2);
   7.147 +            path_dq.push_back(n2);
   7.148 +
   7.149 +            used[n2] = true;
   7.150 +            min_edge2 = INVALID;
   7.151 +
   7.152 +            if (_gr.u(min_edge1) == n2 || _gr.v(min_edge1) == n2)
   7.153 +              min_edge1 = INVALID;
   7.154 +          }
   7.155 +        }
   7.156 +
   7.157 +        n1 = path_dq.back();
   7.158 +        n2 = path_dq.front();
   7.159 +        _path.push_back(n2);
   7.160 +        _sum = _cost[_gr.edge(n1, n2)];
   7.161 +        for (int i = 1; i < int(path_dq.size()); ++i) {
   7.162 +          n1 = n2;
   7.163 +          n2 = path_dq[i];
   7.164 +          _path.push_back(n2);
   7.165 +          _sum += _cost[_gr.edge(n1, n2)];
   7.166 +        }
   7.167 +
   7.168 +        return _sum;
   7.169 +      }
   7.170 +
   7.171 +      /// @}
   7.172 +
   7.173 +      /// \name Query Functions
   7.174 +      /// @{
   7.175 +
   7.176 +      /// \brief The total cost of the found tour.
   7.177 +      ///
   7.178 +      /// This function returns the total cost of the found tour.
   7.179 +      ///
   7.180 +      /// \pre run() must be called before using this function.
   7.181 +      Cost tourCost() const {
   7.182 +        return _sum;
   7.183 +      }
   7.184 +
   7.185 +      /// \brief Returns a const reference to the node sequence of the
   7.186 +      /// found tour.
   7.187 +      ///
   7.188 +      /// This function returns a const reference to a vector
   7.189 +      /// that stores the node sequence of the found tour.
   7.190 +      ///
   7.191 +      /// \pre run() must be called before using this function.
   7.192 +      const std::vector<Node>& tourNodes() const {
   7.193 +        return _path;
   7.194 +      }
   7.195 +
   7.196 +      /// \brief Gives back the node sequence of the found tour.
   7.197 +      ///
   7.198 +      /// This function copies the node sequence of the found tour into
   7.199 +      /// an STL container through the given output iterator. The
   7.200 +      /// <tt>value_type</tt> of the container must be <tt>FullGraph::Node</tt>.
   7.201 +      /// For example,
   7.202 +      /// \code
   7.203 +      /// std::vector<FullGraph::Node> nodes(countNodes(graph));
   7.204 +      /// tsp.tourNodes(nodes.begin());
   7.205 +      /// \endcode
   7.206 +      /// or
   7.207 +      /// \code
   7.208 +      /// std::list<FullGraph::Node> nodes;
   7.209 +      /// tsp.tourNodes(std::back_inserter(nodes));
   7.210 +      /// \endcode
   7.211 +      ///
   7.212 +      /// \pre run() must be called before using this function.
   7.213 +      template <typename Iterator>
   7.214 +      void tourNodes(Iterator out) const {
   7.215 +        std::copy(_path.begin(), _path.end(), out);
   7.216 +      }
   7.217 +
   7.218 +      /// \brief Gives back the found tour as a path.
   7.219 +      ///
   7.220 +      /// This function copies the found tour as a list of arcs/edges into
   7.221 +      /// the given \ref concept::Path "path structure".
   7.222 +      ///
   7.223 +      /// \pre run() must be called before using this function.
   7.224 +      template <typename Path>
   7.225 +      void tour(Path &path) const {
   7.226 +        path.clear();
   7.227 +        for (int i = 0; i < int(_path.size()) - 1; ++i) {
   7.228 +          path.addBack(_gr.arc(_path[i], _path[i+1]));
   7.229 +        }
   7.230 +        if (int(_path.size()) >= 2) {
   7.231 +          path.addBack(_gr.arc(_path.back(), _path.front()));
   7.232 +        }
   7.233 +      }
   7.234 +
   7.235 +      /// @}
   7.236 +
   7.237 +  };
   7.238 +
   7.239 +}; // namespace lemon
   7.240 +
   7.241 +#endif
     8.1 --- /dev/null	Thu Jan 01 00:00:00 1970 +0000
     8.2 +++ b/lemon/opt2_tsp.h	Fri Mar 01 17:59:08 2013 +0100
     8.3 @@ -0,0 +1,367 @@
     8.4 +/* -*- mode: C++; indent-tabs-mode: nil; -*-
     8.5 + *
     8.6 + * This file is a part of LEMON, a generic C++ optimization library.
     8.7 + *
     8.8 + * Copyright (C) 2003-2010
     8.9 + * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    8.10 + * (Egervary Research Group on Combinatorial Optimization, EGRES).
    8.11 + *
    8.12 + * Permission to use, modify and distribute this software is granted
    8.13 + * provided that this copyright notice appears in all copies. For
    8.14 + * precise terms see the accompanying LICENSE file.
    8.15 + *
    8.16 + * This software is provided "AS IS" with no warranty of any kind,
    8.17 + * express or implied, and with no claim as to its suitability for any
    8.18 + * purpose.
    8.19 + *
    8.20 + */
    8.21 +
    8.22 +#ifndef LEMON_OPT2_TSP_H
    8.23 +#define LEMON_OPT2_TSP_H
    8.24 +
    8.25 +/// \ingroup tsp
    8.26 +/// \file
    8.27 +/// \brief 2-opt algorithm for symmetric TSP.
    8.28 +
    8.29 +#include <vector>
    8.30 +#include <lemon/full_graph.h>
    8.31 +
    8.32 +namespace lemon {
    8.33 +
    8.34 +  /// \ingroup tsp
    8.35 +  ///
    8.36 +  /// \brief 2-opt algorithm for symmetric TSP.
    8.37 +  ///
    8.38 +  /// Opt2Tsp implements the 2-opt heuristic for solving
    8.39 +  /// symmetric \ref tsp "TSP".
    8.40 +  ///
    8.41 +  /// This algorithm starts with an initial tour and iteratively improves it.
    8.42 +  /// At each step, it removes two edges and the reconnects the created two
    8.43 +  /// paths in the other way if the resulting tour is shorter.
    8.44 +  /// The algorithm finishes when no such 2-opt move can be applied, and so
    8.45 +  /// the tour is 2-optimal.
    8.46 +  ///
    8.47 +  /// If no starting tour is given to the \ref run() function, then the
    8.48 +  /// algorithm uses the node sequence determined by the node IDs.
    8.49 +  /// Oherwise, it starts with the given tour.
    8.50 +  ///
    8.51 +  /// This is a rather slow but effective method.
    8.52 +  /// Its typical usage is the improvement of the result of a fast tour
    8.53 +  /// construction heuristic (e.g. the InsertionTsp algorithm).
    8.54 +  ///
    8.55 +  /// \tparam CM Type of the cost map.
    8.56 +  template <typename CM>
    8.57 +  class Opt2Tsp
    8.58 +  {
    8.59 +    public:
    8.60 +
    8.61 +      /// Type of the cost map
    8.62 +      typedef CM CostMap;
    8.63 +      /// Type of the edge costs
    8.64 +      typedef typename CM::Value Cost;
    8.65 +
    8.66 +    private:
    8.67 +
    8.68 +      GRAPH_TYPEDEFS(FullGraph);
    8.69 +
    8.70 +      const FullGraph &_gr;
    8.71 +      const CostMap &_cost;
    8.72 +      Cost _sum;
    8.73 +      std::vector<int> _plist;
    8.74 +      std::vector<Node> _path;
    8.75 +
    8.76 +    public:
    8.77 +
    8.78 +      /// \brief Constructor
    8.79 +      ///
    8.80 +      /// Constructor.
    8.81 +      /// \param gr The \ref FullGraph "full graph" the algorithm runs on.
    8.82 +      /// \param cost The cost map.
    8.83 +      Opt2Tsp(const FullGraph &gr, const CostMap &cost)
    8.84 +        : _gr(gr), _cost(cost) {}
    8.85 +
    8.86 +      /// \name Execution Control
    8.87 +      /// @{
    8.88 +
    8.89 +      /// \brief Runs the algorithm from scratch.
    8.90 +      ///
    8.91 +      /// This function runs the algorithm starting from the tour that is
    8.92 +      /// determined by the node ID sequence.
    8.93 +      ///
    8.94 +      /// \return The total cost of the found tour.
    8.95 +      Cost run() {
    8.96 +        _path.clear();
    8.97 +
    8.98 +        if (_gr.nodeNum() == 0) return _sum = 0;
    8.99 +        else if (_gr.nodeNum() == 1) {
   8.100 +          _path.push_back(_gr(0));
   8.101 +          return _sum = 0;
   8.102 +        }
   8.103 +        else if (_gr.nodeNum() == 2) {
   8.104 +          _path.push_back(_gr(0));
   8.105 +          _path.push_back(_gr(1));
   8.106 +          return _sum = 2 * _cost[_gr.edge(_gr(0), _gr(1))];
   8.107 +        }
   8.108 +
   8.109 +        _plist.resize(2*_gr.nodeNum());
   8.110 +        for (int i = 1; i < _gr.nodeNum()-1; ++i) {
   8.111 +          _plist[2*i] = i-1;
   8.112 +          _plist[2*i+1] = i+1;
   8.113 +        }
   8.114 +        _plist[0] = _gr.nodeNum()-1;
   8.115 +        _plist[1] = 1;
   8.116 +        _plist[2*_gr.nodeNum()-2] = _gr.nodeNum()-2;
   8.117 +        _plist[2*_gr.nodeNum()-1] = 0;
   8.118 +
   8.119 +        return start();
   8.120 +      }
   8.121 +
   8.122 +      /// \brief Runs the algorithm starting from the given tour.
   8.123 +      ///
   8.124 +      /// This function runs the algorithm starting from the given tour.
   8.125 +      ///
   8.126 +      /// \param tour The tour as a path structure. It must be a
   8.127 +      /// \ref checkPath() "valid path" containing excactly n arcs.
   8.128 +      ///
   8.129 +      /// \return The total cost of the found tour.
   8.130 +      template <typename Path>
   8.131 +      Cost run(const Path& tour) {
   8.132 +        _path.clear();
   8.133 +
   8.134 +        if (_gr.nodeNum() == 0) return _sum = 0;
   8.135 +        else if (_gr.nodeNum() == 1) {
   8.136 +          _path.push_back(_gr(0));
   8.137 +          return _sum = 0;
   8.138 +        }
   8.139 +        else if (_gr.nodeNum() == 2) {
   8.140 +          _path.push_back(_gr(0));
   8.141 +          _path.push_back(_gr(1));
   8.142 +          return _sum = 2 * _cost[_gr.edge(_gr(0), _gr(1))];
   8.143 +        }
   8.144 +
   8.145 +        _plist.resize(2*_gr.nodeNum());
   8.146 +        typename Path::ArcIt it(tour);
   8.147 +        int first = _gr.id(_gr.source(it)),
   8.148 +            prev = first,
   8.149 +            curr = _gr.id(_gr.target(it)),
   8.150 +            next = -1;
   8.151 +        _plist[2*first+1] = curr;
   8.152 +        for (++it; it != INVALID; ++it) {
   8.153 +          next = _gr.id(_gr.target(it));
   8.154 +          _plist[2*curr] = prev;
   8.155 +          _plist[2*curr+1] = next;
   8.156 +          prev = curr;
   8.157 +          curr = next;
   8.158 +        }
   8.159 +        _plist[2*first] = prev;
   8.160 +
   8.161 +        return start();
   8.162 +      }
   8.163 +
   8.164 +      /// \brief Runs the algorithm starting from the given tour.
   8.165 +      ///
   8.166 +      /// This function runs the algorithm starting from the given tour
   8.167 +      /// (node sequence).
   8.168 +      ///
   8.169 +      /// \param tour A vector that stores all <tt>Node</tt>s of the graph
   8.170 +      /// in the desired order.
   8.171 +      ///
   8.172 +      /// \return The total cost of the found tour.
   8.173 +      Cost run(const std::vector<Node>& tour) {
   8.174 +        _path.clear();
   8.175 +
   8.176 +        if (_gr.nodeNum() == 0) return _sum = 0;
   8.177 +        else if (_gr.nodeNum() == 1) {
   8.178 +          _path.push_back(_gr(0));
   8.179 +          return _sum = 0;
   8.180 +        }
   8.181 +        else if (_gr.nodeNum() == 2) {
   8.182 +          _path.push_back(_gr(0));
   8.183 +          _path.push_back(_gr(1));
   8.184 +          return _sum = 2 * _cost[_gr.edge(_gr(0), _gr(1))];
   8.185 +        }
   8.186 +
   8.187 +        _plist.resize(2*_gr.nodeNum());
   8.188 +        typename std::vector<Node>::const_iterator it = tour.begin();
   8.189 +        int first = _gr.id(*it),
   8.190 +            prev = first,
   8.191 +            curr = _gr.id(*(++it)),
   8.192 +            next = -1;
   8.193 +        _plist[2*first+1] = curr;
   8.194 +        for (++it; it != tour.end(); ++it) {
   8.195 +          next = _gr.id(*it);
   8.196 +          _plist[2*curr] = prev;
   8.197 +          _plist[2*curr+1] = next;
   8.198 +          prev = curr;
   8.199 +          curr = next;
   8.200 +        }
   8.201 +        _plist[2*first] = curr;
   8.202 +        _plist[2*curr] = prev;
   8.203 +        _plist[2*curr+1] = first;
   8.204 +
   8.205 +        return start();
   8.206 +      }
   8.207 +
   8.208 +      /// @}
   8.209 +
   8.210 +      /// \name Query Functions
   8.211 +      /// @{
   8.212 +
   8.213 +      /// \brief The total cost of the found tour.
   8.214 +      ///
   8.215 +      /// This function returns the total cost of the found tour.
   8.216 +      ///
   8.217 +      /// \pre run() must be called before using this function.
   8.218 +      Cost tourCost() const {
   8.219 +        return _sum;
   8.220 +      }
   8.221 +
   8.222 +      /// \brief Returns a const reference to the node sequence of the
   8.223 +      /// found tour.
   8.224 +      ///
   8.225 +      /// This function returns a const reference to a vector
   8.226 +      /// that stores the node sequence of the found tour.
   8.227 +      ///
   8.228 +      /// \pre run() must be called before using this function.
   8.229 +      const std::vector<Node>& tourNodes() const {
   8.230 +        return _path;
   8.231 +      }
   8.232 +
   8.233 +      /// \brief Gives back the node sequence of the found tour.
   8.234 +      ///
   8.235 +      /// This function copies the node sequence of the found tour into
   8.236 +      /// an STL container through the given output iterator. The
   8.237 +      /// <tt>value_type</tt> of the container must be <tt>FullGraph::Node</tt>.
   8.238 +      /// For example,
   8.239 +      /// \code
   8.240 +      /// std::vector<FullGraph::Node> nodes(countNodes(graph));
   8.241 +      /// tsp.tourNodes(nodes.begin());
   8.242 +      /// \endcode
   8.243 +      /// or
   8.244 +      /// \code
   8.245 +      /// std::list<FullGraph::Node> nodes;
   8.246 +      /// tsp.tourNodes(std::back_inserter(nodes));
   8.247 +      /// \endcode
   8.248 +      ///
   8.249 +      /// \pre run() must be called before using this function.
   8.250 +      template <typename Iterator>
   8.251 +      void tourNodes(Iterator out) const {
   8.252 +        std::copy(_path.begin(), _path.end(), out);
   8.253 +      }
   8.254 +
   8.255 +      /// \brief Gives back the found tour as a path.
   8.256 +      ///
   8.257 +      /// This function copies the found tour as a list of arcs/edges into
   8.258 +      /// the given \ref concept::Path "path structure".
   8.259 +      ///
   8.260 +      /// \pre run() must be called before using this function.
   8.261 +      template <typename Path>
   8.262 +      void tour(Path &path) const {
   8.263 +        path.clear();
   8.264 +        for (int i = 0; i < int(_path.size()) - 1; ++i) {
   8.265 +          path.addBack(_gr.arc(_path[i], _path[i+1]));
   8.266 +        }
   8.267 +        if (int(_path.size()) >= 2) {
   8.268 +          path.addBack(_gr.arc(_path.back(), _path.front()));
   8.269 +        }
   8.270 +      }
   8.271 +
   8.272 +      /// @}
   8.273 +
   8.274 +    private:
   8.275 +
   8.276 +      // Iterator class for the linked list storage of the tour
   8.277 +      class PathListIt {
   8.278 +        public:
   8.279 +          PathListIt(const std::vector<int> &pl, int i=0)
   8.280 +            : plist(&pl), act(i), last(pl[2*act]) {}
   8.281 +          PathListIt(const std::vector<int> &pl, int i, int l)
   8.282 +            : plist(&pl), act(i), last(l) {}
   8.283 +
   8.284 +          int nextIndex() const {
   8.285 +            return (*plist)[2*act] == last ? 2*act+1 : 2*act;
   8.286 +          }
   8.287 +
   8.288 +          int prevIndex() const {
   8.289 +            return (*plist)[2*act] == last ? 2*act : 2*act+1;
   8.290 +          }
   8.291 +
   8.292 +          int next() const {
   8.293 +            int x = (*plist)[2*act];
   8.294 +            return x == last ? (*plist)[2*act+1] : x;
   8.295 +          }
   8.296 +
   8.297 +          int prev() const {
   8.298 +            return last;
   8.299 +          }
   8.300 +
   8.301 +          PathListIt& operator++() {
   8.302 +            int tmp = act;
   8.303 +            act = next();
   8.304 +            last = tmp;
   8.305 +            return *this;
   8.306 +          }
   8.307 +
   8.308 +          operator int() const {
   8.309 +            return act;
   8.310 +          }
   8.311 +
   8.312 +        private:
   8.313 +          const std::vector<int> *plist;
   8.314 +          int act;
   8.315 +          int last;
   8.316 +      };
   8.317 +
   8.318 +      // Checks and applies 2-opt move (if it improves the tour)
   8.319 +      bool checkOpt2(const PathListIt& i, const PathListIt& j) {
   8.320 +        Node u  = _gr.nodeFromId(i),
   8.321 +             un = _gr.nodeFromId(i.next()),
   8.322 +             v  = _gr.nodeFromId(j),
   8.323 +             vn = _gr.nodeFromId(j.next());
   8.324 +
   8.325 +        if (_cost[_gr.edge(u, un)] + _cost[_gr.edge(v, vn)] >
   8.326 +            _cost[_gr.edge(u, v)] + _cost[_gr.edge(un, vn)])
   8.327 +        {
   8.328 +          _plist[PathListIt(_plist, i.next(), i).prevIndex()] = j.next();
   8.329 +          _plist[PathListIt(_plist, j.next(), j).prevIndex()] = i.next();
   8.330 +
   8.331 +          _plist[i.nextIndex()] = j;
   8.332 +          _plist[j.nextIndex()] = i;
   8.333 +
   8.334 +          return true;
   8.335 +        }
   8.336 +
   8.337 +        return false;
   8.338 +     }
   8.339 +
   8.340 +      // Executes the algorithm from the initial tour
   8.341 +      Cost start() {
   8.342 +
   8.343 +      restart_search:
   8.344 +        for (PathListIt i(_plist); true; ++i) {
   8.345 +          PathListIt j = i;
   8.346 +          if (++j == 0 || ++j == 0) break;
   8.347 +          for (; j != 0 && j != i.prev(); ++j) {
   8.348 +            if (checkOpt2(i, j))
   8.349 +              goto restart_search;
   8.350 +          }
   8.351 +        }
   8.352 +
   8.353 +        PathListIt i(_plist);
   8.354 +        _path.push_back(_gr.nodeFromId(i));
   8.355 +        for (++i; i != 0; ++i)
   8.356 +          _path.push_back(_gr.nodeFromId(i));
   8.357 +
   8.358 +        _sum = _cost[_gr.edge(_path.back(), _path.front())];
   8.359 +        for (int i = 0; i < int(_path.size())-1; ++i) {
   8.360 +          _sum += _cost[_gr.edge(_path[i], _path[i+1])];
   8.361 +        }
   8.362 +
   8.363 +        return _sum;
   8.364 +      }
   8.365 +
   8.366 +  };
   8.367 +
   8.368 +}; // namespace lemon
   8.369 +
   8.370 +#endif
     9.1 --- a/test/CMakeLists.txt	Tue Feb 12 07:15:52 2013 +0100
     9.2 +++ b/test/CMakeLists.txt	Fri Mar 01 17:59:08 2013 +0100
     9.3 @@ -52,6 +52,7 @@
     9.4    random_test
     9.5    suurballe_test
     9.6    time_measure_test
     9.7 +  tsp_test
     9.8    unionfind_test
     9.9  )
    9.10  
    10.1 --- /dev/null	Thu Jan 01 00:00:00 1970 +0000
    10.2 +++ b/test/tsp_test.cc	Fri Mar 01 17:59:08 2013 +0100
    10.3 @@ -0,0 +1,283 @@
    10.4 +/* -*- mode: C++; indent-tabs-mode: nil; -*-
    10.5 + *
    10.6 + * This file is a part of LEMON, a generic C++ optimization library.
    10.7 + *
    10.8 + * Copyright (C) 2003-2010
    10.9 + * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
   10.10 + * (Egervary Research Group on Combinatorial Optimization, EGRES).
   10.11 + *
   10.12 + * Permission to use, modify and distribute this software is granted
   10.13 + * provided that this copyright notice appears in all copies. For
   10.14 + * precise terms see the accompanying LICENSE file.
   10.15 + *
   10.16 + * This software is provided "AS IS" with no warranty of any kind,
   10.17 + * express or implied, and with no claim as to its suitability for any
   10.18 + * purpose.
   10.19 + *
   10.20 + */
   10.21 +
   10.22 +#include <iostream>
   10.23 +
   10.24 +#include <lemon/full_graph.h>
   10.25 +#include <lemon/math.h>
   10.26 +#include <lemon/maps.h>
   10.27 +#include <lemon/random.h>
   10.28 +#include <lemon/dim2.h>
   10.29 +
   10.30 +#include <lemon/nearest_neighbor_tsp.h>
   10.31 +#include <lemon/greedy_tsp.h>
   10.32 +#include <lemon/insertion_tsp.h>
   10.33 +#include <lemon/christofides_tsp.h>
   10.34 +#include <lemon/opt2_tsp.h>
   10.35 +
   10.36 +#include "test_tools.h"
   10.37 +
   10.38 +using namespace lemon;
   10.39 +
   10.40 +// // Tests checkMetricCost() function
   10.41 +// void metricCostTest() {
   10.42 +//   GRAPH_TYPEDEFS(FullGraph);
   10.43 +//   FullGraph g(10);
   10.44 +//   check(checkMetricCost(g, constMap<Edge>(0)), "Wrong checkMetricCost()");
   10.45 +//   check(checkMetricCost(g, constMap<Edge>(1)), "Wrong checkMetricCost()");
   10.46 +//   check(!checkMetricCost(g, constMap<Edge>(-1)), "Wrong checkMetricCost()");
   10.47 +//   
   10.48 +//   FullGraph::EdgeMap<float> cost(g);
   10.49 +//   for (NodeIt u(g); u != INVALID; ++u) {
   10.50 +//     for (NodeIt v(g); v != INVALID; ++v) {
   10.51 +//       if (u == v) continue;
   10.52 +//       float x1 = g.id(u), x2 = g.id(v);
   10.53 +//       float y1 = x1 * x1, y2 = x2 * x2;
   10.54 +//       cost[g.edge(u, v)] = std::sqrt((x2-x1)*(x2-x1) + (y2-y1)*(y2-y1));
   10.55 +//     }
   10.56 +//   }
   10.57 +//   check(checkMetricCost(g, cost), "Wrong checkMetricCost()");
   10.58 +//   float eps = Tolerance<float>::defaultEpsilon();
   10.59 +//   cost[g.edge(g(0), g(9))] =
   10.60 +//     cost[g.edge(g(0), g(8))] + cost[g.edge(g(8), g(9))] + eps * 2;
   10.61 +//   check(!checkMetricCost(g, cost), "Wrong checkMetricCost()");
   10.62 +//   check(checkMetricCost(g, cost, Tolerance<float>(eps * 4)),
   10.63 +//     "Wrong checkMetricCost()");
   10.64 +// }
   10.65 +
   10.66 +// Checks tour validity
   10.67 +template <typename Container>
   10.68 +bool checkTour(const FullGraph &gr, const Container &p) {
   10.69 +  FullGraph::NodeMap<bool> used(gr, false);
   10.70 +  
   10.71 +  int node_cnt = 0;
   10.72 +  for (typename Container::const_iterator it = p.begin(); it != p.end(); ++it) {
   10.73 +    FullGraph::Node node = *it;
   10.74 +    if (used[node]) return false;
   10.75 +    used[node] = true;
   10.76 +    ++node_cnt;
   10.77 +  }
   10.78 +  
   10.79 +  return (node_cnt == gr.nodeNum());
   10.80 +}
   10.81 +
   10.82 +// Checks tour validity
   10.83 +bool checkTourPath(const FullGraph &gr, const Path<FullGraph> &p) {
   10.84 +  FullGraph::NodeMap<bool> used(gr, false);
   10.85 +  
   10.86 +  if (!checkPath(gr, p)) return false;
   10.87 +  if (gr.nodeNum() <= 1 && p.length() != 0) return false;
   10.88 +  if (gr.nodeNum() > 1 && p.length() != gr.nodeNum()) return false;
   10.89 +
   10.90 +  for (int i = 0; i < p.length(); ++i) {
   10.91 +    if (used[gr.target(p.nth(i))]) return false;
   10.92 +    used[gr.target(p.nth(i))] = true;
   10.93 +  }
   10.94 +  return true;
   10.95 +}
   10.96 +
   10.97 +// Checks tour cost
   10.98 +template <typename CostMap>
   10.99 +bool checkCost(const FullGraph &gr, const std::vector<FullGraph::Node> &p,
  10.100 +               const CostMap &cost, typename CostMap::Value total)
  10.101 +{
  10.102 +  typedef typename CostMap::Value Cost;
  10.103 +
  10.104 +  Cost s = 0;
  10.105 +  for (int i = 0; i < int(p.size()) - 1; ++i)
  10.106 +    s += cost[gr.edge(p[i], p[i+1])];
  10.107 +  if (int(p.size()) >= 2)
  10.108 +    s += cost[gr.edge(p.back(), p.front())];
  10.109 +
  10.110 +  return !Tolerance<Cost>().different(s, total);
  10.111 +}
  10.112 +
  10.113 +// Checks tour cost
  10.114 +template <typename CostMap>
  10.115 +bool checkCost(const FullGraph &, const Path<FullGraph> &p,
  10.116 +               const CostMap &cost, typename CostMap::Value total)
  10.117 +{
  10.118 +  typedef typename CostMap::Value Cost;
  10.119 +
  10.120 +  Cost s = 0;
  10.121 +  for (int i = 0; i < p.length(); ++i)
  10.122 +    s += cost[p.nth(i)];
  10.123 +
  10.124 +  return !Tolerance<Cost>().different(s, total);
  10.125 +}
  10.126 +
  10.127 +// Tests a TSP algorithm on small graphs
  10.128 +template <typename TSP>
  10.129 +void tspTestSmall(const std::string &alg_name) {
  10.130 +  GRAPH_TYPEDEFS(FullGraph);
  10.131 +
  10.132 +  for (int n = 0; n <= 5; ++n) {
  10.133 +    FullGraph g(n);
  10.134 +    unsigned nsize = n;
  10.135 +    int esize = n <= 1 ? 0 : n;
  10.136 +
  10.137 +    TSP alg(g, constMap<Edge, int>(1));
  10.138 +
  10.139 +    check(alg.run() == esize, alg_name + ": Wrong total cost");
  10.140 +    check(alg.tourCost() == esize, alg_name + ": Wrong total cost");
  10.141 +
  10.142 +    std::list<Node> list1(nsize), list2;
  10.143 +    std::vector<Node> vec1(nsize), vec2;
  10.144 +    alg.tourNodes(list1.begin());
  10.145 +    alg.tourNodes(vec1.begin());
  10.146 +    alg.tourNodes(std::front_inserter(list2));
  10.147 +    alg.tourNodes(std::back_inserter(vec2));
  10.148 +    check(checkTour(g, alg.tourNodes()), alg_name + ": Wrong node sequence");
  10.149 +    check(checkTour(g, list1), alg_name + ": Wrong node sequence");
  10.150 +    check(checkTour(g, vec1), alg_name + ": Wrong node sequence");
  10.151 +    check(checkTour(g, list2), alg_name + ": Wrong node sequence");
  10.152 +    check(checkTour(g, vec2), alg_name + ": Wrong node sequence");
  10.153 +    check(checkCost(g, vec1, constMap<Edge, int>(1), esize),
  10.154 +      alg_name + ": Wrong tour cost");
  10.155 +
  10.156 +    SimplePath<FullGraph> path;
  10.157 +    alg.tour(path);
  10.158 +    check(path.length() == esize, alg_name + ": Wrong tour");
  10.159 +    check(checkTourPath(g, path), alg_name + ": Wrong tour");
  10.160 +    check(checkCost(g, path, constMap<Edge, int>(1), esize),
  10.161 +      alg_name + ": Wrong tour cost");
  10.162 +  }
  10.163 +}
  10.164 +
  10.165 +// Tests a TSP algorithm on random graphs
  10.166 +template <typename TSP>
  10.167 +void tspTestRandom(const std::string &alg_name) {
  10.168 +  GRAPH_TYPEDEFS(FullGraph);
  10.169 +
  10.170 +  FullGraph g(20);
  10.171 +  FullGraph::NodeMap<dim2::Point<double> > pos(g);
  10.172 +  DoubleEdgeMap cost(g);
  10.173 +
  10.174 +  TSP alg(g, cost);
  10.175 +  Opt2Tsp<DoubleEdgeMap > opt2(g, cost);
  10.176 +
  10.177 +  for (int i = 1; i <= 3; i++) {
  10.178 +    for (NodeIt u(g); u != INVALID; ++u) {
  10.179 +      pos[u] = dim2::Point<double>(rnd(), rnd());
  10.180 +    }
  10.181 +    for (NodeIt u(g); u != INVALID; ++u) {
  10.182 +      for (NodeIt v(g); v != INVALID; ++v) {
  10.183 +        if (u == v) continue;
  10.184 +        cost[g.edge(u, v)] = (pos[u] - pos[v]).normSquare();
  10.185 +      }
  10.186 +    }
  10.187 +    
  10.188 +    check(alg.run() > 0, alg_name + ": Wrong total cost");
  10.189 +
  10.190 +    std::vector<Node> vec;
  10.191 +    alg.tourNodes(std::back_inserter(vec));
  10.192 +    check(checkTour(g, vec), alg_name + ": Wrong node sequence");
  10.193 +    check(checkCost(g, vec, cost, alg.tourCost()),
  10.194 +      alg_name + ": Wrong tour cost");
  10.195 +
  10.196 +    SimplePath<FullGraph> path;
  10.197 +    alg.tour(path);
  10.198 +    check(checkTourPath(g, path), alg_name + ": Wrong tour");
  10.199 +    check(checkCost(g, path, cost, alg.tourCost()),
  10.200 +      alg_name + ": Wrong tour cost");
  10.201 +    
  10.202 +    check(!Tolerance<double>().less(alg.tourCost(), opt2.run(alg.tourNodes())),
  10.203 +      "2-opt improvement: Wrong total cost");
  10.204 +    check(checkTour(g, opt2.tourNodes()),
  10.205 +      "2-opt improvement: Wrong node sequence");
  10.206 +    check(checkCost(g, opt2.tourNodes(), cost, opt2.tourCost()),
  10.207 +      "2-opt improvement: Wrong tour cost");
  10.208 +    
  10.209 +    check(!Tolerance<double>().less(alg.tourCost(), opt2.run(path)),
  10.210 +      "2-opt improvement: Wrong total cost");
  10.211 +    check(checkTour(g, opt2.tourNodes()),
  10.212 +      "2-opt improvement: Wrong node sequence");
  10.213 +    check(checkCost(g, opt2.tourNodes(), cost, opt2.tourCost()),
  10.214 +      "2-opt improvement: Wrong tour cost");
  10.215 +  }
  10.216 +}
  10.217 +
  10.218 +// Algorithm class for Nearest Insertion 
  10.219 +template <typename CM>
  10.220 +class NearestInsertionTsp : public InsertionTsp<CM> {
  10.221 +public:
  10.222 +  NearestInsertionTsp(const FullGraph &gr, const CM &cost)
  10.223 +    : InsertionTsp<CM>(gr, cost) {}
  10.224 +  typename CM::Value run() {
  10.225 +    return InsertionTsp<CM>::run(InsertionTsp<CM>::NEAREST);
  10.226 +  }
  10.227 +};
  10.228 +
  10.229 +// Algorithm class for Farthest Insertion 
  10.230 +template <typename CM>
  10.231 +class FarthestInsertionTsp : public InsertionTsp<CM> {
  10.232 +public:
  10.233 +  FarthestInsertionTsp(const FullGraph &gr, const CM &cost)
  10.234 +    : InsertionTsp<CM>(gr, cost) {}
  10.235 +  typename CM::Value run() {
  10.236 +    return InsertionTsp<CM>::run(InsertionTsp<CM>::FARTHEST);
  10.237 +  }
  10.238 +};
  10.239 +
  10.240 +// Algorithm class for Cheapest Insertion 
  10.241 +template <typename CM>
  10.242 +class CheapestInsertionTsp : public InsertionTsp<CM> {
  10.243 +public:
  10.244 +  CheapestInsertionTsp(const FullGraph &gr, const CM &cost)
  10.245 +    : InsertionTsp<CM>(gr, cost) {}
  10.246 +  typename CM::Value run() {
  10.247 +    return InsertionTsp<CM>::run(InsertionTsp<CM>::CHEAPEST);
  10.248 +  }
  10.249 +};
  10.250 +
  10.251 +// Algorithm class for Random Insertion 
  10.252 +template <typename CM>
  10.253 +class RandomInsertionTsp : public InsertionTsp<CM> {
  10.254 +public:
  10.255 +  RandomInsertionTsp(const FullGraph &gr, const CM &cost)
  10.256 +    : InsertionTsp<CM>(gr, cost) {}
  10.257 +  typename CM::Value run() {
  10.258 +    return InsertionTsp<CM>::run(InsertionTsp<CM>::RANDOM);
  10.259 +  }
  10.260 +};
  10.261 +
  10.262 +int main() {
  10.263 +  GRAPH_TYPEDEFS(FullGraph);
  10.264 +
  10.265 +  // metricCostTest();
  10.266 +
  10.267 +  tspTestSmall<NearestNeighborTsp<ConstMap<Edge, int> > >("Nearest Neighbor");
  10.268 +  tspTestSmall<GreedyTsp<ConstMap<Edge, int> > >("Greedy");
  10.269 +  tspTestSmall<NearestInsertionTsp<ConstMap<Edge, int> > >("Nearest Insertion");
  10.270 +  tspTestSmall<FarthestInsertionTsp<ConstMap<Edge, int> > >("Farthest Insertion");
  10.271 +  tspTestSmall<CheapestInsertionTsp<ConstMap<Edge, int> > >("Cheapest Insertion");
  10.272 +  tspTestSmall<RandomInsertionTsp<ConstMap<Edge, int> > >("Random Insertion");
  10.273 +  tspTestSmall<ChristofidesTsp<ConstMap<Edge, int> > >("Christofides");
  10.274 +  tspTestSmall<Opt2Tsp<ConstMap<Edge, int> > >("2-opt");
  10.275 +
  10.276 +  tspTestRandom<NearestNeighborTsp<DoubleEdgeMap > >("Nearest Neighbor");
  10.277 +  tspTestRandom<GreedyTsp<DoubleEdgeMap > >("Greedy");
  10.278 +  tspTestRandom<NearestInsertionTsp<DoubleEdgeMap > >("Nearest Insertion");
  10.279 +  tspTestRandom<FarthestInsertionTsp<DoubleEdgeMap > >("Farthest Insertion");
  10.280 +  tspTestRandom<CheapestInsertionTsp<DoubleEdgeMap > >("Cheapest Insertion");
  10.281 +  tspTestRandom<RandomInsertionTsp<DoubleEdgeMap > >("Random Insertion");
  10.282 +  tspTestRandom<ChristofidesTsp<DoubleEdgeMap > >("Christofides");
  10.283 +  tspTestRandom<Opt2Tsp<DoubleEdgeMap > >("2-opt");
  10.284 +
  10.285 +  return 0;
  10.286 +}