equal
deleted
inserted
replaced
19 #ifndef LEMON_OPT2_TSP_H |
19 #ifndef LEMON_OPT2_TSP_H |
20 #define LEMON_OPT2_TSP_H |
20 #define LEMON_OPT2_TSP_H |
21 |
21 |
22 /// \ingroup tsp |
22 /// \ingroup tsp |
23 /// \file |
23 /// \file |
24 /// \brief 2-opt algorithm for symmetric TSP |
24 /// \brief 2-opt algorithm for symmetric TSP. |
25 |
25 |
26 #include <vector> |
26 #include <vector> |
27 #include <lemon/full_graph.h> |
27 #include <lemon/full_graph.h> |
28 |
28 |
29 namespace lemon { |
29 namespace lemon { |
30 |
30 |
|
31 /// \ingroup tsp |
|
32 /// |
31 /// \brief 2-opt algorithm for symmetric TSP. |
33 /// \brief 2-opt algorithm for symmetric TSP. |
32 /// |
34 /// |
33 /// Opt2Tsp implements the 2-opt heuristic for solving |
35 /// Opt2Tsp implements the 2-opt heuristic for solving |
34 /// symmetric \ref tsp "TSP". |
36 /// symmetric \ref tsp "TSP". |
35 /// |
37 /// |
112 _plist[2*_gr.nodeNum()-1] = 0; |
114 _plist[2*_gr.nodeNum()-1] = 0; |
113 |
115 |
114 return start(); |
116 return start(); |
115 } |
117 } |
116 |
118 |
117 /// \brief Runs the algorithm from the given tour. |
119 /// \brief Runs the algorithm starting from the given tour. |
118 /// |
120 /// |
119 /// This function runs the algorithm starting from the given tour. |
121 /// This function runs the algorithm starting from the given tour. |
120 /// |
122 /// |
121 /// \param tour The tour as a path structure. It must be a |
123 /// \param tour The tour as a path structure. It must be a |
122 /// \ref checkPath() "valid path" containing excactly n arcs. |
124 /// \ref checkPath() "valid path" containing excactly n arcs. |
154 _plist[2*first] = prev; |
156 _plist[2*first] = prev; |
155 |
157 |
156 return start(); |
158 return start(); |
157 } |
159 } |
158 |
160 |
159 /// \brief Runs the algorithm from the given tour. |
161 /// \brief Runs the algorithm starting from the given tour. |
160 /// |
162 /// |
161 /// This function runs the algorithm starting from the given tour. |
163 /// This function runs the algorithm starting from the given tour |
162 /// |
164 /// (node sequence). |
163 /// \param tour The tour as a node sequence. It must be a standard |
165 /// |
164 /// sequence container storing all <tt>Node</tt>s in the desired order. |
166 /// \param tour A vector that stores all <tt>Node</tt>s of the graph |
|
167 /// in the desired order. |
165 /// |
168 /// |
166 /// \return The total cost of the found tour. |
169 /// \return The total cost of the found tour. |
167 template <template <typename> class Container> |
170 Cost run(const std::vector<Node>& tour) { |
168 Cost run(const Container<Node>& tour) { |
|
169 _path.clear(); |
171 _path.clear(); |
170 |
172 |
171 if (_gr.nodeNum() == 0) return _sum = 0; |
173 if (_gr.nodeNum() == 0) return _sum = 0; |
172 else if (_gr.nodeNum() == 1) { |
174 else if (_gr.nodeNum() == 1) { |
173 _path.push_back(_gr(0)); |
175 _path.push_back(_gr(0)); |
178 _path.push_back(_gr(1)); |
180 _path.push_back(_gr(1)); |
179 return _sum = 2 * _cost[_gr.edge(_gr(0), _gr(1))]; |
181 return _sum = 2 * _cost[_gr.edge(_gr(0), _gr(1))]; |
180 } |
182 } |
181 |
183 |
182 _plist.resize(2*_gr.nodeNum()); |
184 _plist.resize(2*_gr.nodeNum()); |
183 typename Container<Node>::const_iterator it = tour.begin(); |
185 typename std::vector<Node>::const_iterator it = tour.begin(); |
184 int first = _gr.id(*it), |
186 int first = _gr.id(*it), |
185 prev = first, |
187 prev = first, |
186 curr = _gr.id(*(++it)), |
188 curr = _gr.id(*(++it)), |
187 next = -1; |
189 next = -1; |
188 _plist[2*first+1] = curr; |
190 _plist[2*first+1] = curr; |
215 } |
217 } |
216 |
218 |
217 /// \brief Returns a const reference to the node sequence of the |
219 /// \brief Returns a const reference to the node sequence of the |
218 /// found tour. |
220 /// found tour. |
219 /// |
221 /// |
220 /// This function returns a const reference to the internal structure |
222 /// This function returns a const reference to a vector |
221 /// that stores the node sequence of the found tour. |
223 /// that stores the node sequence of the found tour. |
222 /// |
224 /// |
223 /// \pre run() must be called before using this function. |
225 /// \pre run() must be called before using this function. |
224 const std::vector<Node>& tourNodes() const { |
226 const std::vector<Node>& tourNodes() const { |
225 return _path; |
227 return _path; |