test/graph_test.cc
author Balazs Dezso <deba@inf.elte.hu>
Mon, 01 Dec 2008 23:12:16 +0100
changeset 409 b8ce15103485
parent 372 7b6466ed488a
parent 374 49d9a36b3b84
child 440 88ed40ad0d4f
permissions -rw-r--r--
Port Hao-Orlin algorithm from SVN -r3509 (#58)
alpar@209
     1
/* -*- mode: C++; indent-tabs-mode: nil; -*-
deba@57
     2
 *
alpar@209
     3
 * This file is a part of LEMON, a generic C++ optimization library.
deba@57
     4
 *
alpar@107
     5
 * Copyright (C) 2003-2008
deba@57
     6
 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
deba@57
     7
 * (Egervary Research Group on Combinatorial Optimization, EGRES).
deba@57
     8
 *
deba@57
     9
 * Permission to use, modify and distribute this software is granted
deba@57
    10
 * provided that this copyright notice appears in all copies. For
deba@57
    11
 * precise terms see the accompanying LICENSE file.
deba@57
    12
 *
deba@57
    13
 * This software is provided "AS IS" with no warranty of any kind,
deba@57
    14
 * express or implied, and with no claim as to its suitability for any
deba@57
    15
 * purpose.
deba@57
    16
 *
deba@57
    17
 */
deba@57
    18
deba@57
    19
#include <lemon/concepts/graph.h>
deba@57
    20
#include <lemon/list_graph.h>
deba@109
    21
#include <lemon/smart_graph.h>
deba@353
    22
#include <lemon/full_graph.h>
kpeter@334
    23
#include <lemon/grid_graph.h>
kpeter@365
    24
#include <lemon/hypercube_graph.h>
deba@57
    25
deba@57
    26
#include "test_tools.h"
kpeter@171
    27
#include "graph_test.h"
deba@57
    28
deba@57
    29
using namespace lemon;
deba@57
    30
using namespace lemon::concepts;
deba@57
    31
deba@228
    32
template <class Graph>
kpeter@374
    33
void checkGraphBuild() {
deba@228
    34
  TEMPLATE_GRAPH_TYPEDEFS(Graph);
deba@228
    35
deba@228
    36
  Graph G;
deba@228
    37
  checkGraphNodeList(G, 0);
deba@228
    38
  checkGraphEdgeList(G, 0);
kpeter@374
    39
  checkGraphArcList(G, 0);
deba@228
    40
deba@228
    41
  Node
deba@228
    42
    n1 = G.addNode(),
deba@228
    43
    n2 = G.addNode(),
deba@228
    44
    n3 = G.addNode();
deba@228
    45
  checkGraphNodeList(G, 3);
deba@228
    46
  checkGraphEdgeList(G, 0);
kpeter@374
    47
  checkGraphArcList(G, 0);
deba@228
    48
deba@228
    49
  Edge e1 = G.addEdge(n1, n2);
deba@228
    50
  check((G.u(e1) == n1 && G.v(e1) == n2) || (G.u(e1) == n2 && G.v(e1) == n1),
deba@228
    51
        "Wrong edge");
kpeter@374
    52
deba@228
    53
  checkGraphNodeList(G, 3);
kpeter@374
    54
  checkGraphEdgeList(G, 1);
deba@228
    55
  checkGraphArcList(G, 2);
deba@228
    56
kpeter@374
    57
  checkGraphIncEdgeArcLists(G, n1, 1);
kpeter@374
    58
  checkGraphIncEdgeArcLists(G, n2, 1);
kpeter@374
    59
  checkGraphIncEdgeArcLists(G, n3, 0);
deba@228
    60
kpeter@374
    61
  checkGraphConEdgeList(G, 1);
kpeter@374
    62
  checkGraphConArcList(G, 2);
deba@228
    63
kpeter@374
    64
  Edge e2 = G.addEdge(n2, n1),
kpeter@374
    65
       e3 = G.addEdge(n2, n3);
deba@228
    66
kpeter@374
    67
  checkGraphNodeList(G, 3);
kpeter@374
    68
  checkGraphEdgeList(G, 3);
kpeter@374
    69
  checkGraphArcList(G, 6);
deba@228
    70
kpeter@374
    71
  checkGraphIncEdgeArcLists(G, n1, 2);
kpeter@374
    72
  checkGraphIncEdgeArcLists(G, n2, 3);
kpeter@374
    73
  checkGraphIncEdgeArcLists(G, n3, 1);
deba@228
    74
kpeter@374
    75
  checkGraphConEdgeList(G, 3);
deba@228
    76
  checkGraphConArcList(G, 6);
deba@228
    77
deba@228
    78
  checkArcDirections(G);
deba@228
    79
deba@228
    80
  checkNodeIds(G);
deba@228
    81
  checkArcIds(G);
deba@228
    82
  checkEdgeIds(G);
deba@228
    83
  checkGraphNodeMap(G);
deba@228
    84
  checkGraphArcMap(G);
deba@228
    85
  checkGraphEdgeMap(G);
deba@228
    86
}
deba@228
    87
kpeter@374
    88
template <class Graph>
kpeter@374
    89
void checkGraphAlter() {
kpeter@374
    90
  TEMPLATE_GRAPH_TYPEDEFS(Graph);
kpeter@374
    91
kpeter@374
    92
  Graph G;
kpeter@374
    93
  Node n1 = G.addNode(), n2 = G.addNode(),
kpeter@374
    94
       n3 = G.addNode(), n4 = G.addNode();
kpeter@374
    95
  Edge e1 = G.addEdge(n1, n2), e2 = G.addEdge(n2, n1),
kpeter@374
    96
       e3 = G.addEdge(n2, n3), e4 = G.addEdge(n1, n4),
kpeter@374
    97
       e5 = G.addEdge(n4, n3);
kpeter@374
    98
kpeter@374
    99
  checkGraphNodeList(G, 4);
kpeter@374
   100
  checkGraphEdgeList(G, 5);
kpeter@374
   101
  checkGraphArcList(G, 10);
kpeter@374
   102
kpeter@374
   103
  // Check changeU() and changeV()
kpeter@374
   104
  if (G.u(e2) == n2) {
kpeter@374
   105
    G.changeU(e2, n3);
kpeter@374
   106
  } else {
kpeter@374
   107
    G.changeV(e2, n3);
kpeter@374
   108
  }
kpeter@374
   109
kpeter@374
   110
  checkGraphNodeList(G, 4);
kpeter@374
   111
  checkGraphEdgeList(G, 5);
kpeter@374
   112
  checkGraphArcList(G, 10);
kpeter@374
   113
kpeter@374
   114
  checkGraphIncEdgeArcLists(G, n1, 3);
kpeter@374
   115
  checkGraphIncEdgeArcLists(G, n2, 2);
kpeter@374
   116
  checkGraphIncEdgeArcLists(G, n3, 3);
kpeter@374
   117
  checkGraphIncEdgeArcLists(G, n4, 2);
kpeter@374
   118
kpeter@374
   119
  checkGraphConEdgeList(G, 5);
kpeter@374
   120
  checkGraphConArcList(G, 10);
kpeter@374
   121
kpeter@374
   122
  if (G.u(e2) == n1) {
kpeter@374
   123
    G.changeU(e2, n2);
kpeter@374
   124
  } else {
kpeter@374
   125
    G.changeV(e2, n2);
kpeter@374
   126
  }
kpeter@374
   127
kpeter@374
   128
  checkGraphNodeList(G, 4);
kpeter@374
   129
  checkGraphEdgeList(G, 5);
kpeter@374
   130
  checkGraphArcList(G, 10);
kpeter@374
   131
kpeter@374
   132
  checkGraphIncEdgeArcLists(G, n1, 2);
kpeter@374
   133
  checkGraphIncEdgeArcLists(G, n2, 3);
kpeter@374
   134
  checkGraphIncEdgeArcLists(G, n3, 3);
kpeter@374
   135
  checkGraphIncEdgeArcLists(G, n4, 2);
kpeter@374
   136
kpeter@374
   137
  checkGraphConEdgeList(G, 5);
kpeter@374
   138
  checkGraphConArcList(G, 10);
kpeter@374
   139
kpeter@374
   140
  // Check contract()
kpeter@374
   141
  G.contract(n1, n4, false);
kpeter@374
   142
kpeter@374
   143
  checkGraphNodeList(G, 3);
kpeter@374
   144
  checkGraphEdgeList(G, 5);
kpeter@374
   145
  checkGraphArcList(G, 10);
kpeter@374
   146
kpeter@374
   147
  checkGraphIncEdgeArcLists(G, n1, 4);
kpeter@374
   148
  checkGraphIncEdgeArcLists(G, n2, 3);
kpeter@374
   149
  checkGraphIncEdgeArcLists(G, n3, 3);
kpeter@374
   150
kpeter@374
   151
  checkGraphConEdgeList(G, 5);
kpeter@374
   152
  checkGraphConArcList(G, 10);
kpeter@374
   153
kpeter@374
   154
  G.contract(n2, n3);
kpeter@374
   155
kpeter@374
   156
  checkGraphNodeList(G, 2);
kpeter@374
   157
  checkGraphEdgeList(G, 3);
kpeter@374
   158
  checkGraphArcList(G, 6);
kpeter@374
   159
kpeter@374
   160
  checkGraphIncEdgeArcLists(G, n1, 4);
kpeter@374
   161
  checkGraphIncEdgeArcLists(G, n2, 2);
kpeter@374
   162
kpeter@374
   163
  checkGraphConEdgeList(G, 3);
kpeter@374
   164
  checkGraphConArcList(G, 6);
kpeter@374
   165
}
kpeter@374
   166
kpeter@374
   167
template <class Graph>
kpeter@374
   168
void checkGraphErase() {
kpeter@374
   169
  TEMPLATE_GRAPH_TYPEDEFS(Graph);
kpeter@374
   170
kpeter@374
   171
  Graph G;
kpeter@374
   172
  Node n1 = G.addNode(), n2 = G.addNode(),
kpeter@374
   173
       n3 = G.addNode(), n4 = G.addNode();
kpeter@374
   174
  Edge e1 = G.addEdge(n1, n2), e2 = G.addEdge(n2, n1),
kpeter@374
   175
       e3 = G.addEdge(n2, n3), e4 = G.addEdge(n1, n4),
kpeter@374
   176
       e5 = G.addEdge(n4, n3);
kpeter@374
   177
kpeter@374
   178
  // Check edge deletion
kpeter@374
   179
  G.erase(e2);
kpeter@374
   180
kpeter@374
   181
  checkGraphNodeList(G, 4);
kpeter@374
   182
  checkGraphEdgeList(G, 4);
kpeter@374
   183
  checkGraphArcList(G, 8);
kpeter@374
   184
kpeter@374
   185
  checkGraphIncEdgeArcLists(G, n1, 2);
kpeter@374
   186
  checkGraphIncEdgeArcLists(G, n2, 2);
kpeter@374
   187
  checkGraphIncEdgeArcLists(G, n3, 2);
kpeter@374
   188
  checkGraphIncEdgeArcLists(G, n4, 2);
kpeter@374
   189
kpeter@374
   190
  checkGraphConEdgeList(G, 4);
kpeter@374
   191
  checkGraphConArcList(G, 8);
kpeter@374
   192
kpeter@374
   193
  // Check node deletion
kpeter@374
   194
  G.erase(n3);
kpeter@374
   195
kpeter@374
   196
  checkGraphNodeList(G, 3);
kpeter@374
   197
  checkGraphEdgeList(G, 2);
kpeter@374
   198
  checkGraphArcList(G, 4);
kpeter@374
   199
kpeter@374
   200
  checkGraphIncEdgeArcLists(G, n1, 2);
kpeter@374
   201
  checkGraphIncEdgeArcLists(G, n2, 1);
kpeter@374
   202
  checkGraphIncEdgeArcLists(G, n4, 1);
kpeter@374
   203
kpeter@374
   204
  checkGraphConEdgeList(G, 2);
kpeter@374
   205
  checkGraphConArcList(G, 4);
kpeter@374
   206
}
kpeter@374
   207
kpeter@374
   208
kpeter@374
   209
template <class Graph>
kpeter@374
   210
void checkGraphSnapshot() {
kpeter@374
   211
  TEMPLATE_GRAPH_TYPEDEFS(Graph);
kpeter@374
   212
kpeter@374
   213
  Graph G;
kpeter@374
   214
  Node n1 = G.addNode(), n2 = G.addNode(), n3 = G.addNode();
kpeter@374
   215
  Edge e1 = G.addEdge(n1, n2), e2 = G.addEdge(n2, n1),
kpeter@374
   216
       e3 = G.addEdge(n2, n3);
kpeter@374
   217
kpeter@374
   218
  checkGraphNodeList(G, 3);
kpeter@374
   219
  checkGraphEdgeList(G, 3);
kpeter@374
   220
  checkGraphArcList(G, 6);
kpeter@374
   221
kpeter@374
   222
  typename Graph::Snapshot snapshot(G);
kpeter@374
   223
kpeter@374
   224
  Node n = G.addNode();
kpeter@374
   225
  G.addEdge(n3, n);
kpeter@374
   226
  G.addEdge(n, n3);
kpeter@374
   227
  G.addEdge(n3, n2);
kpeter@374
   228
kpeter@374
   229
  checkGraphNodeList(G, 4);
kpeter@374
   230
  checkGraphEdgeList(G, 6);
kpeter@374
   231
  checkGraphArcList(G, 12);
kpeter@374
   232
kpeter@374
   233
  snapshot.restore();
kpeter@374
   234
kpeter@374
   235
  checkGraphNodeList(G, 3);
kpeter@374
   236
  checkGraphEdgeList(G, 3);
kpeter@374
   237
  checkGraphArcList(G, 6);
kpeter@374
   238
kpeter@374
   239
  checkGraphIncEdgeArcLists(G, n1, 2);
kpeter@374
   240
  checkGraphIncEdgeArcLists(G, n2, 3);
kpeter@374
   241
  checkGraphIncEdgeArcLists(G, n3, 1);
kpeter@374
   242
kpeter@374
   243
  checkGraphConEdgeList(G, 3);
kpeter@374
   244
  checkGraphConArcList(G, 6);
kpeter@374
   245
kpeter@374
   246
  checkNodeIds(G);
kpeter@374
   247
  checkEdgeIds(G);
kpeter@374
   248
  checkArcIds(G);
kpeter@374
   249
  checkGraphNodeMap(G);
kpeter@374
   250
  checkGraphEdgeMap(G);
kpeter@374
   251
  checkGraphArcMap(G);
kpeter@374
   252
kpeter@374
   253
  G.addNode();
kpeter@374
   254
  snapshot.save(G);
kpeter@374
   255
kpeter@374
   256
  G.addEdge(G.addNode(), G.addNode());
kpeter@374
   257
kpeter@374
   258
  snapshot.restore();
kpeter@374
   259
kpeter@374
   260
  checkGraphNodeList(G, 4);
kpeter@374
   261
  checkGraphEdgeList(G, 3);
kpeter@374
   262
  checkGraphArcList(G, 6);
kpeter@374
   263
}
kpeter@374
   264
deba@353
   265
void checkFullGraph(int num) {
deba@353
   266
  typedef FullGraph Graph;
deba@353
   267
  GRAPH_TYPEDEFS(Graph);
deba@353
   268
deba@353
   269
  Graph G(num);
deba@353
   270
  checkGraphNodeList(G, num);
deba@353
   271
  checkGraphEdgeList(G, num * (num - 1) / 2);
deba@353
   272
deba@353
   273
  for (NodeIt n(G); n != INVALID; ++n) {
kpeter@365
   274
    checkGraphOutArcList(G, n, num - 1);
kpeter@365
   275
    checkGraphInArcList(G, n, num - 1);
kpeter@365
   276
    checkGraphIncEdgeList(G, n, num - 1);
deba@353
   277
  }
deba@353
   278
deba@353
   279
  checkGraphConArcList(G, num * (num - 1));
deba@353
   280
  checkGraphConEdgeList(G, num * (num - 1) / 2);
deba@353
   281
deba@353
   282
  checkArcDirections(G);
deba@353
   283
deba@353
   284
  checkNodeIds(G);
deba@353
   285
  checkArcIds(G);
deba@353
   286
  checkEdgeIds(G);
deba@353
   287
  checkGraphNodeMap(G);
deba@353
   288
  checkGraphArcMap(G);
deba@353
   289
  checkGraphEdgeMap(G);
deba@353
   290
kpeter@365
   291
deba@353
   292
  for (int i = 0; i < G.nodeNum(); ++i) {
deba@353
   293
    check(G.index(G(i)) == i, "Wrong index");
deba@353
   294
  }
deba@353
   295
deba@353
   296
  for (NodeIt u(G); u != INVALID; ++u) {
deba@353
   297
    for (NodeIt v(G); v != INVALID; ++v) {
deba@353
   298
      Edge e = G.edge(u, v);
deba@353
   299
      Arc a = G.arc(u, v);
deba@353
   300
      if (u == v) {
deba@353
   301
        check(e == INVALID, "Wrong edge lookup");
deba@353
   302
        check(a == INVALID, "Wrong arc lookup");
deba@353
   303
      } else {
deba@353
   304
        check((G.u(e) == u && G.v(e) == v) ||
deba@353
   305
              (G.u(e) == v && G.v(e) == u), "Wrong edge lookup");
deba@353
   306
        check(G.source(a) == u && G.target(a) == v, "Wrong arc lookup");
deba@353
   307
      }
deba@353
   308
    }
deba@353
   309
  }
deba@353
   310
}
deba@353
   311
deba@228
   312
void checkConcepts() {
kpeter@171
   313
  { // Checking graph components
deba@57
   314
    checkConcept<BaseGraphComponent, BaseGraphComponent >();
deba@57
   315
alpar@209
   316
    checkConcept<IDableGraphComponent<>,
deba@57
   317
      IDableGraphComponent<> >();
deba@57
   318
alpar@209
   319
    checkConcept<IterableGraphComponent<>,
deba@57
   320
      IterableGraphComponent<> >();
deba@57
   321
alpar@209
   322
    checkConcept<MappableGraphComponent<>,
deba@57
   323
      MappableGraphComponent<> >();
deba@57
   324
  }
kpeter@171
   325
  { // Checking skeleton graph
kpeter@171
   326
    checkConcept<Graph, Graph>();
deba@57
   327
  }
kpeter@171
   328
  { // Checking ListGraph
kpeter@171
   329
    checkConcept<Graph, ListGraph>();
kpeter@171
   330
    checkConcept<AlterableGraphComponent<>, ListGraph>();
kpeter@171
   331
    checkConcept<ExtendableGraphComponent<>, ListGraph>();
kpeter@171
   332
    checkConcept<ClearableGraphComponent<>, ListGraph>();
kpeter@171
   333
    checkConcept<ErasableGraphComponent<>, ListGraph>();
kpeter@171
   334
  }
kpeter@171
   335
  { // Checking SmartGraph
kpeter@171
   336
    checkConcept<Graph, SmartGraph>();
kpeter@171
   337
    checkConcept<AlterableGraphComponent<>, SmartGraph>();
kpeter@171
   338
    checkConcept<ExtendableGraphComponent<>, SmartGraph>();
kpeter@171
   339
    checkConcept<ClearableGraphComponent<>, SmartGraph>();
kpeter@171
   340
  }
deba@353
   341
  { // Checking FullGraph
deba@353
   342
    checkConcept<Graph, FullGraph>();
deba@353
   343
  }
kpeter@334
   344
  { // Checking GridGraph
kpeter@334
   345
    checkConcept<Graph, GridGraph>();
kpeter@334
   346
  }
kpeter@365
   347
  { // Checking HypercubeGraph
kpeter@365
   348
    checkConcept<Graph, HypercubeGraph>();
kpeter@365
   349
  }
deba@57
   350
}
deba@57
   351
deba@57
   352
template <typename Graph>
deba@228
   353
void checkGraphValidity() {
deba@149
   354
  TEMPLATE_GRAPH_TYPEDEFS(Graph);
deba@57
   355
  Graph g;
deba@57
   356
deba@57
   357
  Node
deba@57
   358
    n1 = g.addNode(),
deba@57
   359
    n2 = g.addNode(),
deba@57
   360
    n3 = g.addNode();
deba@57
   361
deba@57
   362
  Edge
deba@57
   363
    e1 = g.addEdge(n1, n2),
deba@57
   364
    e2 = g.addEdge(n2, n3);
deba@57
   365
kpeter@171
   366
  check(g.valid(n1), "Wrong validity check");
kpeter@171
   367
  check(g.valid(e1), "Wrong validity check");
kpeter@171
   368
  check(g.valid(g.direct(e1, true)), "Wrong validity check");
kpeter@171
   369
kpeter@171
   370
  check(!g.valid(g.nodeFromId(-1)), "Wrong validity check");
kpeter@171
   371
  check(!g.valid(g.edgeFromId(-1)), "Wrong validity check");
kpeter@171
   372
  check(!g.valid(g.arcFromId(-1)), "Wrong validity check");
deba@57
   373
}
deba@57
   374
deba@149
   375
template <typename Graph>
deba@228
   376
void checkGraphValidityErase() {
deba@149
   377
  TEMPLATE_GRAPH_TYPEDEFS(Graph);
deba@149
   378
  Graph g;
deba@149
   379
deba@149
   380
  Node
deba@149
   381
    n1 = g.addNode(),
deba@149
   382
    n2 = g.addNode(),
deba@149
   383
    n3 = g.addNode();
deba@149
   384
deba@149
   385
  Edge
deba@149
   386
    e1 = g.addEdge(n1, n2),
deba@149
   387
    e2 = g.addEdge(n2, n3);
deba@149
   388
kpeter@171
   389
  check(g.valid(n1), "Wrong validity check");
kpeter@171
   390
  check(g.valid(e1), "Wrong validity check");
kpeter@171
   391
  check(g.valid(g.direct(e1, true)), "Wrong validity check");
deba@149
   392
deba@149
   393
  g.erase(n1);
deba@149
   394
kpeter@171
   395
  check(!g.valid(n1), "Wrong validity check");
kpeter@171
   396
  check(g.valid(n2), "Wrong validity check");
kpeter@171
   397
  check(g.valid(n3), "Wrong validity check");
kpeter@171
   398
  check(!g.valid(e1), "Wrong validity check");
kpeter@171
   399
  check(g.valid(e2), "Wrong validity check");
deba@149
   400
kpeter@171
   401
  check(!g.valid(g.nodeFromId(-1)), "Wrong validity check");
kpeter@171
   402
  check(!g.valid(g.edgeFromId(-1)), "Wrong validity check");
kpeter@171
   403
  check(!g.valid(g.arcFromId(-1)), "Wrong validity check");
deba@149
   404
}
deba@149
   405
deba@335
   406
void checkGridGraph(int width, int height) {
deba@335
   407
  typedef GridGraph Graph;
deba@335
   408
  GRAPH_TYPEDEFS(Graph);
deba@335
   409
  Graph G(width, height);
deba@57
   410
kpeter@336
   411
  check(G.width() == width, "Wrong column number");
kpeter@336
   412
  check(G.height() == height, "Wrong row number");
alpar@209
   413
deba@335
   414
  for (int i = 0; i < width; ++i) {
deba@335
   415
    for (int j = 0; j < height; ++j) {
deba@335
   416
      check(G.col(G(i, j)) == i, "Wrong column");
deba@335
   417
      check(G.row(G(i, j)) == j, "Wrong row");
deba@335
   418
      check(G.pos(G(i, j)).x == i, "Wrong column");
deba@335
   419
      check(G.pos(G(i, j)).y == j, "Wrong row");
kpeter@334
   420
    }
kpeter@334
   421
  }
deba@57
   422
deba@335
   423
  for (int j = 0; j < height; ++j) {
deba@335
   424
    for (int i = 0; i < width - 1; ++i) {
deba@335
   425
      check(G.source(G.right(G(i, j))) == G(i, j), "Wrong right");
deba@335
   426
      check(G.target(G.right(G(i, j))) == G(i + 1, j), "Wrong right");
kpeter@334
   427
    }
deba@335
   428
    check(G.right(G(width - 1, j)) == INVALID, "Wrong right");
kpeter@334
   429
  }
deba@57
   430
deba@335
   431
  for (int j = 0; j < height; ++j) {
deba@335
   432
    for (int i = 1; i < width; ++i) {
deba@335
   433
      check(G.source(G.left(G(i, j))) == G(i, j), "Wrong left");
deba@335
   434
      check(G.target(G.left(G(i, j))) == G(i - 1, j), "Wrong left");
kpeter@334
   435
    }
deba@335
   436
    check(G.left(G(0, j)) == INVALID, "Wrong left");
kpeter@334
   437
  }
deba@57
   438
deba@335
   439
  for (int i = 0; i < width; ++i) {
deba@335
   440
    for (int j = 0; j < height - 1; ++j) {
deba@335
   441
      check(G.source(G.up(G(i, j))) == G(i, j), "Wrong up");
deba@335
   442
      check(G.target(G.up(G(i, j))) == G(i, j + 1), "Wrong up");
kpeter@334
   443
    }
deba@335
   444
    check(G.up(G(i, height - 1)) == INVALID, "Wrong up");
kpeter@334
   445
  }
deba@228
   446
deba@335
   447
  for (int i = 0; i < width; ++i) {
deba@335
   448
    for (int j = 1; j < height; ++j) {
deba@335
   449
      check(G.source(G.down(G(i, j))) == G(i, j), "Wrong down");
deba@335
   450
      check(G.target(G.down(G(i, j))) == G(i, j - 1), "Wrong down");
kpeter@334
   451
    }
deba@335
   452
    check(G.down(G(i, 0)) == INVALID, "Wrong down");
kpeter@334
   453
  }
kpeter@334
   454
deba@335
   455
  checkGraphNodeList(G, width * height);
deba@335
   456
  checkGraphEdgeList(G, width * (height - 1) + (width - 1) * height);
deba@335
   457
  checkGraphArcList(G, 2 * (width * (height - 1) + (width - 1) * height));
kpeter@334
   458
deba@335
   459
  for (NodeIt n(G); n != INVALID; ++n) {
deba@335
   460
    int nb = 4;
deba@335
   461
    if (G.col(n) == 0) --nb;
deba@335
   462
    if (G.col(n) == width - 1) --nb;
deba@335
   463
    if (G.row(n) == 0) --nb;
deba@335
   464
    if (G.row(n) == height - 1) --nb;
kpeter@334
   465
deba@335
   466
    checkGraphOutArcList(G, n, nb);
deba@335
   467
    checkGraphInArcList(G, n, nb);
deba@335
   468
    checkGraphIncEdgeList(G, n, nb);
deba@335
   469
  }
kpeter@334
   470
deba@335
   471
  checkArcDirections(G);
kpeter@334
   472
deba@335
   473
  checkGraphConArcList(G, 2 * (width * (height - 1) + (width - 1) * height));
deba@335
   474
  checkGraphConEdgeList(G, width * (height - 1) + (width - 1) * height);
kpeter@334
   475
deba@335
   476
  checkNodeIds(G);
deba@335
   477
  checkArcIds(G);
deba@335
   478
  checkEdgeIds(G);
deba@335
   479
  checkGraphNodeMap(G);
deba@335
   480
  checkGraphArcMap(G);
deba@335
   481
  checkGraphEdgeMap(G);
kpeter@334
   482
kpeter@334
   483
}
deba@228
   484
kpeter@365
   485
void checkHypercubeGraph(int dim) {
kpeter@365
   486
  GRAPH_TYPEDEFS(HypercubeGraph);
kpeter@365
   487
kpeter@365
   488
  HypercubeGraph G(dim);
kpeter@365
   489
  checkGraphNodeList(G, 1 << dim);
alpar@372
   490
  checkGraphEdgeList(G, dim * (1 << (dim-1)));
kpeter@365
   491
  checkGraphArcList(G, dim * (1 << dim));
kpeter@365
   492
kpeter@365
   493
  Node n = G.nodeFromId(dim);
kpeter@365
   494
kpeter@365
   495
  for (NodeIt n(G); n != INVALID; ++n) {
kpeter@365
   496
    checkGraphIncEdgeList(G, n, dim);
kpeter@365
   497
    for (IncEdgeIt e(G, n); e != INVALID; ++e) {
kpeter@365
   498
      check( (G.u(e) == n &&
alpar@372
   499
              G.id(G.v(e)) == (G.id(n) ^ (1 << G.dimension(e)))) ||
kpeter@365
   500
             (G.v(e) == n &&
alpar@372
   501
              G.id(G.u(e)) == (G.id(n) ^ (1 << G.dimension(e)))),
kpeter@365
   502
             "Wrong edge or wrong dimension");
kpeter@365
   503
    }
kpeter@365
   504
kpeter@365
   505
    checkGraphOutArcList(G, n, dim);
kpeter@365
   506
    for (OutArcIt a(G, n); a != INVALID; ++a) {
kpeter@365
   507
      check(G.source(a) == n &&
alpar@372
   508
            G.id(G.target(a)) == (G.id(n) ^ (1 << G.dimension(a))),
kpeter@365
   509
            "Wrong arc or wrong dimension");
kpeter@365
   510
    }
kpeter@365
   511
kpeter@365
   512
    checkGraphInArcList(G, n, dim);
kpeter@365
   513
    for (InArcIt a(G, n); a != INVALID; ++a) {
kpeter@365
   514
      check(G.target(a) == n &&
alpar@372
   515
            G.id(G.source(a)) == (G.id(n) ^ (1 << G.dimension(a))),
kpeter@365
   516
            "Wrong arc or wrong dimension");
kpeter@365
   517
    }
kpeter@365
   518
  }
kpeter@365
   519
kpeter@365
   520
  checkGraphConArcList(G, (1 << dim) * dim);
alpar@372
   521
  checkGraphConEdgeList(G, dim * (1 << (dim-1)));
kpeter@365
   522
kpeter@365
   523
  checkArcDirections(G);
kpeter@365
   524
kpeter@365
   525
  checkNodeIds(G);
kpeter@365
   526
  checkArcIds(G);
kpeter@365
   527
  checkEdgeIds(G);
kpeter@365
   528
  checkGraphNodeMap(G);
kpeter@365
   529
  checkGraphArcMap(G);
kpeter@365
   530
  checkGraphEdgeMap(G);
kpeter@365
   531
}
deba@57
   532
deba@228
   533
void checkGraphs() {
kpeter@171
   534
  { // Checking ListGraph
kpeter@374
   535
    checkGraphBuild<ListGraph>();
kpeter@374
   536
    checkGraphAlter<ListGraph>();
kpeter@374
   537
    checkGraphErase<ListGraph>();
kpeter@374
   538
    checkGraphSnapshot<ListGraph>();
deba@228
   539
    checkGraphValidityErase<ListGraph>();
kpeter@171
   540
  }
kpeter@171
   541
  { // Checking SmartGraph
kpeter@374
   542
    checkGraphBuild<SmartGraph>();
kpeter@374
   543
    checkGraphSnapshot<SmartGraph>();
deba@228
   544
    checkGraphValidity<SmartGraph>();
kpeter@171
   545
  }
kpeter@365
   546
  { // Checking FullGraph
deba@353
   547
    checkFullGraph(7);
deba@353
   548
    checkFullGraph(8);
deba@353
   549
  }
kpeter@334
   550
  { // Checking GridGraph
deba@335
   551
    checkGridGraph(5, 8);
deba@335
   552
    checkGridGraph(8, 5);
deba@335
   553
    checkGridGraph(5, 5);
deba@335
   554
    checkGridGraph(0, 0);
deba@335
   555
    checkGridGraph(1, 1);
kpeter@334
   556
  }
kpeter@365
   557
  { // Checking HypercubeGraph
kpeter@365
   558
    checkHypercubeGraph(1);
kpeter@365
   559
    checkHypercubeGraph(2);
kpeter@365
   560
    checkHypercubeGraph(3);
kpeter@365
   561
    checkHypercubeGraph(4);
kpeter@365
   562
  }
kpeter@171
   563
}
kpeter@171
   564
deba@57
   565
int main() {
deba@228
   566
  checkConcepts();
deba@228
   567
  checkGraphs();
deba@57
   568
  return 0;
deba@57
   569
}