1.1 --- a/test/path_test.cc Mon Jul 16 16:21:40 2018 +0200
1.2 +++ b/test/path_test.cc Wed Oct 17 19:14:07 2018 +0200
1.3 @@ -2,7 +2,7 @@
1.4 *
1.5 * This file is a part of LEMON, a generic C++ optimization library.
1.6 *
1.7 - * Copyright (C) 2003-2009
1.8 + * Copyright (C) 2003-2013
1.9 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
1.10 * (Egervary Research Group on Combinatorial Optimization, EGRES).
1.11 *
1.12 @@ -21,6 +21,7 @@
1.13
1.14 #include <lemon/concepts/path.h>
1.15 #include <lemon/concepts/digraph.h>
1.16 +#include <lemon/concept_check.h>
1.17
1.18 #include <lemon/path.h>
1.19 #include <lemon/list_graph.h>
1.20 @@ -30,44 +31,309 @@
1.21 using namespace std;
1.22 using namespace lemon;
1.23
1.24 -void check_concepts() {
1.25 - checkConcept<concepts::Path<ListDigraph>, concepts::Path<ListDigraph> >();
1.26 - checkConcept<concepts::Path<ListDigraph>, Path<ListDigraph> >();
1.27 - checkConcept<concepts::Path<ListDigraph>, SimplePath<ListDigraph> >();
1.28 - checkConcept<concepts::Path<ListDigraph>, StaticPath<ListDigraph> >();
1.29 - checkConcept<concepts::Path<ListDigraph>, ListPath<ListDigraph> >();
1.30 +template <typename GR>
1.31 +void checkConcepts() {
1.32 + checkConcept<concepts::Path<GR>, concepts::Path<GR> >();
1.33 + checkConcept<concepts::Path<GR>, Path<GR> >();
1.34 + checkConcept<concepts::Path<GR>, SimplePath<GR> >();
1.35 + checkConcept<concepts::Path<GR>, StaticPath<GR> >();
1.36 + checkConcept<concepts::Path<GR>, ListPath<GR> >();
1.37 +}
1.38 +
1.39 +// Conecpt checking for path structures
1.40 +void checkPathConcepts() {
1.41 + checkConcepts<concepts::Digraph>();
1.42 + checkConcepts<ListDigraph>();
1.43 }
1.44
1.45 // Check if proper copy consructor is called (use valgrind for testing)
1.46 -template<class _Path>
1.47 -void checkCopy()
1.48 -{
1.49 +template <typename GR, typename P1, typename P2>
1.50 +void checkCopy(typename GR::Arc a) {
1.51 + P1 p;
1.52 + p.addBack(a);
1.53 + P1 q;
1.54 + q = p;
1.55 + P1 r(p);
1.56 + P2 q2;
1.57 + q2 = p;
1.58 + P2 r2(p);
1.59 +}
1.60 +
1.61 +// Tests for copy constructors and assignment operators of paths
1.62 +void checkPathCopy() {
1.63 ListDigraph g;
1.64 - ListDigraph::Arc a = g.addArc(g.addNode(), g.addNode());
1.65 -
1.66 - _Path p,q;
1.67 - p.addBack(a);
1.68 - q=p;
1.69 - _Path r(p);
1.70 - StaticPath<ListDigraph> s(r);
1.71 + ListDigraph::Arc a = g.addArc(g.addNode(), g.addNode());
1.72 +
1.73 + typedef Path<ListDigraph> Path1;
1.74 + typedef SimplePath<ListDigraph> Path2;
1.75 + typedef ListPath<ListDigraph> Path3;
1.76 + typedef StaticPath<ListDigraph> Path4;
1.77 + checkCopy<ListDigraph, Path1, Path2>(a);
1.78 + checkCopy<ListDigraph, Path1, Path3>(a);
1.79 + checkCopy<ListDigraph, Path1, Path4>(a);
1.80 + checkCopy<ListDigraph, Path2, Path1>(a);
1.81 + checkCopy<ListDigraph, Path2, Path3>(a);
1.82 + checkCopy<ListDigraph, Path2, Path4>(a);
1.83 + checkCopy<ListDigraph, Path3, Path1>(a);
1.84 + checkCopy<ListDigraph, Path3, Path2>(a);
1.85 + checkCopy<ListDigraph, Path3, Path4>(a);
1.86 }
1.87 -
1.88 +
1.89 +// Class for testing path functions
1.90 +class CheckPathFunctions {
1.91 + typedef ListDigraph GR;
1.92 + DIGRAPH_TYPEDEFS(GR);
1.93 + GR gr;
1.94 + const GR& cgr;
1.95 + Node n1, n2, n3, n4;
1.96 + Node tmp_n;
1.97 + Arc a1, a2, a3, a4;
1.98 + Arc tmp_a;
1.99 +
1.100 +public:
1.101 +
1.102 + CheckPathFunctions() : cgr(gr) {
1.103 + n1 = gr.addNode();
1.104 + n2 = gr.addNode();
1.105 + n3 = gr.addNode();
1.106 + n4 = gr.addNode();
1.107 + a1 = gr.addArc(n1, n2);
1.108 + a2 = gr.addArc(n2, n3);
1.109 + a3 = gr.addArc(n3, n4);
1.110 + a4 = gr.addArc(n4, n1);
1.111 + }
1.112 +
1.113 + void run() {
1.114 + checkBackAndFrontInsertablePath<Path<GR> >();
1.115 + checkBackAndFrontInsertablePath<ListPath<GR> >();
1.116 + checkBackInsertablePath<SimplePath<GR> >();
1.117 +
1.118 + checkListPathSplitAndSplice();
1.119 + }
1.120 +
1.121 +private:
1.122 +
1.123 + template <typename P>
1.124 + void checkBackInsertablePath() {
1.125 +
1.126 + // Create and check empty path
1.127 + P p;
1.128 + const P& cp = p;
1.129 + check(cp.empty(), "The path is not empty");
1.130 + check(cp.length() == 0, "The path is not empty");
1.131 +// check(cp.front() == INVALID, "Wrong front()");
1.132 +// check(cp.back() == INVALID, "Wrong back()");
1.133 + typename P::ArcIt ai(cp);
1.134 + check(ai == INVALID, "Wrong ArcIt");
1.135 + check(pathSource(cgr, cp) == INVALID, "Wrong pathSource()");
1.136 + check(pathTarget(cgr, cp) == INVALID, "Wrong pathTarget()");
1.137 + check(checkPath(cgr, cp), "Wrong checkPath()");
1.138 + PathNodeIt<P> ni(cgr, cp);
1.139 + check(ni == INVALID, "Wrong PathNodeIt");
1.140 +
1.141 + // Check single-arc path
1.142 + p.addBack(a1);
1.143 + check(!cp.empty(), "Wrong empty()");
1.144 + check(cp.length() == 1, "Wrong length");
1.145 + check(cp.front() == a1, "Wrong front()");
1.146 + check(cp.back() == a1, "Wrong back()");
1.147 + check(cp.nth(0) == a1, "Wrong nth()");
1.148 + ai = cp.nthIt(0);
1.149 + check((tmp_a = ai) == a1, "Wrong nthIt()");
1.150 + check(++ai == INVALID, "Wrong nthIt()");
1.151 + typename P::ArcIt ai2(cp);
1.152 + check((tmp_a = ai2) == a1, "Wrong ArcIt");
1.153 + check(++ai2 == INVALID, "Wrong ArcIt");
1.154 + check(pathSource(cgr, cp) == n1, "Wrong pathSource()");
1.155 + check(pathTarget(cgr, cp) == n2, "Wrong pathTarget()");
1.156 + check(checkPath(cgr, cp), "Wrong checkPath()");
1.157 + PathNodeIt<P> ni2(cgr, cp);
1.158 + check((tmp_n = ni2) == n1, "Wrong PathNodeIt");
1.159 + check((tmp_n = ++ni2) == n2, "Wrong PathNodeIt");
1.160 + check(++ni2 == INVALID, "Wrong PathNodeIt");
1.161 +
1.162 + // Check adding more arcs
1.163 + p.addBack(a2);
1.164 + p.addBack(a3);
1.165 + check(!cp.empty(), "Wrong empty()");
1.166 + check(cp.length() == 3, "Wrong length");
1.167 + check(cp.front() == a1, "Wrong front()");
1.168 + check(cp.back() == a3, "Wrong back()");
1.169 + check(cp.nth(0) == a1, "Wrong nth()");
1.170 + check(cp.nth(1) == a2, "Wrong nth()");
1.171 + check(cp.nth(2) == a3, "Wrong nth()");
1.172 + typename P::ArcIt ai3(cp);
1.173 + check((tmp_a = ai3) == a1, "Wrong ArcIt");
1.174 + check((tmp_a = ++ai3) == a2, "Wrong nthIt()");
1.175 + check((tmp_a = ++ai3) == a3, "Wrong nthIt()");
1.176 + check(++ai3 == INVALID, "Wrong nthIt()");
1.177 + ai = cp.nthIt(0);
1.178 + check((tmp_a = ai) == a1, "Wrong nthIt()");
1.179 + check((tmp_a = ++ai) == a2, "Wrong nthIt()");
1.180 + ai = cp.nthIt(2);
1.181 + check((tmp_a = ai) == a3, "Wrong nthIt()");
1.182 + check(++ai == INVALID, "Wrong nthIt()");
1.183 + check(pathSource(cgr, cp) == n1, "Wrong pathSource()");
1.184 + check(pathTarget(cgr, cp) == n4, "Wrong pathTarget()");
1.185 + check(checkPath(cgr, cp), "Wrong checkPath()");
1.186 + PathNodeIt<P> ni3(cgr, cp);
1.187 + check((tmp_n = ni3) == n1, "Wrong PathNodeIt");
1.188 + check((tmp_n = ++ni3) == n2, "Wrong PathNodeIt");
1.189 + check((tmp_n = ++ni3) == n3, "Wrong PathNodeIt");
1.190 + check((tmp_n = ++ni3) == n4, "Wrong PathNodeIt");
1.191 + check(++ni3 == INVALID, "Wrong PathNodeIt");
1.192 +
1.193 + // Check arc removal and addition
1.194 + p.eraseBack();
1.195 + p.eraseBack();
1.196 + p.addBack(a2);
1.197 + check(!cp.empty(), "Wrong empty()");
1.198 + check(cp.length() == 2, "Wrong length");
1.199 + check(cp.front() == a1, "Wrong front()");
1.200 + check(cp.back() == a2, "Wrong back()");
1.201 + check(pathSource(cgr, cp) == n1, "Wrong pathSource()");
1.202 + check(pathTarget(cgr, cp) == n3, "Wrong pathTarget()");
1.203 + check(checkPath(cgr, cp), "Wrong checkPath()");
1.204 +
1.205 + // Check clear()
1.206 + p.clear();
1.207 + check(cp.empty(), "The path is not empty");
1.208 + check(cp.length() == 0, "The path is not empty");
1.209 +
1.210 + // Check inconsistent path
1.211 + p.addBack(a4);
1.212 + p.addBack(a2);
1.213 + p.addBack(a1);
1.214 + check(!cp.empty(), "Wrong empty()");
1.215 + check(cp.length() == 3, "Wrong length");
1.216 + check(cp.front() == a4, "Wrong front()");
1.217 + check(cp.back() == a1, "Wrong back()");
1.218 + check(pathSource(cgr, cp) == n4, "Wrong pathSource()");
1.219 + check(pathTarget(cgr, cp) == n2, "Wrong pathTarget()");
1.220 + check(!checkPath(cgr, cp), "Wrong checkPath()");
1.221 + }
1.222 +
1.223 + template <typename P>
1.224 + void checkBackAndFrontInsertablePath() {
1.225 +
1.226 + // Include back insertable test cases
1.227 + checkBackInsertablePath<P>();
1.228 +
1.229 + // Check front and back insertion
1.230 + P p;
1.231 + const P& cp = p;
1.232 + p.addFront(a4);
1.233 + p.addBack(a1);
1.234 + p.addFront(a3);
1.235 + check(!cp.empty(), "Wrong empty()");
1.236 + check(cp.length() == 3, "Wrong length");
1.237 + check(cp.front() == a3, "Wrong front()");
1.238 + check(cp.back() == a1, "Wrong back()");
1.239 + check(cp.nth(0) == a3, "Wrong nth()");
1.240 + check(cp.nth(1) == a4, "Wrong nth()");
1.241 + check(cp.nth(2) == a1, "Wrong nth()");
1.242 + typename P::ArcIt ai(cp);
1.243 + check((tmp_a = ai) == a3, "Wrong ArcIt");
1.244 + check((tmp_a = ++ai) == a4, "Wrong nthIt()");
1.245 + check((tmp_a = ++ai) == a1, "Wrong nthIt()");
1.246 + check(++ai == INVALID, "Wrong nthIt()");
1.247 + ai = cp.nthIt(0);
1.248 + check((tmp_a = ai) == a3, "Wrong nthIt()");
1.249 + check((tmp_a = ++ai) == a4, "Wrong nthIt()");
1.250 + ai = cp.nthIt(2);
1.251 + check((tmp_a = ai) == a1, "Wrong nthIt()");
1.252 + check(++ai == INVALID, "Wrong nthIt()");
1.253 + check(pathSource(cgr, cp) == n3, "Wrong pathSource()");
1.254 + check(pathTarget(cgr, cp) == n2, "Wrong pathTarget()");
1.255 + check(checkPath(cgr, cp), "Wrong checkPath()");
1.256 +
1.257 + // Check eraseFront()
1.258 + p.eraseFront();
1.259 + p.addBack(a2);
1.260 + check(!cp.empty(), "Wrong empty()");
1.261 + check(cp.length() == 3, "Wrong length");
1.262 + check(cp.front() == a4, "Wrong front()");
1.263 + check(cp.back() == a2, "Wrong back()");
1.264 + check(cp.nth(0) == a4, "Wrong nth()");
1.265 + check(cp.nth(1) == a1, "Wrong nth()");
1.266 + check(cp.nth(2) == a2, "Wrong nth()");
1.267 + typename P::ArcIt ai2(cp);
1.268 + check((tmp_a = ai2) == a4, "Wrong ArcIt");
1.269 + check((tmp_a = ++ai2) == a1, "Wrong nthIt()");
1.270 + check((tmp_a = ++ai2) == a2, "Wrong nthIt()");
1.271 + check(++ai2 == INVALID, "Wrong nthIt()");
1.272 + ai = cp.nthIt(0);
1.273 + check((tmp_a = ai) == a4, "Wrong nthIt()");
1.274 + check((tmp_a = ++ai) == a1, "Wrong nthIt()");
1.275 + ai = cp.nthIt(2);
1.276 + check((tmp_a = ai) == a2, "Wrong nthIt()");
1.277 + check(++ai == INVALID, "Wrong nthIt()");
1.278 + check(pathSource(cgr, cp) == n4, "Wrong pathSource()");
1.279 + check(pathTarget(cgr, cp) == n3, "Wrong pathTarget()");
1.280 + check(checkPath(cgr, cp), "Wrong checkPath()");
1.281 + }
1.282 +
1.283 + void checkListPathSplitAndSplice() {
1.284 +
1.285 + // Build a path with spliceFront() and spliceBack()
1.286 + ListPath<GR> p1, p2, p3, p4;
1.287 + p1.addBack(a3);
1.288 + p1.addFront(a2);
1.289 + p2.addBack(a1);
1.290 + p1.spliceFront(p2);
1.291 + p3.addFront(a4);
1.292 + p1.spliceBack(p3);
1.293 + check(p1.length() == 4, "Wrong length");
1.294 + check(p1.front() == a1, "Wrong front()");
1.295 + check(p1.back() == a4, "Wrong back()");
1.296 + ListPath<GR>::ArcIt ai(p1);
1.297 + check((tmp_a = ai) == a1, "Wrong ArcIt");
1.298 + check((tmp_a = ++ai) == a2, "Wrong nthIt()");
1.299 + check((tmp_a = ++ai) == a3, "Wrong nthIt()");
1.300 + check((tmp_a = ++ai) == a4, "Wrong nthIt()");
1.301 + check(++ai == INVALID, "Wrong nthIt()");
1.302 + check(checkPath(cgr, p1), "Wrong checkPath()");
1.303 +
1.304 + // Check split()
1.305 + p1.split(p1.nthIt(2), p2);
1.306 + check(p1.length() == 2, "Wrong length");
1.307 + ai = p1.nthIt(0);
1.308 + check((tmp_a = ai) == a1, "Wrong ArcIt");
1.309 + check((tmp_a = ++ai) == a2, "Wrong nthIt()");
1.310 + check(++ai == INVALID, "Wrong nthIt()");
1.311 + check(checkPath(cgr, p1), "Wrong checkPath()");
1.312 + check(p2.length() == 2, "Wrong length");
1.313 + ai = p2.nthIt(0);
1.314 + check((tmp_a = ai) == a3, "Wrong ArcIt");
1.315 + check((tmp_a = ++ai) == a4, "Wrong nthIt()");
1.316 + check(++ai == INVALID, "Wrong nthIt()");
1.317 + check(checkPath(cgr, p2), "Wrong checkPath()");
1.318 +
1.319 + // Check split() and splice()
1.320 + p1.spliceFront(p2);
1.321 + p1.split(p1.nthIt(2), p2);
1.322 + p2.split(p2.nthIt(1), p3);
1.323 + p2.spliceBack(p1);
1.324 + p2.splice(p2.nthIt(1), p3);
1.325 + check(p2.length() == 4, "Wrong length");
1.326 + check(p2.front() == a1, "Wrong front()");
1.327 + check(p2.back() == a4, "Wrong back()");
1.328 + ai = p2.nthIt(0);
1.329 + check((tmp_a = ai) == a1, "Wrong ArcIt");
1.330 + check((tmp_a = ++ai) == a2, "Wrong nthIt()");
1.331 + check((tmp_a = ++ai) == a3, "Wrong nthIt()");
1.332 + check((tmp_a = ++ai) == a4, "Wrong nthIt()");
1.333 + check(++ai == INVALID, "Wrong nthIt()");
1.334 + check(checkPath(cgr, p2), "Wrong checkPath()");
1.335 + }
1.336 +
1.337 +};
1.338 +
1.339 int main() {
1.340 - check_concepts();
1.341 -
1.342 - checkCopy<Path<ListDigraph> >();
1.343 - checkCopy<SimplePath<ListDigraph> >();
1.344 - checkCopy<ListPath<ListDigraph> >();
1.345 -
1.346 - ListDigraph g;
1.347 - ListDigraph::Arc a = g.addArc(g.addNode(), g.addNode());
1.348 -
1.349 - Path<ListDigraph> p;
1.350 - StaticPath<ListDigraph> q,r;
1.351 - p.addBack(a);
1.352 - q=p;
1.353 - r=q;
1.354 - StaticPath<ListDigraph> s(q);
1.355 + checkPathConcepts();
1.356 + checkPathCopy();
1.357 + CheckPathFunctions cpf;
1.358 + cpf.run();
1.359
1.360 return 0;
1.361 }