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