1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/lemon/insertion_tsp.h Sat Jan 08 21:59:56 2011 +0100
1.3 @@ -0,0 +1,375 @@
1.4 +#ifndef LEMON_INSERTION_TSP_H
1.5 +#define LEMON_INSERTION_TSP_H
1.6 +
1.7 +#include <lemon/full_graph.h>
1.8 +#include <lemon/path.h>
1.9 +#include <lemon/maps.h>
1.10 +#include <lemon/random.h>
1.11 +#include <vector>
1.12 +
1.13 +namespace lemon {
1.14 +
1.15 + namespace insertion_tsp_helper {
1.16 +
1.17 + template <class L>
1.18 + L vectorConvert(const std::vector<FullGraph::Node> &_path) {
1.19 + return L(_path.begin(), _path.end());
1.20 + };
1.21 +
1.22 + template <>
1.23 + std::vector<FullGraph::Node> vectorConvert(
1.24 + const std::vector<FullGraph::Node> &_path) {
1.25 + return _path;
1.26 + };
1.27 +
1.28 + };
1.29 +
1.30 + template <typename CM>
1.31 + class InsertionTsp {
1.32 + private:
1.33 + GRAPH_TYPEDEFS(FullGraph);
1.34 +
1.35 + public:
1.36 + typedef CM CostMap;
1.37 + typedef typename CM::Value Cost;
1.38 +
1.39 + InsertionTsp(const FullGraph &gr, const CostMap &cost) :
1.40 + _gr(gr), _cost(cost) {}
1.41 +
1.42 + enum InsertionMethod {
1.43 + INSERT_NEAREST,
1.44 + INSERT_FARTHEST,
1.45 + INSERT_CHEAPEST,
1.46 + INSERT_RANDOM
1.47 + };
1.48 +
1.49 + Cost run(InsertionMethod method = INSERT_FARTHEST) {
1.50 + switch (method) {
1.51 + case INSERT_NEAREST:
1.52 + start<InitTour<true>, NearestSelection, DefaultInsert>();
1.53 + break;
1.54 + case INSERT_FARTHEST:
1.55 + start<InitTour<false>, FarthestSelection, DefaultInsert>();
1.56 + break;
1.57 + case INSERT_CHEAPEST:
1.58 + start<InitTour<true>, CheapestSelection, CheapestInsert>();
1.59 + break;
1.60 + case INSERT_RANDOM:
1.61 + start<InitTour<true>, RandomSelection, DefaultInsert>();
1.62 + break;
1.63 + }
1.64 + return sum;
1.65 + }
1.66 +
1.67 + template <typename L>
1.68 + void tourNodes(L &container) {
1.69 + container(insertion_tsp_helper::vectorConvert<L>(nodesPath));
1.70 + }
1.71 +
1.72 + template <template <typename> class L>
1.73 + L<Node> tourNodes() {
1.74 + return insertion_tsp_helper::vectorConvert<L<Node> >(nodesPath);
1.75 + }
1.76 +
1.77 + const std::vector<Node>& tourNodes() {
1.78 + return nodesPath;
1.79 + }
1.80 +
1.81 + Path<FullGraph> tour() {
1.82 + Path<FullGraph> p;
1.83 + if (nodesPath.size()<2)
1.84 + return p;
1.85 +
1.86 + for (unsigned int i=0; i<nodesPath.size()-1; ++i)
1.87 + p.addBack(_gr.arc(nodesPath[i], nodesPath[i+1]));
1.88 +
1.89 + p.addBack(_gr.arc(nodesPath.back(), nodesPath.front()));
1.90 + return p;
1.91 + }
1.92 +
1.93 + Cost tourCost() {
1.94 + return sum;
1.95 + }
1.96 +
1.97 +
1.98 + private:
1.99 +
1.100 + template <bool MIN>
1.101 + class InitTour {
1.102 + public:
1.103 + InitTour(const FullGraph &gr, const CostMap &cost,
1.104 + std::vector<Node> &used, std::vector<Node> ¬used,
1.105 + Cost &fullcost) :
1.106 + _gr(gr), _cost(cost), _used(used), _notused(notused),
1.107 + _fullcost(fullcost) {}
1.108 +
1.109 + std::vector<Node> init() const {
1.110 + Edge min = (MIN) ? mapMin(_gr, _cost) : mapMax(_gr, _cost);
1.111 + std::vector<Node> path;
1.112 + path.push_back(_gr.u(min));
1.113 + path.push_back(_gr.v(min));
1.114 +
1.115 + _used.clear();
1.116 + _notused.clear();
1.117 + for (NodeIt n(_gr); n!=INVALID; ++n) {
1.118 + if (n != _gr.u(min) && n != _gr.v(min)) {
1.119 + _notused.push_back(n);
1.120 + }
1.121 + }
1.122 + _used.push_back(_gr.u(min));
1.123 + _used.push_back(_gr.v(min));
1.124 +
1.125 + _fullcost = _cost[min]*2;
1.126 + return path;
1.127 + }
1.128 +
1.129 + private:
1.130 + const FullGraph &_gr;
1.131 + const CostMap &_cost;
1.132 + std::vector<Node> &_used;
1.133 + std::vector<Node> &_notused;
1.134 + Cost &_fullcost;
1.135 + };
1.136 +
1.137 + class NearestSelection {
1.138 + public:
1.139 + NearestSelection(const FullGraph &gr, const CostMap &cost,
1.140 + std::vector<Node> &used, std::vector<Node> ¬used) :
1.141 + _gr(gr), _cost(cost), _used(used), _notused(notused) {}
1.142 +
1.143 + Node select() const {
1.144 +
1.145 + Cost insert_val =
1.146 + std::numeric_limits<Cost>::max();
1.147 + int insert_node = -1;
1.148 +
1.149 + for (unsigned int i=0; i<_notused.size(); ++i) {
1.150 + Cost min_val = _cost[_gr.edge(_notused[i], _used[0])];
1.151 + int min_node = 0;
1.152 +
1.153 + for (unsigned int j=1; j<_used.size(); ++j) {
1.154 + if (min_val > _cost[_gr.edge(_notused[i], _used[j])]) {
1.155 + min_val = _cost[_gr.edge(_notused[i], _used[j])];
1.156 + min_node = j;
1.157 + }
1.158 + }
1.159 +
1.160 + if (insert_val > min_val) {
1.161 + insert_val = min_val;
1.162 + insert_node = i;
1.163 + }
1.164 + }
1.165 +
1.166 + Node n = _notused[insert_node];
1.167 + _notused.erase(_notused.begin()+insert_node);
1.168 +
1.169 + return n;
1.170 + }
1.171 +
1.172 + private:
1.173 + const FullGraph &_gr;
1.174 + const CostMap &_cost;
1.175 + std::vector<Node> &_used;
1.176 + std::vector<Node> &_notused;
1.177 + };
1.178 +
1.179 + class FarthestSelection {
1.180 + public:
1.181 + FarthestSelection(const FullGraph &gr, const CostMap &cost,
1.182 + std::vector<Node> &used, std::vector<Node> ¬used) :
1.183 + _gr(gr), _cost(cost), _used(used), _notused(notused) {}
1.184 +
1.185 + Node select() const {
1.186 +
1.187 + Cost insert_val =
1.188 + std::numeric_limits<Cost>::min();
1.189 + int insert_node = -1;
1.190 +
1.191 + for (unsigned int i=0; i<_notused.size(); ++i) {
1.192 + Cost min_val = _cost[_gr.edge(_notused[i], _used[0])];
1.193 + int min_node = 0;
1.194 +
1.195 + for (unsigned int j=1; j<_used.size(); ++j) {
1.196 + if (min_val > _cost[_gr.edge(_notused[i], _used[j])]) {
1.197 + min_val = _cost[_gr.edge(_notused[i], _used[j])];
1.198 + min_node = j;
1.199 + }
1.200 + }
1.201 +
1.202 + if (insert_val < min_val || insert_node == -1) {
1.203 + insert_val = min_val;
1.204 + insert_node = i;
1.205 + }
1.206 + }
1.207 +
1.208 + Node n = _notused[insert_node];
1.209 + _notused.erase(_notused.begin()+insert_node);
1.210 +
1.211 + return n;
1.212 + }
1.213 +
1.214 + private:
1.215 + const FullGraph &_gr;
1.216 + const CostMap &_cost;
1.217 + std::vector<Node> &_used;
1.218 + std::vector<Node> &_notused;
1.219 + };
1.220 +
1.221 +
1.222 + class CheapestSelection {
1.223 + private:
1.224 + Cost costDiff(Node u, Node v, Node w) const {
1.225 + return
1.226 + _cost[_gr.edge(u, w)] +
1.227 + _cost[_gr.edge(v, w)] -
1.228 + _cost[_gr.edge(u, v)];
1.229 + }
1.230 +
1.231 + public:
1.232 + CheapestSelection(const FullGraph &gr, const CostMap &cost,
1.233 + std::vector<Node> &used, std::vector<Node> ¬used) :
1.234 + _gr(gr), _cost(cost), _used(used), _notused(notused) {}
1.235 +
1.236 + Cost select() const {
1.237 + int insert_notused = -1;
1.238 + int best_insert_index = -1;
1.239 + Cost insert_val =
1.240 + std::numeric_limits<Cost>::max();
1.241 +
1.242 + for (unsigned int i=0; i<_notused.size(); ++i) {
1.243 + int min = i;
1.244 + int best_insert_tmp = 0;
1.245 + Cost min_val =
1.246 + costDiff(_used.front(), _used.back(), _notused[i]);
1.247 +
1.248 + for (unsigned int j=1; j<_used.size(); ++j) {
1.249 + Cost tmp =
1.250 + costDiff(_used[j-1], _used[j], _notused[i]);
1.251 +
1.252 + if (min_val > tmp) {
1.253 + min = i;
1.254 + min_val = tmp;
1.255 + best_insert_tmp = j;
1.256 + }
1.257 + }
1.258 +
1.259 + if (insert_val > min_val) {
1.260 + insert_notused = min;
1.261 + insert_val = min_val;
1.262 + best_insert_index = best_insert_tmp;
1.263 + }
1.264 + }
1.265 +
1.266 + _used.insert(_used.begin()+best_insert_index, _notused[insert_notused]);
1.267 + _notused.erase(_notused.begin()+insert_notused);
1.268 +
1.269 + return insert_val;
1.270 + }
1.271 +
1.272 + private:
1.273 + const FullGraph &_gr;
1.274 + const CostMap &_cost;
1.275 + std::vector<Node> &_used;
1.276 + std::vector<Node> &_notused;
1.277 + };
1.278 +
1.279 + class RandomSelection {
1.280 + public:
1.281 + RandomSelection(const FullGraph &, const CostMap &,
1.282 + std::vector<Node> &, std::vector<Node> ¬used) :
1.283 + _notused(notused) {
1.284 + rnd.seedFromTime();
1.285 + }
1.286 +
1.287 + Node select() const {
1.288 + const int index = rnd[_notused.size()];
1.289 + Node n = _notused[index];
1.290 + _notused.erase(_notused.begin()+index);
1.291 + return n;
1.292 + }
1.293 + private:
1.294 + std::vector<Node> &_notused;
1.295 + };
1.296 +
1.297 +
1.298 + class DefaultInsert {
1.299 + private:
1.300 + Cost costDiff(Node u, Node v, Node w) const {
1.301 + return
1.302 + _cost[_gr.edge(u, w)] +
1.303 + _cost[_gr.edge(v, w)] -
1.304 + _cost[_gr.edge(u, v)];
1.305 + }
1.306 +
1.307 + public:
1.308 + DefaultInsert(const FullGraph &gr, const CostMap &cost,
1.309 + std::vector<Node> &path, Cost &fullcost) :
1.310 + _gr(gr), _cost(cost), _path(path), _fullcost(fullcost) {}
1.311 +
1.312 + void insert(Node n) const {
1.313 + int min = 0;
1.314 + Cost min_val =
1.315 + costDiff(_path.front(), _path.back(), n);
1.316 +
1.317 + for (unsigned int i=1; i<_path.size(); ++i) {
1.318 + Cost tmp = costDiff(_path[i-1], _path[i], n);
1.319 + if (tmp < min_val) {
1.320 + min = i;
1.321 + min_val = tmp;
1.322 + }
1.323 + }
1.324 +
1.325 + _path.insert(_path.begin()+min, n);
1.326 + _fullcost += min_val;
1.327 + }
1.328 +
1.329 + private:
1.330 + const FullGraph &_gr;
1.331 + const CostMap &_cost;
1.332 + std::vector<Node> &_path;
1.333 + Cost &_fullcost;
1.334 + };
1.335 +
1.336 + class CheapestInsert {
1.337 + TEMPLATE_GRAPH_TYPEDEFS(FullGraph);
1.338 + public:
1.339 + CheapestInsert(const FullGraph &, const CostMap &,
1.340 + std::vector<Node> &, Cost &fullcost) :
1.341 + _fullcost(fullcost) {}
1.342 +
1.343 + void insert(Cost diff) const {
1.344 + _fullcost += diff;
1.345 + }
1.346 +
1.347 + private:
1.348 + Cost &_fullcost;
1.349 + };
1.350 +
1.351 +
1.352 + template <class InitFunctor, class SelectionFunctor, class InsertFunctor>
1.353 + void start() {
1.354 + InitFunctor init(_gr, _cost, nodesPath, notused, sum);
1.355 + SelectionFunctor selectNode(_gr, _cost, nodesPath, notused);
1.356 + InsertFunctor insertNode(_gr, _cost, nodesPath, sum);
1.357 +
1.358 + nodesPath = init.init();
1.359 +
1.360 + for (int i=0; i<_gr.nodeNum()-2; ++i) {
1.361 + insertNode.insert(selectNode.select());
1.362 + }
1.363 +
1.364 + sum = _cost[ _gr.edge(nodesPath.front(), nodesPath.back()) ];
1.365 + for (unsigned int i=0; i<nodesPath.size()-1; ++i)
1.366 + sum += _cost[ _gr.edge(nodesPath[i], nodesPath[i+1]) ];
1.367 + }
1.368 +
1.369 + const FullGraph &_gr;
1.370 + const CostMap &_cost;
1.371 + std::vector<Node> notused;
1.372 + std::vector<Node> nodesPath;
1.373 + Cost sum;
1.374 + };
1.375 +
1.376 +}; // namespace lemon
1.377 +
1.378 +#endif