[209] | 1 | /* -*- mode: C++; indent-tabs-mode: nil; -*- |
---|
[57] | 2 | * |
---|
[209] | 3 | * This file is a part of LEMON, a generic C++ optimization library. |
---|
[57] | 4 | * |
---|
[107] | 5 | * Copyright (C) 2003-2008 |
---|
[57] | 6 | * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport |
---|
| 7 | * (Egervary Research Group on Combinatorial Optimization, EGRES). |
---|
| 8 | * |
---|
| 9 | * Permission to use, modify and distribute this software is granted |
---|
| 10 | * provided that this copyright notice appears in all copies. For |
---|
| 11 | * precise terms see the accompanying LICENSE file. |
---|
| 12 | * |
---|
| 13 | * This software is provided "AS IS" with no warranty of any kind, |
---|
| 14 | * express or implied, and with no claim as to its suitability for any |
---|
| 15 | * purpose. |
---|
| 16 | * |
---|
| 17 | */ |
---|
| 18 | |
---|
| 19 | #include <lemon/concepts/graph.h> |
---|
| 20 | #include <lemon/list_graph.h> |
---|
[109] | 21 | #include <lemon/smart_graph.h> |
---|
[353] | 22 | #include <lemon/full_graph.h> |
---|
[334] | 23 | #include <lemon/grid_graph.h> |
---|
[365] | 24 | #include <lemon/hypercube_graph.h> |
---|
[57] | 25 | |
---|
| 26 | #include "test_tools.h" |
---|
[171] | 27 | #include "graph_test.h" |
---|
[57] | 28 | |
---|
| 29 | using namespace lemon; |
---|
| 30 | using namespace lemon::concepts; |
---|
| 31 | |
---|
[228] | 32 | template <class Graph> |
---|
[374] | 33 | void checkGraphBuild() { |
---|
[228] | 34 | TEMPLATE_GRAPH_TYPEDEFS(Graph); |
---|
| 35 | |
---|
| 36 | Graph G; |
---|
| 37 | checkGraphNodeList(G, 0); |
---|
| 38 | checkGraphEdgeList(G, 0); |
---|
[374] | 39 | checkGraphArcList(G, 0); |
---|
[228] | 40 | |
---|
| 41 | Node |
---|
| 42 | n1 = G.addNode(), |
---|
| 43 | n2 = G.addNode(), |
---|
| 44 | n3 = G.addNode(); |
---|
| 45 | checkGraphNodeList(G, 3); |
---|
| 46 | checkGraphEdgeList(G, 0); |
---|
[374] | 47 | checkGraphArcList(G, 0); |
---|
[228] | 48 | |
---|
| 49 | Edge e1 = G.addEdge(n1, n2); |
---|
| 50 | check((G.u(e1) == n1 && G.v(e1) == n2) || (G.u(e1) == n2 && G.v(e1) == n1), |
---|
| 51 | "Wrong edge"); |
---|
[374] | 52 | |
---|
[228] | 53 | checkGraphNodeList(G, 3); |
---|
[374] | 54 | checkGraphEdgeList(G, 1); |
---|
[228] | 55 | checkGraphArcList(G, 2); |
---|
| 56 | |
---|
[374] | 57 | checkGraphIncEdgeArcLists(G, n1, 1); |
---|
| 58 | checkGraphIncEdgeArcLists(G, n2, 1); |
---|
| 59 | checkGraphIncEdgeArcLists(G, n3, 0); |
---|
[228] | 60 | |
---|
[374] | 61 | checkGraphConEdgeList(G, 1); |
---|
| 62 | checkGraphConArcList(G, 2); |
---|
[228] | 63 | |
---|
[374] | 64 | Edge e2 = G.addEdge(n2, n1), |
---|
| 65 | e3 = G.addEdge(n2, n3); |
---|
[228] | 66 | |
---|
[374] | 67 | checkGraphNodeList(G, 3); |
---|
| 68 | checkGraphEdgeList(G, 3); |
---|
| 69 | checkGraphArcList(G, 6); |
---|
[228] | 70 | |
---|
[374] | 71 | checkGraphIncEdgeArcLists(G, n1, 2); |
---|
| 72 | checkGraphIncEdgeArcLists(G, n2, 3); |
---|
| 73 | checkGraphIncEdgeArcLists(G, n3, 1); |
---|
[228] | 74 | |
---|
[374] | 75 | checkGraphConEdgeList(G, 3); |
---|
[228] | 76 | checkGraphConArcList(G, 6); |
---|
| 77 | |
---|
| 78 | checkArcDirections(G); |
---|
| 79 | |
---|
| 80 | checkNodeIds(G); |
---|
| 81 | checkArcIds(G); |
---|
| 82 | checkEdgeIds(G); |
---|
| 83 | checkGraphNodeMap(G); |
---|
| 84 | checkGraphArcMap(G); |
---|
| 85 | checkGraphEdgeMap(G); |
---|
| 86 | } |
---|
| 87 | |
---|
[374] | 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 deletion |
---|
| 179 | 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 deletion |
---|
| 194 | 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 | |
---|
[353] | 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) { |
---|
[365] | 274 | checkGraphOutArcList(G, n, num - 1); |
---|
| 275 | checkGraphInArcList(G, n, num - 1); |
---|
| 276 | checkGraphIncEdgeList(G, n, num - 1); |
---|
[353] | 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 | |
---|
[365] | 291 | |
---|
[353] | 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 | |
---|
[228] | 312 | void checkConcepts() { |
---|
[171] | 313 | { // Checking graph components |
---|
[57] | 314 | checkConcept<BaseGraphComponent, BaseGraphComponent >(); |
---|
| 315 | |
---|
[209] | 316 | checkConcept<IDableGraphComponent<>, |
---|
[57] | 317 | IDableGraphComponent<> >(); |
---|
| 318 | |
---|
[209] | 319 | checkConcept<IterableGraphComponent<>, |
---|
[57] | 320 | IterableGraphComponent<> >(); |
---|
| 321 | |
---|
[209] | 322 | checkConcept<MappableGraphComponent<>, |
---|
[57] | 323 | MappableGraphComponent<> >(); |
---|
| 324 | } |
---|
[171] | 325 | { // Checking skeleton graph |
---|
| 326 | checkConcept<Graph, Graph>(); |
---|
[57] | 327 | } |
---|
[171] | 328 | { // Checking ListGraph |
---|
| 329 | checkConcept<Graph, ListGraph>(); |
---|
| 330 | checkConcept<AlterableGraphComponent<>, ListGraph>(); |
---|
| 331 | checkConcept<ExtendableGraphComponent<>, ListGraph>(); |
---|
| 332 | checkConcept<ClearableGraphComponent<>, ListGraph>(); |
---|
| 333 | checkConcept<ErasableGraphComponent<>, ListGraph>(); |
---|
| 334 | } |
---|
| 335 | { // Checking SmartGraph |
---|
| 336 | checkConcept<Graph, SmartGraph>(); |
---|
| 337 | checkConcept<AlterableGraphComponent<>, SmartGraph>(); |
---|
| 338 | checkConcept<ExtendableGraphComponent<>, SmartGraph>(); |
---|
| 339 | checkConcept<ClearableGraphComponent<>, SmartGraph>(); |
---|
| 340 | } |
---|
[353] | 341 | { // Checking FullGraph |
---|
| 342 | checkConcept<Graph, FullGraph>(); |
---|
| 343 | } |
---|
[334] | 344 | { // Checking GridGraph |
---|
| 345 | checkConcept<Graph, GridGraph>(); |
---|
| 346 | } |
---|
[365] | 347 | { // Checking HypercubeGraph |
---|
| 348 | checkConcept<Graph, HypercubeGraph>(); |
---|
| 349 | } |
---|
[57] | 350 | } |
---|
| 351 | |
---|
| 352 | template <typename Graph> |
---|
[228] | 353 | void checkGraphValidity() { |
---|
[149] | 354 | TEMPLATE_GRAPH_TYPEDEFS(Graph); |
---|
[57] | 355 | Graph g; |
---|
| 356 | |
---|
| 357 | Node |
---|
| 358 | n1 = g.addNode(), |
---|
| 359 | n2 = g.addNode(), |
---|
| 360 | n3 = g.addNode(); |
---|
| 361 | |
---|
| 362 | Edge |
---|
| 363 | e1 = g.addEdge(n1, n2), |
---|
| 364 | e2 = g.addEdge(n2, n3); |
---|
| 365 | |
---|
[171] | 366 | check(g.valid(n1), "Wrong validity check"); |
---|
| 367 | check(g.valid(e1), "Wrong validity check"); |
---|
| 368 | check(g.valid(g.direct(e1, true)), "Wrong validity check"); |
---|
| 369 | |
---|
| 370 | check(!g.valid(g.nodeFromId(-1)), "Wrong validity check"); |
---|
| 371 | check(!g.valid(g.edgeFromId(-1)), "Wrong validity check"); |
---|
| 372 | check(!g.valid(g.arcFromId(-1)), "Wrong validity check"); |
---|
[57] | 373 | } |
---|
| 374 | |
---|
[149] | 375 | template <typename Graph> |
---|
[228] | 376 | void checkGraphValidityErase() { |
---|
[149] | 377 | TEMPLATE_GRAPH_TYPEDEFS(Graph); |
---|
| 378 | Graph g; |
---|
| 379 | |
---|
| 380 | Node |
---|
| 381 | n1 = g.addNode(), |
---|
| 382 | n2 = g.addNode(), |
---|
| 383 | n3 = g.addNode(); |
---|
| 384 | |
---|
| 385 | Edge |
---|
| 386 | e1 = g.addEdge(n1, n2), |
---|
| 387 | e2 = g.addEdge(n2, n3); |
---|
| 388 | |
---|
[171] | 389 | check(g.valid(n1), "Wrong validity check"); |
---|
| 390 | check(g.valid(e1), "Wrong validity check"); |
---|
| 391 | check(g.valid(g.direct(e1, true)), "Wrong validity check"); |
---|
[149] | 392 | |
---|
| 393 | g.erase(n1); |
---|
| 394 | |
---|
[171] | 395 | check(!g.valid(n1), "Wrong validity check"); |
---|
| 396 | check(g.valid(n2), "Wrong validity check"); |
---|
| 397 | check(g.valid(n3), "Wrong validity check"); |
---|
| 398 | check(!g.valid(e1), "Wrong validity check"); |
---|
| 399 | check(g.valid(e2), "Wrong validity check"); |
---|
[149] | 400 | |
---|
[171] | 401 | check(!g.valid(g.nodeFromId(-1)), "Wrong validity check"); |
---|
| 402 | check(!g.valid(g.edgeFromId(-1)), "Wrong validity check"); |
---|
| 403 | check(!g.valid(g.arcFromId(-1)), "Wrong validity check"); |
---|
[149] | 404 | } |
---|
| 405 | |
---|
[335] | 406 | void checkGridGraph(int width, int height) { |
---|
| 407 | typedef GridGraph Graph; |
---|
| 408 | GRAPH_TYPEDEFS(Graph); |
---|
| 409 | Graph G(width, height); |
---|
[57] | 410 | |
---|
[336] | 411 | check(G.width() == width, "Wrong column number"); |
---|
| 412 | check(G.height() == height, "Wrong row number"); |
---|
[209] | 413 | |
---|
[335] | 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"); |
---|
[334] | 420 | } |
---|
| 421 | } |
---|
[57] | 422 | |
---|
[335] | 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"); |
---|
[334] | 427 | } |
---|
[335] | 428 | check(G.right(G(width - 1, j)) == INVALID, "Wrong right"); |
---|
[334] | 429 | } |
---|
[57] | 430 | |
---|
[335] | 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"); |
---|
[334] | 435 | } |
---|
[335] | 436 | check(G.left(G(0, j)) == INVALID, "Wrong left"); |
---|
[334] | 437 | } |
---|
[57] | 438 | |
---|
[335] | 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"); |
---|
[334] | 443 | } |
---|
[335] | 444 | check(G.up(G(i, height - 1)) == INVALID, "Wrong up"); |
---|
[334] | 445 | } |
---|
[228] | 446 | |
---|
[335] | 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"); |
---|
[334] | 451 | } |
---|
[335] | 452 | check(G.down(G(i, 0)) == INVALID, "Wrong down"); |
---|
[334] | 453 | } |
---|
| 454 | |
---|
[335] | 455 | checkGraphNodeList(G, width * height); |
---|
| 456 | checkGraphEdgeList(G, width * (height - 1) + (width - 1) * height); |
---|
| 457 | checkGraphArcList(G, 2 * (width * (height - 1) + (width - 1) * height)); |
---|
[334] | 458 | |
---|
[335] | 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; |
---|
[334] | 465 | |
---|
[335] | 466 | checkGraphOutArcList(G, n, nb); |
---|
| 467 | checkGraphInArcList(G, n, nb); |
---|
| 468 | checkGraphIncEdgeList(G, n, nb); |
---|
| 469 | } |
---|
[334] | 470 | |
---|
[335] | 471 | checkArcDirections(G); |
---|
[334] | 472 | |
---|
[335] | 473 | checkGraphConArcList(G, 2 * (width * (height - 1) + (width - 1) * height)); |
---|
| 474 | checkGraphConEdgeList(G, width * (height - 1) + (width - 1) * height); |
---|
[334] | 475 | |
---|
[335] | 476 | checkNodeIds(G); |
---|
| 477 | checkArcIds(G); |
---|
| 478 | checkEdgeIds(G); |
---|
| 479 | checkGraphNodeMap(G); |
---|
| 480 | checkGraphArcMap(G); |
---|
| 481 | checkGraphEdgeMap(G); |
---|
[334] | 482 | |
---|
| 483 | } |
---|
[228] | 484 | |
---|
[365] | 485 | void checkHypercubeGraph(int dim) { |
---|
| 486 | GRAPH_TYPEDEFS(HypercubeGraph); |
---|
| 487 | |
---|
| 488 | HypercubeGraph G(dim); |
---|
| 489 | checkGraphNodeList(G, 1 << dim); |
---|
[372] | 490 | checkGraphEdgeList(G, dim * (1 << (dim-1))); |
---|
[365] | 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 && |
---|
[372] | 499 | G.id(G.v(e)) == (G.id(n) ^ (1 << G.dimension(e)))) || |
---|
[365] | 500 | (G.v(e) == n && |
---|
[372] | 501 | G.id(G.u(e)) == (G.id(n) ^ (1 << G.dimension(e)))), |
---|
[365] | 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 && |
---|
[372] | 508 | G.id(G.target(a)) == (G.id(n) ^ (1 << G.dimension(a))), |
---|
[365] | 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 && |
---|
[372] | 515 | G.id(G.source(a)) == (G.id(n) ^ (1 << G.dimension(a))), |
---|
[365] | 516 | "Wrong arc or wrong dimension"); |
---|
| 517 | } |
---|
| 518 | } |
---|
| 519 | |
---|
| 520 | checkGraphConArcList(G, (1 << dim) * dim); |
---|
[372] | 521 | checkGraphConEdgeList(G, dim * (1 << (dim-1))); |
---|
[365] | 522 | |
---|
| 523 | checkArcDirections(G); |
---|
| 524 | |
---|
| 525 | checkNodeIds(G); |
---|
| 526 | checkArcIds(G); |
---|
| 527 | checkEdgeIds(G); |
---|
| 528 | checkGraphNodeMap(G); |
---|
| 529 | checkGraphArcMap(G); |
---|
| 530 | checkGraphEdgeMap(G); |
---|
| 531 | } |
---|
[57] | 532 | |
---|
[228] | 533 | void checkGraphs() { |
---|
[171] | 534 | { // Checking ListGraph |
---|
[374] | 535 | checkGraphBuild<ListGraph>(); |
---|
| 536 | checkGraphAlter<ListGraph>(); |
---|
| 537 | checkGraphErase<ListGraph>(); |
---|
| 538 | checkGraphSnapshot<ListGraph>(); |
---|
[228] | 539 | checkGraphValidityErase<ListGraph>(); |
---|
[171] | 540 | } |
---|
| 541 | { // Checking SmartGraph |
---|
[374] | 542 | checkGraphBuild<SmartGraph>(); |
---|
| 543 | checkGraphSnapshot<SmartGraph>(); |
---|
[228] | 544 | checkGraphValidity<SmartGraph>(); |
---|
[171] | 545 | } |
---|
[365] | 546 | { // Checking FullGraph |
---|
[353] | 547 | checkFullGraph(7); |
---|
| 548 | checkFullGraph(8); |
---|
| 549 | } |
---|
[334] | 550 | { // Checking GridGraph |
---|
[335] | 551 | checkGridGraph(5, 8); |
---|
| 552 | checkGridGraph(8, 5); |
---|
| 553 | checkGridGraph(5, 5); |
---|
| 554 | checkGridGraph(0, 0); |
---|
| 555 | checkGridGraph(1, 1); |
---|
[334] | 556 | } |
---|
[365] | 557 | { // Checking HypercubeGraph |
---|
| 558 | checkHypercubeGraph(1); |
---|
| 559 | checkHypercubeGraph(2); |
---|
| 560 | checkHypercubeGraph(3); |
---|
| 561 | checkHypercubeGraph(4); |
---|
| 562 | } |
---|
[171] | 563 | } |
---|
| 564 | |
---|
[57] | 565 | int main() { |
---|
[228] | 566 | checkConcepts(); |
---|
| 567 | checkGraphs(); |
---|
[57] | 568 | return 0; |
---|
| 569 | } |
---|