1.1 --- a/doc/groups.dox Sat Jan 08 22:51:16 2011 +0100
1.2 +++ b/doc/groups.dox Sun Jan 09 00:56:52 2011 +0100
1.3 @@ -561,8 +561,9 @@
1.4 the problem is to find a shortest possible tour that visits each node exactly
1.5 once (i.e. the minimum cost Hamiltonian cycle).
1.6
1.7 -These TSP algorithms should be used with a
1.8 -metric cost function. Otherwise, they could yield worse results.
1.9 +These TSP algorithms are intended to be used with a \e metric \e cost
1.10 +\e function, i.e. the edge costs should satisfy the triangle inequality.
1.11 +Otherwise the algorithms could yield worse results.
1.12
1.13 LEMON provides five well-known heuristics for solving symmetric TSP:
1.14 - \ref NearestNeighborTsp Neareast neighbor algorithm
2.1 --- a/lemon/christofides_tsp.h Sat Jan 08 22:51:16 2011 +0100
2.2 +++ b/lemon/christofides_tsp.h Sun Jan 09 00:56:52 2011 +0100
2.3 @@ -31,13 +31,15 @@
2.4
2.5 namespace lemon {
2.6
2.7 + /// \ingroup tsp
2.8 + ///
2.9 /// \brief Christofides algorithm for symmetric TSP.
2.10 ///
2.11 /// ChristofidesTsp implements Christofides' heuristic for solving
2.12 /// symmetric \ref tsp "TSP".
2.13 ///
2.14 /// This a well-known approximation method for the TSP problem with
2.15 - /// \ref checkMetricCost() "metric cost function".
2.16 + /// metric cost function.
2.17 /// It yields a tour whose total cost is at most 3/2 of the optimum,
2.18 /// but it is usually much better.
2.19 /// This implementation runs in O(n<sup>3</sup>log(n)) time.
2.20 @@ -54,7 +56,7 @@
2.21 ///
2.22 /// \tparam CM Type of the cost map.
2.23 ///
2.24 - /// \warning \& CM::Value must be signed type.
2.25 + /// \warning CM::Value must be a signed number type.
2.26 template <typename CM>
2.27 class ChristofidesTsp
2.28 {
2.29 @@ -195,7 +197,7 @@
2.30 /// \brief Returns a const reference to the node sequence of the
2.31 /// found tour.
2.32 ///
2.33 - /// This function returns a const reference to the internal structure
2.34 + /// This function returns a const reference to a vector
2.35 /// that stores the node sequence of the found tour.
2.36 ///
2.37 /// \pre run() must be called before using this function.
3.1 --- a/lemon/greedy_tsp.h Sat Jan 08 22:51:16 2011 +0100
3.2 +++ b/lemon/greedy_tsp.h Sun Jan 09 00:56:52 2011 +0100
3.3 @@ -30,6 +30,8 @@
3.4
3.5 namespace lemon {
3.6
3.7 + /// \ingroup tsp
3.8 + ///
3.9 /// \brief Greedy algorithm for symmetric TSP.
3.10 ///
3.11 /// GreedyTsp implements the greedy heuristic for solving
3.12 @@ -42,9 +44,8 @@
3.13 /// not increase the degree of any node above two.
3.14 ///
3.15 /// This method runs in O(n<sup>2</sup>log(n)) time.
3.16 - /// It quickly finds an effectively short tour for most TSP
3.17 - /// instances, but in special cases, it could yield a really bad
3.18 - /// (or even the worst) solution.
3.19 + /// It quickly finds a short tour for most TSP instances, but in special
3.20 + /// cases, it could yield a really bad (or even the worst) solution.
3.21 ///
3.22 /// \tparam CM Type of the cost map.
3.23 template <typename CM>
3.24 @@ -193,7 +194,7 @@
3.25 /// \brief Returns a const reference to the node sequence of the
3.26 /// found tour.
3.27 ///
3.28 - /// This function returns a const reference to the internal structure
3.29 + /// This function returns a const reference to a vector
3.30 /// that stores the node sequence of the found tour.
3.31 ///
3.32 /// \pre run() must be called before using this function.
4.1 --- a/lemon/insertion_tsp.h Sat Jan 08 22:51:16 2011 +0100
4.2 +++ b/lemon/insertion_tsp.h Sun Jan 09 00:56:52 2011 +0100
4.3 @@ -30,6 +30,8 @@
4.4
4.5 namespace lemon {
4.6
4.7 + /// \ingroup tsp
4.8 + ///
4.9 /// \brief Insertion algorithm for symmetric TSP.
4.10 ///
4.11 /// InsertionTsp implements the insertion heuristic for solving
4.12 @@ -74,9 +76,9 @@
4.13 ///
4.14 /// During the algorithm, nodes are selected for addition to the current
4.15 /// subtour according to the applied rule.
4.16 - /// In general, the FARTHEST yields the best tours, thus it is the
4.17 - /// default option. RANDOM usually gives somewhat worse results, but
4.18 - /// it is much faster than the others and it is the most robust.
4.19 + /// In general, the FARTHEST method yields the best tours, thus it is the
4.20 + /// default option. The RANDOM rule usually gives somewhat worse results,
4.21 + /// but it is much faster than the others and it is the most robust.
4.22 ///
4.23 /// The desired selection rule can be specified as a parameter of the
4.24 /// \ref run() function.
4.25 @@ -178,7 +180,7 @@
4.26 /// \brief Returns a const reference to the node sequence of the
4.27 /// found tour.
4.28 ///
4.29 - /// This function returns a const reference to the internal structure
4.30 + /// This function returns a const reference to a vector
4.31 /// that stores the node sequence of the found tour.
4.32 ///
4.33 /// \pre run() must be called before using this function.
5.1 --- a/lemon/nearest_neighbor_tsp.h Sat Jan 08 22:51:16 2011 +0100
5.2 +++ b/lemon/nearest_neighbor_tsp.h Sun Jan 09 00:56:52 2011 +0100
5.3 @@ -24,12 +24,15 @@
5.4 /// \brief Nearest neighbor algorithm for symmetric TSP
5.5
5.6 #include <deque>
5.7 +#include <vector>
5.8 #include <limits>
5.9 #include <lemon/full_graph.h>
5.10 #include <lemon/maps.h>
5.11
5.12 namespace lemon {
5.13
5.14 + /// \ingroup tsp
5.15 + ///
5.16 /// \brief Nearest neighbor algorithm for symmetric TSP.
5.17 ///
5.18 /// NearestNeighborTsp implements the nearest neighbor heuristic for solving
5.19 @@ -41,9 +44,8 @@
5.20 /// Finally, it connects the two end points of the path to form a tour.
5.21 ///
5.22 /// This method runs in O(n<sup>2</sup>) time.
5.23 - /// It quickly finds an effectively short tour for most TSP
5.24 - /// instances, but in special cases, it could yield a really bad
5.25 - /// (or even the worst) solution.
5.26 + /// It quickly finds a short tour for most TSP instances, but in special
5.27 + /// cases, it could yield a really bad (or even the worst) solution.
5.28 ///
5.29 /// \tparam CM Type of the cost map.
5.30 template <typename CM>
5.31 @@ -63,7 +65,7 @@
5.32 const FullGraph &_gr;
5.33 const CostMap &_cost;
5.34 Cost _sum;
5.35 - std::deque<Node> _path;
5.36 + std::vector<Node> _path;
5.37
5.38 public:
5.39
5.40 @@ -85,28 +87,30 @@
5.41 /// \return The total cost of the found tour.
5.42 Cost run() {
5.43 _path.clear();
5.44 -
5.45 - if (_gr.nodeNum() == 0) return _sum = 0;
5.46 + if (_gr.nodeNum() == 0) {
5.47 + return _sum = 0;
5.48 + }
5.49 else if (_gr.nodeNum() == 1) {
5.50 _path.push_back(_gr(0));
5.51 return _sum = 0;
5.52 }
5.53
5.54 + std::deque<Node> path_dq;
5.55 Edge min_edge1 = INVALID,
5.56 min_edge2 = INVALID;
5.57
5.58 min_edge1 = mapMin(_gr, _cost);
5.59 Node n1 = _gr.u(min_edge1),
5.60 n2 = _gr.v(min_edge1);
5.61 - _path.push_back(n1);
5.62 - _path.push_back(n2);
5.63 + path_dq.push_back(n1);
5.64 + path_dq.push_back(n2);
5.65
5.66 FullGraph::NodeMap<bool> used(_gr, false);
5.67 used[n1] = true;
5.68 used[n2] = true;
5.69
5.70 min_edge1 = INVALID;
5.71 - while (int(_path.size()) != _gr.nodeNum()) {
5.72 + while (int(path_dq.size()) != _gr.nodeNum()) {
5.73 if (min_edge1 == INVALID) {
5.74 for (IncEdgeIt e(_gr, n1); e != INVALID; ++e) {
5.75 if (!used[_gr.runningNode(e)] &&
5.76 @@ -127,7 +131,7 @@
5.77
5.78 if (_cost[min_edge1] < _cost[min_edge2]) {
5.79 n1 = _gr.oppositeNode(n1, min_edge1);
5.80 - _path.push_front(n1);
5.81 + path_dq.push_front(n1);
5.82
5.83 used[n1] = true;
5.84 min_edge1 = INVALID;
5.85 @@ -136,7 +140,7 @@
5.86 min_edge2 = INVALID;
5.87 } else {
5.88 n2 = _gr.oppositeNode(n2, min_edge2);
5.89 - _path.push_back(n2);
5.90 + path_dq.push_back(n2);
5.91
5.92 used[n2] = true;
5.93 min_edge2 = INVALID;
5.94 @@ -146,9 +150,15 @@
5.95 }
5.96 }
5.97
5.98 - _sum = _cost[_gr.edge(_path.back(), _path.front())];
5.99 - for (int i = 0; i < int(_path.size())-1; ++i) {
5.100 - _sum += _cost[_gr.edge(_path[i], _path[i+1])];
5.101 + n1 = path_dq.back();
5.102 + n2 = path_dq.front();
5.103 + _path.push_back(n2);
5.104 + _sum = _cost[_gr.edge(n1, n2)];
5.105 + for (int i = 1; i < int(path_dq.size()); ++i) {
5.106 + n1 = n2;
5.107 + n2 = path_dq[i];
5.108 + _path.push_back(n2);
5.109 + _sum += _cost[_gr.edge(n1, n2)];
5.110 }
5.111
5.112 return _sum;
5.113 @@ -171,11 +181,11 @@
5.114 /// \brief Returns a const reference to the node sequence of the
5.115 /// found tour.
5.116 ///
5.117 - /// This function returns a const reference to the internal structure
5.118 + /// This function returns a const reference to a vector
5.119 /// that stores the node sequence of the found tour.
5.120 ///
5.121 /// \pre run() must be called before using this function.
5.122 - const std::deque<Node>& tourNodes() const {
5.123 + const std::vector<Node>& tourNodes() const {
5.124 return _path;
5.125 }
5.126
6.1 --- a/lemon/opt2_tsp.h Sat Jan 08 22:51:16 2011 +0100
6.2 +++ b/lemon/opt2_tsp.h Sun Jan 09 00:56:52 2011 +0100
6.3 @@ -21,13 +21,15 @@
6.4
6.5 /// \ingroup tsp
6.6 /// \file
6.7 -/// \brief 2-opt algorithm for symmetric TSP
6.8 +/// \brief 2-opt algorithm for symmetric TSP.
6.9
6.10 #include <vector>
6.11 #include <lemon/full_graph.h>
6.12
6.13 namespace lemon {
6.14
6.15 + /// \ingroup tsp
6.16 + ///
6.17 /// \brief 2-opt algorithm for symmetric TSP.
6.18 ///
6.19 /// Opt2Tsp implements the 2-opt heuristic for solving
6.20 @@ -114,7 +116,7 @@
6.21 return start();
6.22 }
6.23
6.24 - /// \brief Runs the algorithm from the given tour.
6.25 + /// \brief Runs the algorithm starting from the given tour.
6.26 ///
6.27 /// This function runs the algorithm starting from the given tour.
6.28 ///
6.29 @@ -156,16 +158,16 @@
6.30 return start();
6.31 }
6.32
6.33 - /// \brief Runs the algorithm from the given tour.
6.34 + /// \brief Runs the algorithm starting from the given tour.
6.35 ///
6.36 - /// This function runs the algorithm starting from the given tour.
6.37 + /// This function runs the algorithm starting from the given tour
6.38 + /// (node sequence).
6.39 ///
6.40 - /// \param tour The tour as a node sequence. It must be a standard
6.41 - /// sequence container storing all <tt>Node</tt>s in the desired order.
6.42 + /// \param tour A vector that stores all <tt>Node</tt>s of the graph
6.43 + /// in the desired order.
6.44 ///
6.45 /// \return The total cost of the found tour.
6.46 - template <template <typename> class Container>
6.47 - Cost run(const Container<Node>& tour) {
6.48 + Cost run(const std::vector<Node>& tour) {
6.49 _path.clear();
6.50
6.51 if (_gr.nodeNum() == 0) return _sum = 0;
6.52 @@ -180,7 +182,7 @@
6.53 }
6.54
6.55 _plist.resize(2*_gr.nodeNum());
6.56 - typename Container<Node>::const_iterator it = tour.begin();
6.57 + typename std::vector<Node>::const_iterator it = tour.begin();
6.58 int first = _gr.id(*it),
6.59 prev = first,
6.60 curr = _gr.id(*(++it)),
6.61 @@ -217,7 +219,7 @@
6.62 /// \brief Returns a const reference to the node sequence of the
6.63 /// found tour.
6.64 ///
6.65 - /// This function returns a const reference to the internal structure
6.66 + /// This function returns a const reference to a vector
6.67 /// that stores the node sequence of the found tour.
6.68 ///
6.69 /// \pre run() must be called before using this function.