|
1 #ifndef LEMON_INSERTION_TSP_H |
|
2 #define LEMON_INSERTION_TSP_H |
|
3 |
|
4 #include <lemon/full_graph.h> |
|
5 #include <lemon/path.h> |
|
6 #include <lemon/maps.h> |
|
7 #include <lemon/random.h> |
|
8 #include <vector> |
|
9 |
|
10 namespace lemon { |
|
11 |
|
12 namespace insertion_tsp_helper { |
|
13 |
|
14 template <class L> |
|
15 L vectorConvert(const std::vector<FullGraph::Node> &_path) { |
|
16 return L(_path.begin(), _path.end()); |
|
17 }; |
|
18 |
|
19 template <> |
|
20 std::vector<FullGraph::Node> vectorConvert( |
|
21 const std::vector<FullGraph::Node> &_path) { |
|
22 return _path; |
|
23 }; |
|
24 |
|
25 }; |
|
26 |
|
27 template <typename CM> |
|
28 class InsertionTsp { |
|
29 private: |
|
30 GRAPH_TYPEDEFS(FullGraph); |
|
31 |
|
32 public: |
|
33 typedef CM CostMap; |
|
34 typedef typename CM::Value Cost; |
|
35 |
|
36 InsertionTsp(const FullGraph &gr, const CostMap &cost) : |
|
37 _gr(gr), _cost(cost) {} |
|
38 |
|
39 enum InsertionMethod { |
|
40 INSERT_NEAREST, |
|
41 INSERT_FARTHEST, |
|
42 INSERT_CHEAPEST, |
|
43 INSERT_RANDOM |
|
44 }; |
|
45 |
|
46 Cost run(InsertionMethod method = INSERT_FARTHEST) { |
|
47 switch (method) { |
|
48 case INSERT_NEAREST: |
|
49 start<InitTour<true>, NearestSelection, DefaultInsert>(); |
|
50 break; |
|
51 case INSERT_FARTHEST: |
|
52 start<InitTour<false>, FarthestSelection, DefaultInsert>(); |
|
53 break; |
|
54 case INSERT_CHEAPEST: |
|
55 start<InitTour<true>, CheapestSelection, CheapestInsert>(); |
|
56 break; |
|
57 case INSERT_RANDOM: |
|
58 start<InitTour<true>, RandomSelection, DefaultInsert>(); |
|
59 break; |
|
60 } |
|
61 return sum; |
|
62 } |
|
63 |
|
64 template <typename L> |
|
65 void tourNodes(L &container) { |
|
66 container(insertion_tsp_helper::vectorConvert<L>(nodesPath)); |
|
67 } |
|
68 |
|
69 template <template <typename> class L> |
|
70 L<Node> tourNodes() { |
|
71 return insertion_tsp_helper::vectorConvert<L<Node> >(nodesPath); |
|
72 } |
|
73 |
|
74 const std::vector<Node>& tourNodes() { |
|
75 return nodesPath; |
|
76 } |
|
77 |
|
78 Path<FullGraph> tour() { |
|
79 Path<FullGraph> p; |
|
80 if (nodesPath.size()<2) |
|
81 return p; |
|
82 |
|
83 for (unsigned int i=0; i<nodesPath.size()-1; ++i) |
|
84 p.addBack(_gr.arc(nodesPath[i], nodesPath[i+1])); |
|
85 |
|
86 p.addBack(_gr.arc(nodesPath.back(), nodesPath.front())); |
|
87 return p; |
|
88 } |
|
89 |
|
90 Cost tourCost() { |
|
91 return sum; |
|
92 } |
|
93 |
|
94 |
|
95 private: |
|
96 |
|
97 template <bool MIN> |
|
98 class InitTour { |
|
99 public: |
|
100 InitTour(const FullGraph &gr, const CostMap &cost, |
|
101 std::vector<Node> &used, std::vector<Node> ¬used, |
|
102 Cost &fullcost) : |
|
103 _gr(gr), _cost(cost), _used(used), _notused(notused), |
|
104 _fullcost(fullcost) {} |
|
105 |
|
106 std::vector<Node> init() const { |
|
107 Edge min = (MIN) ? mapMin(_gr, _cost) : mapMax(_gr, _cost); |
|
108 std::vector<Node> path; |
|
109 path.push_back(_gr.u(min)); |
|
110 path.push_back(_gr.v(min)); |
|
111 |
|
112 _used.clear(); |
|
113 _notused.clear(); |
|
114 for (NodeIt n(_gr); n!=INVALID; ++n) { |
|
115 if (n != _gr.u(min) && n != _gr.v(min)) { |
|
116 _notused.push_back(n); |
|
117 } |
|
118 } |
|
119 _used.push_back(_gr.u(min)); |
|
120 _used.push_back(_gr.v(min)); |
|
121 |
|
122 _fullcost = _cost[min]*2; |
|
123 return path; |
|
124 } |
|
125 |
|
126 private: |
|
127 const FullGraph &_gr; |
|
128 const CostMap &_cost; |
|
129 std::vector<Node> &_used; |
|
130 std::vector<Node> &_notused; |
|
131 Cost &_fullcost; |
|
132 }; |
|
133 |
|
134 class NearestSelection { |
|
135 public: |
|
136 NearestSelection(const FullGraph &gr, const CostMap &cost, |
|
137 std::vector<Node> &used, std::vector<Node> ¬used) : |
|
138 _gr(gr), _cost(cost), _used(used), _notused(notused) {} |
|
139 |
|
140 Node select() const { |
|
141 |
|
142 Cost insert_val = |
|
143 std::numeric_limits<Cost>::max(); |
|
144 int insert_node = -1; |
|
145 |
|
146 for (unsigned int i=0; i<_notused.size(); ++i) { |
|
147 Cost min_val = _cost[_gr.edge(_notused[i], _used[0])]; |
|
148 int min_node = 0; |
|
149 |
|
150 for (unsigned int j=1; j<_used.size(); ++j) { |
|
151 if (min_val > _cost[_gr.edge(_notused[i], _used[j])]) { |
|
152 min_val = _cost[_gr.edge(_notused[i], _used[j])]; |
|
153 min_node = j; |
|
154 } |
|
155 } |
|
156 |
|
157 if (insert_val > min_val) { |
|
158 insert_val = min_val; |
|
159 insert_node = i; |
|
160 } |
|
161 } |
|
162 |
|
163 Node n = _notused[insert_node]; |
|
164 _notused.erase(_notused.begin()+insert_node); |
|
165 |
|
166 return n; |
|
167 } |
|
168 |
|
169 private: |
|
170 const FullGraph &_gr; |
|
171 const CostMap &_cost; |
|
172 std::vector<Node> &_used; |
|
173 std::vector<Node> &_notused; |
|
174 }; |
|
175 |
|
176 class FarthestSelection { |
|
177 public: |
|
178 FarthestSelection(const FullGraph &gr, const CostMap &cost, |
|
179 std::vector<Node> &used, std::vector<Node> ¬used) : |
|
180 _gr(gr), _cost(cost), _used(used), _notused(notused) {} |
|
181 |
|
182 Node select() const { |
|
183 |
|
184 Cost insert_val = |
|
185 std::numeric_limits<Cost>::min(); |
|
186 int insert_node = -1; |
|
187 |
|
188 for (unsigned int i=0; i<_notused.size(); ++i) { |
|
189 Cost min_val = _cost[_gr.edge(_notused[i], _used[0])]; |
|
190 int min_node = 0; |
|
191 |
|
192 for (unsigned int j=1; j<_used.size(); ++j) { |
|
193 if (min_val > _cost[_gr.edge(_notused[i], _used[j])]) { |
|
194 min_val = _cost[_gr.edge(_notused[i], _used[j])]; |
|
195 min_node = j; |
|
196 } |
|
197 } |
|
198 |
|
199 if (insert_val < min_val || insert_node == -1) { |
|
200 insert_val = min_val; |
|
201 insert_node = i; |
|
202 } |
|
203 } |
|
204 |
|
205 Node n = _notused[insert_node]; |
|
206 _notused.erase(_notused.begin()+insert_node); |
|
207 |
|
208 return n; |
|
209 } |
|
210 |
|
211 private: |
|
212 const FullGraph &_gr; |
|
213 const CostMap &_cost; |
|
214 std::vector<Node> &_used; |
|
215 std::vector<Node> &_notused; |
|
216 }; |
|
217 |
|
218 |
|
219 class CheapestSelection { |
|
220 private: |
|
221 Cost costDiff(Node u, Node v, Node w) const { |
|
222 return |
|
223 _cost[_gr.edge(u, w)] + |
|
224 _cost[_gr.edge(v, w)] - |
|
225 _cost[_gr.edge(u, v)]; |
|
226 } |
|
227 |
|
228 public: |
|
229 CheapestSelection(const FullGraph &gr, const CostMap &cost, |
|
230 std::vector<Node> &used, std::vector<Node> ¬used) : |
|
231 _gr(gr), _cost(cost), _used(used), _notused(notused) {} |
|
232 |
|
233 Cost select() const { |
|
234 int insert_notused = -1; |
|
235 int best_insert_index = -1; |
|
236 Cost insert_val = |
|
237 std::numeric_limits<Cost>::max(); |
|
238 |
|
239 for (unsigned int i=0; i<_notused.size(); ++i) { |
|
240 int min = i; |
|
241 int best_insert_tmp = 0; |
|
242 Cost min_val = |
|
243 costDiff(_used.front(), _used.back(), _notused[i]); |
|
244 |
|
245 for (unsigned int j=1; j<_used.size(); ++j) { |
|
246 Cost tmp = |
|
247 costDiff(_used[j-1], _used[j], _notused[i]); |
|
248 |
|
249 if (min_val > tmp) { |
|
250 min = i; |
|
251 min_val = tmp; |
|
252 best_insert_tmp = j; |
|
253 } |
|
254 } |
|
255 |
|
256 if (insert_val > min_val) { |
|
257 insert_notused = min; |
|
258 insert_val = min_val; |
|
259 best_insert_index = best_insert_tmp; |
|
260 } |
|
261 } |
|
262 |
|
263 _used.insert(_used.begin()+best_insert_index, _notused[insert_notused]); |
|
264 _notused.erase(_notused.begin()+insert_notused); |
|
265 |
|
266 return insert_val; |
|
267 } |
|
268 |
|
269 private: |
|
270 const FullGraph &_gr; |
|
271 const CostMap &_cost; |
|
272 std::vector<Node> &_used; |
|
273 std::vector<Node> &_notused; |
|
274 }; |
|
275 |
|
276 class RandomSelection { |
|
277 public: |
|
278 RandomSelection(const FullGraph &, const CostMap &, |
|
279 std::vector<Node> &, std::vector<Node> ¬used) : |
|
280 _notused(notused) { |
|
281 rnd.seedFromTime(); |
|
282 } |
|
283 |
|
284 Node select() const { |
|
285 const int index = rnd[_notused.size()]; |
|
286 Node n = _notused[index]; |
|
287 _notused.erase(_notused.begin()+index); |
|
288 return n; |
|
289 } |
|
290 private: |
|
291 std::vector<Node> &_notused; |
|
292 }; |
|
293 |
|
294 |
|
295 class DefaultInsert { |
|
296 private: |
|
297 Cost costDiff(Node u, Node v, Node w) const { |
|
298 return |
|
299 _cost[_gr.edge(u, w)] + |
|
300 _cost[_gr.edge(v, w)] - |
|
301 _cost[_gr.edge(u, v)]; |
|
302 } |
|
303 |
|
304 public: |
|
305 DefaultInsert(const FullGraph &gr, const CostMap &cost, |
|
306 std::vector<Node> &path, Cost &fullcost) : |
|
307 _gr(gr), _cost(cost), _path(path), _fullcost(fullcost) {} |
|
308 |
|
309 void insert(Node n) const { |
|
310 int min = 0; |
|
311 Cost min_val = |
|
312 costDiff(_path.front(), _path.back(), n); |
|
313 |
|
314 for (unsigned int i=1; i<_path.size(); ++i) { |
|
315 Cost tmp = costDiff(_path[i-1], _path[i], n); |
|
316 if (tmp < min_val) { |
|
317 min = i; |
|
318 min_val = tmp; |
|
319 } |
|
320 } |
|
321 |
|
322 _path.insert(_path.begin()+min, n); |
|
323 _fullcost += min_val; |
|
324 } |
|
325 |
|
326 private: |
|
327 const FullGraph &_gr; |
|
328 const CostMap &_cost; |
|
329 std::vector<Node> &_path; |
|
330 Cost &_fullcost; |
|
331 }; |
|
332 |
|
333 class CheapestInsert { |
|
334 TEMPLATE_GRAPH_TYPEDEFS(FullGraph); |
|
335 public: |
|
336 CheapestInsert(const FullGraph &, const CostMap &, |
|
337 std::vector<Node> &, Cost &fullcost) : |
|
338 _fullcost(fullcost) {} |
|
339 |
|
340 void insert(Cost diff) const { |
|
341 _fullcost += diff; |
|
342 } |
|
343 |
|
344 private: |
|
345 Cost &_fullcost; |
|
346 }; |
|
347 |
|
348 |
|
349 template <class InitFunctor, class SelectionFunctor, class InsertFunctor> |
|
350 void start() { |
|
351 InitFunctor init(_gr, _cost, nodesPath, notused, sum); |
|
352 SelectionFunctor selectNode(_gr, _cost, nodesPath, notused); |
|
353 InsertFunctor insertNode(_gr, _cost, nodesPath, sum); |
|
354 |
|
355 nodesPath = init.init(); |
|
356 |
|
357 for (int i=0; i<_gr.nodeNum()-2; ++i) { |
|
358 insertNode.insert(selectNode.select()); |
|
359 } |
|
360 |
|
361 sum = _cost[ _gr.edge(nodesPath.front(), nodesPath.back()) ]; |
|
362 for (unsigned int i=0; i<nodesPath.size()-1; ++i) |
|
363 sum += _cost[ _gr.edge(nodesPath[i], nodesPath[i+1]) ]; |
|
364 } |
|
365 |
|
366 const FullGraph &_gr; |
|
367 const CostMap &_cost; |
|
368 std::vector<Node> notused; |
|
369 std::vector<Node> nodesPath; |
|
370 Cost sum; |
|
371 }; |
|
372 |
|
373 }; // namespace lemon |
|
374 |
|
375 #endif |