1.1 --- a/lemon/nearest_neighbor_tsp.h Sat Jan 08 22:49:09 2011 +0100
1.2 +++ b/lemon/nearest_neighbor_tsp.h Sat Jan 08 22:51:16 2011 +0100
1.3 @@ -1,145 +1,216 @@
1.4 +/* -*- mode: C++; indent-tabs-mode: nil; -*-
1.5 + *
1.6 + * This file is a part of LEMON, a generic C++ optimization library.
1.7 + *
1.8 + * Copyright (C) 2003-2010
1.9 + * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
1.10 + * (Egervary Research Group on Combinatorial Optimization, EGRES).
1.11 + *
1.12 + * Permission to use, modify and distribute this software is granted
1.13 + * provided that this copyright notice appears in all copies. For
1.14 + * precise terms see the accompanying LICENSE file.
1.15 + *
1.16 + * This software is provided "AS IS" with no warranty of any kind,
1.17 + * express or implied, and with no claim as to its suitability for any
1.18 + * purpose.
1.19 + *
1.20 + */
1.21 +
1.22 #ifndef LEMON_NEAREST_NEIGHBOUR_TSP_H
1.23 #define LEMON_NEAREST_NEIGHBOUR_TSP_H
1.24
1.25 +/// \ingroup tsp
1.26 +/// \file
1.27 +/// \brief Nearest neighbor algorithm for symmetric TSP
1.28 +
1.29 #include <deque>
1.30 +#include <limits>
1.31 #include <lemon/full_graph.h>
1.32 -#include <lemon/path.h>
1.33 #include <lemon/maps.h>
1.34
1.35 namespace lemon {
1.36 -
1.37 - namespace nn_helper {
1.38 - template <class L>
1.39 - L dequeConvert(const std::deque<FullGraph::Node> &_path) {
1.40 - return L(_path.begin(), _path.end());
1.41 - }
1.42
1.43 - template <>
1.44 - std::deque<FullGraph::Node> dequeConvert(const std::deque<FullGraph::Node> &_path) {
1.45 - return _path;
1.46 - }
1.47 - }
1.48 -
1.49 + /// \brief Nearest neighbor algorithm for symmetric TSP.
1.50 + ///
1.51 + /// NearestNeighborTsp implements the nearest neighbor heuristic for solving
1.52 + /// symmetric \ref tsp "TSP".
1.53 + ///
1.54 + /// This is probably the simplest TSP heuristic.
1.55 + /// It starts with a minimum cost edge and at each step, it connects the
1.56 + /// nearest unvisited node to the current path.
1.57 + /// Finally, it connects the two end points of the path to form a tour.
1.58 + ///
1.59 + /// This method runs in O(n<sup>2</sup>) time.
1.60 + /// It quickly finds an effectively short tour for most TSP
1.61 + /// instances, but in special cases, it could yield a really bad
1.62 + /// (or even the worst) solution.
1.63 + ///
1.64 + /// \tparam CM Type of the cost map.
1.65 template <typename CM>
1.66 - class NearestNeighborTsp {
1.67 + class NearestNeighborTsp
1.68 + {
1.69 + public:
1.70 +
1.71 + /// Type of the cost map
1.72 + typedef CM CostMap;
1.73 + /// Type of the edge costs
1.74 + typedef typename CM::Value Cost;
1.75 +
1.76 private:
1.77 +
1.78 GRAPH_TYPEDEFS(FullGraph);
1.79
1.80 + const FullGraph &_gr;
1.81 + const CostMap &_cost;
1.82 + Cost _sum;
1.83 + std::deque<Node> _path;
1.84 +
1.85 public:
1.86 - typedef CM CostMap;
1.87 - typedef typename CM::Value Cost;
1.88 -
1.89 - NearestNeighborTsp(const FullGraph &gr, const CostMap &cost) : _gr(gr), _cost(cost) {}
1.90
1.91 + /// \brief Constructor
1.92 + ///
1.93 + /// Constructor.
1.94 + /// \param gr The \ref FullGraph "full graph" the algorithm runs on.
1.95 + /// \param cost The cost map.
1.96 + NearestNeighborTsp(const FullGraph &gr, const CostMap &cost)
1.97 + : _gr(gr), _cost(cost) {}
1.98 +
1.99 + /// \name Execution Control
1.100 + /// @{
1.101 +
1.102 + /// \brief Runs the algorithm.
1.103 + ///
1.104 + /// This function runs the algorithm.
1.105 + ///
1.106 + /// \return The total cost of the found tour.
1.107 Cost run() {
1.108 _path.clear();
1.109
1.110 + if (_gr.nodeNum() == 0) return _sum = 0;
1.111 + else if (_gr.nodeNum() == 1) {
1.112 + _path.push_back(_gr(0));
1.113 + return _sum = 0;
1.114 + }
1.115 +
1.116 Edge min_edge1 = INVALID,
1.117 min_edge2 = INVALID;
1.118 -
1.119 +
1.120 min_edge1 = mapMin(_gr, _cost);
1.121 -
1.122 - FullGraph::NodeMap<bool> used(_gr, false);
1.123 -
1.124 - Node n1 = _gr.u(min_edge1),
1.125 + Node n1 = _gr.u(min_edge1),
1.126 n2 = _gr.v(min_edge1);
1.127 -
1.128 _path.push_back(n1);
1.129 _path.push_back(n2);
1.130
1.131 + FullGraph::NodeMap<bool> used(_gr, false);
1.132 used[n1] = true;
1.133 used[n2] = true;
1.134
1.135 min_edge1 = INVALID;
1.136 -
1.137 while (int(_path.size()) != _gr.nodeNum()) {
1.138 if (min_edge1 == INVALID) {
1.139 - for (IncEdgeIt e(_gr, n1); e!=INVALID; ++e) {
1.140 - if (!used[_gr.runningNode(e)]) {
1.141 - if (min_edge1==INVALID || _cost[min_edge1] > _cost[e])
1.142 - min_edge1 = e;
1.143 + for (IncEdgeIt e(_gr, n1); e != INVALID; ++e) {
1.144 + if (!used[_gr.runningNode(e)] &&
1.145 + (_cost[e] < _cost[min_edge1] || min_edge1 == INVALID)) {
1.146 + min_edge1 = e;
1.147 }
1.148 }
1.149 }
1.150
1.151 if (min_edge2 == INVALID) {
1.152 - for (IncEdgeIt e(_gr, n2); e!=INVALID; ++e) {
1.153 - if (!used[_gr.runningNode(e)]) {
1.154 - if (min_edge2==INVALID || _cost[min_edge2] > _cost[e])
1.155 - min_edge2 = e;
1.156 + for (IncEdgeIt e(_gr, n2); e != INVALID; ++e) {
1.157 + if (!used[_gr.runningNode(e)] &&
1.158 + (_cost[e] < _cost[min_edge2] || min_edge2 == INVALID)) {
1.159 + min_edge2 = e;
1.160 }
1.161 }
1.162 }
1.163
1.164 - if ( _cost[min_edge1] < _cost[min_edge2] ) {
1.165 - n1 = (_gr.u(min_edge1) == n1) ? _gr.v(min_edge1) : _gr.u(min_edge1);
1.166 + if (_cost[min_edge1] < _cost[min_edge2]) {
1.167 + n1 = _gr.oppositeNode(n1, min_edge1);
1.168 _path.push_front(n1);
1.169
1.170 used[n1] = true;
1.171 min_edge1 = INVALID;
1.172
1.173 - if (_gr.u(min_edge2)==n1 || _gr.v(min_edge2)==n1)
1.174 + if (_gr.u(min_edge2) == n1 || _gr.v(min_edge2) == n1)
1.175 min_edge2 = INVALID;
1.176 } else {
1.177 - n2 = (_gr.u(min_edge2) == n2) ? _gr.v(min_edge2) : _gr.u(min_edge2);
1.178 + n2 = _gr.oppositeNode(n2, min_edge2);
1.179 _path.push_back(n2);
1.180
1.181 used[n2] = true;
1.182 min_edge2 = INVALID;
1.183
1.184 - if (_gr.u(min_edge1)==n2 || _gr.v(min_edge1)==n2)
1.185 + if (_gr.u(min_edge1) == n2 || _gr.v(min_edge1) == n2)
1.186 min_edge1 = INVALID;
1.187 }
1.188 }
1.189
1.190 - _sum = _cost[ _gr.edge(_path.back(), _path.front()) ];
1.191 - for (unsigned int i=0; i<_path.size()-1; ++i)
1.192 - _sum += _cost[ _gr.edge(_path[i], _path[i+1]) ];
1.193 + _sum = _cost[_gr.edge(_path.back(), _path.front())];
1.194 + for (int i = 0; i < int(_path.size())-1; ++i) {
1.195 + _sum += _cost[_gr.edge(_path[i], _path[i+1])];
1.196 + }
1.197
1.198 return _sum;
1.199 }
1.200
1.201 -
1.202 - template <typename L>
1.203 - void tourNodes(L &container) {
1.204 - container(nn_helper::dequeConvert<L>(_path));
1.205 + /// @}
1.206 +
1.207 + /// \name Query Functions
1.208 + /// @{
1.209 +
1.210 + /// \brief The total cost of the found tour.
1.211 + ///
1.212 + /// This function returns the total cost of the found tour.
1.213 + ///
1.214 + /// \pre run() must be called before using this function.
1.215 + Cost tourCost() const {
1.216 + return _sum;
1.217 }
1.218 -
1.219 - template <template <typename> class L>
1.220 - L<Node> tourNodes() {
1.221 - return nn_helper::dequeConvert<L<Node> >(_path);
1.222 - }
1.223
1.224 - const std::deque<Node>& tourNodes() {
1.225 + /// \brief Returns a const reference to the node sequence of the
1.226 + /// found tour.
1.227 + ///
1.228 + /// This function returns a const reference to the internal structure
1.229 + /// that stores the node sequence of the found tour.
1.230 + ///
1.231 + /// \pre run() must be called before using this function.
1.232 + const std::deque<Node>& tourNodes() const {
1.233 return _path;
1.234 }
1.235 -
1.236 - Path<FullGraph> tour() {
1.237 - Path<FullGraph> p;
1.238 - if (_path.size()<2)
1.239 - return p;
1.240 -
1.241 - for (unsigned int i=0; i<_path.size()-1; ++i) {
1.242 - p.addBack(_gr.arc(_path[i], _path[i+1]));
1.243 +
1.244 + /// \brief Gives back the node sequence of the found tour.
1.245 + ///
1.246 + /// This function copies the node sequence of the found tour into
1.247 + /// the given standard container.
1.248 + ///
1.249 + /// \pre run() must be called before using this function.
1.250 + template <typename Container>
1.251 + void tourNodes(Container &container) const {
1.252 + container.assign(_path.begin(), _path.end());
1.253 + }
1.254 +
1.255 + /// \brief Gives back the found tour as a path.
1.256 + ///
1.257 + /// This function copies the found tour as a list of arcs/edges into
1.258 + /// the given \ref concept::Path "path structure".
1.259 + ///
1.260 + /// \pre run() must be called before using this function.
1.261 + template <typename Path>
1.262 + void tour(Path &path) const {
1.263 + path.clear();
1.264 + for (int i = 0; i < int(_path.size()) - 1; ++i) {
1.265 + path.addBack(_gr.arc(_path[i], _path[i+1]));
1.266 }
1.267 - p.addBack(_gr.arc(_path.back(), _path.front()));
1.268 -
1.269 - return p;
1.270 + if (int(_path.size()) >= 2) {
1.271 + path.addBack(_gr.arc(_path.back(), _path.front()));
1.272 + }
1.273 }
1.274 -
1.275 - Cost tourCost() {
1.276 - return _sum;
1.277 - }
1.278 -
1.279
1.280 - private:
1.281 - const FullGraph &_gr;
1.282 - const CostMap &_cost;
1.283 - Cost _sum;
1.284 - std::deque<Node> _path;
1.285 + /// @}
1.286 +
1.287 };
1.288
1.289 -
1.290 }; // namespace lemon
1.291
1.292 #endif