1.1 --- a/lemon/nearest_neighbor_tsp.h Sat Jan 08 22:51:16 2011 +0100
1.2 +++ b/lemon/nearest_neighbor_tsp.h Sun Jan 09 00:56:52 2011 +0100
1.3 @@ -24,12 +24,15 @@
1.4 /// \brief Nearest neighbor algorithm for symmetric TSP
1.5
1.6 #include <deque>
1.7 +#include <vector>
1.8 #include <limits>
1.9 #include <lemon/full_graph.h>
1.10 #include <lemon/maps.h>
1.11
1.12 namespace lemon {
1.13
1.14 + /// \ingroup tsp
1.15 + ///
1.16 /// \brief Nearest neighbor algorithm for symmetric TSP.
1.17 ///
1.18 /// NearestNeighborTsp implements the nearest neighbor heuristic for solving
1.19 @@ -41,9 +44,8 @@
1.20 /// Finally, it connects the two end points of the path to form a tour.
1.21 ///
1.22 /// This method runs in O(n<sup>2</sup>) time.
1.23 - /// It quickly finds an effectively short tour for most TSP
1.24 - /// instances, but in special cases, it could yield a really bad
1.25 - /// (or even the worst) solution.
1.26 + /// It quickly finds a short tour for most TSP instances, but in special
1.27 + /// cases, it could yield a really bad (or even the worst) solution.
1.28 ///
1.29 /// \tparam CM Type of the cost map.
1.30 template <typename CM>
1.31 @@ -63,7 +65,7 @@
1.32 const FullGraph &_gr;
1.33 const CostMap &_cost;
1.34 Cost _sum;
1.35 - std::deque<Node> _path;
1.36 + std::vector<Node> _path;
1.37
1.38 public:
1.39
1.40 @@ -85,28 +87,30 @@
1.41 /// \return The total cost of the found tour.
1.42 Cost run() {
1.43 _path.clear();
1.44 -
1.45 - if (_gr.nodeNum() == 0) return _sum = 0;
1.46 + if (_gr.nodeNum() == 0) {
1.47 + return _sum = 0;
1.48 + }
1.49 else if (_gr.nodeNum() == 1) {
1.50 _path.push_back(_gr(0));
1.51 return _sum = 0;
1.52 }
1.53
1.54 + std::deque<Node> path_dq;
1.55 Edge min_edge1 = INVALID,
1.56 min_edge2 = INVALID;
1.57
1.58 min_edge1 = mapMin(_gr, _cost);
1.59 Node n1 = _gr.u(min_edge1),
1.60 n2 = _gr.v(min_edge1);
1.61 - _path.push_back(n1);
1.62 - _path.push_back(n2);
1.63 + path_dq.push_back(n1);
1.64 + path_dq.push_back(n2);
1.65
1.66 FullGraph::NodeMap<bool> used(_gr, false);
1.67 used[n1] = true;
1.68 used[n2] = true;
1.69
1.70 min_edge1 = INVALID;
1.71 - while (int(_path.size()) != _gr.nodeNum()) {
1.72 + while (int(path_dq.size()) != _gr.nodeNum()) {
1.73 if (min_edge1 == INVALID) {
1.74 for (IncEdgeIt e(_gr, n1); e != INVALID; ++e) {
1.75 if (!used[_gr.runningNode(e)] &&
1.76 @@ -127,7 +131,7 @@
1.77
1.78 if (_cost[min_edge1] < _cost[min_edge2]) {
1.79 n1 = _gr.oppositeNode(n1, min_edge1);
1.80 - _path.push_front(n1);
1.81 + path_dq.push_front(n1);
1.82
1.83 used[n1] = true;
1.84 min_edge1 = INVALID;
1.85 @@ -136,7 +140,7 @@
1.86 min_edge2 = INVALID;
1.87 } else {
1.88 n2 = _gr.oppositeNode(n2, min_edge2);
1.89 - _path.push_back(n2);
1.90 + path_dq.push_back(n2);
1.91
1.92 used[n2] = true;
1.93 min_edge2 = INVALID;
1.94 @@ -146,9 +150,15 @@
1.95 }
1.96 }
1.97
1.98 - _sum = _cost[_gr.edge(_path.back(), _path.front())];
1.99 - for (int i = 0; i < int(_path.size())-1; ++i) {
1.100 - _sum += _cost[_gr.edge(_path[i], _path[i+1])];
1.101 + n1 = path_dq.back();
1.102 + n2 = path_dq.front();
1.103 + _path.push_back(n2);
1.104 + _sum = _cost[_gr.edge(n1, n2)];
1.105 + for (int i = 1; i < int(path_dq.size()); ++i) {
1.106 + n1 = n2;
1.107 + n2 = path_dq[i];
1.108 + _path.push_back(n2);
1.109 + _sum += _cost[_gr.edge(n1, n2)];
1.110 }
1.111
1.112 return _sum;
1.113 @@ -171,11 +181,11 @@
1.114 /// \brief Returns a const reference to the node sequence of the
1.115 /// found tour.
1.116 ///
1.117 - /// This function returns a const reference to the internal structure
1.118 + /// This function returns a const reference to a vector
1.119 /// that stores the node sequence of the found tour.
1.120 ///
1.121 /// \pre run() must be called before using this function.
1.122 - const std::deque<Node>& tourNodes() const {
1.123 + const std::vector<Node>& tourNodes() const {
1.124 return _path;
1.125 }
1.126