Changes in test/graph_test.cc [374:49d9a36b3b84:375:2d87dbd7f8c8] in lemon-1.2
- File:
-
- 1 edited
Legend:
- Unmodified
- Added
- Removed
-
test/graph_test.cc
r374 r375 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> 22 #include <lemon/full_graph.h> 23 #include <lemon/grid_graph.h> 24 #include <lemon/hypercube_graph.h> 24 25 25 26 #include "test_tools.h" … … 262 263 } 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 264 312 void checkConcepts() { 265 313 { // Checking graph components … … 291 339 checkConcept<ClearableGraphComponent<>, SmartGraph>(); 292 340 } 293 // { // Checking FullGraph 294 // checkConcept<Graph, FullGraph>(); 295 // checkGraphIterators<FullGraph>(); 296 // } 297 // { // Checking GridGraph 298 // checkConcept<Graph, GridGraph>(); 299 // checkGraphIterators<GridGraph>(); 300 // } 341 { // Checking FullGraph 342 checkConcept<Graph, FullGraph>(); 343 } 344 { // Checking GridGraph 345 checkConcept<Graph, GridGraph>(); 346 } 347 { // Checking HypercubeGraph 348 checkConcept<Graph, HypercubeGraph>(); 349 } 301 350 } 302 351 … … 355 404 } 356 405 357 // void checkGridGraph(const GridGraph& g, int w, int h) { 358 // check(g.width() == w, "Wrong width"); 359 // check(g.height() == h, "Wrong height"); 360 361 // for (int i = 0; i < w; ++i) { 362 // for (int j = 0; j < h; ++j) { 363 // check(g.col(g(i, j)) == i, "Wrong col"); 364 // check(g.row(g(i, j)) == j, "Wrong row"); 365 // } 366 // } 367 368 // for (int i = 0; i < w; ++i) { 369 // for (int j = 0; j < h - 1; ++j) { 370 // check(g.source(g.down(g(i, j))) == g(i, j), "Wrong down"); 371 // check(g.target(g.down(g(i, j))) == g(i, j + 1), "Wrong down"); 372 // } 373 // check(g.down(g(i, h - 1)) == INVALID, "Wrong down"); 374 // } 375 376 // for (int i = 0; i < w; ++i) { 377 // for (int j = 1; j < h; ++j) { 378 // check(g.source(g.up(g(i, j))) == g(i, j), "Wrong up"); 379 // check(g.target(g.up(g(i, j))) == g(i, j - 1), "Wrong up"); 380 // } 381 // check(g.up(g(i, 0)) == INVALID, "Wrong up"); 382 // } 383 384 // for (int j = 0; j < h; ++j) { 385 // for (int i = 0; i < w - 1; ++i) { 386 // check(g.source(g.right(g(i, j))) == g(i, j), "Wrong right"); 387 // check(g.target(g.right(g(i, j))) == g(i + 1, j), "Wrong right"); 388 // } 389 // check(g.right(g(w - 1, j)) == INVALID, "Wrong right"); 390 // } 391 392 // for (int j = 0; j < h; ++j) { 393 // for (int i = 1; i < w; ++i) { 394 // check(g.source(g.left(g(i, j))) == g(i, j), "Wrong left"); 395 // check(g.target(g.left(g(i, j))) == g(i - 1, j), "Wrong left"); 396 // } 397 // check(g.left(g(0, j)) == INVALID, "Wrong left"); 398 // } 399 // } 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 << (dim-1))); 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 << (dim-1))); 522 523 checkArcDirections(G); 524 525 checkNodeIds(G); 526 checkArcIds(G); 527 checkEdgeIds(G); 528 checkGraphNodeMap(G); 529 checkGraphArcMap(G); 530 checkGraphEdgeMap(G); 531 } 400 532 401 533 void checkGraphs() { … … 412 544 checkGraphValidity<SmartGraph>(); 413 545 } 414 // { // Checking FullGraph 415 // FullGraph g(5); 416 // checkGraphNodeList(g, 5); 417 // checkGraphEdgeList(g, 10); 418 // } 419 // { // Checking GridGraph 420 // GridGraph g(5, 6); 421 // checkGraphNodeList(g, 30); 422 // checkGraphEdgeList(g, 49); 423 // checkGridGraph(g, 5, 6); 424 // } 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 } 425 563 } 426 564
Note: See TracChangeset
for help on using the changeset viewer.