|
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 |
|
8 namespace 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 |
|
124 opt2_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 |