1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/lemon/opt2_tsp.h Sat Jan 08 21:59:56 2011 +0100
1.3 @@ -0,0 +1,203 @@
1.4 +#ifndef LEMON_OPT2_TSP_H
1.5 +#define LEMON_OPT2_TSP_H
1.6 +
1.7 +#include <vector>
1.8 +#include <lemon/full_graph.h>
1.9 +#include <lemon/path.h>
1.10 +
1.11 +namespace lemon {
1.12 +
1.13 + namespace opt2_helper {
1.14 + template <class L>
1.15 + L vectorConvert(const std::vector<FullGraph::Node> &_path) {
1.16 + return L(_path.begin(), _path.end());
1.17 + }
1.18 +
1.19 + template <>
1.20 + std::vector<FullGraph::Node> vectorConvert(const std::vector<FullGraph::Node> &_path) {
1.21 + return _path;
1.22 + }
1.23 + }
1.24 +
1.25 + template <typename CM>
1.26 + class Opt2Tsp {
1.27 + private:
1.28 + GRAPH_TYPEDEFS(FullGraph);
1.29 +
1.30 + public:
1.31 + typedef CM CostMap;
1.32 + typedef typename CM::Value Cost;
1.33 +
1.34 +
1.35 + Opt2Tsp(const FullGraph &gr, const CostMap &cost) : _gr(gr), _cost(cost),
1.36 + tmppath(_gr.nodeNum()*2) {
1.37 +
1.38 + for (int i=1; i<_gr.nodeNum()-1; ++i) {
1.39 + tmppath[2*i] = i-1;
1.40 + tmppath[2*i+1] = i+1;
1.41 + }
1.42 + tmppath[0] = _gr.nodeNum()-1;
1.43 + tmppath[1] = 1;
1.44 + tmppath[2*(_gr.nodeNum()-1)] = _gr.nodeNum()-2;
1.45 + tmppath[2*(_gr.nodeNum()-1)+1] = 0;
1.46 + }
1.47 +
1.48 + Opt2Tsp(const FullGraph &gr, const CostMap &cost, const std::vector<Node> &path) :
1.49 + _gr(gr), _cost(cost), tmppath(_gr.nodeNum()*2) {
1.50 +
1.51 + for (unsigned int i=1; i<path.size()-1; ++i) {
1.52 + tmppath[2*_gr.id(path[i])] = _gr.id(path[i-1]);
1.53 + tmppath[2*_gr.id(path[i])+1] = _gr.id(path[i+1]);
1.54 + }
1.55 +
1.56 + tmppath[2*_gr.id(path[0])] = _gr.id(path.back());
1.57 + tmppath[2*_gr.id(path[0])+1] = _gr.id(path[1]);
1.58 + tmppath[2*_gr.id(path.back())] = _gr.id(path[path.size()-2]);
1.59 + tmppath[2*_gr.id(path.back())+1] = _gr.id(path.front());
1.60 + }
1.61 +
1.62 + private:
1.63 + Cost c(int u, int v) {
1.64 + return _cost[_gr.edge(_gr.nodeFromId(u), _gr.nodeFromId(v))];
1.65 + }
1.66 +
1.67 + class It {
1.68 + public:
1.69 + It(const std::vector<int> &path, int i=0) : tmppath(path), act(i), last(tmppath[2*act]) {}
1.70 + It(const std::vector<int> &path, int i, int l) : tmppath(path), act(i), last(l) {}
1.71 +
1.72 + int next_index() const {
1.73 + return (tmppath[2*act]==last)? 2*act+1 : 2*act;
1.74 + }
1.75 +
1.76 + int prev_index() const {
1.77 + return (tmppath[2*act]==last)? 2*act : 2*act+1;
1.78 + }
1.79 +
1.80 + int next() const {
1.81 + return tmppath[next_index()];
1.82 + }
1.83 +
1.84 + int prev() const {
1.85 + return tmppath[prev_index()];
1.86 + }
1.87 +
1.88 + It& operator++() {
1.89 + int tmp = act;
1.90 + act = next();
1.91 + last = tmp;
1.92 + return *this;
1.93 + }
1.94 +
1.95 + operator int() const {
1.96 + return act;
1.97 + }
1.98 +
1.99 + private:
1.100 + const std::vector<int> &tmppath;
1.101 + int act;
1.102 + int last;
1.103 + };
1.104 +
1.105 + bool check(std::vector<int> &path, It i, It j) {
1.106 + if (c(i, i.next()) + c(j, j.next()) >
1.107 + c(i, j) + c(j.next(), i.next())) {
1.108 +
1.109 + path[ It(path, i.next(), i).prev_index() ] = j.next();
1.110 + path[ It(path, j.next(), j).prev_index() ] = i.next();
1.111 +
1.112 + path[i.next_index()] = j;
1.113 + path[j.next_index()] = i;
1.114 +
1.115 + return true;
1.116 + }
1.117 + return false;
1.118 + }
1.119 +
1.120 + public:
1.121 +
1.122 + Cost run() {
1.123 + _path.clear();
1.124 +
1.125 + if (_gr.nodeNum()>3) {
1.126 +
1.127 +opt2_tsp_label:
1.128 + It i(tmppath);
1.129 + It j(tmppath, i, i.prev());
1.130 + ++j; ++j;
1.131 + for (; j.next()!=0; ++j) {
1.132 + if (check(tmppath, i, j))
1.133 + goto opt2_tsp_label;
1.134 + }
1.135 +
1.136 + for (++i; i.next()!=0; ++i) {
1.137 + It j(tmppath, i, i.prev());
1.138 + if (++j==0)
1.139 + break;
1.140 + if (++j==0)
1.141 + break;
1.142 +
1.143 + for (; j!=0; ++j) {
1.144 + if (check(tmppath, i, j))
1.145 + goto opt2_tsp_label;
1.146 + }
1.147 + }
1.148 + }
1.149 +
1.150 + It k(tmppath);
1.151 + _path.push_back(_gr.nodeFromId(k));
1.152 + for (++k; k!=0; ++k)
1.153 + _path.push_back(_gr.nodeFromId(k));
1.154 +
1.155 +
1.156 +
1.157 + _sum = _cost[ _gr.edge(_path.back(), _path.front()) ];
1.158 + for (unsigned int i=0; i<_path.size()-1; ++i)
1.159 + _sum += _cost[ _gr.edge(_path[i], _path[i+1]) ];
1.160 + return _sum;
1.161 + }
1.162 +
1.163 +
1.164 + template <typename L>
1.165 + void tourNodes(L &container) {
1.166 + container(opt2_helper::vectorConvert<L>(_path));
1.167 + }
1.168 +
1.169 + template <template <typename> class L>
1.170 + L<Node> tourNodes() {
1.171 + return opt2_helper::vectorConvert<L<Node> >(_path);
1.172 + }
1.173 +
1.174 + const std::vector<Node>& tourNodes() {
1.175 + return _path;
1.176 + }
1.177 +
1.178 + Path<FullGraph> tour() {
1.179 + Path<FullGraph> p;
1.180 + if (_path.size()<2)
1.181 + return p;
1.182 +
1.183 + for (unsigned int i=0; i<_path.size()-1; ++i) {
1.184 + p.addBack(_gr.arc(_path[i], _path[i+1]));
1.185 + }
1.186 + p.addBack(_gr.arc(_path.back(), _path.front()));
1.187 + return p;
1.188 + }
1.189 +
1.190 + Cost tourCost() {
1.191 + return _sum;
1.192 + }
1.193 +
1.194 +
1.195 + private:
1.196 + const FullGraph &_gr;
1.197 + const CostMap &_cost;
1.198 + Cost _sum;
1.199 + std::vector<int> tmppath;
1.200 + std::vector<Node> _path;
1.201 + };
1.202 +
1.203 +
1.204 +}; // namespace lemon
1.205 +
1.206 +#endif