1.1 --- a/test/graph_test.cc Fri Oct 16 10:21:37 2009 +0200
1.2 +++ b/test/graph_test.cc Thu Nov 05 15:50:01 2009 +0100
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-2008
1.8 + * Copyright (C) 2003-2009
1.9 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
1.10 * (Egervary Research Group on Combinatorial Optimization, EGRES).
1.11 *
1.12 @@ -19,8 +19,9 @@
1.13 #include <lemon/concepts/graph.h>
1.14 #include <lemon/list_graph.h>
1.15 #include <lemon/smart_graph.h>
1.16 -// #include <lemon/full_graph.h>
1.17 -// #include <lemon/grid_graph.h>
1.18 +#include <lemon/full_graph.h>
1.19 +#include <lemon/grid_graph.h>
1.20 +#include <lemon/hypercube_graph.h>
1.21
1.22 #include "test_tools.h"
1.23 #include "graph_test.h"
1.24 @@ -29,12 +30,16 @@
1.25 using namespace lemon::concepts;
1.26
1.27 template <class Graph>
1.28 -void checkGraph() {
1.29 +void checkGraphBuild() {
1.30 TEMPLATE_GRAPH_TYPEDEFS(Graph);
1.31
1.32 Graph G;
1.33 checkGraphNodeList(G, 0);
1.34 checkGraphEdgeList(G, 0);
1.35 + checkGraphArcList(G, 0);
1.36 +
1.37 + G.reserveNode(3);
1.38 + G.reserveEdge(3);
1.39
1.40 Node
1.41 n1 = G.addNode(),
1.42 @@ -42,48 +47,36 @@
1.43 n3 = G.addNode();
1.44 checkGraphNodeList(G, 3);
1.45 checkGraphEdgeList(G, 0);
1.46 + checkGraphArcList(G, 0);
1.47
1.48 Edge e1 = G.addEdge(n1, n2);
1.49 check((G.u(e1) == n1 && G.v(e1) == n2) || (G.u(e1) == n2 && G.v(e1) == n1),
1.50 "Wrong edge");
1.51 +
1.52 checkGraphNodeList(G, 3);
1.53 + checkGraphEdgeList(G, 1);
1.54 checkGraphArcList(G, 2);
1.55 - checkGraphEdgeList(G, 1);
1.56
1.57 - checkGraphOutArcList(G, n1, 1);
1.58 - checkGraphOutArcList(G, n2, 1);
1.59 - checkGraphOutArcList(G, n3, 0);
1.60 + checkGraphIncEdgeArcLists(G, n1, 1);
1.61 + checkGraphIncEdgeArcLists(G, n2, 1);
1.62 + checkGraphIncEdgeArcLists(G, n3, 0);
1.63
1.64 - checkGraphInArcList(G, n1, 1);
1.65 - checkGraphInArcList(G, n2, 1);
1.66 - checkGraphInArcList(G, n3, 0);
1.67 + checkGraphConEdgeList(G, 1);
1.68 + checkGraphConArcList(G, 2);
1.69
1.70 - checkGraphIncEdgeList(G, n1, 1);
1.71 - checkGraphIncEdgeList(G, n2, 1);
1.72 - checkGraphIncEdgeList(G, n3, 0);
1.73 + Edge e2 = G.addEdge(n2, n1),
1.74 + e3 = G.addEdge(n2, n3);
1.75
1.76 - checkGraphConArcList(G, 2);
1.77 - checkGraphConEdgeList(G, 1);
1.78 + checkGraphNodeList(G, 3);
1.79 + checkGraphEdgeList(G, 3);
1.80 + checkGraphArcList(G, 6);
1.81
1.82 - Edge e2 = G.addEdge(n2, n1), e3 = G.addEdge(n2, n3);
1.83 - checkGraphNodeList(G, 3);
1.84 - checkGraphArcList(G, 6);
1.85 - checkGraphEdgeList(G, 3);
1.86 + checkGraphIncEdgeArcLists(G, n1, 2);
1.87 + checkGraphIncEdgeArcLists(G, n2, 3);
1.88 + checkGraphIncEdgeArcLists(G, n3, 1);
1.89
1.90 - checkGraphOutArcList(G, n1, 2);
1.91 - checkGraphOutArcList(G, n2, 3);
1.92 - checkGraphOutArcList(G, n3, 1);
1.93 -
1.94 - checkGraphInArcList(G, n1, 2);
1.95 - checkGraphInArcList(G, n2, 3);
1.96 - checkGraphInArcList(G, n3, 1);
1.97 -
1.98 - checkGraphIncEdgeList(G, n1, 2);
1.99 - checkGraphIncEdgeList(G, n2, 3);
1.100 - checkGraphIncEdgeList(G, n3, 1);
1.101 -
1.102 + checkGraphConEdgeList(G, 3);
1.103 checkGraphConArcList(G, 6);
1.104 - checkGraphConEdgeList(G, 3);
1.105
1.106 checkArcDirections(G);
1.107
1.108 @@ -95,6 +88,246 @@
1.109 checkGraphEdgeMap(G);
1.110 }
1.111
1.112 +template <class Graph>
1.113 +void checkGraphAlter() {
1.114 + TEMPLATE_GRAPH_TYPEDEFS(Graph);
1.115 +
1.116 + Graph G;
1.117 + Node n1 = G.addNode(), n2 = G.addNode(),
1.118 + n3 = G.addNode(), n4 = G.addNode();
1.119 + Edge e1 = G.addEdge(n1, n2), e2 = G.addEdge(n2, n1),
1.120 + e3 = G.addEdge(n2, n3), e4 = G.addEdge(n1, n4),
1.121 + e5 = G.addEdge(n4, n3);
1.122 +
1.123 + checkGraphNodeList(G, 4);
1.124 + checkGraphEdgeList(G, 5);
1.125 + checkGraphArcList(G, 10);
1.126 +
1.127 + // Check changeU() and changeV()
1.128 + if (G.u(e2) == n2) {
1.129 + G.changeU(e2, n3);
1.130 + } else {
1.131 + G.changeV(e2, n3);
1.132 + }
1.133 +
1.134 + checkGraphNodeList(G, 4);
1.135 + checkGraphEdgeList(G, 5);
1.136 + checkGraphArcList(G, 10);
1.137 +
1.138 + checkGraphIncEdgeArcLists(G, n1, 3);
1.139 + checkGraphIncEdgeArcLists(G, n2, 2);
1.140 + checkGraphIncEdgeArcLists(G, n3, 3);
1.141 + checkGraphIncEdgeArcLists(G, n4, 2);
1.142 +
1.143 + checkGraphConEdgeList(G, 5);
1.144 + checkGraphConArcList(G, 10);
1.145 +
1.146 + if (G.u(e2) == n1) {
1.147 + G.changeU(e2, n2);
1.148 + } else {
1.149 + G.changeV(e2, n2);
1.150 + }
1.151 +
1.152 + checkGraphNodeList(G, 4);
1.153 + checkGraphEdgeList(G, 5);
1.154 + checkGraphArcList(G, 10);
1.155 +
1.156 + checkGraphIncEdgeArcLists(G, n1, 2);
1.157 + checkGraphIncEdgeArcLists(G, n2, 3);
1.158 + checkGraphIncEdgeArcLists(G, n3, 3);
1.159 + checkGraphIncEdgeArcLists(G, n4, 2);
1.160 +
1.161 + checkGraphConEdgeList(G, 5);
1.162 + checkGraphConArcList(G, 10);
1.163 +
1.164 + // Check contract()
1.165 + G.contract(n1, n4, false);
1.166 +
1.167 + checkGraphNodeList(G, 3);
1.168 + checkGraphEdgeList(G, 5);
1.169 + checkGraphArcList(G, 10);
1.170 +
1.171 + checkGraphIncEdgeArcLists(G, n1, 4);
1.172 + checkGraphIncEdgeArcLists(G, n2, 3);
1.173 + checkGraphIncEdgeArcLists(G, n3, 3);
1.174 +
1.175 + checkGraphConEdgeList(G, 5);
1.176 + checkGraphConArcList(G, 10);
1.177 +
1.178 + G.contract(n2, n3);
1.179 +
1.180 + checkGraphNodeList(G, 2);
1.181 + checkGraphEdgeList(G, 3);
1.182 + checkGraphArcList(G, 6);
1.183 +
1.184 + checkGraphIncEdgeArcLists(G, n1, 4);
1.185 + checkGraphIncEdgeArcLists(G, n2, 2);
1.186 +
1.187 + checkGraphConEdgeList(G, 3);
1.188 + checkGraphConArcList(G, 6);
1.189 +}
1.190 +
1.191 +template <class Graph>
1.192 +void checkGraphErase() {
1.193 + TEMPLATE_GRAPH_TYPEDEFS(Graph);
1.194 +
1.195 + Graph G;
1.196 + Node n1 = G.addNode(), n2 = G.addNode(),
1.197 + n3 = G.addNode(), n4 = G.addNode();
1.198 + Edge e1 = G.addEdge(n1, n2), e2 = G.addEdge(n2, n1),
1.199 + e3 = G.addEdge(n2, n3), e4 = G.addEdge(n1, n4),
1.200 + e5 = G.addEdge(n4, n3);
1.201 +
1.202 + // Check edge deletion
1.203 + G.erase(e2);
1.204 +
1.205 + checkGraphNodeList(G, 4);
1.206 + checkGraphEdgeList(G, 4);
1.207 + checkGraphArcList(G, 8);
1.208 +
1.209 + checkGraphIncEdgeArcLists(G, n1, 2);
1.210 + checkGraphIncEdgeArcLists(G, n2, 2);
1.211 + checkGraphIncEdgeArcLists(G, n3, 2);
1.212 + checkGraphIncEdgeArcLists(G, n4, 2);
1.213 +
1.214 + checkGraphConEdgeList(G, 4);
1.215 + checkGraphConArcList(G, 8);
1.216 +
1.217 + // Check node deletion
1.218 + G.erase(n3);
1.219 +
1.220 + checkGraphNodeList(G, 3);
1.221 + checkGraphEdgeList(G, 2);
1.222 + checkGraphArcList(G, 4);
1.223 +
1.224 + checkGraphIncEdgeArcLists(G, n1, 2);
1.225 + checkGraphIncEdgeArcLists(G, n2, 1);
1.226 + checkGraphIncEdgeArcLists(G, n4, 1);
1.227 +
1.228 + checkGraphConEdgeList(G, 2);
1.229 + checkGraphConArcList(G, 4);
1.230 +}
1.231 +
1.232 +
1.233 +template <class Graph>
1.234 +void checkGraphSnapshot() {
1.235 + TEMPLATE_GRAPH_TYPEDEFS(Graph);
1.236 +
1.237 + Graph G;
1.238 + Node n1 = G.addNode(), n2 = G.addNode(), n3 = G.addNode();
1.239 + Edge e1 = G.addEdge(n1, n2), e2 = G.addEdge(n2, n1),
1.240 + e3 = G.addEdge(n2, n3);
1.241 +
1.242 + checkGraphNodeList(G, 3);
1.243 + checkGraphEdgeList(G, 3);
1.244 + checkGraphArcList(G, 6);
1.245 +
1.246 + typename Graph::Snapshot snapshot(G);
1.247 +
1.248 + Node n = G.addNode();
1.249 + G.addEdge(n3, n);
1.250 + G.addEdge(n, n3);
1.251 + G.addEdge(n3, n2);
1.252 +
1.253 + checkGraphNodeList(G, 4);
1.254 + checkGraphEdgeList(G, 6);
1.255 + checkGraphArcList(G, 12);
1.256 +
1.257 + snapshot.restore();
1.258 +
1.259 + checkGraphNodeList(G, 3);
1.260 + checkGraphEdgeList(G, 3);
1.261 + checkGraphArcList(G, 6);
1.262 +
1.263 + checkGraphIncEdgeArcLists(G, n1, 2);
1.264 + checkGraphIncEdgeArcLists(G, n2, 3);
1.265 + checkGraphIncEdgeArcLists(G, n3, 1);
1.266 +
1.267 + checkGraphConEdgeList(G, 3);
1.268 + checkGraphConArcList(G, 6);
1.269 +
1.270 + checkNodeIds(G);
1.271 + checkEdgeIds(G);
1.272 + checkArcIds(G);
1.273 + checkGraphNodeMap(G);
1.274 + checkGraphEdgeMap(G);
1.275 + checkGraphArcMap(G);
1.276 +
1.277 + G.addNode();
1.278 + snapshot.save(G);
1.279 +
1.280 + G.addEdge(G.addNode(), G.addNode());
1.281 +
1.282 + snapshot.restore();
1.283 + snapshot.save(G);
1.284 +
1.285 + checkGraphNodeList(G, 4);
1.286 + checkGraphEdgeList(G, 3);
1.287 + checkGraphArcList(G, 6);
1.288 +
1.289 + G.addEdge(G.addNode(), G.addNode());
1.290 +
1.291 + snapshot.restore();
1.292 +
1.293 + checkGraphNodeList(G, 4);
1.294 + checkGraphEdgeList(G, 3);
1.295 + checkGraphArcList(G, 6);
1.296 +}
1.297 +
1.298 +void checkFullGraph(int num) {
1.299 + typedef FullGraph Graph;
1.300 + GRAPH_TYPEDEFS(Graph);
1.301 +
1.302 + Graph G(num);
1.303 + check(G.nodeNum() == num && G.edgeNum() == num * (num - 1) / 2,
1.304 + "Wrong size");
1.305 +
1.306 + G.resize(num);
1.307 + check(G.nodeNum() == num && G.edgeNum() == num * (num - 1) / 2,
1.308 + "Wrong size");
1.309 +
1.310 + checkGraphNodeList(G, num);
1.311 + checkGraphEdgeList(G, num * (num - 1) / 2);
1.312 +
1.313 + for (NodeIt n(G); n != INVALID; ++n) {
1.314 + checkGraphOutArcList(G, n, num - 1);
1.315 + checkGraphInArcList(G, n, num - 1);
1.316 + checkGraphIncEdgeList(G, n, num - 1);
1.317 + }
1.318 +
1.319 + checkGraphConArcList(G, num * (num - 1));
1.320 + checkGraphConEdgeList(G, num * (num - 1) / 2);
1.321 +
1.322 + checkArcDirections(G);
1.323 +
1.324 + checkNodeIds(G);
1.325 + checkArcIds(G);
1.326 + checkEdgeIds(G);
1.327 + checkGraphNodeMap(G);
1.328 + checkGraphArcMap(G);
1.329 + checkGraphEdgeMap(G);
1.330 +
1.331 +
1.332 + for (int i = 0; i < G.nodeNum(); ++i) {
1.333 + check(G.index(G(i)) == i, "Wrong index");
1.334 + }
1.335 +
1.336 + for (NodeIt u(G); u != INVALID; ++u) {
1.337 + for (NodeIt v(G); v != INVALID; ++v) {
1.338 + Edge e = G.edge(u, v);
1.339 + Arc a = G.arc(u, v);
1.340 + if (u == v) {
1.341 + check(e == INVALID, "Wrong edge lookup");
1.342 + check(a == INVALID, "Wrong arc lookup");
1.343 + } else {
1.344 + check((G.u(e) == u && G.v(e) == v) ||
1.345 + (G.u(e) == v && G.v(e) == u), "Wrong edge lookup");
1.346 + check(G.source(a) == u && G.target(a) == v, "Wrong arc lookup");
1.347 + }
1.348 + }
1.349 + }
1.350 +}
1.351 +
1.352 void checkConcepts() {
1.353 { // Checking graph components
1.354 checkConcept<BaseGraphComponent, BaseGraphComponent >();
1.355 @@ -124,14 +357,15 @@
1.356 checkConcept<ExtendableGraphComponent<>, SmartGraph>();
1.357 checkConcept<ClearableGraphComponent<>, SmartGraph>();
1.358 }
1.359 -// { // Checking FullGraph
1.360 -// checkConcept<Graph, FullGraph>();
1.361 -// checkGraphIterators<FullGraph>();
1.362 -// }
1.363 -// { // Checking GridGraph
1.364 -// checkConcept<Graph, GridGraph>();
1.365 -// checkGraphIterators<GridGraph>();
1.366 -// }
1.367 + { // Checking FullGraph
1.368 + checkConcept<Graph, FullGraph>();
1.369 + }
1.370 + { // Checking GridGraph
1.371 + checkConcept<Graph, GridGraph>();
1.372 + }
1.373 + { // Checking HypercubeGraph
1.374 + checkConcept<Graph, HypercubeGraph>();
1.375 + }
1.376 }
1.377
1.378 template <typename Graph>
1.379 @@ -188,70 +422,172 @@
1.380 check(!g.valid(g.arcFromId(-1)), "Wrong validity check");
1.381 }
1.382
1.383 -// void checkGridGraph(const GridGraph& g, int w, int h) {
1.384 -// check(g.width() == w, "Wrong width");
1.385 -// check(g.height() == h, "Wrong height");
1.386 +void checkGridGraph(int width, int height) {
1.387 + typedef GridGraph Graph;
1.388 + GRAPH_TYPEDEFS(Graph);
1.389 + Graph G(width, height);
1.390
1.391 -// for (int i = 0; i < w; ++i) {
1.392 -// for (int j = 0; j < h; ++j) {
1.393 -// check(g.col(g(i, j)) == i, "Wrong col");
1.394 -// check(g.row(g(i, j)) == j, "Wrong row");
1.395 -// }
1.396 -// }
1.397 + check(G.width() == width, "Wrong column number");
1.398 + check(G.height() == height, "Wrong row number");
1.399
1.400 -// for (int i = 0; i < w; ++i) {
1.401 -// for (int j = 0; j < h - 1; ++j) {
1.402 -// check(g.source(g.down(g(i, j))) == g(i, j), "Wrong down");
1.403 -// check(g.target(g.down(g(i, j))) == g(i, j + 1), "Wrong down");
1.404 -// }
1.405 -// check(g.down(g(i, h - 1)) == INVALID, "Wrong down");
1.406 -// }
1.407 + G.resize(width, height);
1.408 + check(G.width() == width, "Wrong column number");
1.409 + check(G.height() == height, "Wrong row number");
1.410
1.411 -// for (int i = 0; i < w; ++i) {
1.412 -// for (int j = 1; j < h; ++j) {
1.413 -// check(g.source(g.up(g(i, j))) == g(i, j), "Wrong up");
1.414 -// check(g.target(g.up(g(i, j))) == g(i, j - 1), "Wrong up");
1.415 -// }
1.416 -// check(g.up(g(i, 0)) == INVALID, "Wrong up");
1.417 -// }
1.418 + for (int i = 0; i < width; ++i) {
1.419 + for (int j = 0; j < height; ++j) {
1.420 + check(G.col(G(i, j)) == i, "Wrong column");
1.421 + check(G.row(G(i, j)) == j, "Wrong row");
1.422 + check(G.pos(G(i, j)).x == i, "Wrong column");
1.423 + check(G.pos(G(i, j)).y == j, "Wrong row");
1.424 + }
1.425 + }
1.426
1.427 -// for (int j = 0; j < h; ++j) {
1.428 -// for (int i = 0; i < w - 1; ++i) {
1.429 -// check(g.source(g.right(g(i, j))) == g(i, j), "Wrong right");
1.430 -// check(g.target(g.right(g(i, j))) == g(i + 1, j), "Wrong right");
1.431 -// }
1.432 -// check(g.right(g(w - 1, j)) == INVALID, "Wrong right");
1.433 -// }
1.434 + for (int j = 0; j < height; ++j) {
1.435 + for (int i = 0; i < width - 1; ++i) {
1.436 + check(G.source(G.right(G(i, j))) == G(i, j), "Wrong right");
1.437 + check(G.target(G.right(G(i, j))) == G(i + 1, j), "Wrong right");
1.438 + }
1.439 + check(G.right(G(width - 1, j)) == INVALID, "Wrong right");
1.440 + }
1.441
1.442 -// for (int j = 0; j < h; ++j) {
1.443 -// for (int i = 1; i < w; ++i) {
1.444 -// check(g.source(g.left(g(i, j))) == g(i, j), "Wrong left");
1.445 -// check(g.target(g.left(g(i, j))) == g(i - 1, j), "Wrong left");
1.446 -// }
1.447 -// check(g.left(g(0, j)) == INVALID, "Wrong left");
1.448 -// }
1.449 -// }
1.450 + for (int j = 0; j < height; ++j) {
1.451 + for (int i = 1; i < width; ++i) {
1.452 + check(G.source(G.left(G(i, j))) == G(i, j), "Wrong left");
1.453 + check(G.target(G.left(G(i, j))) == G(i - 1, j), "Wrong left");
1.454 + }
1.455 + check(G.left(G(0, j)) == INVALID, "Wrong left");
1.456 + }
1.457 +
1.458 + for (int i = 0; i < width; ++i) {
1.459 + for (int j = 0; j < height - 1; ++j) {
1.460 + check(G.source(G.up(G(i, j))) == G(i, j), "Wrong up");
1.461 + check(G.target(G.up(G(i, j))) == G(i, j + 1), "Wrong up");
1.462 + }
1.463 + check(G.up(G(i, height - 1)) == INVALID, "Wrong up");
1.464 + }
1.465 +
1.466 + for (int i = 0; i < width; ++i) {
1.467 + for (int j = 1; j < height; ++j) {
1.468 + check(G.source(G.down(G(i, j))) == G(i, j), "Wrong down");
1.469 + check(G.target(G.down(G(i, j))) == G(i, j - 1), "Wrong down");
1.470 + }
1.471 + check(G.down(G(i, 0)) == INVALID, "Wrong down");
1.472 + }
1.473 +
1.474 + checkGraphNodeList(G, width * height);
1.475 + checkGraphEdgeList(G, width * (height - 1) + (width - 1) * height);
1.476 + checkGraphArcList(G, 2 * (width * (height - 1) + (width - 1) * height));
1.477 +
1.478 + for (NodeIt n(G); n != INVALID; ++n) {
1.479 + int nb = 4;
1.480 + if (G.col(n) == 0) --nb;
1.481 + if (G.col(n) == width - 1) --nb;
1.482 + if (G.row(n) == 0) --nb;
1.483 + if (G.row(n) == height - 1) --nb;
1.484 +
1.485 + checkGraphOutArcList(G, n, nb);
1.486 + checkGraphInArcList(G, n, nb);
1.487 + checkGraphIncEdgeList(G, n, nb);
1.488 + }
1.489 +
1.490 + checkArcDirections(G);
1.491 +
1.492 + checkGraphConArcList(G, 2 * (width * (height - 1) + (width - 1) * height));
1.493 + checkGraphConEdgeList(G, width * (height - 1) + (width - 1) * height);
1.494 +
1.495 + checkNodeIds(G);
1.496 + checkArcIds(G);
1.497 + checkEdgeIds(G);
1.498 + checkGraphNodeMap(G);
1.499 + checkGraphArcMap(G);
1.500 + checkGraphEdgeMap(G);
1.501 +
1.502 +}
1.503 +
1.504 +void checkHypercubeGraph(int dim) {
1.505 + GRAPH_TYPEDEFS(HypercubeGraph);
1.506 +
1.507 + HypercubeGraph G(dim);
1.508 + check(G.dimension() == dim, "Wrong dimension");
1.509 +
1.510 + G.resize(dim);
1.511 + check(G.dimension() == dim, "Wrong dimension");
1.512 +
1.513 + checkGraphNodeList(G, 1 << dim);
1.514 + checkGraphEdgeList(G, dim * (1 << (dim-1)));
1.515 + checkGraphArcList(G, dim * (1 << dim));
1.516 +
1.517 + Node n = G.nodeFromId(dim);
1.518 +
1.519 + for (NodeIt n(G); n != INVALID; ++n) {
1.520 + checkGraphIncEdgeList(G, n, dim);
1.521 + for (IncEdgeIt e(G, n); e != INVALID; ++e) {
1.522 + check( (G.u(e) == n &&
1.523 + G.id(G.v(e)) == (G.id(n) ^ (1 << G.dimension(e)))) ||
1.524 + (G.v(e) == n &&
1.525 + G.id(G.u(e)) == (G.id(n) ^ (1 << G.dimension(e)))),
1.526 + "Wrong edge or wrong dimension");
1.527 + }
1.528 +
1.529 + checkGraphOutArcList(G, n, dim);
1.530 + for (OutArcIt a(G, n); a != INVALID; ++a) {
1.531 + check(G.source(a) == n &&
1.532 + G.id(G.target(a)) == (G.id(n) ^ (1 << G.dimension(a))),
1.533 + "Wrong arc or wrong dimension");
1.534 + }
1.535 +
1.536 + checkGraphInArcList(G, n, dim);
1.537 + for (InArcIt a(G, n); a != INVALID; ++a) {
1.538 + check(G.target(a) == n &&
1.539 + G.id(G.source(a)) == (G.id(n) ^ (1 << G.dimension(a))),
1.540 + "Wrong arc or wrong dimension");
1.541 + }
1.542 + }
1.543 +
1.544 + checkGraphConArcList(G, (1 << dim) * dim);
1.545 + checkGraphConEdgeList(G, dim * (1 << (dim-1)));
1.546 +
1.547 + checkArcDirections(G);
1.548 +
1.549 + checkNodeIds(G);
1.550 + checkArcIds(G);
1.551 + checkEdgeIds(G);
1.552 + checkGraphNodeMap(G);
1.553 + checkGraphArcMap(G);
1.554 + checkGraphEdgeMap(G);
1.555 +}
1.556
1.557 void checkGraphs() {
1.558 { // Checking ListGraph
1.559 - checkGraph<ListGraph>();
1.560 + checkGraphBuild<ListGraph>();
1.561 + checkGraphAlter<ListGraph>();
1.562 + checkGraphErase<ListGraph>();
1.563 + checkGraphSnapshot<ListGraph>();
1.564 checkGraphValidityErase<ListGraph>();
1.565 }
1.566 { // Checking SmartGraph
1.567 - checkGraph<SmartGraph>();
1.568 + checkGraphBuild<SmartGraph>();
1.569 + checkGraphSnapshot<SmartGraph>();
1.570 checkGraphValidity<SmartGraph>();
1.571 }
1.572 -// { // Checking FullGraph
1.573 -// FullGraph g(5);
1.574 -// checkGraphNodeList(g, 5);
1.575 -// checkGraphEdgeList(g, 10);
1.576 -// }
1.577 -// { // Checking GridGraph
1.578 -// GridGraph g(5, 6);
1.579 -// checkGraphNodeList(g, 30);
1.580 -// checkGraphEdgeList(g, 49);
1.581 -// checkGridGraph(g, 5, 6);
1.582 -// }
1.583 + { // Checking FullGraph
1.584 + checkFullGraph(7);
1.585 + checkFullGraph(8);
1.586 + }
1.587 + { // Checking GridGraph
1.588 + checkGridGraph(5, 8);
1.589 + checkGridGraph(8, 5);
1.590 + checkGridGraph(5, 5);
1.591 + checkGridGraph(0, 0);
1.592 + checkGridGraph(1, 1);
1.593 + }
1.594 + { // Checking HypercubeGraph
1.595 + checkHypercubeGraph(1);
1.596 + checkHypercubeGraph(2);
1.597 + checkHypercubeGraph(3);
1.598 + checkHypercubeGraph(4);
1.599 + }
1.600 }
1.601
1.602 int main() {