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