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> ¬used)
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> ¬used)
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> ¬used)
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 +}