59 // check(checkMetricCost(g, cost, Tolerance<float>(eps * 4)), |
59 // check(checkMetricCost(g, cost, Tolerance<float>(eps * 4)), |
60 // "Wrong checkMetricCost()"); |
60 // "Wrong checkMetricCost()"); |
61 // } |
61 // } |
62 |
62 |
63 // Checks tour validity |
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 FullGraph::NodeMap<bool> used(gr, false); |
66 FullGraph::NodeMap<bool> used(gr, false); |
66 |
67 |
67 int nodes = 0; |
68 int node_cnt = 0; |
68 for (int i = 0; i < int(p.size()); ++i) { |
69 for (typename Container::const_iterator it = p.begin(); it != p.end(); ++it) { |
69 if (used[p[i]]) return false; |
70 FullGraph::Node node = *it; |
70 used[p[i]] = true; |
71 if (used[node]) return false; |
71 ++nodes; |
72 used[node] = true; |
|
73 ++node_cnt; |
72 } |
74 } |
73 |
75 |
74 return (nodes == gr.nodeNum()); |
76 return (node_cnt == gr.nodeNum()); |
75 } |
77 } |
76 |
78 |
77 // Checks tour validity |
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 FullGraph::NodeMap<bool> used(gr, false); |
81 FullGraph::NodeMap<bool> used(gr, false); |
80 |
82 |
81 if (!checkPath(gr, p)) return false; |
83 if (!checkPath(gr, p)) return false; |
82 if (gr.nodeNum() <= 1 && p.length() != 0) return false; |
84 if (gr.nodeNum() <= 1 && p.length() != 0) return false; |
83 if (gr.nodeNum() > 1 && p.length() != gr.nodeNum()) return false; |
85 if (gr.nodeNum() > 1 && p.length() != gr.nodeNum()) return false; |
132 TSP alg(g, constMap<Edge, int>(1)); |
134 TSP alg(g, constMap<Edge, int>(1)); |
133 |
135 |
134 check(alg.run() == esize, alg_name + ": Wrong total cost"); |
136 check(alg.run() == esize, alg_name + ": Wrong total cost"); |
135 check(alg.tourCost() == esize, alg_name + ": Wrong total cost"); |
137 check(alg.tourCost() == esize, alg_name + ": Wrong total cost"); |
136 |
138 |
137 std::list<Node> list; |
139 std::list<Node> list1(nsize), list2; |
138 std::vector<Node> vec; |
140 std::vector<Node> vec1(nsize), vec2; |
139 alg.tourNodes(list); |
141 alg.tourNodes(list1.begin()); |
140 alg.tourNodes(vec); |
142 alg.tourNodes(vec1.begin()); |
141 check(list.size() == nsize, alg_name + ": Wrong node sequence"); |
143 alg.tourNodes(std::front_inserter(list2)); |
142 check(vec.size() == nsize, alg_name + ": Wrong node sequence"); |
144 alg.tourNodes(std::back_inserter(vec2)); |
143 check(alg.tourNodes().size() == nsize, alg_name + ": Wrong node sequence"); |
145 check(checkTour(g, alg.tourNodes()), alg_name + ": Wrong node sequence"); |
144 check(checkTour(g, vec), alg_name + ": Wrong node sequence"); |
146 check(checkTour(g, list1), alg_name + ": Wrong node sequence"); |
145 check(checkCost(g, vec, constMap<Edge, int>(1), esize), |
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 alg_name + ": Wrong tour cost"); |
151 alg_name + ": Wrong tour cost"); |
147 |
152 |
148 SimplePath<FullGraph> path; |
153 SimplePath<FullGraph> path; |
149 alg.tour(path); |
154 alg.tour(path); |
150 check(path.length() == esize, alg_name + ": Wrong tour"); |
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 check(checkCost(g, path, constMap<Edge, int>(1), esize), |
157 check(checkCost(g, path, constMap<Edge, int>(1), esize), |
153 alg_name + ": Wrong tour cost"); |
158 alg_name + ": Wrong tour cost"); |
154 } |
159 } |
155 } |
160 } |
156 |
161 |
178 } |
183 } |
179 |
184 |
180 check(alg.run() > 0, alg_name + ": Wrong total cost"); |
185 check(alg.run() > 0, alg_name + ": Wrong total cost"); |
181 |
186 |
182 std::vector<Node> vec; |
187 std::vector<Node> vec; |
183 alg.tourNodes(vec); |
188 alg.tourNodes(std::back_inserter(vec)); |
184 check(checkTour(g, vec), alg_name + ": Wrong node sequence"); |
189 check(checkTour(g, vec), alg_name + ": Wrong node sequence"); |
185 check(checkCost(g, vec, cost, alg.tourCost()), |
190 check(checkCost(g, vec, cost, alg.tourCost()), |
186 alg_name + ": Wrong tour cost"); |
191 alg_name + ": Wrong tour cost"); |
187 |
192 |
188 SimplePath<FullGraph> path; |
193 SimplePath<FullGraph> path; |
189 alg.tour(path); |
194 alg.tour(path); |
190 check(checkTour(g, path), alg_name + ": Wrong tour"); |
195 check(checkTourPath(g, path), alg_name + ": Wrong tour"); |
191 check(checkCost(g, path, cost, alg.tourCost()), |
196 check(checkCost(g, path, cost, alg.tourCost()), |
192 alg_name + ": Wrong tour cost"); |
197 alg_name + ": Wrong tour cost"); |
193 |
198 |
194 check(!Tolerance<double>().less(alg.tourCost(), opt2.run(alg.tourNodes())), |
199 check(!Tolerance<double>().less(alg.tourCost(), opt2.run(alg.tourNodes())), |
195 "2-opt improvement: Wrong total cost"); |
200 "2-opt improvement: Wrong total cost"); |