1.1 --- a/lemon/christofides_tsp.h Sat Jan 08 22:49:09 2011 +0100
1.2 +++ b/lemon/christofides_tsp.h Sat Jan 08 22:51:16 2011 +0100
1.3 @@ -1,129 +1,240 @@
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_CHRISTOFIDES_TSP_H
1.23 #define LEMON_CHRISTOFIDES_TSP_H
1.24
1.25 +/// \ingroup tsp
1.26 +/// \file
1.27 +/// \brief Christofides algorithm for symmetric TSP
1.28 +
1.29 #include <lemon/full_graph.h>
1.30 #include <lemon/smart_graph.h>
1.31 -#include <lemon/path.h>
1.32 #include <lemon/kruskal.h>
1.33 #include <lemon/matching.h>
1.34 -#include <lemon/adaptors.h>
1.35 -#include <lemon/maps.h>
1.36 #include <lemon/euler.h>
1.37
1.38 namespace lemon {
1.39
1.40 - namespace christofides_helper {
1.41 - template <class L>
1.42 - L vectorConvert(const std::vector<FullGraph::Node> &_path) {
1.43 - return L(_path.begin(), _path.end());
1.44 - }
1.45 -
1.46 - template <>
1.47 - std::vector<FullGraph::Node> vectorConvert(const std::vector<FullGraph::Node> &_path) {
1.48 - return _path;
1.49 - }
1.50 - }
1.51 -
1.52 + /// \brief Christofides algorithm for symmetric TSP.
1.53 + ///
1.54 + /// ChristofidesTsp implements Christofides' heuristic for solving
1.55 + /// symmetric \ref tsp "TSP".
1.56 + ///
1.57 + /// This a well-known approximation method for the TSP problem with
1.58 + /// \ref checkMetricCost() "metric cost function".
1.59 + /// It yields a tour whose total cost is at most 3/2 of the optimum,
1.60 + /// but it is usually much better.
1.61 + /// This implementation runs in O(n<sup>3</sup>log(n)) time.
1.62 + ///
1.63 + /// The algorithm starts with a \ref spantree "minimum cost spanning tree" and
1.64 + /// finds a \ref MaxWeightedPerfectMatching "minimum cost perfect matching"
1.65 + /// in the subgraph induced by the nodes that have odd degree in the
1.66 + /// spanning tree.
1.67 + /// Finally, it constructs the tour from the \ref EulerIt "Euler traversal"
1.68 + /// of the union of the spanning tree and the matching.
1.69 + /// During this last step, the algorithm simply skips the visited nodes
1.70 + /// (i.e. creates shortcuts) assuming that the triangle inequality holds
1.71 + /// for the cost function.
1.72 + ///
1.73 + /// \tparam CM Type of the cost map.
1.74 + ///
1.75 + /// \warning \& CM::Value must be signed type.
1.76 template <typename CM>
1.77 - class ChristofidesTsp {
1.78 + class ChristofidesTsp
1.79 + {
1.80 + public:
1.81 +
1.82 + /// Type of the cost map
1.83 + typedef CM CostMap;
1.84 + /// Type of the edge costs
1.85 + typedef typename CM::Value Cost;
1.86 +
1.87 private:
1.88 - GRAPH_TYPEDEFS(SmartGraph);
1.89 +
1.90 + GRAPH_TYPEDEFS(FullGraph);
1.91 +
1.92 + const FullGraph &_gr;
1.93 + const CostMap &_cost;
1.94 + std::vector<Node> _path;
1.95 + Cost _sum;
1.96
1.97 public:
1.98 - typedef typename CM::Value Cost;
1.99 - typedef SmartGraph::EdgeMap<Cost> CostMap;
1.100 -
1.101 - ChristofidesTsp(const FullGraph &gr, const CM &cost) : _cost(_gr), fullg(gr), fullcost(cost), nr(_gr) {
1.102 - graphCopy(gr, _gr).nodeCrossRef(nr).edgeMap(cost, _cost).run();
1.103 - }
1.104
1.105 + /// \brief Constructor
1.106 + ///
1.107 + /// Constructor.
1.108 + /// \param gr The \ref FullGraph "full graph" the algorithm runs on.
1.109 + /// \param cost The cost map.
1.110 + ChristofidesTsp(const FullGraph &gr, const CostMap &cost)
1.111 + : _gr(gr), _cost(cost) {}
1.112 +
1.113 + /// \name Execution Control
1.114 + /// @{
1.115 +
1.116 + /// \brief Runs the algorithm.
1.117 + ///
1.118 + /// This function runs the algorithm.
1.119 + ///
1.120 + /// \return The total cost of the found tour.
1.121 Cost run() {
1.122 _path.clear();
1.123 +
1.124 + if (_gr.nodeNum() == 0) return _sum = 0;
1.125 + else if (_gr.nodeNum() == 1) {
1.126 + _path.push_back(_gr(0));
1.127 + return _sum = 0;
1.128 + }
1.129 + else if (_gr.nodeNum() == 2) {
1.130 + _path.push_back(_gr(0));
1.131 + _path.push_back(_gr(1));
1.132 + return _sum = 2 * _cost[_gr.edge(_gr(0), _gr(1))];
1.133 + }
1.134
1.135 - SmartGraph::EdgeMap<bool> tree(_gr);
1.136 - kruskal(_gr, _cost, tree);
1.137 + // Compute min. cost spanning tree
1.138 + std::vector<Edge> tree;
1.139 + kruskal(_gr, _cost, std::back_inserter(tree));
1.140
1.141 - FilterEdges<SmartGraph> treefiltered(_gr, tree);
1.142 - InDegMap<FilterEdges<SmartGraph> > deg(treefiltered);
1.143 -
1.144 - SmartGraph::NodeMap<bool> oddfilter(_gr, false);
1.145 - FilterNodes<SmartGraph> oddNodes(_gr, oddfilter);
1.146 -
1.147 - for (NodeIt n(_gr); n!=INVALID; ++n) {
1.148 - if (deg[n]%2 == 1) {
1.149 - oddNodes.enable(n);
1.150 + FullGraph::NodeMap<int> deg(_gr, 0);
1.151 + for (int i = 0; i != int(tree.size()); ++i) {
1.152 + Edge e = tree[i];
1.153 + ++deg[_gr.u(e)];
1.154 + ++deg[_gr.v(e)];
1.155 + }
1.156 +
1.157 + // Copy the induced subgraph of odd nodes
1.158 + std::vector<Node> odd_nodes;
1.159 + for (NodeIt u(_gr); u != INVALID; ++u) {
1.160 + if (deg[u] % 2 == 1) odd_nodes.push_back(u);
1.161 + }
1.162 +
1.163 + SmartGraph sgr;
1.164 + SmartGraph::EdgeMap<Cost> scost(sgr);
1.165 + for (int i = 0; i != int(odd_nodes.size()); ++i) {
1.166 + sgr.addNode();
1.167 + }
1.168 + for (int i = 0; i != int(odd_nodes.size()); ++i) {
1.169 + for (int j = 0; j != int(odd_nodes.size()); ++j) {
1.170 + if (j == i) continue;
1.171 + SmartGraph::Edge e =
1.172 + sgr.addEdge(sgr.nodeFromId(i), sgr.nodeFromId(j));
1.173 + scost[e] = -_cost[_gr.edge(odd_nodes[i], odd_nodes[j])];
1.174 }
1.175 }
1.176
1.177 - NegMap<CostMap> negmap(_cost);
1.178 - MaxWeightedPerfectMatching<FilterNodes<SmartGraph>,
1.179 - NegMap<CostMap> > perfmatch(oddNodes, negmap);
1.180 - perfmatch.run();
1.181 + // Compute min. cost perfect matching
1.182 + MaxWeightedPerfectMatching<SmartGraph, SmartGraph::EdgeMap<Cost> >
1.183 + mwpm(sgr, scost);
1.184 + mwpm.run();
1.185
1.186 - for (FilterNodes<SmartGraph>::EdgeIt e(oddNodes); e!=INVALID; ++e) {
1.187 - if (perfmatch.matching(e)) {
1.188 - treefiltered.enable(_gr.addEdge(_gr.u(e), _gr.v(e)));
1.189 + for (SmartGraph::EdgeIt e(sgr); e != INVALID; ++e) {
1.190 + if (mwpm.matching(e)) {
1.191 + tree.push_back( _gr.edge(odd_nodes[sgr.id(sgr.u(e))],
1.192 + odd_nodes[sgr.id(sgr.v(e))]) );
1.193 }
1.194 }
1.195
1.196 - FilterEdges<SmartGraph>::NodeMap<bool> seen(treefiltered, false);
1.197 - for (EulerIt<FilterEdges<SmartGraph> > e(treefiltered); e!=INVALID; ++e) {
1.198 - if (seen[treefiltered.target(e)]==false) {
1.199 - _path.push_back(nr[treefiltered.target(e)]);
1.200 - seen[treefiltered.target(e)] = true;
1.201 + // Join the spanning tree and the matching
1.202 + sgr.clear();
1.203 + for (int i = 0; i != _gr.nodeNum(); ++i) {
1.204 + sgr.addNode();
1.205 + }
1.206 + for (int i = 0; i != int(tree.size()); ++i) {
1.207 + int ui = _gr.id(_gr.u(tree[i])),
1.208 + vi = _gr.id(_gr.v(tree[i]));
1.209 + sgr.addEdge(sgr.nodeFromId(ui), sgr.nodeFromId(vi));
1.210 + }
1.211 +
1.212 + // Compute the tour from the Euler traversal
1.213 + SmartGraph::NodeMap<bool> visited(sgr, false);
1.214 + for (EulerIt<SmartGraph> e(sgr); e != INVALID; ++e) {
1.215 + SmartGraph::Node n = sgr.target(e);
1.216 + if (!visited[n]) {
1.217 + _path.push_back(_gr(sgr.id(n)));
1.218 + visited[n] = true;
1.219 }
1.220 }
1.221
1.222 - _sum = fullcost[ fullg.edge(_path.back(), _path.front()) ];
1.223 - for (unsigned int i=0; i<_path.size()-1; ++i)
1.224 - _sum += fullcost[ fullg.edge(_path[i], _path[i+1]) ];
1.225 + _sum = _cost[_gr.edge(_path.back(), _path.front())];
1.226 + for (int i = 0; i < int(_path.size())-1; ++i) {
1.227 + _sum += _cost[_gr.edge(_path[i], _path[i+1])];
1.228 + }
1.229
1.230 return _sum;
1.231 }
1.232
1.233 - template <typename L>
1.234 - void tourNodes(L &container) {
1.235 - container(christofides_helper::vectorConvert<L>(_path));
1.236 - }
1.237 + /// @}
1.238
1.239 - template <template <typename> class L>
1.240 - L<FullGraph::Node> tourNodes() {
1.241 - return christofides_helper::vectorConvert<L<FullGraph::Node> >(_path);
1.242 - }
1.243 -
1.244 - const std::vector<Node>& tourNodes() {
1.245 - return _path;
1.246 - }
1.247 + /// \name Query Functions
1.248 + /// @{
1.249
1.250 - Path<FullGraph> tour() {
1.251 - Path<FullGraph> p;
1.252 - if (_path.size()<2)
1.253 - return p;
1.254 -
1.255 - for (unsigned int i=0; i<_path.size()-1; ++i) {
1.256 - p.addBack(fullg.arc(_path[i], _path[i+1]));
1.257 - }
1.258 - p.addBack(fullg.arc(_path.back(), _path.front()));
1.259 -
1.260 - return p;
1.261 - }
1.262 -
1.263 - Cost tourCost() {
1.264 + /// \brief The total cost of the found tour.
1.265 + ///
1.266 + /// This function returns the total cost of the found tour.
1.267 + ///
1.268 + /// \pre run() must be called before using this function.
1.269 + Cost tourCost() const {
1.270 return _sum;
1.271 }
1.272
1.273 + /// \brief Returns a const reference to the node sequence of the
1.274 + /// found tour.
1.275 + ///
1.276 + /// This function returns a const reference to the internal structure
1.277 + /// that stores the node sequence of the found tour.
1.278 + ///
1.279 + /// \pre run() must be called before using this function.
1.280 + const std::vector<Node>& tourNodes() const {
1.281 + return _path;
1.282 + }
1.283
1.284 - private:
1.285 - SmartGraph _gr;
1.286 - CostMap _cost;
1.287 - Cost _sum;
1.288 - const FullGraph &fullg;
1.289 - const CM &fullcost;
1.290 - std::vector<FullGraph::Node> _path;
1.291 - SmartGraph::NodeMap<FullGraph::Node> nr;
1.292 + /// \brief Gives back the node sequence of the found tour.
1.293 + ///
1.294 + /// This function copies the node sequence of the found tour into
1.295 + /// the given standard container.
1.296 + ///
1.297 + /// \pre run() must be called before using this function.
1.298 + template <typename Container>
1.299 + void tourNodes(Container &container) const {
1.300 + container.assign(_path.begin(), _path.end());
1.301 + }
1.302 +
1.303 + /// \brief Gives back the found tour as a path.
1.304 + ///
1.305 + /// This function copies the found tour as a list of arcs/edges into
1.306 + /// the given \ref concept::Path "path structure".
1.307 + ///
1.308 + /// \pre run() must be called before using this function.
1.309 + template <typename Path>
1.310 + void tour(Path &path) const {
1.311 + path.clear();
1.312 + for (int i = 0; i < int(_path.size()) - 1; ++i) {
1.313 + path.addBack(_gr.arc(_path[i], _path[i+1]));
1.314 + }
1.315 + if (int(_path.size()) >= 2) {
1.316 + path.addBack(_gr.arc(_path.back(), _path.front()));
1.317 + }
1.318 + }
1.319 +
1.320 + /// @}
1.321 +
1.322 };
1.323
1.324 -
1.325 }; // namespace lemon
1.326
1.327 #endif
2.1 --- a/lemon/greedy_tsp.h Sat Jan 08 22:49:09 2011 +0100
2.2 +++ b/lemon/greedy_tsp.h Sat Jan 08 22:51:16 2011 +0100
2.3 @@ -1,174 +1,236 @@
2.4 +/* -*- mode: C++; indent-tabs-mode: nil; -*-
2.5 + *
2.6 + * This file is a part of LEMON, a generic C++ optimization library.
2.7 + *
2.8 + * Copyright (C) 2003-2010
2.9 + * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
2.10 + * (Egervary Research Group on Combinatorial Optimization, EGRES).
2.11 + *
2.12 + * Permission to use, modify and distribute this software is granted
2.13 + * provided that this copyright notice appears in all copies. For
2.14 + * precise terms see the accompanying LICENSE file.
2.15 + *
2.16 + * This software is provided "AS IS" with no warranty of any kind,
2.17 + * express or implied, and with no claim as to its suitability for any
2.18 + * purpose.
2.19 + *
2.20 + */
2.21 +
2.22 #ifndef LEMON_GREEDY_TSP_H
2.23 #define LEMON_GREEDY_TSP_H
2.24
2.25 -#include <lemon/path.h>
2.26 +/// \ingroup tsp
2.27 +/// \file
2.28 +/// \brief Greedy algorithm for symmetric TSP
2.29 +
2.30 +#include <vector>
2.31 +#include <algorithm>
2.32 #include <lemon/full_graph.h>
2.33 #include <lemon/unionfind.h>
2.34 -#include <algorithm>
2.35
2.36 namespace lemon {
2.37
2.38 - namespace greedy_tsp_helper {
2.39 + /// \brief Greedy algorithm for symmetric TSP.
2.40 + ///
2.41 + /// GreedyTsp implements the greedy heuristic for solving
2.42 + /// symmetric \ref tsp "TSP".
2.43 + ///
2.44 + /// This algorithm is quite similar to the \ref NearestNeighborTsp
2.45 + /// "nearest neighbor" heuristic, but it maintains a set of disjoint paths.
2.46 + /// At each step, the shortest possible edge is added to these paths
2.47 + /// as long as it does not create a cycle of less than n edges and it does
2.48 + /// not increase the degree of any node above two.
2.49 + ///
2.50 + /// This method runs in O(n<sup>2</sup>log(n)) time.
2.51 + /// It quickly finds an effectively short tour for most TSP
2.52 + /// instances, but in special cases, it could yield a really bad
2.53 + /// (or even the worst) solution.
2.54 + ///
2.55 + /// \tparam CM Type of the cost map.
2.56 + template <typename CM>
2.57 + class GreedyTsp
2.58 + {
2.59 + public:
2.60
2.61 - template <typename CostMap>
2.62 - class KeyComp {
2.63 - typedef typename CostMap::Key Key;
2.64 - const CostMap &cost;
2.65 + /// Type of the cost map
2.66 + typedef CM CostMap;
2.67 + /// Type of the edge costs
2.68 + typedef typename CM::Value Cost;
2.69 +
2.70 + private:
2.71 +
2.72 + GRAPH_TYPEDEFS(FullGraph);
2.73 +
2.74 + const FullGraph &_gr;
2.75 + const CostMap &_cost;
2.76 + Cost _sum;
2.77 + std::vector<Node> _path;
2.78
2.79 + private:
2.80 +
2.81 + // Functor class to compare edges by their costs
2.82 + class EdgeComp {
2.83 + private:
2.84 + const CostMap &_cost;
2.85 +
2.86 public:
2.87 - KeyComp(const CostMap &_cost) : cost(_cost) {}
2.88 -
2.89 - bool operator() (const Key &a, const Key &b) const {
2.90 - return cost[a] < cost[b];
2.91 + EdgeComp(const CostMap &cost) : _cost(cost) {}
2.92 +
2.93 + bool operator()(const Edge &a, const Edge &b) const {
2.94 + return _cost[a] < _cost[b];
2.95 }
2.96 - };
2.97 + };
2.98
2.99 -
2.100 - template <class L>
2.101 - L vectorConvert(const std::vector<FullGraph::Node> &_path) {
2.102 - return L(_path.begin(), _path.end());
2.103 - }
2.104 -
2.105 - template <>
2.106 - std::vector<FullGraph::Node> vectorConvert(const std::vector<FullGraph::Node> &_path) {
2.107 - return _path;
2.108 - }
2.109 -
2.110 - }
2.111 + public:
2.112
2.113 + /// \brief Constructor
2.114 + ///
2.115 + /// Constructor.
2.116 + /// \param gr The \ref FullGraph "full graph" the algorithm runs on.
2.117 + /// \param cost The cost map.
2.118 + GreedyTsp(const FullGraph &gr, const CostMap &cost)
2.119 + : _gr(gr), _cost(cost) {}
2.120
2.121 - template <typename CM>
2.122 - class GreedyTsp {
2.123 - private:
2.124 - GRAPH_TYPEDEFS(FullGraph);
2.125 -
2.126 - public:
2.127 - typedef CM CostMap;
2.128 - typedef typename CM::Value Cost;
2.129 -
2.130 - GreedyTsp(const FullGraph &gr, const CostMap &cost) : _gr(gr), _cost(cost) {}
2.131 + /// \name Execution Control
2.132 + /// @{
2.133
2.134 + /// \brief Runs the algorithm.
2.135 + ///
2.136 + /// This function runs the algorithm.
2.137 + ///
2.138 + /// \return The total cost of the found tour.
2.139 Cost run() {
2.140 - typedef UnionFind<FullGraph::NodeMap<int> > Union;
2.141 - _nodes.clear();
2.142 -
2.143 - std::vector<int> path;
2.144 - path.resize(_gr.nodeNum()*2, -1);
2.145 -
2.146 - std::vector<typename CostMap::Key> sorted_edges;
2.147 + _path.clear();
2.148 +
2.149 + if (_gr.nodeNum() == 0) return _sum = 0;
2.150 + else if (_gr.nodeNum() == 1) {
2.151 + _path.push_back(_gr(0));
2.152 + return _sum = 0;
2.153 + }
2.154 +
2.155 + std::vector<int> plist;
2.156 + plist.resize(_gr.nodeNum()*2, -1);
2.157 +
2.158 + std::vector<Edge> sorted_edges;
2.159 sorted_edges.reserve(_gr.edgeNum());
2.160 - for (EdgeIt n(_gr); n != INVALID; ++n)
2.161 - sorted_edges.push_back(n);
2.162 + for (EdgeIt e(_gr); e != INVALID; ++e)
2.163 + sorted_edges.push_back(e);
2.164 + std::sort(sorted_edges.begin(), sorted_edges.end(), EdgeComp(_cost));
2.165
2.166 - std::sort(sorted_edges.begin(), sorted_edges.end(), greedy_tsp_helper::KeyComp<CostMap>(_cost));
2.167 + FullGraph::NodeMap<int> item_int_map(_gr);
2.168 + UnionFind<FullGraph::NodeMap<int> > union_find(item_int_map);
2.169 + for (NodeIt n(_gr); n != INVALID; ++n)
2.170 + union_find.insert(n);
2.171
2.172 - FullGraph::NodeMap<int> nodemap(_gr);
2.173 - Union unionfind(nodemap);
2.174 -
2.175 - for (NodeIt n(_gr); n != INVALID; ++n)
2.176 - unionfind.insert(n);
2.177 -
2.178 FullGraph::NodeMap<int> degree(_gr, 0);
2.179
2.180 int nodesNum = 0, i = 0;
2.181 + while (nodesNum != _gr.nodeNum()-1) {
2.182 + Edge e = sorted_edges[i++];
2.183 + Node u = _gr.u(e),
2.184 + v = _gr.v(e);
2.185
2.186 - while ( nodesNum != _gr.nodeNum()-1 ) {
2.187 - const Edge &e = sorted_edges[i];
2.188 -
2.189 - const Node u = _gr.u(e),
2.190 - v = _gr.v(e);
2.191 -
2.192 - if (degree[u]<=1 && degree[v]<=1) {
2.193 - if (unionfind.join(u, v)) {
2.194 + if (degree[u] <= 1 && degree[v] <= 1) {
2.195 + if (union_find.join(u, v)) {
2.196 + const int uid = _gr.id(u),
2.197 + vid = _gr.id(v);
2.198 +
2.199 + plist[uid*2 + degree[u]] = vid;
2.200 + plist[vid*2 + degree[v]] = uid;
2.201 +
2.202 ++degree[u];
2.203 ++degree[v];
2.204 ++nodesNum;
2.205 -
2.206 - const int uid = _gr.id(u),
2.207 - vid = _gr.id(v);
2.208 -
2.209 -
2.210 - path[uid*2 + (path[uid*2]==-1 ? 0 : 1)] = vid;
2.211 - path[vid*2 + (path[vid*2]==-1 ? 0 : 1)] = uid;
2.212 }
2.213 }
2.214 -
2.215 - ++i;
2.216 }
2.217
2.218 -
2.219 for (int i=0, n=-1; i<_gr.nodeNum()*2; ++i) {
2.220 - if (path[i] == -1) {
2.221 + if (plist[i] == -1) {
2.222 if (n==-1) {
2.223 n = i;
2.224 } else {
2.225 - path[n] = i/2;
2.226 - path[i] = n/2;
2.227 + plist[n] = i/2;
2.228 + plist[i] = n/2;
2.229 break;
2.230 }
2.231 }
2.232 }
2.233
2.234 -
2.235 - for (int i=0, j=0, last=-1; i!=_gr.nodeNum(); ++i) {
2.236 - _nodes.push_back(_gr.nodeFromId(j));
2.237 -
2.238 - if (path[2*j] != last) {
2.239 - last = j;
2.240 - j = path[2*j];
2.241 + for (int i=0, next=0, last=-1; i!=_gr.nodeNum(); ++i) {
2.242 + _path.push_back(_gr.nodeFromId(next));
2.243 + if (plist[2*next] != last) {
2.244 + last = next;
2.245 + next = plist[2*next];
2.246 } else {
2.247 - last = j;
2.248 - j = path[2*j+1];
2.249 + last = next;
2.250 + next = plist[2*next+1];
2.251 }
2.252 }
2.253
2.254 - _sum = _cost[_gr.edge(_nodes.back(), _nodes.front())];
2.255 - for (unsigned int i=0; i<_nodes.size()-1; ++i)
2.256 - _sum += _cost[_gr.edge(_nodes[i], _nodes[i+1])];
2.257 + _sum = _cost[_gr.edge(_path.back(), _path.front())];
2.258 + for (int i = 0; i < int(_path.size())-1; ++i) {
2.259 + _sum += _cost[_gr.edge(_path[i], _path[i+1])];
2.260 + }
2.261
2.262 return _sum;
2.263 }
2.264
2.265 + /// @}
2.266
2.267 + /// \name Query Functions
2.268 + /// @{
2.269
2.270 - template <typename L>
2.271 - void tourNodes(L &container) {
2.272 - container(greedy_tsp_helper::vectorConvert<L>(_nodes));
2.273 - }
2.274 -
2.275 - template <template <typename> class L>
2.276 - L<Node> tourNodes() {
2.277 - return greedy_tsp_helper::vectorConvert<L<Node> >(_nodes);
2.278 - }
2.279 -
2.280 - const std::vector<Node>& tourNodes() {
2.281 - return _nodes;
2.282 - }
2.283 -
2.284 - Path<FullGraph> tour() {
2.285 - Path<FullGraph> p;
2.286 - if (_nodes.size()<2)
2.287 - return p;
2.288 -
2.289 - for (unsigned int i=0; i<_nodes.size()-1; ++i) {
2.290 - p.addBack(_gr.arc(_nodes[i], _nodes[i+1]));
2.291 - }
2.292 -
2.293 - p.addBack(_gr.arc(_nodes.back(), _nodes.front()));
2.294 -
2.295 - return p;
2.296 - }
2.297 -
2.298 - Cost tourCost() {
2.299 + /// \brief The total cost of the found tour.
2.300 + ///
2.301 + /// This function returns the total cost of the found tour.
2.302 + ///
2.303 + /// \pre run() must be called before using this function.
2.304 + Cost tourCost() const {
2.305 return _sum;
2.306 }
2.307 -
2.308
2.309 - private:
2.310 - const FullGraph &_gr;
2.311 - const CostMap &_cost;
2.312 - Cost _sum;
2.313 - std::vector<Node> _nodes;
2.314 + /// \brief Returns a const reference to the node sequence of the
2.315 + /// found tour.
2.316 + ///
2.317 + /// This function returns a const reference to the internal structure
2.318 + /// that stores the node sequence of the found tour.
2.319 + ///
2.320 + /// \pre run() must be called before using this function.
2.321 + const std::vector<Node>& tourNodes() const {
2.322 + return _path;
2.323 + }
2.324 +
2.325 + /// \brief Gives back the node sequence of the found tour.
2.326 + ///
2.327 + /// This function copies the node sequence of the found tour into
2.328 + /// the given standard container.
2.329 + ///
2.330 + /// \pre run() must be called before using this function.
2.331 + template <typename Container>
2.332 + void tourNodes(Container &container) const {
2.333 + container.assign(_path.begin(), _path.end());
2.334 + }
2.335 +
2.336 + /// \brief Gives back the found tour as a path.
2.337 + ///
2.338 + /// This function copies the found tour as a list of arcs/edges into
2.339 + /// the given \ref concept::Path "path structure".
2.340 + ///
2.341 + /// \pre run() must be called before using this function.
2.342 + template <typename Path>
2.343 + void tour(Path &path) const {
2.344 + path.clear();
2.345 + for (int i = 0; i < int(_path.size()) - 1; ++i) {
2.346 + path.addBack(_gr.arc(_path[i], _path[i+1]));
2.347 + }
2.348 + if (int(_path.size()) >= 2) {
2.349 + path.addBack(_gr.arc(_path.back(), _path.front()));
2.350 + }
2.351 + }
2.352 +
2.353 + /// @}
2.354 +
2.355 };
2.356
2.357 }; // namespace lemon
3.1 --- a/lemon/insertion_tsp.h Sat Jan 08 22:49:09 2011 +0100
3.2 +++ b/lemon/insertion_tsp.h Sat Jan 08 22:51:16 2011 +0100
3.3 @@ -1,225 +1,349 @@
3.4 +/* -*- mode: C++; indent-tabs-mode: nil; -*-
3.5 + *
3.6 + * This file is a part of LEMON, a generic C++ optimization library.
3.7 + *
3.8 + * Copyright (C) 2003-2010
3.9 + * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
3.10 + * (Egervary Research Group on Combinatorial Optimization, EGRES).
3.11 + *
3.12 + * Permission to use, modify and distribute this software is granted
3.13 + * provided that this copyright notice appears in all copies. For
3.14 + * precise terms see the accompanying LICENSE file.
3.15 + *
3.16 + * This software is provided "AS IS" with no warranty of any kind,
3.17 + * express or implied, and with no claim as to its suitability for any
3.18 + * purpose.
3.19 + *
3.20 + */
3.21 +
3.22 #ifndef LEMON_INSERTION_TSP_H
3.23 #define LEMON_INSERTION_TSP_H
3.24
3.25 +/// \ingroup tsp
3.26 +/// \file
3.27 +/// \brief Insertion algorithm for symmetric TSP
3.28 +
3.29 +#include <vector>
3.30 #include <lemon/full_graph.h>
3.31 -#include <lemon/path.h>
3.32 #include <lemon/maps.h>
3.33 #include <lemon/random.h>
3.34 -#include <vector>
3.35
3.36 namespace lemon {
3.37
3.38 - namespace insertion_tsp_helper {
3.39 -
3.40 - template <class L>
3.41 - L vectorConvert(const std::vector<FullGraph::Node> &_path) {
3.42 - return L(_path.begin(), _path.end());
3.43 - };
3.44 -
3.45 - template <>
3.46 - std::vector<FullGraph::Node> vectorConvert(
3.47 - const std::vector<FullGraph::Node> &_path) {
3.48 - return _path;
3.49 - };
3.50 -
3.51 - };
3.52 + /// \brief Insertion algorithm for symmetric TSP.
3.53 + ///
3.54 + /// InsertionTsp implements the insertion heuristic for solving
3.55 + /// symmetric \ref tsp "TSP".
3.56 + ///
3.57 + /// This is a basic TSP heuristic that has many variants.
3.58 + /// It starts with a subtour containing a few nodes of the graph and it
3.59 + /// iteratively inserts the other nodes into this subtour according to a
3.60 + /// certain node selection rule.
3.61 + ///
3.62 + /// This implementation provides four different node selection rules,
3.63 + /// from which the most powerful one is used by default.
3.64 + /// For more information, see \ref SelectionRule.
3.65 + ///
3.66 + /// \tparam CM Type of the cost map.
3.67 + template <typename CM>
3.68 + class InsertionTsp
3.69 + {
3.70 + public:
3.71
3.72 - template <typename CM>
3.73 - class InsertionTsp {
3.74 - private:
3.75 - GRAPH_TYPEDEFS(FullGraph);
3.76 -
3.77 - public:
3.78 + /// Type of the cost map
3.79 typedef CM CostMap;
3.80 + /// Type of the edge costs
3.81 typedef typename CM::Value Cost;
3.82 -
3.83 - InsertionTsp(const FullGraph &gr, const CostMap &cost) :
3.84 - _gr(gr), _cost(cost) {}
3.85 -
3.86 - enum InsertionMethod {
3.87 - INSERT_NEAREST,
3.88 - INSERT_FARTHEST,
3.89 - INSERT_CHEAPEST,
3.90 - INSERT_RANDOM
3.91 - };
3.92 -
3.93 - Cost run(InsertionMethod method = INSERT_FARTHEST) {
3.94 - switch (method) {
3.95 - case INSERT_NEAREST:
3.96 - start<InitTour<true>, NearestSelection, DefaultInsert>();
3.97 - break;
3.98 - case INSERT_FARTHEST:
3.99 - start<InitTour<false>, FarthestSelection, DefaultInsert>();
3.100 - break;
3.101 - case INSERT_CHEAPEST:
3.102 - start<InitTour<true>, CheapestSelection, CheapestInsert>();
3.103 - break;
3.104 - case INSERT_RANDOM:
3.105 - start<InitTour<true>, RandomSelection, DefaultInsert>();
3.106 - break;
3.107 - }
3.108 - return sum;
3.109 - }
3.110 -
3.111 - template <typename L>
3.112 - void tourNodes(L &container) {
3.113 - container(insertion_tsp_helper::vectorConvert<L>(nodesPath));
3.114 - }
3.115 -
3.116 - template <template <typename> class L>
3.117 - L<Node> tourNodes() {
3.118 - return insertion_tsp_helper::vectorConvert<L<Node> >(nodesPath);
3.119 - }
3.120 -
3.121 - const std::vector<Node>& tourNodes() {
3.122 - return nodesPath;
3.123 - }
3.124 -
3.125 - Path<FullGraph> tour() {
3.126 - Path<FullGraph> p;
3.127 - if (nodesPath.size()<2)
3.128 - return p;
3.129 -
3.130 - for (unsigned int i=0; i<nodesPath.size()-1; ++i)
3.131 - p.addBack(_gr.arc(nodesPath[i], nodesPath[i+1]));
3.132 -
3.133 - p.addBack(_gr.arc(nodesPath.back(), nodesPath.front()));
3.134 - return p;
3.135 - }
3.136 -
3.137 - Cost tourCost() {
3.138 - return sum;
3.139 - }
3.140 -
3.141
3.142 private:
3.143
3.144 - template <bool MIN>
3.145 - class InitTour {
3.146 + GRAPH_TYPEDEFS(FullGraph);
3.147 +
3.148 + const FullGraph &_gr;
3.149 + const CostMap &_cost;
3.150 + std::vector<Node> _notused;
3.151 + std::vector<Node> _path;
3.152 + Cost _sum;
3.153 +
3.154 + public:
3.155 +
3.156 + /// \brief Constants for specifying the node selection rule.
3.157 + ///
3.158 + /// Enum type containing constants for specifying the node selection
3.159 + /// rule for the \ref run() function.
3.160 + ///
3.161 + /// During the algorithm, nodes are selected for addition to the current
3.162 + /// subtour according to the applied rule.
3.163 + /// In general, the FARTHEST yields the best tours, thus it is the
3.164 + /// default option. RANDOM usually gives somewhat worse results, but
3.165 + /// it is much faster than the others and it is the most robust.
3.166 + ///
3.167 + /// The desired selection rule can be specified as a parameter of the
3.168 + /// \ref run() function.
3.169 + enum SelectionRule {
3.170 +
3.171 + /// An unvisited node having minimum distance from the current
3.172 + /// subtour is selected at each step.
3.173 + /// The algorithm runs in O(n<sup>3</sup>) time using this
3.174 + /// selection rule.
3.175 + NEAREST,
3.176 +
3.177 + /// An unvisited node having maximum distance from the current
3.178 + /// subtour is selected at each step.
3.179 + /// The algorithm runs in O(n<sup>3</sup>) time using this
3.180 + /// selection rule.
3.181 + FARTHEST,
3.182 +
3.183 + /// An unvisited node whose insertion results in the least
3.184 + /// increase of the subtour's total cost is selected at each step.
3.185 + /// The algorithm runs in O(n<sup>3</sup>) time using this
3.186 + /// selection rule.
3.187 + CHEAPEST,
3.188 +
3.189 + /// An unvisited node is selected randomly without any evaluation
3.190 + /// at each step.
3.191 + /// The global \ref rnd "random number generator instance" is used.
3.192 + /// You can seed it before executing the algorithm, if you
3.193 + /// would like to.
3.194 + /// The algorithm runs in O(n<sup>2</sup>) time using this
3.195 + /// selection rule.
3.196 + RANDOM
3.197 + };
3.198 +
3.199 + public:
3.200 +
3.201 + /// \brief Constructor
3.202 + ///
3.203 + /// Constructor.
3.204 + /// \param gr The \ref FullGraph "full graph" the algorithm runs on.
3.205 + /// \param cost The cost map.
3.206 + InsertionTsp(const FullGraph &gr, const CostMap &cost)
3.207 + : _gr(gr), _cost(cost) {}
3.208 +
3.209 + /// \name Execution Control
3.210 + /// @{
3.211 +
3.212 + /// \brief Runs the algorithm.
3.213 + ///
3.214 + /// This function runs the algorithm.
3.215 + ///
3.216 + /// \param rule The node selection rule. For more information, see
3.217 + /// \ref SelectionRule.
3.218 + ///
3.219 + /// \return The total cost of the found tour.
3.220 + Cost run(SelectionRule rule = FARTHEST) {
3.221 + _path.clear();
3.222 +
3.223 + if (_gr.nodeNum() == 0) return _sum = 0;
3.224 + else if (_gr.nodeNum() == 1) {
3.225 + _path.push_back(_gr(0));
3.226 + return _sum = 0;
3.227 + }
3.228 +
3.229 + switch (rule) {
3.230 + case NEAREST:
3.231 + init(true);
3.232 + start<NearestSelection, DefaultInsertion>();
3.233 + break;
3.234 + case FARTHEST:
3.235 + init(false);
3.236 + start<FarthestSelection, DefaultInsertion>();
3.237 + break;
3.238 + case CHEAPEST:
3.239 + init(true);
3.240 + start<CheapestSelection, CheapestInsertion>();
3.241 + break;
3.242 + case RANDOM:
3.243 + init(true);
3.244 + start<RandomSelection, DefaultInsertion>();
3.245 + break;
3.246 + }
3.247 + return _sum;
3.248 + }
3.249 +
3.250 + /// @}
3.251 +
3.252 + /// \name Query Functions
3.253 + /// @{
3.254 +
3.255 + /// \brief The total cost of the found tour.
3.256 + ///
3.257 + /// This function returns the total cost of the found tour.
3.258 + ///
3.259 + /// \pre run() must be called before using this function.
3.260 + Cost tourCost() const {
3.261 + return _sum;
3.262 + }
3.263 +
3.264 + /// \brief Returns a const reference to the node sequence of the
3.265 + /// found tour.
3.266 + ///
3.267 + /// This function returns a const reference to the internal structure
3.268 + /// that stores the node sequence of the found tour.
3.269 + ///
3.270 + /// \pre run() must be called before using this function.
3.271 + const std::vector<Node>& tourNodes() const {
3.272 + return _path;
3.273 + }
3.274 +
3.275 + /// \brief Gives back the node sequence of the found tour.
3.276 + ///
3.277 + /// This function copies the node sequence of the found tour into
3.278 + /// the given standard container.
3.279 + ///
3.280 + /// \pre run() must be called before using this function.
3.281 + template <typename Container>
3.282 + void tourNodes(Container &container) const {
3.283 + container.assign(_path.begin(), _path.end());
3.284 + }
3.285 +
3.286 + /// \brief Gives back the found tour as a path.
3.287 + ///
3.288 + /// This function copies the found tour as a list of arcs/edges into
3.289 + /// the given \ref concept::Path "path structure".
3.290 + ///
3.291 + /// \pre run() must be called before using this function.
3.292 + template <typename Path>
3.293 + void tour(Path &path) const {
3.294 + path.clear();
3.295 + for (int i = 0; i < int(_path.size()) - 1; ++i) {
3.296 + path.addBack(_gr.arc(_path[i], _path[i+1]));
3.297 + }
3.298 + if (int(_path.size()) >= 2) {
3.299 + path.addBack(_gr.arc(_path.back(), _path.front()));
3.300 + }
3.301 + }
3.302 +
3.303 + /// @}
3.304 +
3.305 + private:
3.306 +
3.307 + // Initializes the algorithm
3.308 + void init(bool min) {
3.309 + Edge min_edge = min ? mapMin(_gr, _cost) : mapMax(_gr, _cost);
3.310 +
3.311 + _path.clear();
3.312 + _path.push_back(_gr.u(min_edge));
3.313 + _path.push_back(_gr.v(min_edge));
3.314 +
3.315 + _notused.clear();
3.316 + for (NodeIt n(_gr); n!=INVALID; ++n) {
3.317 + if (n != _gr.u(min_edge) && n != _gr.v(min_edge)) {
3.318 + _notused.push_back(n);
3.319 + }
3.320 + }
3.321 +
3.322 + _sum = _cost[min_edge] * 2;
3.323 + }
3.324 +
3.325 + // Executes the algorithm
3.326 + template <class SelectionFunctor, class InsertionFunctor>
3.327 + void start() {
3.328 + SelectionFunctor selectNode(_gr, _cost, _path, _notused);
3.329 + InsertionFunctor insertNode(_gr, _cost, _path, _sum);
3.330 +
3.331 + for (int i=0; i<_gr.nodeNum()-2; ++i) {
3.332 + insertNode.insert(selectNode.select());
3.333 + }
3.334 +
3.335 + _sum = _cost[_gr.edge(_path.back(), _path.front())];
3.336 + for (int i = 0; i < int(_path.size())-1; ++i) {
3.337 + _sum += _cost[_gr.edge(_path[i], _path[i+1])];
3.338 + }
3.339 + }
3.340 +
3.341 +
3.342 + // Implementation of the nearest selection rule
3.343 + class NearestSelection {
3.344 public:
3.345 - InitTour(const FullGraph &gr, const CostMap &cost,
3.346 - std::vector<Node> &used, std::vector<Node> ¬used,
3.347 - Cost &fullcost) :
3.348 - _gr(gr), _cost(cost), _used(used), _notused(notused),
3.349 - _fullcost(fullcost) {}
3.350 + NearestSelection(const FullGraph &gr, const CostMap &cost,
3.351 + std::vector<Node> &path, std::vector<Node> ¬used)
3.352 + : _gr(gr), _cost(cost), _path(path), _notused(notused) {}
3.353
3.354 - std::vector<Node> init() const {
3.355 - Edge min = (MIN) ? mapMin(_gr, _cost) : mapMax(_gr, _cost);
3.356 - std::vector<Node> path;
3.357 - path.push_back(_gr.u(min));
3.358 - path.push_back(_gr.v(min));
3.359 -
3.360 - _used.clear();
3.361 - _notused.clear();
3.362 - for (NodeIt n(_gr); n!=INVALID; ++n) {
3.363 - if (n != _gr.u(min) && n != _gr.v(min)) {
3.364 - _notused.push_back(n);
3.365 + Node select() const {
3.366 + Cost insert_val = 0;
3.367 + int insert_node = -1;
3.368 +
3.369 + for (unsigned int i=0; i<_notused.size(); ++i) {
3.370 + Cost min_val = _cost[_gr.edge(_notused[i], _path[0])];
3.371 + int min_node = 0;
3.372 +
3.373 + for (unsigned int j=1; j<_path.size(); ++j) {
3.374 + Cost curr = _cost[_gr.edge(_notused[i], _path[j])];
3.375 + if (min_val > curr) {
3.376 + min_val = curr;
3.377 + min_node = j;
3.378 + }
3.379 + }
3.380 +
3.381 + if (insert_val > min_val || insert_node == -1) {
3.382 + insert_val = min_val;
3.383 + insert_node = i;
3.384 }
3.385 }
3.386 - _used.push_back(_gr.u(min));
3.387 - _used.push_back(_gr.v(min));
3.388 -
3.389 - _fullcost = _cost[min]*2;
3.390 - return path;
3.391 +
3.392 + Node n = _notused[insert_node];
3.393 + _notused.erase(_notused.begin()+insert_node);
3.394 +
3.395 + return n;
3.396 }
3.397
3.398 private:
3.399 const FullGraph &_gr;
3.400 const CostMap &_cost;
3.401 - std::vector<Node> &_used;
3.402 - std::vector<Node> &_notused;
3.403 - Cost &_fullcost;
3.404 - };
3.405 -
3.406 - class NearestSelection {
3.407 - public:
3.408 - NearestSelection(const FullGraph &gr, const CostMap &cost,
3.409 - std::vector<Node> &used, std::vector<Node> ¬used) :
3.410 - _gr(gr), _cost(cost), _used(used), _notused(notused) {}
3.411 -
3.412 - Node select() const {
3.413 -
3.414 - Cost insert_val =
3.415 - std::numeric_limits<Cost>::max();
3.416 - int insert_node = -1;
3.417 -
3.418 - for (unsigned int i=0; i<_notused.size(); ++i) {
3.419 - Cost min_val = _cost[_gr.edge(_notused[i], _used[0])];
3.420 - int min_node = 0;
3.421 -
3.422 - for (unsigned int j=1; j<_used.size(); ++j) {
3.423 - if (min_val > _cost[_gr.edge(_notused[i], _used[j])]) {
3.424 - min_val = _cost[_gr.edge(_notused[i], _used[j])];
3.425 - min_node = j;
3.426 - }
3.427 - }
3.428 -
3.429 - if (insert_val > min_val) {
3.430 - insert_val = min_val;
3.431 - insert_node = i;
3.432 - }
3.433 - }
3.434 -
3.435 - Node n = _notused[insert_node];
3.436 - _notused.erase(_notused.begin()+insert_node);
3.437 -
3.438 - return n;
3.439 - }
3.440 -
3.441 - private:
3.442 - const FullGraph &_gr;
3.443 - const CostMap &_cost;
3.444 - std::vector<Node> &_used;
3.445 + std::vector<Node> &_path;
3.446 std::vector<Node> &_notused;
3.447 };
3.448
3.449 +
3.450 + // Implementation of the farthest selection rule
3.451 class FarthestSelection {
3.452 public:
3.453 FarthestSelection(const FullGraph &gr, const CostMap &cost,
3.454 - std::vector<Node> &used, std::vector<Node> ¬used) :
3.455 - _gr(gr), _cost(cost), _used(used), _notused(notused) {}
3.456 -
3.457 + std::vector<Node> &path, std::vector<Node> ¬used)
3.458 + : _gr(gr), _cost(cost), _path(path), _notused(notused) {}
3.459 +
3.460 Node select() const {
3.461 + Cost insert_val = 0;
3.462 + int insert_node = -1;
3.463
3.464 - Cost insert_val =
3.465 - std::numeric_limits<Cost>::min();
3.466 - int insert_node = -1;
3.467 -
3.468 for (unsigned int i=0; i<_notused.size(); ++i) {
3.469 - Cost min_val = _cost[_gr.edge(_notused[i], _used[0])];
3.470 + Cost min_val = _cost[_gr.edge(_notused[i], _path[0])];
3.471 int min_node = 0;
3.472 -
3.473 - for (unsigned int j=1; j<_used.size(); ++j) {
3.474 - if (min_val > _cost[_gr.edge(_notused[i], _used[j])]) {
3.475 - min_val = _cost[_gr.edge(_notused[i], _used[j])];
3.476 +
3.477 + for (unsigned int j=1; j<_path.size(); ++j) {
3.478 + Cost curr = _cost[_gr.edge(_notused[i], _path[j])];
3.479 + if (min_val > curr) {
3.480 + min_val = curr;
3.481 min_node = j;
3.482 }
3.483 }
3.484 -
3.485 +
3.486 if (insert_val < min_val || insert_node == -1) {
3.487 insert_val = min_val;
3.488 insert_node = i;
3.489 }
3.490 }
3.491 -
3.492 +
3.493 Node n = _notused[insert_node];
3.494 _notused.erase(_notused.begin()+insert_node);
3.495 -
3.496 +
3.497 return n;
3.498 }
3.499 -
3.500 +
3.501 private:
3.502 const FullGraph &_gr;
3.503 const CostMap &_cost;
3.504 - std::vector<Node> &_used;
3.505 + std::vector<Node> &_path;
3.506 std::vector<Node> &_notused;
3.507 };
3.508
3.509
3.510 + // Implementation of the cheapest selection rule
3.511 class CheapestSelection {
3.512 private:
3.513 Cost costDiff(Node u, Node v, Node w) const {
3.514 - return
3.515 + return
3.516 _cost[_gr.edge(u, w)] +
3.517 _cost[_gr.edge(v, w)] -
3.518 _cost[_gr.edge(u, v)];
3.519 @@ -227,24 +351,23 @@
3.520
3.521 public:
3.522 CheapestSelection(const FullGraph &gr, const CostMap &cost,
3.523 - std::vector<Node> &used, std::vector<Node> ¬used) :
3.524 - _gr(gr), _cost(cost), _used(used), _notused(notused) {}
3.525 -
3.526 + std::vector<Node> &path, std::vector<Node> ¬used)
3.527 + : _gr(gr), _cost(cost), _path(path), _notused(notused) {}
3.528 +
3.529 Cost select() const {
3.530 int insert_notused = -1;
3.531 int best_insert_index = -1;
3.532 - Cost insert_val =
3.533 - std::numeric_limits<Cost>::max();
3.534 -
3.535 + Cost insert_val = 0;
3.536 +
3.537 for (unsigned int i=0; i<_notused.size(); ++i) {
3.538 int min = i;
3.539 int best_insert_tmp = 0;
3.540 Cost min_val =
3.541 - costDiff(_used.front(), _used.back(), _notused[i]);
3.542 -
3.543 - for (unsigned int j=1; j<_used.size(); ++j) {
3.544 + costDiff(_path.front(), _path.back(), _notused[i]);
3.545 +
3.546 + for (unsigned int j=1; j<_path.size(); ++j) {
3.547 Cost tmp =
3.548 - costDiff(_used[j-1], _used[j], _notused[i]);
3.549 + costDiff(_path[j-1], _path[j], _notused[i]);
3.550
3.551 if (min_val > tmp) {
3.552 min = i;
3.553 @@ -253,34 +376,34 @@
3.554 }
3.555 }
3.556
3.557 - if (insert_val > min_val) {
3.558 + if (insert_val > min_val || insert_notused == -1) {
3.559 insert_notused = min;
3.560 insert_val = min_val;
3.561 best_insert_index = best_insert_tmp;
3.562 }
3.563 }
3.564
3.565 - _used.insert(_used.begin()+best_insert_index, _notused[insert_notused]);
3.566 + _path.insert(_path.begin()+best_insert_index,
3.567 + _notused[insert_notused]);
3.568 _notused.erase(_notused.begin()+insert_notused);
3.569
3.570 return insert_val;
3.571 }
3.572 -
3.573 +
3.574 private:
3.575 const FullGraph &_gr;
3.576 const CostMap &_cost;
3.577 - std::vector<Node> &_used;
3.578 + std::vector<Node> &_path;
3.579 std::vector<Node> &_notused;
3.580 };
3.581
3.582 + // Implementation of the random selection rule
3.583 class RandomSelection {
3.584 public:
3.585 RandomSelection(const FullGraph &, const CostMap &,
3.586 - std::vector<Node> &, std::vector<Node> ¬used) :
3.587 - _notused(notused) {
3.588 - rnd.seedFromTime();
3.589 - }
3.590 -
3.591 + std::vector<Node> &, std::vector<Node> ¬used)
3.592 + : _notused(notused) {}
3.593 +
3.594 Node select() const {
3.595 const int index = rnd[_notused.size()];
3.596 Node n = _notused[index];
3.597 @@ -292,25 +415,26 @@
3.598 };
3.599
3.600
3.601 - class DefaultInsert {
3.602 + // Implementation of the default insertion method
3.603 + class DefaultInsertion {
3.604 private:
3.605 Cost costDiff(Node u, Node v, Node w) const {
3.606 - return
3.607 + return
3.608 _cost[_gr.edge(u, w)] +
3.609 _cost[_gr.edge(v, w)] -
3.610 _cost[_gr.edge(u, v)];
3.611 }
3.612 -
3.613 +
3.614 public:
3.615 - DefaultInsert(const FullGraph &gr, const CostMap &cost,
3.616 - std::vector<Node> &path, Cost &fullcost) :
3.617 - _gr(gr), _cost(cost), _path(path), _fullcost(fullcost) {}
3.618 -
3.619 + DefaultInsertion(const FullGraph &gr, const CostMap &cost,
3.620 + std::vector<Node> &path, Cost &total_cost) :
3.621 + _gr(gr), _cost(cost), _path(path), _total(total_cost) {}
3.622 +
3.623 void insert(Node n) const {
3.624 int min = 0;
3.625 Cost min_val =
3.626 costDiff(_path.front(), _path.back(), n);
3.627 -
3.628 +
3.629 for (unsigned int i=1; i<_path.size(); ++i) {
3.630 Cost tmp = costDiff(_path[i-1], _path[i], n);
3.631 if (tmp < min_val) {
3.632 @@ -318,58 +442,37 @@
3.633 min_val = tmp;
3.634 }
3.635 }
3.636 -
3.637 +
3.638 _path.insert(_path.begin()+min, n);
3.639 - _fullcost += min_val;
3.640 + _total += min_val;
3.641 }
3.642 -
3.643 +
3.644 private:
3.645 const FullGraph &_gr;
3.646 const CostMap &_cost;
3.647 std::vector<Node> &_path;
3.648 - Cost &_fullcost;
3.649 + Cost &_total;
3.650 };
3.651 -
3.652 - class CheapestInsert {
3.653 +
3.654 + // Implementation of a special insertion method for the cheapest
3.655 + // selection rule
3.656 + class CheapestInsertion {
3.657 TEMPLATE_GRAPH_TYPEDEFS(FullGraph);
3.658 public:
3.659 - CheapestInsert(const FullGraph &, const CostMap &,
3.660 - std::vector<Node> &, Cost &fullcost) :
3.661 - _fullcost(fullcost) {}
3.662 -
3.663 + CheapestInsertion(const FullGraph &, const CostMap &,
3.664 + std::vector<Node> &, Cost &total_cost) :
3.665 + _total(total_cost) {}
3.666 +
3.667 void insert(Cost diff) const {
3.668 - _fullcost += diff;
3.669 + _total += diff;
3.670 }
3.671
3.672 private:
3.673 - Cost &_fullcost;
3.674 - };
3.675 -
3.676 -
3.677 - template <class InitFunctor, class SelectionFunctor, class InsertFunctor>
3.678 - void start() {
3.679 - InitFunctor init(_gr, _cost, nodesPath, notused, sum);
3.680 - SelectionFunctor selectNode(_gr, _cost, nodesPath, notused);
3.681 - InsertFunctor insertNode(_gr, _cost, nodesPath, sum);
3.682 -
3.683 - nodesPath = init.init();
3.684 -
3.685 - for (int i=0; i<_gr.nodeNum()-2; ++i) {
3.686 - insertNode.insert(selectNode.select());
3.687 - }
3.688 -
3.689 - sum = _cost[ _gr.edge(nodesPath.front(), nodesPath.back()) ];
3.690 - for (unsigned int i=0; i<nodesPath.size()-1; ++i)
3.691 - sum += _cost[ _gr.edge(nodesPath[i], nodesPath[i+1]) ];
3.692 - }
3.693 -
3.694 - const FullGraph &_gr;
3.695 - const CostMap &_cost;
3.696 - std::vector<Node> notused;
3.697 - std::vector<Node> nodesPath;
3.698 - Cost sum;
3.699 + Cost &_total;
3.700 + };
3.701 +
3.702 };
3.703 -
3.704 +
3.705 }; // namespace lemon
3.706
3.707 #endif
4.1 --- a/lemon/nearest_neighbor_tsp.h Sat Jan 08 22:49:09 2011 +0100
4.2 +++ b/lemon/nearest_neighbor_tsp.h Sat Jan 08 22:51:16 2011 +0100
4.3 @@ -1,145 +1,216 @@
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_NEAREST_NEIGHBOUR_TSP_H
4.23 #define LEMON_NEAREST_NEIGHBOUR_TSP_H
4.24
4.25 +/// \ingroup tsp
4.26 +/// \file
4.27 +/// \brief Nearest neighbor algorithm for symmetric TSP
4.28 +
4.29 #include <deque>
4.30 +#include <limits>
4.31 #include <lemon/full_graph.h>
4.32 -#include <lemon/path.h>
4.33 #include <lemon/maps.h>
4.34
4.35 namespace lemon {
4.36 -
4.37 - namespace nn_helper {
4.38 - template <class L>
4.39 - L dequeConvert(const std::deque<FullGraph::Node> &_path) {
4.40 - return L(_path.begin(), _path.end());
4.41 - }
4.42
4.43 - template <>
4.44 - std::deque<FullGraph::Node> dequeConvert(const std::deque<FullGraph::Node> &_path) {
4.45 - return _path;
4.46 - }
4.47 - }
4.48 -
4.49 + /// \brief Nearest neighbor algorithm for symmetric TSP.
4.50 + ///
4.51 + /// NearestNeighborTsp implements the nearest neighbor heuristic for solving
4.52 + /// symmetric \ref tsp "TSP".
4.53 + ///
4.54 + /// This is probably the simplest TSP heuristic.
4.55 + /// It starts with a minimum cost edge and at each step, it connects the
4.56 + /// nearest unvisited node to the current path.
4.57 + /// Finally, it connects the two end points of the path to form a tour.
4.58 + ///
4.59 + /// This method runs in O(n<sup>2</sup>) time.
4.60 + /// It quickly finds an effectively short tour for most TSP
4.61 + /// instances, but in special cases, it could yield a really bad
4.62 + /// (or even the worst) solution.
4.63 + ///
4.64 + /// \tparam CM Type of the cost map.
4.65 template <typename CM>
4.66 - class NearestNeighborTsp {
4.67 + class NearestNeighborTsp
4.68 + {
4.69 + public:
4.70 +
4.71 + /// Type of the cost map
4.72 + typedef CM CostMap;
4.73 + /// Type of the edge costs
4.74 + typedef typename CM::Value Cost;
4.75 +
4.76 private:
4.77 +
4.78 GRAPH_TYPEDEFS(FullGraph);
4.79
4.80 + const FullGraph &_gr;
4.81 + const CostMap &_cost;
4.82 + Cost _sum;
4.83 + std::deque<Node> _path;
4.84 +
4.85 public:
4.86 - typedef CM CostMap;
4.87 - typedef typename CM::Value Cost;
4.88 -
4.89 - NearestNeighborTsp(const FullGraph &gr, const CostMap &cost) : _gr(gr), _cost(cost) {}
4.90
4.91 + /// \brief Constructor
4.92 + ///
4.93 + /// Constructor.
4.94 + /// \param gr The \ref FullGraph "full graph" the algorithm runs on.
4.95 + /// \param cost The cost map.
4.96 + NearestNeighborTsp(const FullGraph &gr, const CostMap &cost)
4.97 + : _gr(gr), _cost(cost) {}
4.98 +
4.99 + /// \name Execution Control
4.100 + /// @{
4.101 +
4.102 + /// \brief Runs the algorithm.
4.103 + ///
4.104 + /// This function runs the algorithm.
4.105 + ///
4.106 + /// \return The total cost of the found tour.
4.107 Cost run() {
4.108 _path.clear();
4.109
4.110 + if (_gr.nodeNum() == 0) return _sum = 0;
4.111 + else if (_gr.nodeNum() == 1) {
4.112 + _path.push_back(_gr(0));
4.113 + return _sum = 0;
4.114 + }
4.115 +
4.116 Edge min_edge1 = INVALID,
4.117 min_edge2 = INVALID;
4.118 -
4.119 +
4.120 min_edge1 = mapMin(_gr, _cost);
4.121 -
4.122 - FullGraph::NodeMap<bool> used(_gr, false);
4.123 -
4.124 - Node n1 = _gr.u(min_edge1),
4.125 + Node n1 = _gr.u(min_edge1),
4.126 n2 = _gr.v(min_edge1);
4.127 -
4.128 _path.push_back(n1);
4.129 _path.push_back(n2);
4.130
4.131 + FullGraph::NodeMap<bool> used(_gr, false);
4.132 used[n1] = true;
4.133 used[n2] = true;
4.134
4.135 min_edge1 = INVALID;
4.136 -
4.137 while (int(_path.size()) != _gr.nodeNum()) {
4.138 if (min_edge1 == INVALID) {
4.139 - for (IncEdgeIt e(_gr, n1); e!=INVALID; ++e) {
4.140 - if (!used[_gr.runningNode(e)]) {
4.141 - if (min_edge1==INVALID || _cost[min_edge1] > _cost[e])
4.142 - min_edge1 = e;
4.143 + for (IncEdgeIt e(_gr, n1); e != INVALID; ++e) {
4.144 + if (!used[_gr.runningNode(e)] &&
4.145 + (_cost[e] < _cost[min_edge1] || min_edge1 == INVALID)) {
4.146 + min_edge1 = e;
4.147 }
4.148 }
4.149 }
4.150
4.151 if (min_edge2 == INVALID) {
4.152 - for (IncEdgeIt e(_gr, n2); e!=INVALID; ++e) {
4.153 - if (!used[_gr.runningNode(e)]) {
4.154 - if (min_edge2==INVALID || _cost[min_edge2] > _cost[e])
4.155 - min_edge2 = e;
4.156 + for (IncEdgeIt e(_gr, n2); e != INVALID; ++e) {
4.157 + if (!used[_gr.runningNode(e)] &&
4.158 + (_cost[e] < _cost[min_edge2] || min_edge2 == INVALID)) {
4.159 + min_edge2 = e;
4.160 }
4.161 }
4.162 }
4.163
4.164 - if ( _cost[min_edge1] < _cost[min_edge2] ) {
4.165 - n1 = (_gr.u(min_edge1) == n1) ? _gr.v(min_edge1) : _gr.u(min_edge1);
4.166 + if (_cost[min_edge1] < _cost[min_edge2]) {
4.167 + n1 = _gr.oppositeNode(n1, min_edge1);
4.168 _path.push_front(n1);
4.169
4.170 used[n1] = true;
4.171 min_edge1 = INVALID;
4.172
4.173 - if (_gr.u(min_edge2)==n1 || _gr.v(min_edge2)==n1)
4.174 + if (_gr.u(min_edge2) == n1 || _gr.v(min_edge2) == n1)
4.175 min_edge2 = INVALID;
4.176 } else {
4.177 - n2 = (_gr.u(min_edge2) == n2) ? _gr.v(min_edge2) : _gr.u(min_edge2);
4.178 + n2 = _gr.oppositeNode(n2, min_edge2);
4.179 _path.push_back(n2);
4.180
4.181 used[n2] = true;
4.182 min_edge2 = INVALID;
4.183
4.184 - if (_gr.u(min_edge1)==n2 || _gr.v(min_edge1)==n2)
4.185 + if (_gr.u(min_edge1) == n2 || _gr.v(min_edge1) == n2)
4.186 min_edge1 = INVALID;
4.187 }
4.188 }
4.189
4.190 - _sum = _cost[ _gr.edge(_path.back(), _path.front()) ];
4.191 - for (unsigned int i=0; i<_path.size()-1; ++i)
4.192 - _sum += _cost[ _gr.edge(_path[i], _path[i+1]) ];
4.193 + _sum = _cost[_gr.edge(_path.back(), _path.front())];
4.194 + for (int i = 0; i < int(_path.size())-1; ++i) {
4.195 + _sum += _cost[_gr.edge(_path[i], _path[i+1])];
4.196 + }
4.197
4.198 return _sum;
4.199 }
4.200
4.201 -
4.202 - template <typename L>
4.203 - void tourNodes(L &container) {
4.204 - container(nn_helper::dequeConvert<L>(_path));
4.205 + /// @}
4.206 +
4.207 + /// \name Query Functions
4.208 + /// @{
4.209 +
4.210 + /// \brief The total cost of the found tour.
4.211 + ///
4.212 + /// This function returns the total cost of the found tour.
4.213 + ///
4.214 + /// \pre run() must be called before using this function.
4.215 + Cost tourCost() const {
4.216 + return _sum;
4.217 }
4.218 -
4.219 - template <template <typename> class L>
4.220 - L<Node> tourNodes() {
4.221 - return nn_helper::dequeConvert<L<Node> >(_path);
4.222 - }
4.223
4.224 - const std::deque<Node>& tourNodes() {
4.225 + /// \brief Returns a const reference to the node sequence of the
4.226 + /// found tour.
4.227 + ///
4.228 + /// This function returns a const reference to the internal structure
4.229 + /// that stores the node sequence of the found tour.
4.230 + ///
4.231 + /// \pre run() must be called before using this function.
4.232 + const std::deque<Node>& tourNodes() const {
4.233 return _path;
4.234 }
4.235 -
4.236 - Path<FullGraph> tour() {
4.237 - Path<FullGraph> p;
4.238 - if (_path.size()<2)
4.239 - return p;
4.240 -
4.241 - for (unsigned int i=0; i<_path.size()-1; ++i) {
4.242 - p.addBack(_gr.arc(_path[i], _path[i+1]));
4.243 +
4.244 + /// \brief Gives back the node sequence of the found tour.
4.245 + ///
4.246 + /// This function copies the node sequence of the found tour into
4.247 + /// the given standard container.
4.248 + ///
4.249 + /// \pre run() must be called before using this function.
4.250 + template <typename Container>
4.251 + void tourNodes(Container &container) const {
4.252 + container.assign(_path.begin(), _path.end());
4.253 + }
4.254 +
4.255 + /// \brief Gives back the found tour as a path.
4.256 + ///
4.257 + /// This function copies the found tour as a list of arcs/edges into
4.258 + /// the given \ref concept::Path "path structure".
4.259 + ///
4.260 + /// \pre run() must be called before using this function.
4.261 + template <typename Path>
4.262 + void tour(Path &path) const {
4.263 + path.clear();
4.264 + for (int i = 0; i < int(_path.size()) - 1; ++i) {
4.265 + path.addBack(_gr.arc(_path[i], _path[i+1]));
4.266 }
4.267 - p.addBack(_gr.arc(_path.back(), _path.front()));
4.268 -
4.269 - return p;
4.270 + if (int(_path.size()) >= 2) {
4.271 + path.addBack(_gr.arc(_path.back(), _path.front()));
4.272 + }
4.273 }
4.274 -
4.275 - Cost tourCost() {
4.276 - return _sum;
4.277 - }
4.278 -
4.279
4.280 - private:
4.281 - const FullGraph &_gr;
4.282 - const CostMap &_cost;
4.283 - Cost _sum;
4.284 - std::deque<Node> _path;
4.285 + /// @}
4.286 +
4.287 };
4.288
4.289 -
4.290 }; // namespace lemon
4.291
4.292 #endif
5.1 --- a/lemon/opt2_tsp.h Sat Jan 08 22:49:09 2011 +0100
5.2 +++ b/lemon/opt2_tsp.h Sat Jan 08 22:51:16 2011 +0100
5.3 @@ -1,203 +1,354 @@
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_OPT2_TSP_H
5.23 #define LEMON_OPT2_TSP_H
5.24
5.25 +/// \ingroup tsp
5.26 +/// \file
5.27 +/// \brief 2-opt algorithm for symmetric TSP
5.28 +
5.29 #include <vector>
5.30 #include <lemon/full_graph.h>
5.31 -#include <lemon/path.h>
5.32
5.33 namespace lemon {
5.34 -
5.35 - namespace opt2_helper {
5.36 - template <class L>
5.37 - L vectorConvert(const std::vector<FullGraph::Node> &_path) {
5.38 - return L(_path.begin(), _path.end());
5.39 - }
5.40 -
5.41 - template <>
5.42 - std::vector<FullGraph::Node> vectorConvert(const std::vector<FullGraph::Node> &_path) {
5.43 - return _path;
5.44 - }
5.45 - }
5.46 -
5.47 +
5.48 + /// \brief 2-opt algorithm for symmetric TSP.
5.49 + ///
5.50 + /// Opt2Tsp implements the 2-opt heuristic for solving
5.51 + /// symmetric \ref tsp "TSP".
5.52 + ///
5.53 + /// This algorithm starts with an initial tour and iteratively improves it.
5.54 + /// At each step, it removes two edges and the reconnects the created two
5.55 + /// paths in the other way if the resulting tour is shorter.
5.56 + /// The algorithm finishes when no such 2-opt move can be applied, and so
5.57 + /// the tour is 2-optimal.
5.58 + ///
5.59 + /// If no starting tour is given to the \ref run() function, then the
5.60 + /// algorithm uses the node sequence determined by the node IDs.
5.61 + /// Oherwise, it starts with the given tour.
5.62 + ///
5.63 + /// This is a relatively slow but powerful method.
5.64 + /// A typical usage of it is the improvement of a solution that is resulted
5.65 + /// by a fast tour construction heuristic (e.g. the InsertionTsp algorithm).
5.66 + ///
5.67 + /// \tparam CM Type of the cost map.
5.68 template <typename CM>
5.69 - class Opt2Tsp {
5.70 + class Opt2Tsp
5.71 + {
5.72 + public:
5.73 +
5.74 + /// Type of the cost map
5.75 + typedef CM CostMap;
5.76 + /// Type of the edge costs
5.77 + typedef typename CM::Value Cost;
5.78 +
5.79 private:
5.80 +
5.81 GRAPH_TYPEDEFS(FullGraph);
5.82
5.83 + const FullGraph &_gr;
5.84 + const CostMap &_cost;
5.85 + Cost _sum;
5.86 + std::vector<int> _plist;
5.87 + std::vector<Node> _path;
5.88 +
5.89 public:
5.90 - typedef CM CostMap;
5.91 - typedef typename CM::Value Cost;
5.92 -
5.93 -
5.94 - Opt2Tsp(const FullGraph &gr, const CostMap &cost) : _gr(gr), _cost(cost),
5.95 - tmppath(_gr.nodeNum()*2) {
5.96 -
5.97 - for (int i=1; i<_gr.nodeNum()-1; ++i) {
5.98 - tmppath[2*i] = i-1;
5.99 - tmppath[2*i+1] = i+1;
5.100 +
5.101 + /// \brief Constructor
5.102 + ///
5.103 + /// Constructor.
5.104 + /// \param gr The \ref FullGraph "full graph" the algorithm runs on.
5.105 + /// \param cost The cost map.
5.106 + Opt2Tsp(const FullGraph &gr, const CostMap &cost)
5.107 + : _gr(gr), _cost(cost) {}
5.108 +
5.109 + /// \name Execution Control
5.110 + /// @{
5.111 +
5.112 + /// \brief Runs the algorithm from scratch.
5.113 + ///
5.114 + /// This function runs the algorithm starting from the tour that is
5.115 + /// determined by the node ID sequence.
5.116 + ///
5.117 + /// \return The total cost of the found tour.
5.118 + Cost run() {
5.119 + _path.clear();
5.120 +
5.121 + if (_gr.nodeNum() == 0) return _sum = 0;
5.122 + else if (_gr.nodeNum() == 1) {
5.123 + _path.push_back(_gr(0));
5.124 + return _sum = 0;
5.125 }
5.126 - tmppath[0] = _gr.nodeNum()-1;
5.127 - tmppath[1] = 1;
5.128 - tmppath[2*(_gr.nodeNum()-1)] = _gr.nodeNum()-2;
5.129 - tmppath[2*(_gr.nodeNum()-1)+1] = 0;
5.130 - }
5.131 -
5.132 - Opt2Tsp(const FullGraph &gr, const CostMap &cost, const std::vector<Node> &path) :
5.133 - _gr(gr), _cost(cost), tmppath(_gr.nodeNum()*2) {
5.134 + else if (_gr.nodeNum() == 2) {
5.135 + _path.push_back(_gr(0));
5.136 + _path.push_back(_gr(1));
5.137 + return _sum = 2 * _cost[_gr.edge(_gr(0), _gr(1))];
5.138 + }
5.139
5.140 - for (unsigned int i=1; i<path.size()-1; ++i) {
5.141 - tmppath[2*_gr.id(path[i])] = _gr.id(path[i-1]);
5.142 - tmppath[2*_gr.id(path[i])+1] = _gr.id(path[i+1]);
5.143 + _plist.resize(2*_gr.nodeNum());
5.144 + for (int i = 1; i < _gr.nodeNum()-1; ++i) {
5.145 + _plist[2*i] = i-1;
5.146 + _plist[2*i+1] = i+1;
5.147 }
5.148 -
5.149 - tmppath[2*_gr.id(path[0])] = _gr.id(path.back());
5.150 - tmppath[2*_gr.id(path[0])+1] = _gr.id(path[1]);
5.151 - tmppath[2*_gr.id(path.back())] = _gr.id(path[path.size()-2]);
5.152 - tmppath[2*_gr.id(path.back())+1] = _gr.id(path.front());
5.153 + _plist[0] = _gr.nodeNum()-1;
5.154 + _plist[1] = 1;
5.155 + _plist[2*_gr.nodeNum()-2] = _gr.nodeNum()-2;
5.156 + _plist[2*_gr.nodeNum()-1] = 0;
5.157 +
5.158 + return start();
5.159 }
5.160
5.161 + /// \brief Runs the algorithm from the given tour.
5.162 + ///
5.163 + /// This function runs the algorithm starting from the given tour.
5.164 + ///
5.165 + /// \param tour The tour as a path structure. It must be a
5.166 + /// \ref checkPath() "valid path" containing excactly n arcs.
5.167 + ///
5.168 + /// \return The total cost of the found tour.
5.169 + template <typename Path>
5.170 + Cost run(const Path& tour) {
5.171 + _path.clear();
5.172 +
5.173 + if (_gr.nodeNum() == 0) return _sum = 0;
5.174 + else if (_gr.nodeNum() == 1) {
5.175 + _path.push_back(_gr(0));
5.176 + return _sum = 0;
5.177 + }
5.178 + else if (_gr.nodeNum() == 2) {
5.179 + _path.push_back(_gr(0));
5.180 + _path.push_back(_gr(1));
5.181 + return _sum = 2 * _cost[_gr.edge(_gr(0), _gr(1))];
5.182 + }
5.183 +
5.184 + _plist.resize(2*_gr.nodeNum());
5.185 + typename Path::ArcIt it(tour);
5.186 + int first = _gr.id(_gr.source(it)),
5.187 + prev = first,
5.188 + curr = _gr.id(_gr.target(it)),
5.189 + next = -1;
5.190 + _plist[2*first+1] = curr;
5.191 + for (++it; it != INVALID; ++it) {
5.192 + next = _gr.id(_gr.target(it));
5.193 + _plist[2*curr] = prev;
5.194 + _plist[2*curr+1] = next;
5.195 + prev = curr;
5.196 + curr = next;
5.197 + }
5.198 + _plist[2*first] = prev;
5.199 +
5.200 + return start();
5.201 + }
5.202 +
5.203 + /// \brief Runs the algorithm from the given tour.
5.204 + ///
5.205 + /// This function runs the algorithm starting from the given tour.
5.206 + ///
5.207 + /// \param tour The tour as a node sequence. It must be a standard
5.208 + /// sequence container storing all <tt>Node</tt>s in the desired order.
5.209 + ///
5.210 + /// \return The total cost of the found tour.
5.211 + template <template <typename> class Container>
5.212 + Cost run(const Container<Node>& tour) {
5.213 + _path.clear();
5.214 +
5.215 + if (_gr.nodeNum() == 0) return _sum = 0;
5.216 + else if (_gr.nodeNum() == 1) {
5.217 + _path.push_back(_gr(0));
5.218 + return _sum = 0;
5.219 + }
5.220 + else if (_gr.nodeNum() == 2) {
5.221 + _path.push_back(_gr(0));
5.222 + _path.push_back(_gr(1));
5.223 + return _sum = 2 * _cost[_gr.edge(_gr(0), _gr(1))];
5.224 + }
5.225 +
5.226 + _plist.resize(2*_gr.nodeNum());
5.227 + typename Container<Node>::const_iterator it = tour.begin();
5.228 + int first = _gr.id(*it),
5.229 + prev = first,
5.230 + curr = _gr.id(*(++it)),
5.231 + next = -1;
5.232 + _plist[2*first+1] = curr;
5.233 + for (++it; it != tour.end(); ++it) {
5.234 + next = _gr.id(*it);
5.235 + _plist[2*curr] = prev;
5.236 + _plist[2*curr+1] = next;
5.237 + prev = curr;
5.238 + curr = next;
5.239 + }
5.240 + _plist[2*first] = curr;
5.241 + _plist[2*curr] = prev;
5.242 + _plist[2*curr+1] = first;
5.243 +
5.244 + return start();
5.245 + }
5.246 +
5.247 + /// @}
5.248 +
5.249 + /// \name Query Functions
5.250 + /// @{
5.251 +
5.252 + /// \brief The total cost of the found tour.
5.253 + ///
5.254 + /// This function returns the total cost of the found tour.
5.255 + ///
5.256 + /// \pre run() must be called before using this function.
5.257 + Cost tourCost() const {
5.258 + return _sum;
5.259 + }
5.260 +
5.261 + /// \brief Returns a const reference to the node sequence of the
5.262 + /// found tour.
5.263 + ///
5.264 + /// This function returns a const reference to the internal structure
5.265 + /// that stores the node sequence of the found tour.
5.266 + ///
5.267 + /// \pre run() must be called before using this function.
5.268 + const std::vector<Node>& tourNodes() const {
5.269 + return _path;
5.270 + }
5.271 +
5.272 + /// \brief Gives back the node sequence of the found tour.
5.273 + ///
5.274 + /// This function copies the node sequence of the found tour into
5.275 + /// the given standard container.
5.276 + ///
5.277 + /// \pre run() must be called before using this function.
5.278 + template <typename Container>
5.279 + void tourNodes(Container &container) const {
5.280 + container.assign(_path.begin(), _path.end());
5.281 + }
5.282 +
5.283 + /// \brief Gives back the found tour as a path.
5.284 + ///
5.285 + /// This function copies the found tour as a list of arcs/edges into
5.286 + /// the given \ref concept::Path "path structure".
5.287 + ///
5.288 + /// \pre run() must be called before using this function.
5.289 + template <typename Path>
5.290 + void tour(Path &path) const {
5.291 + path.clear();
5.292 + for (int i = 0; i < int(_path.size()) - 1; ++i) {
5.293 + path.addBack(_gr.arc(_path[i], _path[i+1]));
5.294 + }
5.295 + if (int(_path.size()) >= 2) {
5.296 + path.addBack(_gr.arc(_path.back(), _path.front()));
5.297 + }
5.298 + }
5.299 +
5.300 + /// @}
5.301 +
5.302 private:
5.303 - Cost c(int u, int v) {
5.304 - return _cost[_gr.edge(_gr.nodeFromId(u), _gr.nodeFromId(v))];
5.305 - }
5.306 -
5.307 - class It {
5.308 +
5.309 + // Iterator class for the linked list storage of the tour
5.310 + class PathListIt {
5.311 public:
5.312 - It(const std::vector<int> &path, int i=0) : tmppath(path), act(i), last(tmppath[2*act]) {}
5.313 - It(const std::vector<int> &path, int i, int l) : tmppath(path), act(i), last(l) {}
5.314 + PathListIt(const std::vector<int> &pl, int i=0)
5.315 + : plist(&pl), act(i), last(pl[2*act]) {}
5.316 + PathListIt(const std::vector<int> &pl, int i, int l)
5.317 + : plist(&pl), act(i), last(l) {}
5.318
5.319 - int next_index() const {
5.320 - return (tmppath[2*act]==last)? 2*act+1 : 2*act;
5.321 + int nextIndex() const {
5.322 + return (*plist)[2*act] == last ? 2*act+1 : 2*act;
5.323 }
5.324 -
5.325 - int prev_index() const {
5.326 - return (tmppath[2*act]==last)? 2*act : 2*act+1;
5.327 +
5.328 + int prevIndex() const {
5.329 + return (*plist)[2*act] == last ? 2*act : 2*act+1;
5.330 }
5.331 -
5.332 +
5.333 int next() const {
5.334 - return tmppath[next_index()];
5.335 + int x = (*plist)[2*act];
5.336 + return x == last ? (*plist)[2*act+1] : x;
5.337 }
5.338
5.339 int prev() const {
5.340 - return tmppath[prev_index()];
5.341 + return last;
5.342 }
5.343 -
5.344 - It& operator++() {
5.345 +
5.346 + PathListIt& operator++() {
5.347 int tmp = act;
5.348 act = next();
5.349 last = tmp;
5.350 return *this;
5.351 }
5.352 -
5.353 +
5.354 operator int() const {
5.355 return act;
5.356 }
5.357 -
5.358 +
5.359 private:
5.360 - const std::vector<int> &tmppath;
5.361 + const std::vector<int> *plist;
5.362 int act;
5.363 int last;
5.364 };
5.365
5.366 - bool check(std::vector<int> &path, It i, It j) {
5.367 - if (c(i, i.next()) + c(j, j.next()) >
5.368 - c(i, j) + c(j.next(), i.next())) {
5.369 + // Checks and applies 2-opt move (if it improves the tour)
5.370 + bool checkOpt2(const PathListIt& i, const PathListIt& j) {
5.371 + Node u = _gr.nodeFromId(i),
5.372 + un = _gr.nodeFromId(i.next()),
5.373 + v = _gr.nodeFromId(j),
5.374 + vn = _gr.nodeFromId(j.next());
5.375
5.376 - path[ It(path, i.next(), i).prev_index() ] = j.next();
5.377 - path[ It(path, j.next(), j).prev_index() ] = i.next();
5.378 + if (_cost[_gr.edge(u, un)] + _cost[_gr.edge(v, vn)] >
5.379 + _cost[_gr.edge(u, v)] + _cost[_gr.edge(un, vn)])
5.380 + {
5.381 + _plist[PathListIt(_plist, i.next(), i).prevIndex()] = j.next();
5.382 + _plist[PathListIt(_plist, j.next(), j).prevIndex()] = i.next();
5.383
5.384 - path[i.next_index()] = j;
5.385 - path[j.next_index()] = i;
5.386 + _plist[i.nextIndex()] = j;
5.387 + _plist[j.nextIndex()] = i;
5.388
5.389 - return true;
5.390 + return true;
5.391 }
5.392 +
5.393 return false;
5.394 - }
5.395 -
5.396 - public:
5.397 -
5.398 - Cost run() {
5.399 - _path.clear();
5.400 + }
5.401
5.402 - if (_gr.nodeNum()>3) {
5.403 + // Executes the algorithm from the initial tour
5.404 + Cost start() {
5.405
5.406 -opt2_tsp_label:
5.407 - It i(tmppath);
5.408 - It j(tmppath, i, i.prev());
5.409 - ++j; ++j;
5.410 - for (; j.next()!=0; ++j) {
5.411 - if (check(tmppath, i, j))
5.412 - goto opt2_tsp_label;
5.413 - }
5.414 -
5.415 - for (++i; i.next()!=0; ++i) {
5.416 - It j(tmppath, i, i.prev());
5.417 - if (++j==0)
5.418 - break;
5.419 - if (++j==0)
5.420 - break;
5.421 -
5.422 - for (; j!=0; ++j) {
5.423 - if (check(tmppath, i, j))
5.424 - goto opt2_tsp_label;
5.425 - }
5.426 + restart_search:
5.427 + for (PathListIt i(_plist); true; ++i) {
5.428 + PathListIt j = i;
5.429 + if (++j == 0 || ++j == 0) break;
5.430 + for (; j != 0 && j != i.prev(); ++j) {
5.431 + if (checkOpt2(i, j))
5.432 + goto restart_search;
5.433 }
5.434 }
5.435
5.436 - It k(tmppath);
5.437 - _path.push_back(_gr.nodeFromId(k));
5.438 - for (++k; k!=0; ++k)
5.439 - _path.push_back(_gr.nodeFromId(k));
5.440 + PathListIt i(_plist);
5.441 + _path.push_back(_gr.nodeFromId(i));
5.442 + for (++i; i != 0; ++i)
5.443 + _path.push_back(_gr.nodeFromId(i));
5.444
5.445 -
5.446 + _sum = _cost[_gr.edge(_path.back(), _path.front())];
5.447 + for (int i = 0; i < int(_path.size())-1; ++i) {
5.448 + _sum += _cost[_gr.edge(_path[i], _path[i+1])];
5.449 + }
5.450
5.451 - _sum = _cost[ _gr.edge(_path.back(), _path.front()) ];
5.452 - for (unsigned int i=0; i<_path.size()-1; ++i)
5.453 - _sum += _cost[ _gr.edge(_path[i], _path[i+1]) ];
5.454 return _sum;
5.455 }
5.456
5.457 -
5.458 - template <typename L>
5.459 - void tourNodes(L &container) {
5.460 - container(opt2_helper::vectorConvert<L>(_path));
5.461 - }
5.462 -
5.463 - template <template <typename> class L>
5.464 - L<Node> tourNodes() {
5.465 - return opt2_helper::vectorConvert<L<Node> >(_path);
5.466 - }
5.467 -
5.468 - const std::vector<Node>& tourNodes() {
5.469 - return _path;
5.470 - }
5.471 -
5.472 - Path<FullGraph> tour() {
5.473 - Path<FullGraph> p;
5.474 - if (_path.size()<2)
5.475 - return p;
5.476 -
5.477 - for (unsigned int i=0; i<_path.size()-1; ++i) {
5.478 - p.addBack(_gr.arc(_path[i], _path[i+1]));
5.479 - }
5.480 - p.addBack(_gr.arc(_path.back(), _path.front()));
5.481 - return p;
5.482 - }
5.483 -
5.484 - Cost tourCost() {
5.485 - return _sum;
5.486 - }
5.487 -
5.488 -
5.489 - private:
5.490 - const FullGraph &_gr;
5.491 - const CostMap &_cost;
5.492 - Cost _sum;
5.493 - std::vector<int> tmppath;
5.494 - std::vector<Node> _path;
5.495 };
5.496
5.497 -
5.498 }; // namespace lemon
5.499
5.500 #endif