1.1 --- a/lemon/greedy_tsp.h Sat Jan 08 22:49:09 2011 +0100
1.2 +++ b/lemon/greedy_tsp.h Sat Jan 08 22:51:16 2011 +0100
1.3 @@ -1,174 +1,236 @@
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_GREEDY_TSP_H
1.23 #define LEMON_GREEDY_TSP_H
1.24
1.25 -#include <lemon/path.h>
1.26 +/// \ingroup tsp
1.27 +/// \file
1.28 +/// \brief Greedy algorithm for symmetric TSP
1.29 +
1.30 +#include <vector>
1.31 +#include <algorithm>
1.32 #include <lemon/full_graph.h>
1.33 #include <lemon/unionfind.h>
1.34 -#include <algorithm>
1.35
1.36 namespace lemon {
1.37
1.38 - namespace greedy_tsp_helper {
1.39 + /// \brief Greedy algorithm for symmetric TSP.
1.40 + ///
1.41 + /// GreedyTsp implements the greedy heuristic for solving
1.42 + /// symmetric \ref tsp "TSP".
1.43 + ///
1.44 + /// This algorithm is quite similar to the \ref NearestNeighborTsp
1.45 + /// "nearest neighbor" heuristic, but it maintains a set of disjoint paths.
1.46 + /// At each step, the shortest possible edge is added to these paths
1.47 + /// as long as it does not create a cycle of less than n edges and it does
1.48 + /// not increase the degree of any node above two.
1.49 + ///
1.50 + /// This method runs in O(n<sup>2</sup>log(n)) time.
1.51 + /// It quickly finds an effectively short tour for most TSP
1.52 + /// instances, but in special cases, it could yield a really bad
1.53 + /// (or even the worst) solution.
1.54 + ///
1.55 + /// \tparam CM Type of the cost map.
1.56 + template <typename CM>
1.57 + class GreedyTsp
1.58 + {
1.59 + public:
1.60
1.61 - template <typename CostMap>
1.62 - class KeyComp {
1.63 - typedef typename CostMap::Key Key;
1.64 - const CostMap &cost;
1.65 + /// Type of the cost map
1.66 + typedef CM CostMap;
1.67 + /// Type of the edge costs
1.68 + typedef typename CM::Value Cost;
1.69 +
1.70 + private:
1.71 +
1.72 + GRAPH_TYPEDEFS(FullGraph);
1.73 +
1.74 + const FullGraph &_gr;
1.75 + const CostMap &_cost;
1.76 + Cost _sum;
1.77 + std::vector<Node> _path;
1.78
1.79 + private:
1.80 +
1.81 + // Functor class to compare edges by their costs
1.82 + class EdgeComp {
1.83 + private:
1.84 + const CostMap &_cost;
1.85 +
1.86 public:
1.87 - KeyComp(const CostMap &_cost) : cost(_cost) {}
1.88 -
1.89 - bool operator() (const Key &a, const Key &b) const {
1.90 - return cost[a] < cost[b];
1.91 + EdgeComp(const CostMap &cost) : _cost(cost) {}
1.92 +
1.93 + bool operator()(const Edge &a, const Edge &b) const {
1.94 + return _cost[a] < _cost[b];
1.95 }
1.96 - };
1.97 + };
1.98
1.99 -
1.100 - template <class L>
1.101 - L vectorConvert(const std::vector<FullGraph::Node> &_path) {
1.102 - return L(_path.begin(), _path.end());
1.103 - }
1.104 -
1.105 - template <>
1.106 - std::vector<FullGraph::Node> vectorConvert(const std::vector<FullGraph::Node> &_path) {
1.107 - return _path;
1.108 - }
1.109 -
1.110 - }
1.111 + public:
1.112
1.113 + /// \brief Constructor
1.114 + ///
1.115 + /// Constructor.
1.116 + /// \param gr The \ref FullGraph "full graph" the algorithm runs on.
1.117 + /// \param cost The cost map.
1.118 + GreedyTsp(const FullGraph &gr, const CostMap &cost)
1.119 + : _gr(gr), _cost(cost) {}
1.120
1.121 - template <typename CM>
1.122 - class GreedyTsp {
1.123 - private:
1.124 - GRAPH_TYPEDEFS(FullGraph);
1.125 -
1.126 - public:
1.127 - typedef CM CostMap;
1.128 - typedef typename CM::Value Cost;
1.129 -
1.130 - GreedyTsp(const FullGraph &gr, const CostMap &cost) : _gr(gr), _cost(cost) {}
1.131 + /// \name Execution Control
1.132 + /// @{
1.133
1.134 + /// \brief Runs the algorithm.
1.135 + ///
1.136 + /// This function runs the algorithm.
1.137 + ///
1.138 + /// \return The total cost of the found tour.
1.139 Cost run() {
1.140 - typedef UnionFind<FullGraph::NodeMap<int> > Union;
1.141 - _nodes.clear();
1.142 -
1.143 - std::vector<int> path;
1.144 - path.resize(_gr.nodeNum()*2, -1);
1.145 -
1.146 - std::vector<typename CostMap::Key> sorted_edges;
1.147 + _path.clear();
1.148 +
1.149 + if (_gr.nodeNum() == 0) return _sum = 0;
1.150 + else if (_gr.nodeNum() == 1) {
1.151 + _path.push_back(_gr(0));
1.152 + return _sum = 0;
1.153 + }
1.154 +
1.155 + std::vector<int> plist;
1.156 + plist.resize(_gr.nodeNum()*2, -1);
1.157 +
1.158 + std::vector<Edge> sorted_edges;
1.159 sorted_edges.reserve(_gr.edgeNum());
1.160 - for (EdgeIt n(_gr); n != INVALID; ++n)
1.161 - sorted_edges.push_back(n);
1.162 + for (EdgeIt e(_gr); e != INVALID; ++e)
1.163 + sorted_edges.push_back(e);
1.164 + std::sort(sorted_edges.begin(), sorted_edges.end(), EdgeComp(_cost));
1.165
1.166 - std::sort(sorted_edges.begin(), sorted_edges.end(), greedy_tsp_helper::KeyComp<CostMap>(_cost));
1.167 + FullGraph::NodeMap<int> item_int_map(_gr);
1.168 + UnionFind<FullGraph::NodeMap<int> > union_find(item_int_map);
1.169 + for (NodeIt n(_gr); n != INVALID; ++n)
1.170 + union_find.insert(n);
1.171
1.172 - FullGraph::NodeMap<int> nodemap(_gr);
1.173 - Union unionfind(nodemap);
1.174 -
1.175 - for (NodeIt n(_gr); n != INVALID; ++n)
1.176 - unionfind.insert(n);
1.177 -
1.178 FullGraph::NodeMap<int> degree(_gr, 0);
1.179
1.180 int nodesNum = 0, i = 0;
1.181 + while (nodesNum != _gr.nodeNum()-1) {
1.182 + Edge e = sorted_edges[i++];
1.183 + Node u = _gr.u(e),
1.184 + v = _gr.v(e);
1.185
1.186 - while ( nodesNum != _gr.nodeNum()-1 ) {
1.187 - const Edge &e = sorted_edges[i];
1.188 -
1.189 - const Node u = _gr.u(e),
1.190 - v = _gr.v(e);
1.191 -
1.192 - if (degree[u]<=1 && degree[v]<=1) {
1.193 - if (unionfind.join(u, v)) {
1.194 + if (degree[u] <= 1 && degree[v] <= 1) {
1.195 + if (union_find.join(u, v)) {
1.196 + const int uid = _gr.id(u),
1.197 + vid = _gr.id(v);
1.198 +
1.199 + plist[uid*2 + degree[u]] = vid;
1.200 + plist[vid*2 + degree[v]] = uid;
1.201 +
1.202 ++degree[u];
1.203 ++degree[v];
1.204 ++nodesNum;
1.205 -
1.206 - const int uid = _gr.id(u),
1.207 - vid = _gr.id(v);
1.208 -
1.209 -
1.210 - path[uid*2 + (path[uid*2]==-1 ? 0 : 1)] = vid;
1.211 - path[vid*2 + (path[vid*2]==-1 ? 0 : 1)] = uid;
1.212 }
1.213 }
1.214 -
1.215 - ++i;
1.216 }
1.217
1.218 -
1.219 for (int i=0, n=-1; i<_gr.nodeNum()*2; ++i) {
1.220 - if (path[i] == -1) {
1.221 + if (plist[i] == -1) {
1.222 if (n==-1) {
1.223 n = i;
1.224 } else {
1.225 - path[n] = i/2;
1.226 - path[i] = n/2;
1.227 + plist[n] = i/2;
1.228 + plist[i] = n/2;
1.229 break;
1.230 }
1.231 }
1.232 }
1.233
1.234 -
1.235 - for (int i=0, j=0, last=-1; i!=_gr.nodeNum(); ++i) {
1.236 - _nodes.push_back(_gr.nodeFromId(j));
1.237 -
1.238 - if (path[2*j] != last) {
1.239 - last = j;
1.240 - j = path[2*j];
1.241 + for (int i=0, next=0, last=-1; i!=_gr.nodeNum(); ++i) {
1.242 + _path.push_back(_gr.nodeFromId(next));
1.243 + if (plist[2*next] != last) {
1.244 + last = next;
1.245 + next = plist[2*next];
1.246 } else {
1.247 - last = j;
1.248 - j = path[2*j+1];
1.249 + last = next;
1.250 + next = plist[2*next+1];
1.251 }
1.252 }
1.253
1.254 - _sum = _cost[_gr.edge(_nodes.back(), _nodes.front())];
1.255 - for (unsigned int i=0; i<_nodes.size()-1; ++i)
1.256 - _sum += _cost[_gr.edge(_nodes[i], _nodes[i+1])];
1.257 + _sum = _cost[_gr.edge(_path.back(), _path.front())];
1.258 + for (int i = 0; i < int(_path.size())-1; ++i) {
1.259 + _sum += _cost[_gr.edge(_path[i], _path[i+1])];
1.260 + }
1.261
1.262 return _sum;
1.263 }
1.264
1.265 + /// @}
1.266
1.267 + /// \name Query Functions
1.268 + /// @{
1.269
1.270 - template <typename L>
1.271 - void tourNodes(L &container) {
1.272 - container(greedy_tsp_helper::vectorConvert<L>(_nodes));
1.273 - }
1.274 -
1.275 - template <template <typename> class L>
1.276 - L<Node> tourNodes() {
1.277 - return greedy_tsp_helper::vectorConvert<L<Node> >(_nodes);
1.278 - }
1.279 -
1.280 - const std::vector<Node>& tourNodes() {
1.281 - return _nodes;
1.282 - }
1.283 -
1.284 - Path<FullGraph> tour() {
1.285 - Path<FullGraph> p;
1.286 - if (_nodes.size()<2)
1.287 - return p;
1.288 -
1.289 - for (unsigned int i=0; i<_nodes.size()-1; ++i) {
1.290 - p.addBack(_gr.arc(_nodes[i], _nodes[i+1]));
1.291 - }
1.292 -
1.293 - p.addBack(_gr.arc(_nodes.back(), _nodes.front()));
1.294 -
1.295 - return p;
1.296 - }
1.297 -
1.298 - Cost tourCost() {
1.299 + /// \brief The total cost of the found tour.
1.300 + ///
1.301 + /// This function returns the total cost of the found tour.
1.302 + ///
1.303 + /// \pre run() must be called before using this function.
1.304 + Cost tourCost() const {
1.305 return _sum;
1.306 }
1.307 -
1.308
1.309 - private:
1.310 - const FullGraph &_gr;
1.311 - const CostMap &_cost;
1.312 - Cost _sum;
1.313 - std::vector<Node> _nodes;
1.314 + /// \brief Returns a const reference to the node sequence of the
1.315 + /// found tour.
1.316 + ///
1.317 + /// This function returns a const reference to the internal structure
1.318 + /// that stores the node sequence of the found tour.
1.319 + ///
1.320 + /// \pre run() must be called before using this function.
1.321 + const std::vector<Node>& tourNodes() const {
1.322 + return _path;
1.323 + }
1.324 +
1.325 + /// \brief Gives back the node sequence of the found tour.
1.326 + ///
1.327 + /// This function copies the node sequence of the found tour into
1.328 + /// the given standard container.
1.329 + ///
1.330 + /// \pre run() must be called before using this function.
1.331 + template <typename Container>
1.332 + void tourNodes(Container &container) const {
1.333 + container.assign(_path.begin(), _path.end());
1.334 + }
1.335 +
1.336 + /// \brief Gives back the found tour as a path.
1.337 + ///
1.338 + /// This function copies the found tour as a list of arcs/edges into
1.339 + /// the given \ref concept::Path "path structure".
1.340 + ///
1.341 + /// \pre run() must be called before using this function.
1.342 + template <typename Path>
1.343 + void tour(Path &path) const {
1.344 + path.clear();
1.345 + for (int i = 0; i < int(_path.size()) - 1; ++i) {
1.346 + path.addBack(_gr.arc(_path[i], _path[i+1]));
1.347 + }
1.348 + if (int(_path.size()) >= 2) {
1.349 + path.addBack(_gr.arc(_path.back(), _path.front()));
1.350 + }
1.351 + }
1.352 +
1.353 + /// @}
1.354 +
1.355 };
1.356
1.357 }; // namespace lemon