1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/lemon/greedy_tsp.h Wed Oct 17 19:14:07 2018 +0200
1.3 @@ -0,0 +1,251 @@
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-2013
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 +/// \ingroup tsp
1.26 +/// \file
1.27 +/// \brief Greedy algorithm for symmetric TSP
1.28 +
1.29 +#include <vector>
1.30 +#include <algorithm>
1.31 +#include <lemon/full_graph.h>
1.32 +#include <lemon/unionfind.h>
1.33 +
1.34 +namespace lemon {
1.35 +
1.36 + /// \ingroup tsp
1.37 + ///
1.38 + /// \brief Greedy algorithm for symmetric TSP.
1.39 + ///
1.40 + /// GreedyTsp implements the greedy heuristic for solving
1.41 + /// symmetric \ref tsp "TSP".
1.42 + ///
1.43 + /// This algorithm is quite similar to the \ref NearestNeighborTsp
1.44 + /// "nearest neighbor" heuristic, but it maintains a set of disjoint paths.
1.45 + /// At each step, the shortest possible edge is added to these paths
1.46 + /// as long as it does not create a cycle of less than n edges and it does
1.47 + /// not increase the degree of any node above two.
1.48 + ///
1.49 + /// This method runs in O(n<sup>2</sup>) time.
1.50 + /// It quickly finds a relatively short tour for most TSP instances,
1.51 + /// but it could also yield a really bad (or even the worst) solution
1.52 + /// in special cases.
1.53 + ///
1.54 + /// \tparam CM Type of the cost map.
1.55 + template <typename CM>
1.56 + class GreedyTsp
1.57 + {
1.58 + public:
1.59 +
1.60 + /// Type of the cost map
1.61 + typedef CM CostMap;
1.62 + /// Type of the edge costs
1.63 + typedef typename CM::Value Cost;
1.64 +
1.65 + private:
1.66 +
1.67 + GRAPH_TYPEDEFS(FullGraph);
1.68 +
1.69 + const FullGraph &_gr;
1.70 + const CostMap &_cost;
1.71 + Cost _sum;
1.72 + std::vector<Node> _path;
1.73 +
1.74 + private:
1.75 +
1.76 + // Functor class to compare edges by their costs
1.77 + class EdgeComp {
1.78 + private:
1.79 + const CostMap &_cost;
1.80 +
1.81 + public:
1.82 + EdgeComp(const CostMap &cost) : _cost(cost) {}
1.83 +
1.84 + bool operator()(const Edge &a, const Edge &b) const {
1.85 + return _cost[a] < _cost[b];
1.86 + }
1.87 + };
1.88 +
1.89 + public:
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 + GreedyTsp(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 + std::vector<int> plist;
1.117 + plist.resize(_gr.nodeNum()*2, -1);
1.118 +
1.119 + std::vector<Edge> sorted_edges;
1.120 + sorted_edges.reserve(_gr.edgeNum());
1.121 + for (EdgeIt e(_gr); e != INVALID; ++e)
1.122 + sorted_edges.push_back(e);
1.123 + std::sort(sorted_edges.begin(), sorted_edges.end(), EdgeComp(_cost));
1.124 +
1.125 + FullGraph::NodeMap<int> item_int_map(_gr);
1.126 + UnionFind<FullGraph::NodeMap<int> > union_find(item_int_map);
1.127 + for (NodeIt n(_gr); n != INVALID; ++n)
1.128 + union_find.insert(n);
1.129 +
1.130 + FullGraph::NodeMap<int> degree(_gr, 0);
1.131 +
1.132 + int nodesNum = 0, i = 0;
1.133 + while (nodesNum != _gr.nodeNum()-1) {
1.134 + Edge e = sorted_edges[i++];
1.135 + Node u = _gr.u(e),
1.136 + v = _gr.v(e);
1.137 +
1.138 + if (degree[u] <= 1 && degree[v] <= 1) {
1.139 + if (union_find.join(u, v)) {
1.140 + const int uid = _gr.id(u),
1.141 + vid = _gr.id(v);
1.142 +
1.143 + plist[uid*2 + degree[u]] = vid;
1.144 + plist[vid*2 + degree[v]] = uid;
1.145 +
1.146 + ++degree[u];
1.147 + ++degree[v];
1.148 + ++nodesNum;
1.149 + }
1.150 + }
1.151 + }
1.152 +
1.153 + for (int i=0, n=-1; i<_gr.nodeNum()*2; ++i) {
1.154 + if (plist[i] == -1) {
1.155 + if (n==-1) {
1.156 + n = i;
1.157 + } else {
1.158 + plist[n] = i/2;
1.159 + plist[i] = n/2;
1.160 + break;
1.161 + }
1.162 + }
1.163 + }
1.164 +
1.165 + for (int i=0, next=0, last=-1; i!=_gr.nodeNum(); ++i) {
1.166 + _path.push_back(_gr.nodeFromId(next));
1.167 + if (plist[2*next] != last) {
1.168 + last = next;
1.169 + next = plist[2*next];
1.170 + } else {
1.171 + last = next;
1.172 + next = plist[2*next+1];
1.173 + }
1.174 + }
1.175 +
1.176 + _sum = _cost[_gr.edge(_path.back(), _path.front())];
1.177 + for (int i = 0; i < int(_path.size())-1; ++i) {
1.178 + _sum += _cost[_gr.edge(_path[i], _path[i+1])];
1.179 + }
1.180 +
1.181 + return _sum;
1.182 + }
1.183 +
1.184 + /// @}
1.185 +
1.186 + /// \name Query Functions
1.187 + /// @{
1.188 +
1.189 + /// \brief The total cost of the found tour.
1.190 + ///
1.191 + /// This function returns the total cost of the found tour.
1.192 + ///
1.193 + /// \pre run() must be called before using this function.
1.194 + Cost tourCost() const {
1.195 + return _sum;
1.196 + }
1.197 +
1.198 + /// \brief Returns a const reference to the node sequence of the
1.199 + /// found tour.
1.200 + ///
1.201 + /// This function returns a const reference to a vector
1.202 + /// that stores the node sequence of the found tour.
1.203 + ///
1.204 + /// \pre run() must be called before using this function.
1.205 + const std::vector<Node>& tourNodes() const {
1.206 + return _path;
1.207 + }
1.208 +
1.209 + /// \brief Gives back the node sequence of the found tour.
1.210 + ///
1.211 + /// This function copies the node sequence of the found tour into
1.212 + /// an STL container through the given output iterator. The
1.213 + /// <tt>value_type</tt> of the container must be <tt>FullGraph::Node</tt>.
1.214 + /// For example,
1.215 + /// \code
1.216 + /// std::vector<FullGraph::Node> nodes(countNodes(graph));
1.217 + /// tsp.tourNodes(nodes.begin());
1.218 + /// \endcode
1.219 + /// or
1.220 + /// \code
1.221 + /// std::list<FullGraph::Node> nodes;
1.222 + /// tsp.tourNodes(std::back_inserter(nodes));
1.223 + /// \endcode
1.224 + ///
1.225 + /// \pre run() must be called before using this function.
1.226 + template <typename Iterator>
1.227 + void tourNodes(Iterator out) const {
1.228 + std::copy(_path.begin(), _path.end(), out);
1.229 + }
1.230 +
1.231 + /// \brief Gives back the found tour as a path.
1.232 + ///
1.233 + /// This function copies the found tour as a list of arcs/edges into
1.234 + /// the given \ref lemon::concepts::Path "path structure".
1.235 + ///
1.236 + /// \pre run() must be called before using this function.
1.237 + template <typename Path>
1.238 + void tour(Path &path) const {
1.239 + path.clear();
1.240 + for (int i = 0; i < int(_path.size()) - 1; ++i) {
1.241 + path.addBack(_gr.arc(_path[i], _path[i+1]));
1.242 + }
1.243 + if (int(_path.size()) >= 2) {
1.244 + path.addBack(_gr.arc(_path.back(), _path.front()));
1.245 + }
1.246 + }
1.247 +
1.248 + /// @}
1.249 +
1.250 + };
1.251 +
1.252 +}; // namespace lemon
1.253 +
1.254 +#endif