# source:lemon/lemon/opt2_tsp.h@1199:ae0b056593a7

Last change on this file since 1199:ae0b056593a7 was 1199:ae0b056593a7, checked in by Gabor Varga <f4c3@…>, 11 years ago

Heuristic algorithms for symmetric TSP (#386)

File size: 5.0 KB
Line
1#ifndef LEMON_OPT2_TSP_H
2#define LEMON_OPT2_TSP_H
3
4#include <vector>
5#include <lemon/full_graph.h>
6#include <lemon/path.h>
7
8namespace lemon {
9
10  namespace opt2_helper {
11    template <class L>
12    L vectorConvert(const std::vector<FullGraph::Node> &_path) {
13      return L(_path.begin(), _path.end());
14    }
15
16    template <>
17    std::vector<FullGraph::Node> vectorConvert(const std::vector<FullGraph::Node> &_path) {
18      return _path;
19    }
20  }
21
22  template <typename CM>
23  class Opt2Tsp {
24    private:
25      GRAPH_TYPEDEFS(FullGraph);
26
27    public:
28      typedef CM CostMap;
29      typedef typename CM::Value Cost;
30
31
32      Opt2Tsp(const FullGraph &gr, const CostMap &cost) : _gr(gr), _cost(cost),
33            tmppath(_gr.nodeNum()*2) {
34
35        for (int i=1; i<_gr.nodeNum()-1; ++i) {
36          tmppath[2*i] = i-1;
37          tmppath[2*i+1] = i+1;
38        }
39        tmppath[0] = _gr.nodeNum()-1;
40        tmppath[1] = 1;
41        tmppath[2*(_gr.nodeNum()-1)] = _gr.nodeNum()-2;
42        tmppath[2*(_gr.nodeNum()-1)+1] = 0;
43      }
44
45      Opt2Tsp(const FullGraph &gr, const CostMap &cost, const std::vector<Node> &path) :
46              _gr(gr), _cost(cost), tmppath(_gr.nodeNum()*2) {
47
48        for (unsigned int i=1; i<path.size()-1; ++i) {
49          tmppath[2*_gr.id(path[i])] = _gr.id(path[i-1]);
50          tmppath[2*_gr.id(path[i])+1] = _gr.id(path[i+1]);
51        }
52
53        tmppath[2*_gr.id(path[0])] = _gr.id(path.back());
54        tmppath[2*_gr.id(path[0])+1] = _gr.id(path[1]);
55        tmppath[2*_gr.id(path.back())] = _gr.id(path[path.size()-2]);
56        tmppath[2*_gr.id(path.back())+1] = _gr.id(path.front());
57      }
58
59    private:
60      Cost c(int u, int v) {
61        return _cost[_gr.edge(_gr.nodeFromId(u), _gr.nodeFromId(v))];
62      }
63
64      class It {
65        public:
66          It(const std::vector<int> &path, int i=0) : tmppath(path), act(i), last(tmppath[2*act]) {}
67          It(const std::vector<int> &path, int i, int l) : tmppath(path), act(i), last(l) {}
68
69          int next_index() const {
70            return (tmppath[2*act]==last)? 2*act+1 : 2*act;
71          }
72
73          int prev_index() const {
74            return (tmppath[2*act]==last)? 2*act : 2*act+1;
75          }
76
77          int next() const {
78            return tmppath[next_index()];
79          }
80
81          int prev() const {
82            return tmppath[prev_index()];
83          }
84
85          It& operator++() {
86            int tmp = act;
87            act = next();
88            last = tmp;
89            return *this;
90          }
91
92          operator int() const {
93            return act;
94          }
95
96        private:
97          const std::vector<int> &tmppath;
98          int act;
99          int last;
100      };
101
102      bool check(std::vector<int> &path, It i, It j) {
103        if (c(i, i.next()) + c(j, j.next()) >
104            c(i, j) + c(j.next(), i.next())) {
105
106            path[ It(path, i.next(), i).prev_index() ] = j.next();
107            path[ It(path, j.next(), j).prev_index() ] = i.next();
108
109            path[i.next_index()] = j;
110            path[j.next_index()] = i;
111
112            return true;
113        }
114        return false;
115      }
116
117    public:
118
119      Cost run() {
120        _path.clear();
121
122        if (_gr.nodeNum()>3) {
123
124opt2_tsp_label:
125          It i(tmppath);
126          It j(tmppath, i, i.prev());
127          ++j; ++j;
128          for (; j.next()!=0; ++j) {
129            if (check(tmppath, i, j))
130              goto opt2_tsp_label;
131          }
132
133          for (++i; i.next()!=0; ++i) {
134            It j(tmppath, i, i.prev());
135            if (++j==0)
136              break;
137            if (++j==0)
138              break;
139
140            for (; j!=0; ++j) {
141              if (check(tmppath, i, j))
142                goto opt2_tsp_label;
143            }
144          }
145        }
146
147        It k(tmppath);
148        _path.push_back(_gr.nodeFromId(k));
149        for (++k; k!=0; ++k)
150          _path.push_back(_gr.nodeFromId(k));
151
152
153
154        _sum = _cost[ _gr.edge(_path.back(), _path.front()) ];
155        for (unsigned int i=0; i<_path.size()-1; ++i)
156          _sum += _cost[ _gr.edge(_path[i], _path[i+1]) ];
157        return _sum;
158      }
159
160
161      template <typename L>
162      void tourNodes(L &container) {
163        container(opt2_helper::vectorConvert<L>(_path));
164      }
165
166      template <template <typename> class L>
167      L<Node> tourNodes() {
168        return opt2_helper::vectorConvert<L<Node> >(_path);
169      }
170
171      const std::vector<Node>& tourNodes() {
172        return _path;
173      }
174
175      Path<FullGraph> tour() {
176        Path<FullGraph> p;
177        if (_path.size()<2)
178          return p;
179
180        for (unsigned int i=0; i<_path.size()-1; ++i) {
181          p.addBack(_gr.arc(_path[i], _path[i+1]));
182        }
183        p.addBack(_gr.arc(_path.back(), _path.front()));
184        return p;
185      }
186
187      Cost tourCost() {
188        return _sum;
189      }
190
191
192  private:
193    const FullGraph &_gr;
194    const CostMap &_cost;
195    Cost _sum;
196    std::vector<int> tmppath;
197    std::vector<Node> _path;
198  };
199
200
201}; // namespace lemon
202
203#endif
Note: See TracBrowser for help on using the repository browser.