Changeset 1037:d3dcc49e6403 in lemon-main
- Timestamp:
- 02/28/13 17:13:14 (12 years ago)
- Branch:
- default
- Phase:
- public
- Files:
-
- 6 edited
Legend:
- Unmodified
- Added
- Removed
-
lemon/christofides_tsp.h
r1036 r1037 210 210 /// 211 211 /// This function copies the node sequence of the found tour into 212 /// the given standard container. 213 /// 214 /// \pre run() must be called before using this function. 215 template <typename Container> 216 void tourNodes(Container &container) const { 217 container.assign(_path.begin(), _path.end()); 212 /// an STL container through the given output iterator. The 213 /// <tt>value_type</tt> of the container must be <tt>FullGraph::Node</tt>. 214 /// For example, 215 /// \code 216 /// std::vector<FullGraph::Node> nodes(countNodes(graph)); 217 /// tsp.tourNodes(nodes.begin()); 218 /// \endcode 219 /// or 220 /// \code 221 /// std::list<FullGraph::Node> nodes; 222 /// tsp.tourNodes(std::back_inserter(nodes)); 223 /// \endcode 224 /// 225 /// \pre run() must be called before using this function. 226 template <typename Iterator> 227 void tourNodes(Iterator out) const { 228 std::copy(_path.begin(), _path.end(), out); 218 229 } 219 230 -
lemon/greedy_tsp.h
r1036 r1037 207 207 /// 208 208 /// This function copies the node sequence of the found tour into 209 /// the given standard container. 210 /// 211 /// \pre run() must be called before using this function. 212 template <typename Container> 213 void tourNodes(Container &container) const { 214 container.assign(_path.begin(), _path.end()); 209 /// an STL container through the given output iterator. The 210 /// <tt>value_type</tt> of the container must be <tt>FullGraph::Node</tt>. 211 /// For example, 212 /// \code 213 /// std::vector<FullGraph::Node> nodes(countNodes(graph)); 214 /// tsp.tourNodes(nodes.begin()); 215 /// \endcode 216 /// or 217 /// \code 218 /// std::list<FullGraph::Node> nodes; 219 /// tsp.tourNodes(std::back_inserter(nodes)); 220 /// \endcode 221 /// 222 /// \pre run() must be called before using this function. 223 template <typename Iterator> 224 void tourNodes(Iterator out) const { 225 std::copy(_path.begin(), _path.end(), out); 215 226 } 216 227 -
lemon/insertion_tsp.h
r1036 r1037 204 204 /// 205 205 /// This function copies the node sequence of the found tour into 206 /// the given standard container. 206 /// an STL container through the given output iterator. The 207 /// <tt>value_type</tt> of the container must be <tt>FullGraph::Node</tt>. 208 /// For example, 209 /// \code 210 /// std::vector<FullGraph::Node> nodes(countNodes(graph)); 211 /// tsp.tourNodes(nodes.begin()); 212 /// \endcode 213 /// or 214 /// \code 215 /// std::list<FullGraph::Node> nodes; 216 /// tsp.tourNodes(std::back_inserter(nodes)); 217 /// \endcode 207 218 /// 208 219 /// \pre run() must be called before using this function. 209 template <typename Container>210 void tourNodes( Container &container) const {211 container.assign(_tour.begin(), _tour.end());220 template <typename Iterator> 221 void tourNodes(Iterator out) const { 222 std::copy(_tour.begin(), _tour.end(), out); 212 223 } 213 224 -
lemon/nearest_neighbor_tsp.h
r1036 r1037 194 194 /// 195 195 /// This function copies the node sequence of the found tour into 196 /// the given standard container. 197 /// 198 /// \pre run() must be called before using this function. 199 template <typename Container> 200 void tourNodes(Container &container) const { 201 container.assign(_path.begin(), _path.end()); 196 /// an STL container through the given output iterator. The 197 /// <tt>value_type</tt> of the container must be <tt>FullGraph::Node</tt>. 198 /// For example, 199 /// \code 200 /// std::vector<FullGraph::Node> nodes(countNodes(graph)); 201 /// tsp.tourNodes(nodes.begin()); 202 /// \endcode 203 /// or 204 /// \code 205 /// std::list<FullGraph::Node> nodes; 206 /// tsp.tourNodes(std::back_inserter(nodes)); 207 /// \endcode 208 /// 209 /// \pre run() must be called before using this function. 210 template <typename Iterator> 211 void tourNodes(Iterator out) const { 212 std::copy(_path.begin(), _path.end(), out); 202 213 } 203 214 -
lemon/opt2_tsp.h
r1036 r1037 231 231 /// 232 232 /// This function copies the node sequence of the found tour into 233 /// the given standard container. 233 /// an STL container through the given output iterator. The 234 /// <tt>value_type</tt> of the container must be <tt>FullGraph::Node</tt>. 235 /// For example, 236 /// \code 237 /// std::vector<FullGraph::Node> nodes(countNodes(graph)); 238 /// tsp.tourNodes(nodes.begin()); 239 /// \endcode 240 /// or 241 /// \code 242 /// std::list<FullGraph::Node> nodes; 243 /// tsp.tourNodes(std::back_inserter(nodes)); 244 /// \endcode 234 245 /// 235 246 /// \pre run() must be called before using this function. 236 template <typename Container>237 void tourNodes( Container &container) const {238 container.assign(_path.begin(), _path.end());247 template <typename Iterator> 248 void tourNodes(Iterator out) const { 249 std::copy(_path.begin(), _path.end(), out); 239 250 } 240 251 -
test/tsp_test.cc
r1035 r1037 62 62 63 63 // Checks tour validity 64 bool checkTour(const FullGraph &gr, const std::vector<FullGraph::Node> &p) { 64 template <typename Container> 65 bool checkTour(const FullGraph &gr, const Container &p) { 65 66 FullGraph::NodeMap<bool> used(gr, false); 66 67 67 int nodes = 0; 68 for (int i = 0; i < int(p.size()); ++i) { 69 if (used[p[i]]) return false; 70 used[p[i]] = true; 71 ++nodes; 68 int node_cnt = 0; 69 for (typename Container::const_iterator it = p.begin(); it != p.end(); ++it) { 70 FullGraph::Node node = *it; 71 if (used[node]) return false; 72 used[node] = true; 73 ++node_cnt; 72 74 } 73 75 74 return (node s== gr.nodeNum());76 return (node_cnt == gr.nodeNum()); 75 77 } 76 78 77 79 // Checks tour validity 78 bool checkTour (const FullGraph &gr, const Path<FullGraph> &p) {80 bool checkTourPath(const FullGraph &gr, const Path<FullGraph> &p) { 79 81 FullGraph::NodeMap<bool> used(gr, false); 80 82 … … 135 137 check(alg.tourCost() == esize, alg_name + ": Wrong total cost"); 136 138 137 std::list<Node> list; 138 std::vector<Node> vec; 139 alg.tourNodes(list); 140 alg.tourNodes(vec); 141 check(list.size() == nsize, alg_name + ": Wrong node sequence"); 142 check(vec.size() == nsize, alg_name + ": Wrong node sequence"); 143 check(alg.tourNodes().size() == nsize, alg_name + ": Wrong node sequence"); 144 check(checkTour(g, vec), alg_name + ": Wrong node sequence"); 145 check(checkCost(g, vec, constMap<Edge, int>(1), esize), 139 std::list<Node> list1(nsize), list2; 140 std::vector<Node> vec1(nsize), vec2; 141 alg.tourNodes(list1.begin()); 142 alg.tourNodes(vec1.begin()); 143 alg.tourNodes(std::front_inserter(list2)); 144 alg.tourNodes(std::back_inserter(vec2)); 145 check(checkTour(g, alg.tourNodes()), alg_name + ": Wrong node sequence"); 146 check(checkTour(g, list1), alg_name + ": Wrong node sequence"); 147 check(checkTour(g, vec1), alg_name + ": Wrong node sequence"); 148 check(checkTour(g, list2), alg_name + ": Wrong node sequence"); 149 check(checkTour(g, vec2), alg_name + ": Wrong node sequence"); 150 check(checkCost(g, vec1, constMap<Edge, int>(1), esize), 146 151 alg_name + ": Wrong tour cost"); 147 152 … … 149 154 alg.tour(path); 150 155 check(path.length() == esize, alg_name + ": Wrong tour"); 151 check(checkTour (g, path), alg_name + ": Wrong tour");156 check(checkTourPath(g, path), alg_name + ": Wrong tour"); 152 157 check(checkCost(g, path, constMap<Edge, int>(1), esize), 153 158 alg_name + ": Wrong tour cost"); … … 181 186 182 187 std::vector<Node> vec; 183 alg.tourNodes( vec);188 alg.tourNodes(std::back_inserter(vec)); 184 189 check(checkTour(g, vec), alg_name + ": Wrong node sequence"); 185 190 check(checkCost(g, vec, cost, alg.tourCost()), … … 188 193 SimplePath<FullGraph> path; 189 194 alg.tour(path); 190 check(checkTour (g, path), alg_name + ": Wrong tour");195 check(checkTourPath(g, path), alg_name + ": Wrong tour"); 191 196 check(checkCost(g, path, cost, alg.tourCost()), 192 197 alg_name + ": Wrong tour cost");
Note: See TracChangeset
for help on using the changeset viewer.