Changeset 1212:15d7c5eadaca in lemon
- Timestamp:
- 03/08/13 10:47:38 (12 years ago)
- Branch:
- default
- Phase:
- public
- Files:
-
- 2 edited
Legend:
- Unmodified
- Added
- Removed
-
lemon/path.h
r1162 r1212 318 318 /// Constructor with starting point 319 319 ArcIt(const SimplePath &_path, int _idx) 320 : idx(_idx), path(&_path) {}320 : path(&_path), idx(_idx) {} 321 321 322 322 public: -
test/path_test.cc
r1144 r1212 22 22 #include <lemon/concepts/path.h> 23 23 #include <lemon/concepts/digraph.h> 24 #include <lemon/concept_check.h> 24 25 25 26 #include <lemon/path.h> … … 31 32 using namespace lemon; 32 33 33 void check_concepts() { 34 checkConcept<concepts::Path<ListDigraph>, concepts::Path<ListDigraph> >(); 35 checkConcept<concepts::Path<ListDigraph>, Path<ListDigraph> >(); 36 checkConcept<concepts::Path<ListDigraph>, SimplePath<ListDigraph> >(); 37 checkConcept<concepts::Path<ListDigraph>, StaticPath<ListDigraph> >(); 38 checkConcept<concepts::Path<ListDigraph>, ListPath<ListDigraph> >(); 34 template <typename GR> 35 void checkConcepts() { 36 checkConcept<concepts::Path<GR>, concepts::Path<GR> >(); 37 checkConcept<concepts::Path<GR>, Path<GR> >(); 38 checkConcept<concepts::Path<GR>, SimplePath<GR> >(); 39 checkConcept<concepts::Path<GR>, StaticPath<GR> >(); 40 checkConcept<concepts::Path<GR>, ListPath<GR> >(); 41 } 42 43 // Conecpt checking for path structures 44 void checkPathConcepts() { 45 checkConcepts<concepts::Digraph>(); 46 checkConcepts<ListDigraph>(); 39 47 } 40 48 41 49 // Check if proper copy consructor is called (use valgrind for testing) 42 template<class _Path> 43 void checkCopy() 44 { 50 template <typename GR, typename P1, typename P2> 51 void checkCopy(typename GR::Arc a) { 52 P1 p; 53 p.addBack(a); 54 P1 q; 55 q = p; 56 P1 r(p); 57 P2 q2; 58 q2 = p; 59 P2 r2(p); 60 } 61 62 // Tests for copy constructors and assignment operators of paths 63 void checkPathCopy() { 45 64 ListDigraph g; 46 ListDigraph::Arc a = g.addArc(g.addNode(), g.addNode()); 47 48 _Path p,q; 49 p.addBack(a); 50 q=p; 51 _Path r(p); 52 StaticPath<ListDigraph> s(r); 53 } 54 65 ListDigraph::Arc a = g.addArc(g.addNode(), g.addNode()); 66 67 typedef Path<ListDigraph> Path1; 68 typedef SimplePath<ListDigraph> Path2; 69 typedef ListPath<ListDigraph> Path3; 70 typedef StaticPath<ListDigraph> Path4; 71 checkCopy<ListDigraph, Path1, Path2>(a); 72 checkCopy<ListDigraph, Path1, Path3>(a); 73 checkCopy<ListDigraph, Path1, Path4>(a); 74 checkCopy<ListDigraph, Path2, Path1>(a); 75 checkCopy<ListDigraph, Path2, Path3>(a); 76 checkCopy<ListDigraph, Path2, Path4>(a); 77 checkCopy<ListDigraph, Path3, Path1>(a); 78 checkCopy<ListDigraph, Path3, Path2>(a); 79 checkCopy<ListDigraph, Path3, Path4>(a); 80 } 81 82 // Class for testing path functions 83 class CheckPathFunctions { 84 typedef ListDigraph GR; 85 DIGRAPH_TYPEDEFS(GR); 86 GR gr; 87 const GR& cgr; 88 Node n1, n2, n3, n4; 89 Node tmp_n; 90 Arc a1, a2, a3, a4; 91 Arc tmp_a; 92 93 public: 94 95 CheckPathFunctions() : cgr(gr) { 96 n1 = gr.addNode(); 97 n2 = gr.addNode(); 98 n3 = gr.addNode(); 99 n4 = gr.addNode(); 100 a1 = gr.addArc(n1, n2); 101 a2 = gr.addArc(n2, n3); 102 a3 = gr.addArc(n3, n4); 103 a4 = gr.addArc(n4, n1); 104 } 105 106 void run() { 107 checkBackAndFrontInsertablePath<Path<GR> >(); 108 checkBackAndFrontInsertablePath<ListPath<GR> >(); 109 checkBackInsertablePath<SimplePath<GR> >(); 110 111 checkListPathSplitAndSplice(); 112 } 113 114 private: 115 116 template <typename P> 117 void checkBackInsertablePath() { 118 119 // Create and check empty path 120 P p; 121 const P& cp = p; 122 check(cp.empty(), "The path is not empty"); 123 check(cp.length() == 0, "The path is not empty"); 124 // check(cp.front() == INVALID, "Wrong front()"); 125 // check(cp.back() == INVALID, "Wrong back()"); 126 typename P::ArcIt ai(cp); 127 check(ai == INVALID, "Wrong ArcIt"); 128 check(pathSource(cgr, cp) == INVALID, "Wrong pathSource()"); 129 check(pathTarget(cgr, cp) == INVALID, "Wrong pathTarget()"); 130 check(checkPath(cgr, cp), "Wrong checkPath()"); 131 PathNodeIt<P> ni(cgr, cp); 132 check(ni == INVALID, "Wrong PathNodeIt"); 133 134 // Check single-arc path 135 p.addBack(a1); 136 check(!cp.empty(), "Wrong empty()"); 137 check(cp.length() == 1, "Wrong length"); 138 check(cp.front() == a1, "Wrong front()"); 139 check(cp.back() == a1, "Wrong back()"); 140 check(cp.nth(0) == a1, "Wrong nth()"); 141 ai = cp.nthIt(0); 142 check((tmp_a = ai) == a1, "Wrong nthIt()"); 143 check(++ai == INVALID, "Wrong nthIt()"); 144 typename P::ArcIt ai2(cp); 145 check((tmp_a = ai2) == a1, "Wrong ArcIt"); 146 check(++ai2 == INVALID, "Wrong ArcIt"); 147 check(pathSource(cgr, cp) == n1, "Wrong pathSource()"); 148 check(pathTarget(cgr, cp) == n2, "Wrong pathTarget()"); 149 check(checkPath(cgr, cp), "Wrong checkPath()"); 150 PathNodeIt<P> ni2(cgr, cp); 151 check((tmp_n = ni2) == n1, "Wrong PathNodeIt"); 152 check((tmp_n = ++ni2) == n2, "Wrong PathNodeIt"); 153 check(++ni2 == INVALID, "Wrong PathNodeIt"); 154 155 // Check adding more arcs 156 p.addBack(a2); 157 p.addBack(a3); 158 check(!cp.empty(), "Wrong empty()"); 159 check(cp.length() == 3, "Wrong length"); 160 check(cp.front() == a1, "Wrong front()"); 161 check(cp.back() == a3, "Wrong back()"); 162 check(cp.nth(0) == a1, "Wrong nth()"); 163 check(cp.nth(1) == a2, "Wrong nth()"); 164 check(cp.nth(2) == a3, "Wrong nth()"); 165 typename P::ArcIt ai3(cp); 166 check((tmp_a = ai3) == a1, "Wrong ArcIt"); 167 check((tmp_a = ++ai3) == a2, "Wrong nthIt()"); 168 check((tmp_a = ++ai3) == a3, "Wrong nthIt()"); 169 check(++ai3 == INVALID, "Wrong nthIt()"); 170 ai = cp.nthIt(0); 171 check((tmp_a = ai) == a1, "Wrong nthIt()"); 172 check((tmp_a = ++ai) == a2, "Wrong nthIt()"); 173 ai = cp.nthIt(2); 174 check((tmp_a = ai) == a3, "Wrong nthIt()"); 175 check(++ai == INVALID, "Wrong nthIt()"); 176 check(pathSource(cgr, cp) == n1, "Wrong pathSource()"); 177 check(pathTarget(cgr, cp) == n4, "Wrong pathTarget()"); 178 check(checkPath(cgr, cp), "Wrong checkPath()"); 179 PathNodeIt<P> ni3(cgr, cp); 180 check((tmp_n = ni3) == n1, "Wrong PathNodeIt"); 181 check((tmp_n = ++ni3) == n2, "Wrong PathNodeIt"); 182 check((tmp_n = ++ni3) == n3, "Wrong PathNodeIt"); 183 check((tmp_n = ++ni3) == n4, "Wrong PathNodeIt"); 184 check(++ni3 == INVALID, "Wrong PathNodeIt"); 185 186 // Check arc removal and addition 187 p.eraseBack(); 188 p.eraseBack(); 189 p.addBack(a2); 190 check(!cp.empty(), "Wrong empty()"); 191 check(cp.length() == 2, "Wrong length"); 192 check(cp.front() == a1, "Wrong front()"); 193 check(cp.back() == a2, "Wrong back()"); 194 check(pathSource(cgr, cp) == n1, "Wrong pathSource()"); 195 check(pathTarget(cgr, cp) == n3, "Wrong pathTarget()"); 196 check(checkPath(cgr, cp), "Wrong checkPath()"); 197 198 // Check clear() 199 p.clear(); 200 check(cp.empty(), "The path is not empty"); 201 check(cp.length() == 0, "The path is not empty"); 202 203 // Check inconsistent path 204 p.addBack(a4); 205 p.addBack(a2); 206 p.addBack(a1); 207 check(!cp.empty(), "Wrong empty()"); 208 check(cp.length() == 3, "Wrong length"); 209 check(cp.front() == a4, "Wrong front()"); 210 check(cp.back() == a1, "Wrong back()"); 211 check(pathSource(cgr, cp) == n4, "Wrong pathSource()"); 212 check(pathTarget(cgr, cp) == n2, "Wrong pathTarget()"); 213 check(!checkPath(cgr, cp), "Wrong checkPath()"); 214 } 215 216 template <typename P> 217 void checkBackAndFrontInsertablePath() { 218 219 // Include back insertable test cases 220 checkBackInsertablePath<P>(); 221 222 // Check front and back insertion 223 P p; 224 const P& cp = p; 225 p.addFront(a4); 226 p.addBack(a1); 227 p.addFront(a3); 228 check(!cp.empty(), "Wrong empty()"); 229 check(cp.length() == 3, "Wrong length"); 230 check(cp.front() == a3, "Wrong front()"); 231 check(cp.back() == a1, "Wrong back()"); 232 check(cp.nth(0) == a3, "Wrong nth()"); 233 check(cp.nth(1) == a4, "Wrong nth()"); 234 check(cp.nth(2) == a1, "Wrong nth()"); 235 typename P::ArcIt ai(cp); 236 check((tmp_a = ai) == a3, "Wrong ArcIt"); 237 check((tmp_a = ++ai) == a4, "Wrong nthIt()"); 238 check((tmp_a = ++ai) == a1, "Wrong nthIt()"); 239 check(++ai == INVALID, "Wrong nthIt()"); 240 ai = cp.nthIt(0); 241 check((tmp_a = ai) == a3, "Wrong nthIt()"); 242 check((tmp_a = ++ai) == a4, "Wrong nthIt()"); 243 ai = cp.nthIt(2); 244 check((tmp_a = ai) == a1, "Wrong nthIt()"); 245 check(++ai == INVALID, "Wrong nthIt()"); 246 check(pathSource(cgr, cp) == n3, "Wrong pathSource()"); 247 check(pathTarget(cgr, cp) == n2, "Wrong pathTarget()"); 248 check(checkPath(cgr, cp), "Wrong checkPath()"); 249 250 // Check eraseFront() 251 p.eraseFront(); 252 p.addBack(a2); 253 check(!cp.empty(), "Wrong empty()"); 254 check(cp.length() == 3, "Wrong length"); 255 check(cp.front() == a4, "Wrong front()"); 256 check(cp.back() == a2, "Wrong back()"); 257 check(cp.nth(0) == a4, "Wrong nth()"); 258 check(cp.nth(1) == a1, "Wrong nth()"); 259 check(cp.nth(2) == a2, "Wrong nth()"); 260 typename P::ArcIt ai2(cp); 261 check((tmp_a = ai2) == a4, "Wrong ArcIt"); 262 check((tmp_a = ++ai2) == a1, "Wrong nthIt()"); 263 check((tmp_a = ++ai2) == a2, "Wrong nthIt()"); 264 check(++ai2 == INVALID, "Wrong nthIt()"); 265 ai = cp.nthIt(0); 266 check((tmp_a = ai) == a4, "Wrong nthIt()"); 267 check((tmp_a = ++ai) == a1, "Wrong nthIt()"); 268 ai = cp.nthIt(2); 269 check((tmp_a = ai) == a2, "Wrong nthIt()"); 270 check(++ai == INVALID, "Wrong nthIt()"); 271 check(pathSource(cgr, cp) == n4, "Wrong pathSource()"); 272 check(pathTarget(cgr, cp) == n3, "Wrong pathTarget()"); 273 check(checkPath(cgr, cp), "Wrong checkPath()"); 274 } 275 276 void checkListPathSplitAndSplice() { 277 278 // Build a path with spliceFront() and spliceBack() 279 ListPath<GR> p1, p2, p3, p4; 280 p1.addBack(a3); 281 p1.addFront(a2); 282 p2.addBack(a1); 283 p1.spliceFront(p2); 284 p3.addFront(a4); 285 p1.spliceBack(p3); 286 check(p1.length() == 4, "Wrong length"); 287 check(p1.front() == a1, "Wrong front()"); 288 check(p1.back() == a4, "Wrong back()"); 289 ListPath<GR>::ArcIt ai(p1); 290 check((tmp_a = ai) == a1, "Wrong ArcIt"); 291 check((tmp_a = ++ai) == a2, "Wrong nthIt()"); 292 check((tmp_a = ++ai) == a3, "Wrong nthIt()"); 293 check((tmp_a = ++ai) == a4, "Wrong nthIt()"); 294 check(++ai == INVALID, "Wrong nthIt()"); 295 check(checkPath(cgr, p1), "Wrong checkPath()"); 296 297 // Check split() 298 p1.split(p1.nthIt(2), p2); 299 check(p1.length() == 2, "Wrong length"); 300 ai = p1.nthIt(0); 301 check((tmp_a = ai) == a1, "Wrong ArcIt"); 302 check((tmp_a = ++ai) == a2, "Wrong nthIt()"); 303 check(++ai == INVALID, "Wrong nthIt()"); 304 check(checkPath(cgr, p1), "Wrong checkPath()"); 305 check(p2.length() == 2, "Wrong length"); 306 ai = p2.nthIt(0); 307 check((tmp_a = ai) == a3, "Wrong ArcIt"); 308 check((tmp_a = ++ai) == a4, "Wrong nthIt()"); 309 check(++ai == INVALID, "Wrong nthIt()"); 310 check(checkPath(cgr, p2), "Wrong checkPath()"); 311 312 // Check split() and splice() 313 p1.spliceFront(p2); 314 p1.split(p1.nthIt(2), p2); 315 p2.split(p2.nthIt(1), p3); 316 p2.spliceBack(p1); 317 p2.splice(p2.nthIt(1), p3); 318 check(p2.length() == 4, "Wrong length"); 319 check(p2.front() == a1, "Wrong front()"); 320 check(p2.back() == a4, "Wrong back()"); 321 ai = p2.nthIt(0); 322 check((tmp_a = ai) == a1, "Wrong ArcIt"); 323 check((tmp_a = ++ai) == a2, "Wrong nthIt()"); 324 check((tmp_a = ++ai) == a3, "Wrong nthIt()"); 325 check((tmp_a = ++ai) == a4, "Wrong nthIt()"); 326 check(++ai == INVALID, "Wrong nthIt()"); 327 check(checkPath(cgr, p2), "Wrong checkPath()"); 328 } 329 330 }; 331 55 332 int main() { 56 check_concepts(); 57 58 checkCopy<Path<ListDigraph> >(); 59 checkCopy<SimplePath<ListDigraph> >(); 60 checkCopy<ListPath<ListDigraph> >(); 61 62 ListDigraph g; 63 ListDigraph::Arc a = g.addArc(g.addNode(), g.addNode()); 64 65 Path<ListDigraph> p; 66 StaticPath<ListDigraph> q,r; 67 p.addBack(a); 68 q=p; 69 r=q; 70 StaticPath<ListDigraph> s(q); 333 checkPathConcepts(); 334 checkPathCopy(); 335 CheckPathFunctions cpf; 336 cpf.run(); 71 337 72 338 return 0;
Note: See TracChangeset
for help on using the changeset viewer.