|
1 /* -*- mode: C++; indent-tabs-mode: nil; -*- |
|
2 * |
|
3 * This file is a part of LEMON, a generic C++ optimization library. |
|
4 * |
|
5 * Copyright (C) 2003-2010 |
|
6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport |
|
7 * (Egervary Research Group on Combinatorial Optimization, EGRES). |
|
8 * |
|
9 * Permission to use, modify and distribute this software is granted |
|
10 * provided that this copyright notice appears in all copies. For |
|
11 * precise terms see the accompanying LICENSE file. |
|
12 * |
|
13 * This software is provided "AS IS" with no warranty of any kind, |
|
14 * express or implied, and with no claim as to its suitability for any |
|
15 * purpose. |
|
16 * |
|
17 */ |
|
18 |
1 #ifndef LEMON_INSERTION_TSP_H |
19 #ifndef LEMON_INSERTION_TSP_H |
2 #define LEMON_INSERTION_TSP_H |
20 #define LEMON_INSERTION_TSP_H |
3 |
21 |
|
22 /// \ingroup tsp |
|
23 /// \file |
|
24 /// \brief Insertion algorithm for symmetric TSP |
|
25 |
|
26 #include <vector> |
4 #include <lemon/full_graph.h> |
27 #include <lemon/full_graph.h> |
5 #include <lemon/path.h> |
|
6 #include <lemon/maps.h> |
28 #include <lemon/maps.h> |
7 #include <lemon/random.h> |
29 #include <lemon/random.h> |
8 #include <vector> |
|
9 |
30 |
10 namespace lemon { |
31 namespace lemon { |
11 |
32 |
12 namespace insertion_tsp_helper { |
33 /// \brief Insertion algorithm for symmetric TSP. |
13 |
34 /// |
14 template <class L> |
35 /// InsertionTsp implements the insertion heuristic for solving |
15 L vectorConvert(const std::vector<FullGraph::Node> &_path) { |
36 /// symmetric \ref tsp "TSP". |
16 return L(_path.begin(), _path.end()); |
37 /// |
17 }; |
38 /// This is a basic TSP heuristic that has many variants. |
18 |
39 /// It starts with a subtour containing a few nodes of the graph and it |
19 template <> |
40 /// iteratively inserts the other nodes into this subtour according to a |
20 std::vector<FullGraph::Node> vectorConvert( |
41 /// certain node selection rule. |
21 const std::vector<FullGraph::Node> &_path) { |
42 /// |
22 return _path; |
43 /// This implementation provides four different node selection rules, |
23 }; |
44 /// from which the most powerful one is used by default. |
24 |
45 /// For more information, see \ref SelectionRule. |
25 }; |
46 /// |
26 |
47 /// \tparam CM Type of the cost map. |
27 template <typename CM> |
48 template <typename CM> |
28 class InsertionTsp { |
49 class InsertionTsp |
|
50 { |
|
51 public: |
|
52 |
|
53 /// Type of the cost map |
|
54 typedef CM CostMap; |
|
55 /// Type of the edge costs |
|
56 typedef typename CM::Value Cost; |
|
57 |
29 private: |
58 private: |
|
59 |
30 GRAPH_TYPEDEFS(FullGraph); |
60 GRAPH_TYPEDEFS(FullGraph); |
31 |
61 |
32 public: |
62 const FullGraph &_gr; |
33 typedef CM CostMap; |
63 const CostMap &_cost; |
34 typedef typename CM::Value Cost; |
64 std::vector<Node> _notused; |
35 |
65 std::vector<Node> _path; |
36 InsertionTsp(const FullGraph &gr, const CostMap &cost) : |
66 Cost _sum; |
37 _gr(gr), _cost(cost) {} |
67 |
38 |
68 public: |
39 enum InsertionMethod { |
69 |
40 INSERT_NEAREST, |
70 /// \brief Constants for specifying the node selection rule. |
41 INSERT_FARTHEST, |
71 /// |
42 INSERT_CHEAPEST, |
72 /// Enum type containing constants for specifying the node selection |
43 INSERT_RANDOM |
73 /// rule for the \ref run() function. |
44 }; |
74 /// |
45 |
75 /// During the algorithm, nodes are selected for addition to the current |
46 Cost run(InsertionMethod method = INSERT_FARTHEST) { |
76 /// subtour according to the applied rule. |
47 switch (method) { |
77 /// In general, the FARTHEST yields the best tours, thus it is the |
48 case INSERT_NEAREST: |
78 /// default option. RANDOM usually gives somewhat worse results, but |
49 start<InitTour<true>, NearestSelection, DefaultInsert>(); |
79 /// it is much faster than the others and it is the most robust. |
|
80 /// |
|
81 /// The desired selection rule can be specified as a parameter of the |
|
82 /// \ref run() function. |
|
83 enum SelectionRule { |
|
84 |
|
85 /// An unvisited node having minimum distance from the current |
|
86 /// subtour is selected at each step. |
|
87 /// The algorithm runs in O(n<sup>3</sup>) time using this |
|
88 /// selection rule. |
|
89 NEAREST, |
|
90 |
|
91 /// An unvisited node having maximum distance from the current |
|
92 /// subtour is selected at each step. |
|
93 /// The algorithm runs in O(n<sup>3</sup>) time using this |
|
94 /// selection rule. |
|
95 FARTHEST, |
|
96 |
|
97 /// An unvisited node whose insertion results in the least |
|
98 /// increase of the subtour's total cost is selected at each step. |
|
99 /// The algorithm runs in O(n<sup>3</sup>) time using this |
|
100 /// selection rule. |
|
101 CHEAPEST, |
|
102 |
|
103 /// An unvisited node is selected randomly without any evaluation |
|
104 /// at each step. |
|
105 /// The global \ref rnd "random number generator instance" is used. |
|
106 /// You can seed it before executing the algorithm, if you |
|
107 /// would like to. |
|
108 /// The algorithm runs in O(n<sup>2</sup>) time using this |
|
109 /// selection rule. |
|
110 RANDOM |
|
111 }; |
|
112 |
|
113 public: |
|
114 |
|
115 /// \brief Constructor |
|
116 /// |
|
117 /// Constructor. |
|
118 /// \param gr The \ref FullGraph "full graph" the algorithm runs on. |
|
119 /// \param cost The cost map. |
|
120 InsertionTsp(const FullGraph &gr, const CostMap &cost) |
|
121 : _gr(gr), _cost(cost) {} |
|
122 |
|
123 /// \name Execution Control |
|
124 /// @{ |
|
125 |
|
126 /// \brief Runs the algorithm. |
|
127 /// |
|
128 /// This function runs the algorithm. |
|
129 /// |
|
130 /// \param rule The node selection rule. For more information, see |
|
131 /// \ref SelectionRule. |
|
132 /// |
|
133 /// \return The total cost of the found tour. |
|
134 Cost run(SelectionRule rule = FARTHEST) { |
|
135 _path.clear(); |
|
136 |
|
137 if (_gr.nodeNum() == 0) return _sum = 0; |
|
138 else if (_gr.nodeNum() == 1) { |
|
139 _path.push_back(_gr(0)); |
|
140 return _sum = 0; |
|
141 } |
|
142 |
|
143 switch (rule) { |
|
144 case NEAREST: |
|
145 init(true); |
|
146 start<NearestSelection, DefaultInsertion>(); |
50 break; |
147 break; |
51 case INSERT_FARTHEST: |
148 case FARTHEST: |
52 start<InitTour<false>, FarthestSelection, DefaultInsert>(); |
149 init(false); |
|
150 start<FarthestSelection, DefaultInsertion>(); |
53 break; |
151 break; |
54 case INSERT_CHEAPEST: |
152 case CHEAPEST: |
55 start<InitTour<true>, CheapestSelection, CheapestInsert>(); |
153 init(true); |
|
154 start<CheapestSelection, CheapestInsertion>(); |
56 break; |
155 break; |
57 case INSERT_RANDOM: |
156 case RANDOM: |
58 start<InitTour<true>, RandomSelection, DefaultInsert>(); |
157 init(true); |
|
158 start<RandomSelection, DefaultInsertion>(); |
59 break; |
159 break; |
60 } |
160 } |
61 return sum; |
161 return _sum; |
62 } |
162 } |
63 |
163 |
64 template <typename L> |
164 /// @} |
65 void tourNodes(L &container) { |
165 |
66 container(insertion_tsp_helper::vectorConvert<L>(nodesPath)); |
166 /// \name Query Functions |
67 } |
167 /// @{ |
68 |
168 |
69 template <template <typename> class L> |
169 /// \brief The total cost of the found tour. |
70 L<Node> tourNodes() { |
170 /// |
71 return insertion_tsp_helper::vectorConvert<L<Node> >(nodesPath); |
171 /// This function returns the total cost of the found tour. |
72 } |
172 /// |
73 |
173 /// \pre run() must be called before using this function. |
74 const std::vector<Node>& tourNodes() { |
174 Cost tourCost() const { |
75 return nodesPath; |
175 return _sum; |
76 } |
176 } |
77 |
177 |
78 Path<FullGraph> tour() { |
178 /// \brief Returns a const reference to the node sequence of the |
79 Path<FullGraph> p; |
179 /// found tour. |
80 if (nodesPath.size()<2) |
180 /// |
81 return p; |
181 /// This function returns a const reference to the internal structure |
82 |
182 /// that stores the node sequence of the found tour. |
83 for (unsigned int i=0; i<nodesPath.size()-1; ++i) |
183 /// |
84 p.addBack(_gr.arc(nodesPath[i], nodesPath[i+1])); |
184 /// \pre run() must be called before using this function. |
85 |
185 const std::vector<Node>& tourNodes() const { |
86 p.addBack(_gr.arc(nodesPath.back(), nodesPath.front())); |
186 return _path; |
87 return p; |
187 } |
88 } |
188 |
89 |
189 /// \brief Gives back the node sequence of the found tour. |
90 Cost tourCost() { |
190 /// |
91 return sum; |
191 /// This function copies the node sequence of the found tour into |
92 } |
192 /// the given standard container. |
93 |
193 /// |
|
194 /// \pre run() must be called before using this function. |
|
195 template <typename Container> |
|
196 void tourNodes(Container &container) const { |
|
197 container.assign(_path.begin(), _path.end()); |
|
198 } |
|
199 |
|
200 /// \brief Gives back the found tour as a path. |
|
201 /// |
|
202 /// This function copies the found tour as a list of arcs/edges into |
|
203 /// the given \ref concept::Path "path structure". |
|
204 /// |
|
205 /// \pre run() must be called before using this function. |
|
206 template <typename Path> |
|
207 void tour(Path &path) const { |
|
208 path.clear(); |
|
209 for (int i = 0; i < int(_path.size()) - 1; ++i) { |
|
210 path.addBack(_gr.arc(_path[i], _path[i+1])); |
|
211 } |
|
212 if (int(_path.size()) >= 2) { |
|
213 path.addBack(_gr.arc(_path.back(), _path.front())); |
|
214 } |
|
215 } |
|
216 |
|
217 /// @} |
94 |
218 |
95 private: |
219 private: |
96 |
220 |
97 template <bool MIN> |
221 // Initializes the algorithm |
98 class InitTour { |
222 void init(bool min) { |
99 public: |
223 Edge min_edge = min ? mapMin(_gr, _cost) : mapMax(_gr, _cost); |
100 InitTour(const FullGraph &gr, const CostMap &cost, |
224 |
101 std::vector<Node> &used, std::vector<Node> ¬used, |
225 _path.clear(); |
102 Cost &fullcost) : |
226 _path.push_back(_gr.u(min_edge)); |
103 _gr(gr), _cost(cost), _used(used), _notused(notused), |
227 _path.push_back(_gr.v(min_edge)); |
104 _fullcost(fullcost) {} |
228 |
105 |
229 _notused.clear(); |
106 std::vector<Node> init() const { |
230 for (NodeIt n(_gr); n!=INVALID; ++n) { |
107 Edge min = (MIN) ? mapMin(_gr, _cost) : mapMax(_gr, _cost); |
231 if (n != _gr.u(min_edge) && n != _gr.v(min_edge)) { |
108 std::vector<Node> path; |
232 _notused.push_back(n); |
109 path.push_back(_gr.u(min)); |
233 } |
110 path.push_back(_gr.v(min)); |
234 } |
111 |
235 |
112 _used.clear(); |
236 _sum = _cost[min_edge] * 2; |
113 _notused.clear(); |
237 } |
114 for (NodeIt n(_gr); n!=INVALID; ++n) { |
238 |
115 if (n != _gr.u(min) && n != _gr.v(min)) { |
239 // Executes the algorithm |
116 _notused.push_back(n); |
240 template <class SelectionFunctor, class InsertionFunctor> |
|
241 void start() { |
|
242 SelectionFunctor selectNode(_gr, _cost, _path, _notused); |
|
243 InsertionFunctor insertNode(_gr, _cost, _path, _sum); |
|
244 |
|
245 for (int i=0; i<_gr.nodeNum()-2; ++i) { |
|
246 insertNode.insert(selectNode.select()); |
|
247 } |
|
248 |
|
249 _sum = _cost[_gr.edge(_path.back(), _path.front())]; |
|
250 for (int i = 0; i < int(_path.size())-1; ++i) { |
|
251 _sum += _cost[_gr.edge(_path[i], _path[i+1])]; |
|
252 } |
|
253 } |
|
254 |
|
255 |
|
256 // Implementation of the nearest selection rule |
|
257 class NearestSelection { |
|
258 public: |
|
259 NearestSelection(const FullGraph &gr, const CostMap &cost, |
|
260 std::vector<Node> &path, std::vector<Node> ¬used) |
|
261 : _gr(gr), _cost(cost), _path(path), _notused(notused) {} |
|
262 |
|
263 Node select() const { |
|
264 Cost insert_val = 0; |
|
265 int insert_node = -1; |
|
266 |
|
267 for (unsigned int i=0; i<_notused.size(); ++i) { |
|
268 Cost min_val = _cost[_gr.edge(_notused[i], _path[0])]; |
|
269 int min_node = 0; |
|
270 |
|
271 for (unsigned int j=1; j<_path.size(); ++j) { |
|
272 Cost curr = _cost[_gr.edge(_notused[i], _path[j])]; |
|
273 if (min_val > curr) { |
|
274 min_val = curr; |
|
275 min_node = j; |
|
276 } |
|
277 } |
|
278 |
|
279 if (insert_val > min_val || insert_node == -1) { |
|
280 insert_val = min_val; |
|
281 insert_node = i; |
117 } |
282 } |
118 } |
283 } |
119 _used.push_back(_gr.u(min)); |
284 |
120 _used.push_back(_gr.v(min)); |
285 Node n = _notused[insert_node]; |
121 |
286 _notused.erase(_notused.begin()+insert_node); |
122 _fullcost = _cost[min]*2; |
287 |
123 return path; |
288 return n; |
124 } |
289 } |
125 |
290 |
126 private: |
291 private: |
127 const FullGraph &_gr; |
292 const FullGraph &_gr; |
128 const CostMap &_cost; |
293 const CostMap &_cost; |
129 std::vector<Node> &_used; |
294 std::vector<Node> &_path; |
130 std::vector<Node> &_notused; |
295 std::vector<Node> &_notused; |
131 Cost &_fullcost; |
296 }; |
132 }; |
297 |
133 |
298 |
134 class NearestSelection { |
299 // Implementation of the farthest selection rule |
135 public: |
300 class FarthestSelection { |
136 NearestSelection(const FullGraph &gr, const CostMap &cost, |
301 public: |
137 std::vector<Node> &used, std::vector<Node> ¬used) : |
302 FarthestSelection(const FullGraph &gr, const CostMap &cost, |
138 _gr(gr), _cost(cost), _used(used), _notused(notused) {} |
303 std::vector<Node> &path, std::vector<Node> ¬used) |
139 |
304 : _gr(gr), _cost(cost), _path(path), _notused(notused) {} |
|
305 |
140 Node select() const { |
306 Node select() const { |
141 |
307 Cost insert_val = 0; |
142 Cost insert_val = |
|
143 std::numeric_limits<Cost>::max(); |
|
144 int insert_node = -1; |
308 int insert_node = -1; |
145 |
309 |
146 for (unsigned int i=0; i<_notused.size(); ++i) { |
310 for (unsigned int i=0; i<_notused.size(); ++i) { |
147 Cost min_val = _cost[_gr.edge(_notused[i], _used[0])]; |
311 Cost min_val = _cost[_gr.edge(_notused[i], _path[0])]; |
148 int min_node = 0; |
312 int min_node = 0; |
149 |
313 |
150 for (unsigned int j=1; j<_used.size(); ++j) { |
314 for (unsigned int j=1; j<_path.size(); ++j) { |
151 if (min_val > _cost[_gr.edge(_notused[i], _used[j])]) { |
315 Cost curr = _cost[_gr.edge(_notused[i], _path[j])]; |
152 min_val = _cost[_gr.edge(_notused[i], _used[j])]; |
316 if (min_val > curr) { |
153 min_node = j; |
317 min_val = curr; |
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; |
318 min_node = j; |
196 } |
319 } |
197 } |
320 } |
198 |
321 |
199 if (insert_val < min_val || insert_node == -1) { |
322 if (insert_val < min_val || insert_node == -1) { |
200 insert_val = min_val; |
323 insert_val = min_val; |
201 insert_node = i; |
324 insert_node = i; |
202 } |
325 } |
203 } |
326 } |
204 |
327 |
205 Node n = _notused[insert_node]; |
328 Node n = _notused[insert_node]; |
206 _notused.erase(_notused.begin()+insert_node); |
329 _notused.erase(_notused.begin()+insert_node); |
207 |
330 |
208 return n; |
331 return n; |
209 } |
332 } |
210 |
333 |
211 private: |
334 private: |
212 const FullGraph &_gr; |
335 const FullGraph &_gr; |
213 const CostMap &_cost; |
336 const CostMap &_cost; |
214 std::vector<Node> &_used; |
337 std::vector<Node> &_path; |
215 std::vector<Node> &_notused; |
338 std::vector<Node> &_notused; |
216 }; |
339 }; |
217 |
340 |
218 |
341 |
|
342 // Implementation of the cheapest selection rule |
219 class CheapestSelection { |
343 class CheapestSelection { |
220 private: |
344 private: |
221 Cost costDiff(Node u, Node v, Node w) const { |
345 Cost costDiff(Node u, Node v, Node w) const { |
222 return |
346 return |
223 _cost[_gr.edge(u, w)] + |
347 _cost[_gr.edge(u, w)] + |
224 _cost[_gr.edge(v, w)] - |
348 _cost[_gr.edge(v, w)] - |
225 _cost[_gr.edge(u, v)]; |
349 _cost[_gr.edge(u, v)]; |
226 } |
350 } |
227 |
351 |
228 public: |
352 public: |
229 CheapestSelection(const FullGraph &gr, const CostMap &cost, |
353 CheapestSelection(const FullGraph &gr, const CostMap &cost, |
230 std::vector<Node> &used, std::vector<Node> ¬used) : |
354 std::vector<Node> &path, std::vector<Node> ¬used) |
231 _gr(gr), _cost(cost), _used(used), _notused(notused) {} |
355 : _gr(gr), _cost(cost), _path(path), _notused(notused) {} |
232 |
356 |
233 Cost select() const { |
357 Cost select() const { |
234 int insert_notused = -1; |
358 int insert_notused = -1; |
235 int best_insert_index = -1; |
359 int best_insert_index = -1; |
236 Cost insert_val = |
360 Cost insert_val = 0; |
237 std::numeric_limits<Cost>::max(); |
361 |
238 |
|
239 for (unsigned int i=0; i<_notused.size(); ++i) { |
362 for (unsigned int i=0; i<_notused.size(); ++i) { |
240 int min = i; |
363 int min = i; |
241 int best_insert_tmp = 0; |
364 int best_insert_tmp = 0; |
242 Cost min_val = |
365 Cost min_val = |
243 costDiff(_used.front(), _used.back(), _notused[i]); |
366 costDiff(_path.front(), _path.back(), _notused[i]); |
244 |
367 |
245 for (unsigned int j=1; j<_used.size(); ++j) { |
368 for (unsigned int j=1; j<_path.size(); ++j) { |
246 Cost tmp = |
369 Cost tmp = |
247 costDiff(_used[j-1], _used[j], _notused[i]); |
370 costDiff(_path[j-1], _path[j], _notused[i]); |
248 |
371 |
249 if (min_val > tmp) { |
372 if (min_val > tmp) { |
250 min = i; |
373 min = i; |
251 min_val = tmp; |
374 min_val = tmp; |
252 best_insert_tmp = j; |
375 best_insert_tmp = j; |
253 } |
376 } |
254 } |
377 } |
255 |
378 |
256 if (insert_val > min_val) { |
379 if (insert_val > min_val || insert_notused == -1) { |
257 insert_notused = min; |
380 insert_notused = min; |
258 insert_val = min_val; |
381 insert_val = min_val; |
259 best_insert_index = best_insert_tmp; |
382 best_insert_index = best_insert_tmp; |
260 } |
383 } |
261 } |
384 } |
262 |
385 |
263 _used.insert(_used.begin()+best_insert_index, _notused[insert_notused]); |
386 _path.insert(_path.begin()+best_insert_index, |
|
387 _notused[insert_notused]); |
264 _notused.erase(_notused.begin()+insert_notused); |
388 _notused.erase(_notused.begin()+insert_notused); |
265 |
389 |
266 return insert_val; |
390 return insert_val; |
267 } |
391 } |
268 |
392 |
269 private: |
393 private: |
270 const FullGraph &_gr; |
394 const FullGraph &_gr; |
271 const CostMap &_cost; |
395 const CostMap &_cost; |
272 std::vector<Node> &_used; |
396 std::vector<Node> &_path; |
273 std::vector<Node> &_notused; |
397 std::vector<Node> &_notused; |
274 }; |
398 }; |
275 |
399 |
|
400 // Implementation of the random selection rule |
276 class RandomSelection { |
401 class RandomSelection { |
277 public: |
402 public: |
278 RandomSelection(const FullGraph &, const CostMap &, |
403 RandomSelection(const FullGraph &, const CostMap &, |
279 std::vector<Node> &, std::vector<Node> ¬used) : |
404 std::vector<Node> &, std::vector<Node> ¬used) |
280 _notused(notused) { |
405 : _notused(notused) {} |
281 rnd.seedFromTime(); |
406 |
282 } |
|
283 |
|
284 Node select() const { |
407 Node select() const { |
285 const int index = rnd[_notused.size()]; |
408 const int index = rnd[_notused.size()]; |
286 Node n = _notused[index]; |
409 Node n = _notused[index]; |
287 _notused.erase(_notused.begin()+index); |
410 _notused.erase(_notused.begin()+index); |
288 return n; |
411 return n; |
290 private: |
413 private: |
291 std::vector<Node> &_notused; |
414 std::vector<Node> &_notused; |
292 }; |
415 }; |
293 |
416 |
294 |
417 |
295 class DefaultInsert { |
418 // Implementation of the default insertion method |
|
419 class DefaultInsertion { |
296 private: |
420 private: |
297 Cost costDiff(Node u, Node v, Node w) const { |
421 Cost costDiff(Node u, Node v, Node w) const { |
298 return |
422 return |
299 _cost[_gr.edge(u, w)] + |
423 _cost[_gr.edge(u, w)] + |
300 _cost[_gr.edge(v, w)] - |
424 _cost[_gr.edge(v, w)] - |
301 _cost[_gr.edge(u, v)]; |
425 _cost[_gr.edge(u, v)]; |
302 } |
426 } |
303 |
427 |
304 public: |
428 public: |
305 DefaultInsert(const FullGraph &gr, const CostMap &cost, |
429 DefaultInsertion(const FullGraph &gr, const CostMap &cost, |
306 std::vector<Node> &path, Cost &fullcost) : |
430 std::vector<Node> &path, Cost &total_cost) : |
307 _gr(gr), _cost(cost), _path(path), _fullcost(fullcost) {} |
431 _gr(gr), _cost(cost), _path(path), _total(total_cost) {} |
308 |
432 |
309 void insert(Node n) const { |
433 void insert(Node n) const { |
310 int min = 0; |
434 int min = 0; |
311 Cost min_val = |
435 Cost min_val = |
312 costDiff(_path.front(), _path.back(), n); |
436 costDiff(_path.front(), _path.back(), n); |
313 |
437 |
314 for (unsigned int i=1; i<_path.size(); ++i) { |
438 for (unsigned int i=1; i<_path.size(); ++i) { |
315 Cost tmp = costDiff(_path[i-1], _path[i], n); |
439 Cost tmp = costDiff(_path[i-1], _path[i], n); |
316 if (tmp < min_val) { |
440 if (tmp < min_val) { |
317 min = i; |
441 min = i; |
318 min_val = tmp; |
442 min_val = tmp; |
319 } |
443 } |
320 } |
444 } |
321 |
445 |
322 _path.insert(_path.begin()+min, n); |
446 _path.insert(_path.begin()+min, n); |
323 _fullcost += min_val; |
447 _total += min_val; |
324 } |
448 } |
325 |
449 |
326 private: |
450 private: |
327 const FullGraph &_gr; |
451 const FullGraph &_gr; |
328 const CostMap &_cost; |
452 const CostMap &_cost; |
329 std::vector<Node> &_path; |
453 std::vector<Node> &_path; |
330 Cost &_fullcost; |
454 Cost &_total; |
331 }; |
455 }; |
332 |
456 |
333 class CheapestInsert { |
457 // Implementation of a special insertion method for the cheapest |
|
458 // selection rule |
|
459 class CheapestInsertion { |
334 TEMPLATE_GRAPH_TYPEDEFS(FullGraph); |
460 TEMPLATE_GRAPH_TYPEDEFS(FullGraph); |
335 public: |
461 public: |
336 CheapestInsert(const FullGraph &, const CostMap &, |
462 CheapestInsertion(const FullGraph &, const CostMap &, |
337 std::vector<Node> &, Cost &fullcost) : |
463 std::vector<Node> &, Cost &total_cost) : |
338 _fullcost(fullcost) {} |
464 _total(total_cost) {} |
339 |
465 |
340 void insert(Cost diff) const { |
466 void insert(Cost diff) const { |
341 _fullcost += diff; |
467 _total += diff; |
342 } |
468 } |
343 |
469 |
344 private: |
470 private: |
345 Cost &_fullcost; |
471 Cost &_total; |
346 }; |
472 }; |
347 |
473 |
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 }; |
474 }; |
372 |
475 |
373 }; // namespace lemon |
476 }; // namespace lemon |
374 |
477 |
375 #endif |
478 #endif |