1.1 --- a/lemon/insertion_tsp.h Sat Jan 08 22:49:09 2011 +0100
1.2 +++ b/lemon/insertion_tsp.h Sat Jan 08 22:51:16 2011 +0100
1.3 @@ -1,225 +1,349 @@
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_INSERTION_TSP_H
1.23 #define LEMON_INSERTION_TSP_H
1.24
1.25 +/// \ingroup tsp
1.26 +/// \file
1.27 +/// \brief Insertion algorithm for symmetric TSP
1.28 +
1.29 +#include <vector>
1.30 #include <lemon/full_graph.h>
1.31 -#include <lemon/path.h>
1.32 #include <lemon/maps.h>
1.33 #include <lemon/random.h>
1.34 -#include <vector>
1.35
1.36 namespace lemon {
1.37
1.38 - namespace insertion_tsp_helper {
1.39 -
1.40 - template <class L>
1.41 - L vectorConvert(const std::vector<FullGraph::Node> &_path) {
1.42 - return L(_path.begin(), _path.end());
1.43 - };
1.44 -
1.45 - template <>
1.46 - std::vector<FullGraph::Node> vectorConvert(
1.47 - const std::vector<FullGraph::Node> &_path) {
1.48 - return _path;
1.49 - };
1.50 -
1.51 - };
1.52 + /// \brief Insertion algorithm for symmetric TSP.
1.53 + ///
1.54 + /// InsertionTsp implements the insertion heuristic for solving
1.55 + /// symmetric \ref tsp "TSP".
1.56 + ///
1.57 + /// This is a basic TSP heuristic that has many variants.
1.58 + /// It starts with a subtour containing a few nodes of the graph and it
1.59 + /// iteratively inserts the other nodes into this subtour according to a
1.60 + /// certain node selection rule.
1.61 + ///
1.62 + /// This implementation provides four different node selection rules,
1.63 + /// from which the most powerful one is used by default.
1.64 + /// For more information, see \ref SelectionRule.
1.65 + ///
1.66 + /// \tparam CM Type of the cost map.
1.67 + template <typename CM>
1.68 + class InsertionTsp
1.69 + {
1.70 + public:
1.71
1.72 - template <typename CM>
1.73 - class InsertionTsp {
1.74 - private:
1.75 - GRAPH_TYPEDEFS(FullGraph);
1.76 -
1.77 - public:
1.78 + /// Type of the cost map
1.79 typedef CM CostMap;
1.80 + /// Type of the edge costs
1.81 typedef typename CM::Value Cost;
1.82 -
1.83 - InsertionTsp(const FullGraph &gr, const CostMap &cost) :
1.84 - _gr(gr), _cost(cost) {}
1.85 -
1.86 - enum InsertionMethod {
1.87 - INSERT_NEAREST,
1.88 - INSERT_FARTHEST,
1.89 - INSERT_CHEAPEST,
1.90 - INSERT_RANDOM
1.91 - };
1.92 -
1.93 - Cost run(InsertionMethod method = INSERT_FARTHEST) {
1.94 - switch (method) {
1.95 - case INSERT_NEAREST:
1.96 - start<InitTour<true>, NearestSelection, DefaultInsert>();
1.97 - break;
1.98 - case INSERT_FARTHEST:
1.99 - start<InitTour<false>, FarthestSelection, DefaultInsert>();
1.100 - break;
1.101 - case INSERT_CHEAPEST:
1.102 - start<InitTour<true>, CheapestSelection, CheapestInsert>();
1.103 - break;
1.104 - case INSERT_RANDOM:
1.105 - start<InitTour<true>, RandomSelection, DefaultInsert>();
1.106 - break;
1.107 - }
1.108 - return sum;
1.109 - }
1.110 -
1.111 - template <typename L>
1.112 - void tourNodes(L &container) {
1.113 - container(insertion_tsp_helper::vectorConvert<L>(nodesPath));
1.114 - }
1.115 -
1.116 - template <template <typename> class L>
1.117 - L<Node> tourNodes() {
1.118 - return insertion_tsp_helper::vectorConvert<L<Node> >(nodesPath);
1.119 - }
1.120 -
1.121 - const std::vector<Node>& tourNodes() {
1.122 - return nodesPath;
1.123 - }
1.124 -
1.125 - Path<FullGraph> tour() {
1.126 - Path<FullGraph> p;
1.127 - if (nodesPath.size()<2)
1.128 - return p;
1.129 -
1.130 - for (unsigned int i=0; i<nodesPath.size()-1; ++i)
1.131 - p.addBack(_gr.arc(nodesPath[i], nodesPath[i+1]));
1.132 -
1.133 - p.addBack(_gr.arc(nodesPath.back(), nodesPath.front()));
1.134 - return p;
1.135 - }
1.136 -
1.137 - Cost tourCost() {
1.138 - return sum;
1.139 - }
1.140 -
1.141
1.142 private:
1.143
1.144 - template <bool MIN>
1.145 - class InitTour {
1.146 + GRAPH_TYPEDEFS(FullGraph);
1.147 +
1.148 + const FullGraph &_gr;
1.149 + const CostMap &_cost;
1.150 + std::vector<Node> _notused;
1.151 + std::vector<Node> _path;
1.152 + Cost _sum;
1.153 +
1.154 + public:
1.155 +
1.156 + /// \brief Constants for specifying the node selection rule.
1.157 + ///
1.158 + /// Enum type containing constants for specifying the node selection
1.159 + /// rule for the \ref run() function.
1.160 + ///
1.161 + /// During the algorithm, nodes are selected for addition to the current
1.162 + /// subtour according to the applied rule.
1.163 + /// In general, the FARTHEST yields the best tours, thus it is the
1.164 + /// default option. RANDOM usually gives somewhat worse results, but
1.165 + /// it is much faster than the others and it is the most robust.
1.166 + ///
1.167 + /// The desired selection rule can be specified as a parameter of the
1.168 + /// \ref run() function.
1.169 + enum SelectionRule {
1.170 +
1.171 + /// An unvisited node having minimum distance from the current
1.172 + /// subtour is selected at each step.
1.173 + /// The algorithm runs in O(n<sup>3</sup>) time using this
1.174 + /// selection rule.
1.175 + NEAREST,
1.176 +
1.177 + /// An unvisited node having maximum distance from the current
1.178 + /// subtour is selected at each step.
1.179 + /// The algorithm runs in O(n<sup>3</sup>) time using this
1.180 + /// selection rule.
1.181 + FARTHEST,
1.182 +
1.183 + /// An unvisited node whose insertion results in the least
1.184 + /// increase of the subtour's total cost is selected at each step.
1.185 + /// The algorithm runs in O(n<sup>3</sup>) time using this
1.186 + /// selection rule.
1.187 + CHEAPEST,
1.188 +
1.189 + /// An unvisited node is selected randomly without any evaluation
1.190 + /// at each step.
1.191 + /// The global \ref rnd "random number generator instance" is used.
1.192 + /// You can seed it before executing the algorithm, if you
1.193 + /// would like to.
1.194 + /// The algorithm runs in O(n<sup>2</sup>) time using this
1.195 + /// selection rule.
1.196 + RANDOM
1.197 + };
1.198 +
1.199 + public:
1.200 +
1.201 + /// \brief Constructor
1.202 + ///
1.203 + /// Constructor.
1.204 + /// \param gr The \ref FullGraph "full graph" the algorithm runs on.
1.205 + /// \param cost The cost map.
1.206 + InsertionTsp(const FullGraph &gr, const CostMap &cost)
1.207 + : _gr(gr), _cost(cost) {}
1.208 +
1.209 + /// \name Execution Control
1.210 + /// @{
1.211 +
1.212 + /// \brief Runs the algorithm.
1.213 + ///
1.214 + /// This function runs the algorithm.
1.215 + ///
1.216 + /// \param rule The node selection rule. For more information, see
1.217 + /// \ref SelectionRule.
1.218 + ///
1.219 + /// \return The total cost of the found tour.
1.220 + Cost run(SelectionRule rule = FARTHEST) {
1.221 + _path.clear();
1.222 +
1.223 + if (_gr.nodeNum() == 0) return _sum = 0;
1.224 + else if (_gr.nodeNum() == 1) {
1.225 + _path.push_back(_gr(0));
1.226 + return _sum = 0;
1.227 + }
1.228 +
1.229 + switch (rule) {
1.230 + case NEAREST:
1.231 + init(true);
1.232 + start<NearestSelection, DefaultInsertion>();
1.233 + break;
1.234 + case FARTHEST:
1.235 + init(false);
1.236 + start<FarthestSelection, DefaultInsertion>();
1.237 + break;
1.238 + case CHEAPEST:
1.239 + init(true);
1.240 + start<CheapestSelection, CheapestInsertion>();
1.241 + break;
1.242 + case RANDOM:
1.243 + init(true);
1.244 + start<RandomSelection, DefaultInsertion>();
1.245 + break;
1.246 + }
1.247 + return _sum;
1.248 + }
1.249 +
1.250 + /// @}
1.251 +
1.252 + /// \name Query Functions
1.253 + /// @{
1.254 +
1.255 + /// \brief The total cost of the found tour.
1.256 + ///
1.257 + /// This function returns the total cost of the found tour.
1.258 + ///
1.259 + /// \pre run() must be called before using this function.
1.260 + Cost tourCost() const {
1.261 + return _sum;
1.262 + }
1.263 +
1.264 + /// \brief Returns a const reference to the node sequence of the
1.265 + /// found tour.
1.266 + ///
1.267 + /// This function returns a const reference to the internal structure
1.268 + /// that stores the node sequence of the found tour.
1.269 + ///
1.270 + /// \pre run() must be called before using this function.
1.271 + const std::vector<Node>& tourNodes() const {
1.272 + return _path;
1.273 + }
1.274 +
1.275 + /// \brief Gives back the node sequence of the found tour.
1.276 + ///
1.277 + /// This function copies the node sequence of the found tour into
1.278 + /// the given standard container.
1.279 + ///
1.280 + /// \pre run() must be called before using this function.
1.281 + template <typename Container>
1.282 + void tourNodes(Container &container) const {
1.283 + container.assign(_path.begin(), _path.end());
1.284 + }
1.285 +
1.286 + /// \brief Gives back the found tour as a path.
1.287 + ///
1.288 + /// This function copies the found tour as a list of arcs/edges into
1.289 + /// the given \ref concept::Path "path structure".
1.290 + ///
1.291 + /// \pre run() must be called before using this function.
1.292 + template <typename Path>
1.293 + void tour(Path &path) const {
1.294 + path.clear();
1.295 + for (int i = 0; i < int(_path.size()) - 1; ++i) {
1.296 + path.addBack(_gr.arc(_path[i], _path[i+1]));
1.297 + }
1.298 + if (int(_path.size()) >= 2) {
1.299 + path.addBack(_gr.arc(_path.back(), _path.front()));
1.300 + }
1.301 + }
1.302 +
1.303 + /// @}
1.304 +
1.305 + private:
1.306 +
1.307 + // Initializes the algorithm
1.308 + void init(bool min) {
1.309 + Edge min_edge = min ? mapMin(_gr, _cost) : mapMax(_gr, _cost);
1.310 +
1.311 + _path.clear();
1.312 + _path.push_back(_gr.u(min_edge));
1.313 + _path.push_back(_gr.v(min_edge));
1.314 +
1.315 + _notused.clear();
1.316 + for (NodeIt n(_gr); n!=INVALID; ++n) {
1.317 + if (n != _gr.u(min_edge) && n != _gr.v(min_edge)) {
1.318 + _notused.push_back(n);
1.319 + }
1.320 + }
1.321 +
1.322 + _sum = _cost[min_edge] * 2;
1.323 + }
1.324 +
1.325 + // Executes the algorithm
1.326 + template <class SelectionFunctor, class InsertionFunctor>
1.327 + void start() {
1.328 + SelectionFunctor selectNode(_gr, _cost, _path, _notused);
1.329 + InsertionFunctor insertNode(_gr, _cost, _path, _sum);
1.330 +
1.331 + for (int i=0; i<_gr.nodeNum()-2; ++i) {
1.332 + insertNode.insert(selectNode.select());
1.333 + }
1.334 +
1.335 + _sum = _cost[_gr.edge(_path.back(), _path.front())];
1.336 + for (int i = 0; i < int(_path.size())-1; ++i) {
1.337 + _sum += _cost[_gr.edge(_path[i], _path[i+1])];
1.338 + }
1.339 + }
1.340 +
1.341 +
1.342 + // Implementation of the nearest selection rule
1.343 + class NearestSelection {
1.344 public:
1.345 - InitTour(const FullGraph &gr, const CostMap &cost,
1.346 - std::vector<Node> &used, std::vector<Node> ¬used,
1.347 - Cost &fullcost) :
1.348 - _gr(gr), _cost(cost), _used(used), _notused(notused),
1.349 - _fullcost(fullcost) {}
1.350 + NearestSelection(const FullGraph &gr, const CostMap &cost,
1.351 + std::vector<Node> &path, std::vector<Node> ¬used)
1.352 + : _gr(gr), _cost(cost), _path(path), _notused(notused) {}
1.353
1.354 - std::vector<Node> init() const {
1.355 - Edge min = (MIN) ? mapMin(_gr, _cost) : mapMax(_gr, _cost);
1.356 - std::vector<Node> path;
1.357 - path.push_back(_gr.u(min));
1.358 - path.push_back(_gr.v(min));
1.359 -
1.360 - _used.clear();
1.361 - _notused.clear();
1.362 - for (NodeIt n(_gr); n!=INVALID; ++n) {
1.363 - if (n != _gr.u(min) && n != _gr.v(min)) {
1.364 - _notused.push_back(n);
1.365 + Node select() const {
1.366 + Cost insert_val = 0;
1.367 + int insert_node = -1;
1.368 +
1.369 + for (unsigned int i=0; i<_notused.size(); ++i) {
1.370 + Cost min_val = _cost[_gr.edge(_notused[i], _path[0])];
1.371 + int min_node = 0;
1.372 +
1.373 + for (unsigned int j=1; j<_path.size(); ++j) {
1.374 + Cost curr = _cost[_gr.edge(_notused[i], _path[j])];
1.375 + if (min_val > curr) {
1.376 + min_val = curr;
1.377 + min_node = j;
1.378 + }
1.379 + }
1.380 +
1.381 + if (insert_val > min_val || insert_node == -1) {
1.382 + insert_val = min_val;
1.383 + insert_node = i;
1.384 }
1.385 }
1.386 - _used.push_back(_gr.u(min));
1.387 - _used.push_back(_gr.v(min));
1.388 -
1.389 - _fullcost = _cost[min]*2;
1.390 - return path;
1.391 +
1.392 + Node n = _notused[insert_node];
1.393 + _notused.erase(_notused.begin()+insert_node);
1.394 +
1.395 + return n;
1.396 }
1.397
1.398 private:
1.399 const FullGraph &_gr;
1.400 const CostMap &_cost;
1.401 - std::vector<Node> &_used;
1.402 - std::vector<Node> &_notused;
1.403 - Cost &_fullcost;
1.404 - };
1.405 -
1.406 - class NearestSelection {
1.407 - public:
1.408 - NearestSelection(const FullGraph &gr, const CostMap &cost,
1.409 - std::vector<Node> &used, std::vector<Node> ¬used) :
1.410 - _gr(gr), _cost(cost), _used(used), _notused(notused) {}
1.411 -
1.412 - Node select() const {
1.413 -
1.414 - Cost insert_val =
1.415 - std::numeric_limits<Cost>::max();
1.416 - int insert_node = -1;
1.417 -
1.418 - for (unsigned int i=0; i<_notused.size(); ++i) {
1.419 - Cost min_val = _cost[_gr.edge(_notused[i], _used[0])];
1.420 - int min_node = 0;
1.421 -
1.422 - for (unsigned int j=1; j<_used.size(); ++j) {
1.423 - if (min_val > _cost[_gr.edge(_notused[i], _used[j])]) {
1.424 - min_val = _cost[_gr.edge(_notused[i], _used[j])];
1.425 - min_node = j;
1.426 - }
1.427 - }
1.428 -
1.429 - if (insert_val > min_val) {
1.430 - insert_val = min_val;
1.431 - insert_node = i;
1.432 - }
1.433 - }
1.434 -
1.435 - Node n = _notused[insert_node];
1.436 - _notused.erase(_notused.begin()+insert_node);
1.437 -
1.438 - return n;
1.439 - }
1.440 -
1.441 - private:
1.442 - const FullGraph &_gr;
1.443 - const CostMap &_cost;
1.444 - std::vector<Node> &_used;
1.445 + std::vector<Node> &_path;
1.446 std::vector<Node> &_notused;
1.447 };
1.448
1.449 +
1.450 + // Implementation of the farthest selection rule
1.451 class FarthestSelection {
1.452 public:
1.453 FarthestSelection(const FullGraph &gr, const CostMap &cost,
1.454 - std::vector<Node> &used, std::vector<Node> ¬used) :
1.455 - _gr(gr), _cost(cost), _used(used), _notused(notused) {}
1.456 -
1.457 + std::vector<Node> &path, std::vector<Node> ¬used)
1.458 + : _gr(gr), _cost(cost), _path(path), _notused(notused) {}
1.459 +
1.460 Node select() const {
1.461 + Cost insert_val = 0;
1.462 + int insert_node = -1;
1.463
1.464 - Cost insert_val =
1.465 - std::numeric_limits<Cost>::min();
1.466 - int insert_node = -1;
1.467 -
1.468 for (unsigned int i=0; i<_notused.size(); ++i) {
1.469 - Cost min_val = _cost[_gr.edge(_notused[i], _used[0])];
1.470 + Cost min_val = _cost[_gr.edge(_notused[i], _path[0])];
1.471 int min_node = 0;
1.472 -
1.473 - for (unsigned int j=1; j<_used.size(); ++j) {
1.474 - if (min_val > _cost[_gr.edge(_notused[i], _used[j])]) {
1.475 - min_val = _cost[_gr.edge(_notused[i], _used[j])];
1.476 +
1.477 + for (unsigned int j=1; j<_path.size(); ++j) {
1.478 + Cost curr = _cost[_gr.edge(_notused[i], _path[j])];
1.479 + if (min_val > curr) {
1.480 + min_val = curr;
1.481 min_node = j;
1.482 }
1.483 }
1.484 -
1.485 +
1.486 if (insert_val < min_val || insert_node == -1) {
1.487 insert_val = min_val;
1.488 insert_node = i;
1.489 }
1.490 }
1.491 -
1.492 +
1.493 Node n = _notused[insert_node];
1.494 _notused.erase(_notused.begin()+insert_node);
1.495 -
1.496 +
1.497 return n;
1.498 }
1.499 -
1.500 +
1.501 private:
1.502 const FullGraph &_gr;
1.503 const CostMap &_cost;
1.504 - std::vector<Node> &_used;
1.505 + std::vector<Node> &_path;
1.506 std::vector<Node> &_notused;
1.507 };
1.508
1.509
1.510 + // Implementation of the cheapest selection rule
1.511 class CheapestSelection {
1.512 private:
1.513 Cost costDiff(Node u, Node v, Node w) const {
1.514 - return
1.515 + return
1.516 _cost[_gr.edge(u, w)] +
1.517 _cost[_gr.edge(v, w)] -
1.518 _cost[_gr.edge(u, v)];
1.519 @@ -227,24 +351,23 @@
1.520
1.521 public:
1.522 CheapestSelection(const FullGraph &gr, const CostMap &cost,
1.523 - std::vector<Node> &used, std::vector<Node> ¬used) :
1.524 - _gr(gr), _cost(cost), _used(used), _notused(notused) {}
1.525 -
1.526 + std::vector<Node> &path, std::vector<Node> ¬used)
1.527 + : _gr(gr), _cost(cost), _path(path), _notused(notused) {}
1.528 +
1.529 Cost select() const {
1.530 int insert_notused = -1;
1.531 int best_insert_index = -1;
1.532 - Cost insert_val =
1.533 - std::numeric_limits<Cost>::max();
1.534 -
1.535 + Cost insert_val = 0;
1.536 +
1.537 for (unsigned int i=0; i<_notused.size(); ++i) {
1.538 int min = i;
1.539 int best_insert_tmp = 0;
1.540 Cost min_val =
1.541 - costDiff(_used.front(), _used.back(), _notused[i]);
1.542 -
1.543 - for (unsigned int j=1; j<_used.size(); ++j) {
1.544 + costDiff(_path.front(), _path.back(), _notused[i]);
1.545 +
1.546 + for (unsigned int j=1; j<_path.size(); ++j) {
1.547 Cost tmp =
1.548 - costDiff(_used[j-1], _used[j], _notused[i]);
1.549 + costDiff(_path[j-1], _path[j], _notused[i]);
1.550
1.551 if (min_val > tmp) {
1.552 min = i;
1.553 @@ -253,34 +376,34 @@
1.554 }
1.555 }
1.556
1.557 - if (insert_val > min_val) {
1.558 + if (insert_val > min_val || insert_notused == -1) {
1.559 insert_notused = min;
1.560 insert_val = min_val;
1.561 best_insert_index = best_insert_tmp;
1.562 }
1.563 }
1.564
1.565 - _used.insert(_used.begin()+best_insert_index, _notused[insert_notused]);
1.566 + _path.insert(_path.begin()+best_insert_index,
1.567 + _notused[insert_notused]);
1.568 _notused.erase(_notused.begin()+insert_notused);
1.569
1.570 return insert_val;
1.571 }
1.572 -
1.573 +
1.574 private:
1.575 const FullGraph &_gr;
1.576 const CostMap &_cost;
1.577 - std::vector<Node> &_used;
1.578 + std::vector<Node> &_path;
1.579 std::vector<Node> &_notused;
1.580 };
1.581
1.582 + // Implementation of the random selection rule
1.583 class RandomSelection {
1.584 public:
1.585 RandomSelection(const FullGraph &, const CostMap &,
1.586 - std::vector<Node> &, std::vector<Node> ¬used) :
1.587 - _notused(notused) {
1.588 - rnd.seedFromTime();
1.589 - }
1.590 -
1.591 + std::vector<Node> &, std::vector<Node> ¬used)
1.592 + : _notused(notused) {}
1.593 +
1.594 Node select() const {
1.595 const int index = rnd[_notused.size()];
1.596 Node n = _notused[index];
1.597 @@ -292,25 +415,26 @@
1.598 };
1.599
1.600
1.601 - class DefaultInsert {
1.602 + // Implementation of the default insertion method
1.603 + class DefaultInsertion {
1.604 private:
1.605 Cost costDiff(Node u, Node v, Node w) const {
1.606 - return
1.607 + return
1.608 _cost[_gr.edge(u, w)] +
1.609 _cost[_gr.edge(v, w)] -
1.610 _cost[_gr.edge(u, v)];
1.611 }
1.612 -
1.613 +
1.614 public:
1.615 - DefaultInsert(const FullGraph &gr, const CostMap &cost,
1.616 - std::vector<Node> &path, Cost &fullcost) :
1.617 - _gr(gr), _cost(cost), _path(path), _fullcost(fullcost) {}
1.618 -
1.619 + DefaultInsertion(const FullGraph &gr, const CostMap &cost,
1.620 + std::vector<Node> &path, Cost &total_cost) :
1.621 + _gr(gr), _cost(cost), _path(path), _total(total_cost) {}
1.622 +
1.623 void insert(Node n) const {
1.624 int min = 0;
1.625 Cost min_val =
1.626 costDiff(_path.front(), _path.back(), n);
1.627 -
1.628 +
1.629 for (unsigned int i=1; i<_path.size(); ++i) {
1.630 Cost tmp = costDiff(_path[i-1], _path[i], n);
1.631 if (tmp < min_val) {
1.632 @@ -318,58 +442,37 @@
1.633 min_val = tmp;
1.634 }
1.635 }
1.636 -
1.637 +
1.638 _path.insert(_path.begin()+min, n);
1.639 - _fullcost += min_val;
1.640 + _total += min_val;
1.641 }
1.642 -
1.643 +
1.644 private:
1.645 const FullGraph &_gr;
1.646 const CostMap &_cost;
1.647 std::vector<Node> &_path;
1.648 - Cost &_fullcost;
1.649 + Cost &_total;
1.650 };
1.651 -
1.652 - class CheapestInsert {
1.653 +
1.654 + // Implementation of a special insertion method for the cheapest
1.655 + // selection rule
1.656 + class CheapestInsertion {
1.657 TEMPLATE_GRAPH_TYPEDEFS(FullGraph);
1.658 public:
1.659 - CheapestInsert(const FullGraph &, const CostMap &,
1.660 - std::vector<Node> &, Cost &fullcost) :
1.661 - _fullcost(fullcost) {}
1.662 -
1.663 + CheapestInsertion(const FullGraph &, const CostMap &,
1.664 + std::vector<Node> &, Cost &total_cost) :
1.665 + _total(total_cost) {}
1.666 +
1.667 void insert(Cost diff) const {
1.668 - _fullcost += diff;
1.669 + _total += diff;
1.670 }
1.671
1.672 private:
1.673 - Cost &_fullcost;
1.674 - };
1.675 -
1.676 -
1.677 - template <class InitFunctor, class SelectionFunctor, class InsertFunctor>
1.678 - void start() {
1.679 - InitFunctor init(_gr, _cost, nodesPath, notused, sum);
1.680 - SelectionFunctor selectNode(_gr, _cost, nodesPath, notused);
1.681 - InsertFunctor insertNode(_gr, _cost, nodesPath, sum);
1.682 -
1.683 - nodesPath = init.init();
1.684 -
1.685 - for (int i=0; i<_gr.nodeNum()-2; ++i) {
1.686 - insertNode.insert(selectNode.select());
1.687 - }
1.688 -
1.689 - sum = _cost[ _gr.edge(nodesPath.front(), nodesPath.back()) ];
1.690 - for (unsigned int i=0; i<nodesPath.size()-1; ++i)
1.691 - sum += _cost[ _gr.edge(nodesPath[i], nodesPath[i+1]) ];
1.692 - }
1.693 -
1.694 - const FullGraph &_gr;
1.695 - const CostMap &_cost;
1.696 - std::vector<Node> notused;
1.697 - std::vector<Node> nodesPath;
1.698 - Cost sum;
1.699 + Cost &_total;
1.700 + };
1.701 +
1.702 };
1.703 -
1.704 +
1.705 }; // namespace lemon
1.706
1.707 #endif