test/graph_test.cc
author Alpar Juttner <alpar@cs.elte.hu>
Mon, 12 Oct 2009 17:02:03 +0100
changeset 753 48fe2a46bf91
parent 737 9d6c3e8b2421
child 877 141f9c0db4a3
permissions -rw-r--r--
Merge bugfix #322
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@740
   262
  snapshot.save(G);
kpeter@740
   263
kpeter@740
   264
  checkGraphNodeList(G, 4);
kpeter@740
   265
  checkGraphEdgeList(G, 3);
kpeter@740
   266
  checkGraphArcList(G, 6);
kpeter@740
   267
  
kpeter@740
   268
  G.addEdge(G.addNode(), G.addNode());
kpeter@740
   269
kpeter@740
   270
  snapshot.restore();
kpeter@374
   271
kpeter@374
   272
  checkGraphNodeList(G, 4);
kpeter@374
   273
  checkGraphEdgeList(G, 3);
kpeter@374
   274
  checkGraphArcList(G, 6);
kpeter@374
   275
}
kpeter@374
   276
deba@353
   277
void checkFullGraph(int num) {
deba@353
   278
  typedef FullGraph Graph;
deba@353
   279
  GRAPH_TYPEDEFS(Graph);
deba@353
   280
deba@353
   281
  Graph G(num);
kpeter@737
   282
  check(G.nodeNum() == num && G.edgeNum() == num * (num - 1) / 2,
kpeter@737
   283
        "Wrong size");
kpeter@737
   284
kpeter@737
   285
  G.resize(num);
kpeter@737
   286
  check(G.nodeNum() == num && G.edgeNum() == num * (num - 1) / 2,
kpeter@737
   287
        "Wrong size");
kpeter@737
   288
deba@353
   289
  checkGraphNodeList(G, num);
deba@353
   290
  checkGraphEdgeList(G, num * (num - 1) / 2);
deba@353
   291
deba@353
   292
  for (NodeIt n(G); n != INVALID; ++n) {
kpeter@365
   293
    checkGraphOutArcList(G, n, num - 1);
kpeter@365
   294
    checkGraphInArcList(G, n, num - 1);
kpeter@365
   295
    checkGraphIncEdgeList(G, n, num - 1);
deba@353
   296
  }
deba@353
   297
deba@353
   298
  checkGraphConArcList(G, num * (num - 1));
deba@353
   299
  checkGraphConEdgeList(G, num * (num - 1) / 2);
deba@353
   300
deba@353
   301
  checkArcDirections(G);
deba@353
   302
deba@353
   303
  checkNodeIds(G);
deba@353
   304
  checkArcIds(G);
deba@353
   305
  checkEdgeIds(G);
deba@353
   306
  checkGraphNodeMap(G);
deba@353
   307
  checkGraphArcMap(G);
deba@353
   308
  checkGraphEdgeMap(G);
deba@353
   309
kpeter@365
   310
deba@353
   311
  for (int i = 0; i < G.nodeNum(); ++i) {
deba@353
   312
    check(G.index(G(i)) == i, "Wrong index");
deba@353
   313
  }
deba@353
   314
deba@353
   315
  for (NodeIt u(G); u != INVALID; ++u) {
deba@353
   316
    for (NodeIt v(G); v != INVALID; ++v) {
deba@353
   317
      Edge e = G.edge(u, v);
deba@353
   318
      Arc a = G.arc(u, v);
deba@353
   319
      if (u == v) {
deba@353
   320
        check(e == INVALID, "Wrong edge lookup");
deba@353
   321
        check(a == INVALID, "Wrong arc lookup");
deba@353
   322
      } else {
deba@353
   323
        check((G.u(e) == u && G.v(e) == v) ||
deba@353
   324
              (G.u(e) == v && G.v(e) == u), "Wrong edge lookup");
deba@353
   325
        check(G.source(a) == u && G.target(a) == v, "Wrong arc lookup");
deba@353
   326
      }
deba@353
   327
    }
deba@353
   328
  }
deba@353
   329
}
deba@353
   330
deba@228
   331
void checkConcepts() {
kpeter@171
   332
  { // Checking graph components
deba@57
   333
    checkConcept<BaseGraphComponent, BaseGraphComponent >();
deba@57
   334
alpar@209
   335
    checkConcept<IDableGraphComponent<>,
deba@57
   336
      IDableGraphComponent<> >();
deba@57
   337
alpar@209
   338
    checkConcept<IterableGraphComponent<>,
deba@57
   339
      IterableGraphComponent<> >();
deba@57
   340
alpar@209
   341
    checkConcept<MappableGraphComponent<>,
deba@57
   342
      MappableGraphComponent<> >();
deba@57
   343
  }
kpeter@171
   344
  { // Checking skeleton graph
kpeter@171
   345
    checkConcept<Graph, Graph>();
deba@57
   346
  }
kpeter@171
   347
  { // Checking ListGraph
kpeter@171
   348
    checkConcept<Graph, ListGraph>();
kpeter@171
   349
    checkConcept<AlterableGraphComponent<>, ListGraph>();
kpeter@171
   350
    checkConcept<ExtendableGraphComponent<>, ListGraph>();
kpeter@171
   351
    checkConcept<ClearableGraphComponent<>, ListGraph>();
kpeter@171
   352
    checkConcept<ErasableGraphComponent<>, ListGraph>();
kpeter@171
   353
  }
kpeter@171
   354
  { // Checking SmartGraph
kpeter@171
   355
    checkConcept<Graph, SmartGraph>();
kpeter@171
   356
    checkConcept<AlterableGraphComponent<>, SmartGraph>();
kpeter@171
   357
    checkConcept<ExtendableGraphComponent<>, SmartGraph>();
kpeter@171
   358
    checkConcept<ClearableGraphComponent<>, SmartGraph>();
kpeter@171
   359
  }
deba@353
   360
  { // Checking FullGraph
deba@353
   361
    checkConcept<Graph, FullGraph>();
deba@353
   362
  }
kpeter@334
   363
  { // Checking GridGraph
kpeter@334
   364
    checkConcept<Graph, GridGraph>();
kpeter@334
   365
  }
kpeter@365
   366
  { // Checking HypercubeGraph
kpeter@365
   367
    checkConcept<Graph, HypercubeGraph>();
kpeter@365
   368
  }
deba@57
   369
}
deba@57
   370
deba@57
   371
template <typename Graph>
deba@228
   372
void checkGraphValidity() {
deba@149
   373
  TEMPLATE_GRAPH_TYPEDEFS(Graph);
deba@57
   374
  Graph g;
deba@57
   375
deba@57
   376
  Node
deba@57
   377
    n1 = g.addNode(),
deba@57
   378
    n2 = g.addNode(),
deba@57
   379
    n3 = g.addNode();
deba@57
   380
deba@57
   381
  Edge
deba@57
   382
    e1 = g.addEdge(n1, n2),
deba@57
   383
    e2 = g.addEdge(n2, n3);
deba@57
   384
kpeter@171
   385
  check(g.valid(n1), "Wrong validity check");
kpeter@171
   386
  check(g.valid(e1), "Wrong validity check");
kpeter@171
   387
  check(g.valid(g.direct(e1, true)), "Wrong validity check");
kpeter@171
   388
kpeter@171
   389
  check(!g.valid(g.nodeFromId(-1)), "Wrong validity check");
kpeter@171
   390
  check(!g.valid(g.edgeFromId(-1)), "Wrong validity check");
kpeter@171
   391
  check(!g.valid(g.arcFromId(-1)), "Wrong validity check");
deba@57
   392
}
deba@57
   393
deba@149
   394
template <typename Graph>
deba@228
   395
void checkGraphValidityErase() {
deba@149
   396
  TEMPLATE_GRAPH_TYPEDEFS(Graph);
deba@149
   397
  Graph g;
deba@149
   398
deba@149
   399
  Node
deba@149
   400
    n1 = g.addNode(),
deba@149
   401
    n2 = g.addNode(),
deba@149
   402
    n3 = g.addNode();
deba@149
   403
deba@149
   404
  Edge
deba@149
   405
    e1 = g.addEdge(n1, n2),
deba@149
   406
    e2 = g.addEdge(n2, n3);
deba@149
   407
kpeter@171
   408
  check(g.valid(n1), "Wrong validity check");
kpeter@171
   409
  check(g.valid(e1), "Wrong validity check");
kpeter@171
   410
  check(g.valid(g.direct(e1, true)), "Wrong validity check");
deba@149
   411
deba@149
   412
  g.erase(n1);
deba@149
   413
kpeter@171
   414
  check(!g.valid(n1), "Wrong validity check");
kpeter@171
   415
  check(g.valid(n2), "Wrong validity check");
kpeter@171
   416
  check(g.valid(n3), "Wrong validity check");
kpeter@171
   417
  check(!g.valid(e1), "Wrong validity check");
kpeter@171
   418
  check(g.valid(e2), "Wrong validity check");
deba@149
   419
kpeter@171
   420
  check(!g.valid(g.nodeFromId(-1)), "Wrong validity check");
kpeter@171
   421
  check(!g.valid(g.edgeFromId(-1)), "Wrong validity check");
kpeter@171
   422
  check(!g.valid(g.arcFromId(-1)), "Wrong validity check");
deba@149
   423
}
deba@149
   424
deba@335
   425
void checkGridGraph(int width, int height) {
deba@335
   426
  typedef GridGraph Graph;
deba@335
   427
  GRAPH_TYPEDEFS(Graph);
deba@335
   428
  Graph G(width, height);
deba@57
   429
kpeter@336
   430
  check(G.width() == width, "Wrong column number");
kpeter@336
   431
  check(G.height() == height, "Wrong row number");
alpar@209
   432
kpeter@737
   433
  G.resize(width, height);
kpeter@737
   434
  check(G.width() == width, "Wrong column number");
kpeter@737
   435
  check(G.height() == height, "Wrong row number");
kpeter@737
   436
deba@335
   437
  for (int i = 0; i < width; ++i) {
deba@335
   438
    for (int j = 0; j < height; ++j) {
deba@335
   439
      check(G.col(G(i, j)) == i, "Wrong column");
deba@335
   440
      check(G.row(G(i, j)) == j, "Wrong row");
deba@335
   441
      check(G.pos(G(i, j)).x == i, "Wrong column");
deba@335
   442
      check(G.pos(G(i, j)).y == j, "Wrong row");
kpeter@334
   443
    }
kpeter@334
   444
  }
deba@57
   445
deba@335
   446
  for (int j = 0; j < height; ++j) {
deba@335
   447
    for (int i = 0; i < width - 1; ++i) {
deba@335
   448
      check(G.source(G.right(G(i, j))) == G(i, j), "Wrong right");
deba@335
   449
      check(G.target(G.right(G(i, j))) == G(i + 1, j), "Wrong right");
kpeter@334
   450
    }
deba@335
   451
    check(G.right(G(width - 1, j)) == INVALID, "Wrong right");
kpeter@334
   452
  }
deba@57
   453
deba@335
   454
  for (int j = 0; j < height; ++j) {
deba@335
   455
    for (int i = 1; i < width; ++i) {
deba@335
   456
      check(G.source(G.left(G(i, j))) == G(i, j), "Wrong left");
deba@335
   457
      check(G.target(G.left(G(i, j))) == G(i - 1, j), "Wrong left");
kpeter@334
   458
    }
deba@335
   459
    check(G.left(G(0, j)) == INVALID, "Wrong left");
kpeter@334
   460
  }
deba@57
   461
deba@335
   462
  for (int i = 0; i < width; ++i) {
deba@335
   463
    for (int j = 0; j < height - 1; ++j) {
deba@335
   464
      check(G.source(G.up(G(i, j))) == G(i, j), "Wrong up");
deba@335
   465
      check(G.target(G.up(G(i, j))) == G(i, j + 1), "Wrong up");
kpeter@334
   466
    }
deba@335
   467
    check(G.up(G(i, height - 1)) == INVALID, "Wrong up");
kpeter@334
   468
  }
deba@228
   469
deba@335
   470
  for (int i = 0; i < width; ++i) {
deba@335
   471
    for (int j = 1; j < height; ++j) {
deba@335
   472
      check(G.source(G.down(G(i, j))) == G(i, j), "Wrong down");
deba@335
   473
      check(G.target(G.down(G(i, j))) == G(i, j - 1), "Wrong down");
kpeter@334
   474
    }
deba@335
   475
    check(G.down(G(i, 0)) == INVALID, "Wrong down");
kpeter@334
   476
  }
kpeter@334
   477
deba@335
   478
  checkGraphNodeList(G, width * height);
deba@335
   479
  checkGraphEdgeList(G, width * (height - 1) + (width - 1) * height);
deba@335
   480
  checkGraphArcList(G, 2 * (width * (height - 1) + (width - 1) * height));
kpeter@334
   481
deba@335
   482
  for (NodeIt n(G); n != INVALID; ++n) {
deba@335
   483
    int nb = 4;
deba@335
   484
    if (G.col(n) == 0) --nb;
deba@335
   485
    if (G.col(n) == width - 1) --nb;
deba@335
   486
    if (G.row(n) == 0) --nb;
deba@335
   487
    if (G.row(n) == height - 1) --nb;
kpeter@334
   488
deba@335
   489
    checkGraphOutArcList(G, n, nb);
deba@335
   490
    checkGraphInArcList(G, n, nb);
deba@335
   491
    checkGraphIncEdgeList(G, n, nb);
deba@335
   492
  }
kpeter@334
   493
deba@335
   494
  checkArcDirections(G);
kpeter@334
   495
deba@335
   496
  checkGraphConArcList(G, 2 * (width * (height - 1) + (width - 1) * height));
deba@335
   497
  checkGraphConEdgeList(G, width * (height - 1) + (width - 1) * height);
kpeter@334
   498
deba@335
   499
  checkNodeIds(G);
deba@335
   500
  checkArcIds(G);
deba@335
   501
  checkEdgeIds(G);
deba@335
   502
  checkGraphNodeMap(G);
deba@335
   503
  checkGraphArcMap(G);
deba@335
   504
  checkGraphEdgeMap(G);
kpeter@334
   505
kpeter@334
   506
}
deba@228
   507
kpeter@365
   508
void checkHypercubeGraph(int dim) {
kpeter@365
   509
  GRAPH_TYPEDEFS(HypercubeGraph);
kpeter@365
   510
kpeter@365
   511
  HypercubeGraph G(dim);
kpeter@737
   512
  check(G.dimension() == dim, "Wrong dimension");
kpeter@737
   513
kpeter@737
   514
  G.resize(dim);
kpeter@737
   515
  check(G.dimension() == dim, "Wrong dimension");
kpeter@737
   516
  
kpeter@365
   517
  checkGraphNodeList(G, 1 << dim);
alpar@372
   518
  checkGraphEdgeList(G, dim * (1 << (dim-1)));
kpeter@365
   519
  checkGraphArcList(G, dim * (1 << dim));
kpeter@365
   520
kpeter@365
   521
  Node n = G.nodeFromId(dim);
kpeter@365
   522
kpeter@365
   523
  for (NodeIt n(G); n != INVALID; ++n) {
kpeter@365
   524
    checkGraphIncEdgeList(G, n, dim);
kpeter@365
   525
    for (IncEdgeIt e(G, n); e != INVALID; ++e) {
kpeter@365
   526
      check( (G.u(e) == n &&
alpar@372
   527
              G.id(G.v(e)) == (G.id(n) ^ (1 << G.dimension(e)))) ||
kpeter@365
   528
             (G.v(e) == n &&
alpar@372
   529
              G.id(G.u(e)) == (G.id(n) ^ (1 << G.dimension(e)))),
kpeter@365
   530
             "Wrong edge or wrong dimension");
kpeter@365
   531
    }
kpeter@365
   532
kpeter@365
   533
    checkGraphOutArcList(G, n, dim);
kpeter@365
   534
    for (OutArcIt a(G, n); a != INVALID; ++a) {
kpeter@365
   535
      check(G.source(a) == n &&
alpar@372
   536
            G.id(G.target(a)) == (G.id(n) ^ (1 << G.dimension(a))),
kpeter@365
   537
            "Wrong arc or wrong dimension");
kpeter@365
   538
    }
kpeter@365
   539
kpeter@365
   540
    checkGraphInArcList(G, n, dim);
kpeter@365
   541
    for (InArcIt a(G, n); a != INVALID; ++a) {
kpeter@365
   542
      check(G.target(a) == n &&
alpar@372
   543
            G.id(G.source(a)) == (G.id(n) ^ (1 << G.dimension(a))),
kpeter@365
   544
            "Wrong arc or wrong dimension");
kpeter@365
   545
    }
kpeter@365
   546
  }
kpeter@365
   547
kpeter@365
   548
  checkGraphConArcList(G, (1 << dim) * dim);
alpar@372
   549
  checkGraphConEdgeList(G, dim * (1 << (dim-1)));
kpeter@365
   550
kpeter@365
   551
  checkArcDirections(G);
kpeter@365
   552
kpeter@365
   553
  checkNodeIds(G);
kpeter@365
   554
  checkArcIds(G);
kpeter@365
   555
  checkEdgeIds(G);
kpeter@365
   556
  checkGraphNodeMap(G);
kpeter@365
   557
  checkGraphArcMap(G);
kpeter@365
   558
  checkGraphEdgeMap(G);
kpeter@365
   559
}
deba@57
   560
deba@228
   561
void checkGraphs() {
kpeter@171
   562
  { // Checking ListGraph
kpeter@374
   563
    checkGraphBuild<ListGraph>();
kpeter@374
   564
    checkGraphAlter<ListGraph>();
kpeter@374
   565
    checkGraphErase<ListGraph>();
kpeter@374
   566
    checkGraphSnapshot<ListGraph>();
deba@228
   567
    checkGraphValidityErase<ListGraph>();
kpeter@171
   568
  }
kpeter@171
   569
  { // Checking SmartGraph
kpeter@374
   570
    checkGraphBuild<SmartGraph>();
kpeter@374
   571
    checkGraphSnapshot<SmartGraph>();
deba@228
   572
    checkGraphValidity<SmartGraph>();
kpeter@171
   573
  }
kpeter@365
   574
  { // Checking FullGraph
deba@353
   575
    checkFullGraph(7);
deba@353
   576
    checkFullGraph(8);
deba@353
   577
  }
kpeter@334
   578
  { // Checking GridGraph
deba@335
   579
    checkGridGraph(5, 8);
deba@335
   580
    checkGridGraph(8, 5);
deba@335
   581
    checkGridGraph(5, 5);
deba@335
   582
    checkGridGraph(0, 0);
deba@335
   583
    checkGridGraph(1, 1);
kpeter@334
   584
  }
kpeter@365
   585
  { // Checking HypercubeGraph
kpeter@365
   586
    checkHypercubeGraph(1);
kpeter@365
   587
    checkHypercubeGraph(2);
kpeter@365
   588
    checkHypercubeGraph(3);
kpeter@365
   589
    checkHypercubeGraph(4);
kpeter@365
   590
  }
kpeter@171
   591
}
kpeter@171
   592
deba@57
   593
int main() {
deba@228
   594
  checkConcepts();
deba@228
   595
  checkGraphs();
deba@57
   596
  return 0;
deba@57
   597
}