Changes in test/graph_test.cc [388:2d87dbd7f8c8:228:b6732e0d38c5] in lemon
 File:

 1 edited
Legend:
 Unmodified
 Added
 Removed

test/graph_test.cc
r388 r228 20 20 #include <lemon/list_graph.h> 21 21 #include <lemon/smart_graph.h> 22 #include <lemon/full_graph.h> 23 #include <lemon/grid_graph.h> 24 #include <lemon/hypercube_graph.h> 22 // #include <lemon/full_graph.h> 23 // #include <lemon/grid_graph.h> 25 24 26 25 #include "test_tools.h" … … 31 30 32 31 template <class Graph> 33 void checkGraph Build() {32 void checkGraph() { 34 33 TEMPLATE_GRAPH_TYPEDEFS(Graph); 35 34 … … 37 36 checkGraphNodeList(G, 0); 38 37 checkGraphEdgeList(G, 0); 39 checkGraphArcList(G, 0);40 38 41 39 Node … … 45 43 checkGraphNodeList(G, 3); 46 44 checkGraphEdgeList(G, 0); 47 checkGraphArcList(G, 0);48 45 49 46 Edge e1 = G.addEdge(n1, n2); 50 47 check((G.u(e1) == n1 && G.v(e1) == n2)  (G.u(e1) == n2 && G.v(e1) == n1), 51 48 "Wrong edge"); 52 53 49 checkGraphNodeList(G, 3); 50 checkGraphArcList(G, 2); 54 51 checkGraphEdgeList(G, 1); 55 checkGraphArcList(G, 2); 56 57 checkGraphIncEdgeArcLists(G, n1, 1); 58 checkGraphIncEdgeArcLists(G, n2, 1); 59 checkGraphIncEdgeArcLists(G, n3, 0); 60 52 53 checkGraphOutArcList(G, n1, 1); 54 checkGraphOutArcList(G, n2, 1); 55 checkGraphOutArcList(G, n3, 0); 56 57 checkGraphInArcList(G, n1, 1); 58 checkGraphInArcList(G, n2, 1); 59 checkGraphInArcList(G, n3, 0); 60 61 checkGraphIncEdgeList(G, n1, 1); 62 checkGraphIncEdgeList(G, n2, 1); 63 checkGraphIncEdgeList(G, n3, 0); 64 65 checkGraphConArcList(G, 2); 61 66 checkGraphConEdgeList(G, 1); 62 checkGraphConArcList(G, 2); 63 64 Edge e2 = G.addEdge(n2, n1), 65 e3 = G.addEdge(n2, n3); 66 67 68 Edge e2 = G.addEdge(n2, n1), e3 = G.addEdge(n2, n3); 67 69 checkGraphNodeList(G, 3); 70 checkGraphArcList(G, 6); 68 71 checkGraphEdgeList(G, 3); 69 checkGraphArcList(G, 6); 70 71 checkGraphIncEdgeArcLists(G, n1, 2); 72 checkGraphIncEdgeArcLists(G, n2, 3); 73 checkGraphIncEdgeArcLists(G, n3, 1); 74 72 73 checkGraphOutArcList(G, n1, 2); 74 checkGraphOutArcList(G, n2, 3); 75 checkGraphOutArcList(G, n3, 1); 76 77 checkGraphInArcList(G, n1, 2); 78 checkGraphInArcList(G, n2, 3); 79 checkGraphInArcList(G, n3, 1); 80 81 checkGraphIncEdgeList(G, n1, 2); 82 checkGraphIncEdgeList(G, n2, 3); 83 checkGraphIncEdgeList(G, n3, 1); 84 85 checkGraphConArcList(G, 6); 75 86 checkGraphConEdgeList(G, 3); 76 checkGraphConArcList(G, 6);77 87 78 88 checkArcDirections(G); … … 86 96 } 87 97 88 template <class Graph>89 void checkGraphAlter() {90 TEMPLATE_GRAPH_TYPEDEFS(Graph);91 92 Graph G;93 Node n1 = G.addNode(), n2 = G.addNode(),94 n3 = G.addNode(), n4 = G.addNode();95 Edge e1 = G.addEdge(n1, n2), e2 = G.addEdge(n2, n1),96 e3 = G.addEdge(n2, n3), e4 = G.addEdge(n1, n4),97 e5 = G.addEdge(n4, n3);98 99 checkGraphNodeList(G, 4);100 checkGraphEdgeList(G, 5);101 checkGraphArcList(G, 10);102 103 // Check changeU() and changeV()104 if (G.u(e2) == n2) {105 G.changeU(e2, n3);106 } else {107 G.changeV(e2, n3);108 }109 110 checkGraphNodeList(G, 4);111 checkGraphEdgeList(G, 5);112 checkGraphArcList(G, 10);113 114 checkGraphIncEdgeArcLists(G, n1, 3);115 checkGraphIncEdgeArcLists(G, n2, 2);116 checkGraphIncEdgeArcLists(G, n3, 3);117 checkGraphIncEdgeArcLists(G, n4, 2);118 119 checkGraphConEdgeList(G, 5);120 checkGraphConArcList(G, 10);121 122 if (G.u(e2) == n1) {123 G.changeU(e2, n2);124 } else {125 G.changeV(e2, n2);126 }127 128 checkGraphNodeList(G, 4);129 checkGraphEdgeList(G, 5);130 checkGraphArcList(G, 10);131 132 checkGraphIncEdgeArcLists(G, n1, 2);133 checkGraphIncEdgeArcLists(G, n2, 3);134 checkGraphIncEdgeArcLists(G, n3, 3);135 checkGraphIncEdgeArcLists(G, n4, 2);136 137 checkGraphConEdgeList(G, 5);138 checkGraphConArcList(G, 10);139 140 // Check contract()141 G.contract(n1, n4, false);142 143 checkGraphNodeList(G, 3);144 checkGraphEdgeList(G, 5);145 checkGraphArcList(G, 10);146 147 checkGraphIncEdgeArcLists(G, n1, 4);148 checkGraphIncEdgeArcLists(G, n2, 3);149 checkGraphIncEdgeArcLists(G, n3, 3);150 151 checkGraphConEdgeList(G, 5);152 checkGraphConArcList(G, 10);153 154 G.contract(n2, n3);155 156 checkGraphNodeList(G, 2);157 checkGraphEdgeList(G, 3);158 checkGraphArcList(G, 6);159 160 checkGraphIncEdgeArcLists(G, n1, 4);161 checkGraphIncEdgeArcLists(G, n2, 2);162 163 checkGraphConEdgeList(G, 3);164 checkGraphConArcList(G, 6);165 }166 167 template <class Graph>168 void checkGraphErase() {169 TEMPLATE_GRAPH_TYPEDEFS(Graph);170 171 Graph G;172 Node n1 = G.addNode(), n2 = G.addNode(),173 n3 = G.addNode(), n4 = G.addNode();174 Edge e1 = G.addEdge(n1, n2), e2 = G.addEdge(n2, n1),175 e3 = G.addEdge(n2, n3), e4 = G.addEdge(n1, n4),176 e5 = G.addEdge(n4, n3);177 178 // Check edge deletion179 G.erase(e2);180 181 checkGraphNodeList(G, 4);182 checkGraphEdgeList(G, 4);183 checkGraphArcList(G, 8);184 185 checkGraphIncEdgeArcLists(G, n1, 2);186 checkGraphIncEdgeArcLists(G, n2, 2);187 checkGraphIncEdgeArcLists(G, n3, 2);188 checkGraphIncEdgeArcLists(G, n4, 2);189 190 checkGraphConEdgeList(G, 4);191 checkGraphConArcList(G, 8);192 193 // Check node deletion194 G.erase(n3);195 196 checkGraphNodeList(G, 3);197 checkGraphEdgeList(G, 2);198 checkGraphArcList(G, 4);199 200 checkGraphIncEdgeArcLists(G, n1, 2);201 checkGraphIncEdgeArcLists(G, n2, 1);202 checkGraphIncEdgeArcLists(G, n4, 1);203 204 checkGraphConEdgeList(G, 2);205 checkGraphConArcList(G, 4);206 }207 208 209 template <class Graph>210 void checkGraphSnapshot() {211 TEMPLATE_GRAPH_TYPEDEFS(Graph);212 213 Graph G;214 Node n1 = G.addNode(), n2 = G.addNode(), n3 = G.addNode();215 Edge e1 = G.addEdge(n1, n2), e2 = G.addEdge(n2, n1),216 e3 = G.addEdge(n2, n3);217 218 checkGraphNodeList(G, 3);219 checkGraphEdgeList(G, 3);220 checkGraphArcList(G, 6);221 222 typename Graph::Snapshot snapshot(G);223 224 Node n = G.addNode();225 G.addEdge(n3, n);226 G.addEdge(n, n3);227 G.addEdge(n3, n2);228 229 checkGraphNodeList(G, 4);230 checkGraphEdgeList(G, 6);231 checkGraphArcList(G, 12);232 233 snapshot.restore();234 235 checkGraphNodeList(G, 3);236 checkGraphEdgeList(G, 3);237 checkGraphArcList(G, 6);238 239 checkGraphIncEdgeArcLists(G, n1, 2);240 checkGraphIncEdgeArcLists(G, n2, 3);241 checkGraphIncEdgeArcLists(G, n3, 1);242 243 checkGraphConEdgeList(G, 3);244 checkGraphConArcList(G, 6);245 246 checkNodeIds(G);247 checkEdgeIds(G);248 checkArcIds(G);249 checkGraphNodeMap(G);250 checkGraphEdgeMap(G);251 checkGraphArcMap(G);252 253 G.addNode();254 snapshot.save(G);255 256 G.addEdge(G.addNode(), G.addNode());257 258 snapshot.restore();259 260 checkGraphNodeList(G, 4);261 checkGraphEdgeList(G, 3);262 checkGraphArcList(G, 6);263 }264 265 void checkFullGraph(int num) {266 typedef FullGraph Graph;267 GRAPH_TYPEDEFS(Graph);268 269 Graph G(num);270 checkGraphNodeList(G, num);271 checkGraphEdgeList(G, num * (num  1) / 2);272 273 for (NodeIt n(G); n != INVALID; ++n) {274 checkGraphOutArcList(G, n, num  1);275 checkGraphInArcList(G, n, num  1);276 checkGraphIncEdgeList(G, n, num  1);277 }278 279 checkGraphConArcList(G, num * (num  1));280 checkGraphConEdgeList(G, num * (num  1) / 2);281 282 checkArcDirections(G);283 284 checkNodeIds(G);285 checkArcIds(G);286 checkEdgeIds(G);287 checkGraphNodeMap(G);288 checkGraphArcMap(G);289 checkGraphEdgeMap(G);290 291 292 for (int i = 0; i < G.nodeNum(); ++i) {293 check(G.index(G(i)) == i, "Wrong index");294 }295 296 for (NodeIt u(G); u != INVALID; ++u) {297 for (NodeIt v(G); v != INVALID; ++v) {298 Edge e = G.edge(u, v);299 Arc a = G.arc(u, v);300 if (u == v) {301 check(e == INVALID, "Wrong edge lookup");302 check(a == INVALID, "Wrong arc lookup");303 } else {304 check((G.u(e) == u && G.v(e) == v) 305 (G.u(e) == v && G.v(e) == u), "Wrong edge lookup");306 check(G.source(a) == u && G.target(a) == v, "Wrong arc lookup");307 }308 }309 }310 }311 312 98 void checkConcepts() { 313 99 { // Checking graph components … … 339 125 checkConcept<ClearableGraphComponent<>, SmartGraph>(); 340 126 } 341 { // Checking FullGraph 342 checkConcept<Graph, FullGraph>(); 343 } 344 { // Checking GridGraph 345 checkConcept<Graph, GridGraph>(); 346 } 347 { // Checking HypercubeGraph 348 checkConcept<Graph, HypercubeGraph>(); 349 } 127 // { // Checking FullGraph 128 // checkConcept<Graph, FullGraph>(); 129 // checkGraphIterators<FullGraph>(); 130 // } 131 // { // Checking GridGraph 132 // checkConcept<Graph, GridGraph>(); 133 // checkGraphIterators<GridGraph>(); 134 // } 350 135 } 351 136 … … 404 189 } 405 190 406 void checkGridGraph(int width, int height) { 407 typedef GridGraph Graph; 408 GRAPH_TYPEDEFS(Graph); 409 Graph G(width, height); 410 411 check(G.width() == width, "Wrong column number"); 412 check(G.height() == height, "Wrong row number"); 413 414 for (int i = 0; i < width; ++i) { 415 for (int j = 0; j < height; ++j) { 416 check(G.col(G(i, j)) == i, "Wrong column"); 417 check(G.row(G(i, j)) == j, "Wrong row"); 418 check(G.pos(G(i, j)).x == i, "Wrong column"); 419 check(G.pos(G(i, j)).y == j, "Wrong row"); 420 } 421 } 422 423 for (int j = 0; j < height; ++j) { 424 for (int i = 0; i < width  1; ++i) { 425 check(G.source(G.right(G(i, j))) == G(i, j), "Wrong right"); 426 check(G.target(G.right(G(i, j))) == G(i + 1, j), "Wrong right"); 427 } 428 check(G.right(G(width  1, j)) == INVALID, "Wrong right"); 429 } 430 431 for (int j = 0; j < height; ++j) { 432 for (int i = 1; i < width; ++i) { 433 check(G.source(G.left(G(i, j))) == G(i, j), "Wrong left"); 434 check(G.target(G.left(G(i, j))) == G(i  1, j), "Wrong left"); 435 } 436 check(G.left(G(0, j)) == INVALID, "Wrong left"); 437 } 438 439 for (int i = 0; i < width; ++i) { 440 for (int j = 0; j < height  1; ++j) { 441 check(G.source(G.up(G(i, j))) == G(i, j), "Wrong up"); 442 check(G.target(G.up(G(i, j))) == G(i, j + 1), "Wrong up"); 443 } 444 check(G.up(G(i, height  1)) == INVALID, "Wrong up"); 445 } 446 447 for (int i = 0; i < width; ++i) { 448 for (int j = 1; j < height; ++j) { 449 check(G.source(G.down(G(i, j))) == G(i, j), "Wrong down"); 450 check(G.target(G.down(G(i, j))) == G(i, j  1), "Wrong down"); 451 } 452 check(G.down(G(i, 0)) == INVALID, "Wrong down"); 453 } 454 455 checkGraphNodeList(G, width * height); 456 checkGraphEdgeList(G, width * (height  1) + (width  1) * height); 457 checkGraphArcList(G, 2 * (width * (height  1) + (width  1) * height)); 458 459 for (NodeIt n(G); n != INVALID; ++n) { 460 int nb = 4; 461 if (G.col(n) == 0) nb; 462 if (G.col(n) == width  1) nb; 463 if (G.row(n) == 0) nb; 464 if (G.row(n) == height  1) nb; 465 466 checkGraphOutArcList(G, n, nb); 467 checkGraphInArcList(G, n, nb); 468 checkGraphIncEdgeList(G, n, nb); 469 } 470 471 checkArcDirections(G); 472 473 checkGraphConArcList(G, 2 * (width * (height  1) + (width  1) * height)); 474 checkGraphConEdgeList(G, width * (height  1) + (width  1) * height); 475 476 checkNodeIds(G); 477 checkArcIds(G); 478 checkEdgeIds(G); 479 checkGraphNodeMap(G); 480 checkGraphArcMap(G); 481 checkGraphEdgeMap(G); 482 483 } 484 485 void checkHypercubeGraph(int dim) { 486 GRAPH_TYPEDEFS(HypercubeGraph); 487 488 HypercubeGraph G(dim); 489 checkGraphNodeList(G, 1 << dim); 490 checkGraphEdgeList(G, dim * (1 << (dim1))); 491 checkGraphArcList(G, dim * (1 << dim)); 492 493 Node n = G.nodeFromId(dim); 494 495 for (NodeIt n(G); n != INVALID; ++n) { 496 checkGraphIncEdgeList(G, n, dim); 497 for (IncEdgeIt e(G, n); e != INVALID; ++e) { 498 check( (G.u(e) == n && 499 G.id(G.v(e)) == (G.id(n) ^ (1 << G.dimension(e))))  500 (G.v(e) == n && 501 G.id(G.u(e)) == (G.id(n) ^ (1 << G.dimension(e)))), 502 "Wrong edge or wrong dimension"); 503 } 504 505 checkGraphOutArcList(G, n, dim); 506 for (OutArcIt a(G, n); a != INVALID; ++a) { 507 check(G.source(a) == n && 508 G.id(G.target(a)) == (G.id(n) ^ (1 << G.dimension(a))), 509 "Wrong arc or wrong dimension"); 510 } 511 512 checkGraphInArcList(G, n, dim); 513 for (InArcIt a(G, n); a != INVALID; ++a) { 514 check(G.target(a) == n && 515 G.id(G.source(a)) == (G.id(n) ^ (1 << G.dimension(a))), 516 "Wrong arc or wrong dimension"); 517 } 518 } 519 520 checkGraphConArcList(G, (1 << dim) * dim); 521 checkGraphConEdgeList(G, dim * (1 << (dim1))); 522 523 checkArcDirections(G); 524 525 checkNodeIds(G); 526 checkArcIds(G); 527 checkEdgeIds(G); 528 checkGraphNodeMap(G); 529 checkGraphArcMap(G); 530 checkGraphEdgeMap(G); 531 } 191 // void checkGridGraph(const GridGraph& g, int w, int h) { 192 // check(g.width() == w, "Wrong width"); 193 // check(g.height() == h, "Wrong height"); 194 195 // for (int i = 0; i < w; ++i) { 196 // for (int j = 0; j < h; ++j) { 197 // check(g.col(g(i, j)) == i, "Wrong col"); 198 // check(g.row(g(i, j)) == j, "Wrong row"); 199 // } 200 // } 201 202 // for (int i = 0; i < w; ++i) { 203 // for (int j = 0; j < h  1; ++j) { 204 // check(g.source(g.down(g(i, j))) == g(i, j), "Wrong down"); 205 // check(g.target(g.down(g(i, j))) == g(i, j + 1), "Wrong down"); 206 // } 207 // check(g.down(g(i, h  1)) == INVALID, "Wrong down"); 208 // } 209 210 // for (int i = 0; i < w; ++i) { 211 // for (int j = 1; j < h; ++j) { 212 // check(g.source(g.up(g(i, j))) == g(i, j), "Wrong up"); 213 // check(g.target(g.up(g(i, j))) == g(i, j  1), "Wrong up"); 214 // } 215 // check(g.up(g(i, 0)) == INVALID, "Wrong up"); 216 // } 217 218 // for (int j = 0; j < h; ++j) { 219 // for (int i = 0; i < w  1; ++i) { 220 // check(g.source(g.right(g(i, j))) == g(i, j), "Wrong right"); 221 // check(g.target(g.right(g(i, j))) == g(i + 1, j), "Wrong right"); 222 // } 223 // check(g.right(g(w  1, j)) == INVALID, "Wrong right"); 224 // } 225 226 // for (int j = 0; j < h; ++j) { 227 // for (int i = 1; i < w; ++i) { 228 // check(g.source(g.left(g(i, j))) == g(i, j), "Wrong left"); 229 // check(g.target(g.left(g(i, j))) == g(i  1, j), "Wrong left"); 230 // } 231 // check(g.left(g(0, j)) == INVALID, "Wrong left"); 232 // } 233 // } 532 234 533 235 void checkGraphs() { 534 236 { // Checking ListGraph 535 checkGraphBuild<ListGraph>(); 536 checkGraphAlter<ListGraph>(); 537 checkGraphErase<ListGraph>(); 538 checkGraphSnapshot<ListGraph>(); 237 checkGraph<ListGraph>(); 539 238 checkGraphValidityErase<ListGraph>(); 540 239 } 541 240 { // Checking SmartGraph 542 checkGraphBuild<SmartGraph>(); 543 checkGraphSnapshot<SmartGraph>(); 241 checkGraph<SmartGraph>(); 544 242 checkGraphValidity<SmartGraph>(); 545 243 } 546 { // Checking FullGraph 547 checkFullGraph(7); 548 checkFullGraph(8); 549 } 550 { // Checking GridGraph 551 checkGridGraph(5, 8); 552 checkGridGraph(8, 5); 553 checkGridGraph(5, 5); 554 checkGridGraph(0, 0); 555 checkGridGraph(1, 1); 556 } 557 { // Checking HypercubeGraph 558 checkHypercubeGraph(1); 559 checkHypercubeGraph(2); 560 checkHypercubeGraph(3); 561 checkHypercubeGraph(4); 562 } 244 // { // Checking FullGraph 245 // FullGraph g(5); 246 // checkGraphNodeList(g, 5); 247 // checkGraphEdgeList(g, 10); 248 // } 249 // { // Checking GridGraph 250 // GridGraph g(5, 6); 251 // checkGraphNodeList(g, 30); 252 // checkGraphEdgeList(g, 49); 253 // checkGridGraph(g, 5, 6); 254 // } 563 255 } 564 256
Note: See TracChangeset
for help on using the changeset viewer.