test/graph_test.cc
author Peter Kovacs <kpeter@inf.elte.hu>
Fri, 17 Apr 2009 09:54:14 +0200
changeset 640 7ac52d6a268e
parent 388 2d87dbd7f8c8
child 783 2e20aad15754
child 1157 761fe0846f49
permissions -rw-r--r--
Extend and modify the interface of matching algorithms (#265)

- Rename decomposition() to status() in MaxMatching.
- Add a new query function statusMap() to MaxMatching.
- Add a new query function matchingMap() to all the three classes.
- Rename matchingValue() to matchingWeight() in the weighted
matching classes.
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@463
     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@365
    22
#include <lemon/full_graph.h>
kpeter@346
    23
#include <lemon/grid_graph.h>
kpeter@377
    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@387
    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@387
    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@387
    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@387
    52
deba@228
    53
  checkGraphNodeList(G, 3);
kpeter@387
    54
  checkGraphEdgeList(G, 1);
deba@228
    55
  checkGraphArcList(G, 2);
deba@228
    56
kpeter@387
    57
  checkGraphIncEdgeArcLists(G, n1, 1);
kpeter@387
    58
  checkGraphIncEdgeArcLists(G, n2, 1);
kpeter@387
    59
  checkGraphIncEdgeArcLists(G, n3, 0);
deba@228
    60
kpeter@387
    61
  checkGraphConEdgeList(G, 1);
kpeter@387
    62
  checkGraphConArcList(G, 2);
deba@228
    63
kpeter@387
    64
  Edge e2 = G.addEdge(n2, n1),
kpeter@387
    65
       e3 = G.addEdge(n2, n3);
deba@228
    66
kpeter@387
    67
  checkGraphNodeList(G, 3);
kpeter@387
    68
  checkGraphEdgeList(G, 3);
kpeter@387
    69
  checkGraphArcList(G, 6);
deba@228
    70
kpeter@387
    71
  checkGraphIncEdgeArcLists(G, n1, 2);
kpeter@387
    72
  checkGraphIncEdgeArcLists(G, n2, 3);
kpeter@387
    73
  checkGraphIncEdgeArcLists(G, n3, 1);
deba@228
    74
kpeter@387
    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@387
    88
template <class Graph>
kpeter@387
    89
void checkGraphAlter() {
kpeter@387
    90
  TEMPLATE_GRAPH_TYPEDEFS(Graph);
kpeter@387
    91
kpeter@387
    92
  Graph G;
kpeter@387
    93
  Node n1 = G.addNode(), n2 = G.addNode(),
kpeter@387
    94
       n3 = G.addNode(), n4 = G.addNode();
kpeter@387
    95
  Edge e1 = G.addEdge(n1, n2), e2 = G.addEdge(n2, n1),
kpeter@387
    96
       e3 = G.addEdge(n2, n3), e4 = G.addEdge(n1, n4),
kpeter@387
    97
       e5 = G.addEdge(n4, n3);
kpeter@387
    98
kpeter@387
    99
  checkGraphNodeList(G, 4);
kpeter@387
   100
  checkGraphEdgeList(G, 5);
kpeter@387
   101
  checkGraphArcList(G, 10);
kpeter@387
   102
kpeter@387
   103
  // Check changeU() and changeV()
kpeter@387
   104
  if (G.u(e2) == n2) {
kpeter@387
   105
    G.changeU(e2, n3);
kpeter@387
   106
  } else {
kpeter@387
   107
    G.changeV(e2, n3);
kpeter@387
   108
  }
kpeter@387
   109
kpeter@387
   110
  checkGraphNodeList(G, 4);
kpeter@387
   111
  checkGraphEdgeList(G, 5);
kpeter@387
   112
  checkGraphArcList(G, 10);
kpeter@387
   113
kpeter@387
   114
  checkGraphIncEdgeArcLists(G, n1, 3);
kpeter@387
   115
  checkGraphIncEdgeArcLists(G, n2, 2);
kpeter@387
   116
  checkGraphIncEdgeArcLists(G, n3, 3);
kpeter@387
   117
  checkGraphIncEdgeArcLists(G, n4, 2);
kpeter@387
   118
kpeter@387
   119
  checkGraphConEdgeList(G, 5);
kpeter@387
   120
  checkGraphConArcList(G, 10);
kpeter@387
   121
kpeter@387
   122
  if (G.u(e2) == n1) {
kpeter@387
   123
    G.changeU(e2, n2);
kpeter@387
   124
  } else {
kpeter@387
   125
    G.changeV(e2, n2);
kpeter@387
   126
  }
kpeter@387
   127
kpeter@387
   128
  checkGraphNodeList(G, 4);
kpeter@387
   129
  checkGraphEdgeList(G, 5);
kpeter@387
   130
  checkGraphArcList(G, 10);
kpeter@387
   131
kpeter@387
   132
  checkGraphIncEdgeArcLists(G, n1, 2);
kpeter@387
   133
  checkGraphIncEdgeArcLists(G, n2, 3);
kpeter@387
   134
  checkGraphIncEdgeArcLists(G, n3, 3);
kpeter@387
   135
  checkGraphIncEdgeArcLists(G, n4, 2);
kpeter@387
   136
kpeter@387
   137
  checkGraphConEdgeList(G, 5);
kpeter@387
   138
  checkGraphConArcList(G, 10);
kpeter@387
   139
kpeter@387
   140
  // Check contract()
kpeter@387
   141
  G.contract(n1, n4, false);
kpeter@387
   142
kpeter@387
   143
  checkGraphNodeList(G, 3);
kpeter@387
   144
  checkGraphEdgeList(G, 5);
kpeter@387
   145
  checkGraphArcList(G, 10);
kpeter@387
   146
kpeter@387
   147
  checkGraphIncEdgeArcLists(G, n1, 4);
kpeter@387
   148
  checkGraphIncEdgeArcLists(G, n2, 3);
kpeter@387
   149
  checkGraphIncEdgeArcLists(G, n3, 3);
kpeter@387
   150
kpeter@387
   151
  checkGraphConEdgeList(G, 5);
kpeter@387
   152
  checkGraphConArcList(G, 10);
kpeter@387
   153
kpeter@387
   154
  G.contract(n2, n3);
kpeter@387
   155
kpeter@387
   156
  checkGraphNodeList(G, 2);
kpeter@387
   157
  checkGraphEdgeList(G, 3);
kpeter@387
   158
  checkGraphArcList(G, 6);
kpeter@387
   159
kpeter@387
   160
  checkGraphIncEdgeArcLists(G, n1, 4);
kpeter@387
   161
  checkGraphIncEdgeArcLists(G, n2, 2);
kpeter@387
   162
kpeter@387
   163
  checkGraphConEdgeList(G, 3);
kpeter@387
   164
  checkGraphConArcList(G, 6);
kpeter@387
   165
}
kpeter@387
   166
kpeter@387
   167
template <class Graph>
kpeter@387
   168
void checkGraphErase() {
kpeter@387
   169
  TEMPLATE_GRAPH_TYPEDEFS(Graph);
kpeter@387
   170
kpeter@387
   171
  Graph G;
kpeter@387
   172
  Node n1 = G.addNode(), n2 = G.addNode(),
kpeter@387
   173
       n3 = G.addNode(), n4 = G.addNode();
kpeter@387
   174
  Edge e1 = G.addEdge(n1, n2), e2 = G.addEdge(n2, n1),
kpeter@387
   175
       e3 = G.addEdge(n2, n3), e4 = G.addEdge(n1, n4),
kpeter@387
   176
       e5 = G.addEdge(n4, n3);
kpeter@387
   177
kpeter@387
   178
  // Check edge deletion
kpeter@387
   179
  G.erase(e2);
kpeter@387
   180
kpeter@387
   181
  checkGraphNodeList(G, 4);
kpeter@387
   182
  checkGraphEdgeList(G, 4);
kpeter@387
   183
  checkGraphArcList(G, 8);
kpeter@387
   184
kpeter@387
   185
  checkGraphIncEdgeArcLists(G, n1, 2);
kpeter@387
   186
  checkGraphIncEdgeArcLists(G, n2, 2);
kpeter@387
   187
  checkGraphIncEdgeArcLists(G, n3, 2);
kpeter@387
   188
  checkGraphIncEdgeArcLists(G, n4, 2);
kpeter@387
   189
kpeter@387
   190
  checkGraphConEdgeList(G, 4);
kpeter@387
   191
  checkGraphConArcList(G, 8);
kpeter@387
   192
kpeter@387
   193
  // Check node deletion
kpeter@387
   194
  G.erase(n3);
kpeter@387
   195
kpeter@387
   196
  checkGraphNodeList(G, 3);
kpeter@387
   197
  checkGraphEdgeList(G, 2);
kpeter@387
   198
  checkGraphArcList(G, 4);
kpeter@387
   199
kpeter@387
   200
  checkGraphIncEdgeArcLists(G, n1, 2);
kpeter@387
   201
  checkGraphIncEdgeArcLists(G, n2, 1);
kpeter@387
   202
  checkGraphIncEdgeArcLists(G, n4, 1);
kpeter@387
   203
kpeter@387
   204
  checkGraphConEdgeList(G, 2);
kpeter@387
   205
  checkGraphConArcList(G, 4);
kpeter@387
   206
}
kpeter@387
   207
kpeter@387
   208
kpeter@387
   209
template <class Graph>
kpeter@387
   210
void checkGraphSnapshot() {
kpeter@387
   211
  TEMPLATE_GRAPH_TYPEDEFS(Graph);
kpeter@387
   212
kpeter@387
   213
  Graph G;
kpeter@387
   214
  Node n1 = G.addNode(), n2 = G.addNode(), n3 = G.addNode();
kpeter@387
   215
  Edge e1 = G.addEdge(n1, n2), e2 = G.addEdge(n2, n1),
kpeter@387
   216
       e3 = G.addEdge(n2, n3);
kpeter@387
   217
kpeter@387
   218
  checkGraphNodeList(G, 3);
kpeter@387
   219
  checkGraphEdgeList(G, 3);
kpeter@387
   220
  checkGraphArcList(G, 6);
kpeter@387
   221
kpeter@387
   222
  typename Graph::Snapshot snapshot(G);
kpeter@387
   223
kpeter@387
   224
  Node n = G.addNode();
kpeter@387
   225
  G.addEdge(n3, n);
kpeter@387
   226
  G.addEdge(n, n3);
kpeter@387
   227
  G.addEdge(n3, n2);
kpeter@387
   228
kpeter@387
   229
  checkGraphNodeList(G, 4);
kpeter@387
   230
  checkGraphEdgeList(G, 6);
kpeter@387
   231
  checkGraphArcList(G, 12);
kpeter@387
   232
kpeter@387
   233
  snapshot.restore();
kpeter@387
   234
kpeter@387
   235
  checkGraphNodeList(G, 3);
kpeter@387
   236
  checkGraphEdgeList(G, 3);
kpeter@387
   237
  checkGraphArcList(G, 6);
kpeter@387
   238
kpeter@387
   239
  checkGraphIncEdgeArcLists(G, n1, 2);
kpeter@387
   240
  checkGraphIncEdgeArcLists(G, n2, 3);
kpeter@387
   241
  checkGraphIncEdgeArcLists(G, n3, 1);
kpeter@387
   242
kpeter@387
   243
  checkGraphConEdgeList(G, 3);
kpeter@387
   244
  checkGraphConArcList(G, 6);
kpeter@387
   245
kpeter@387
   246
  checkNodeIds(G);
kpeter@387
   247
  checkEdgeIds(G);
kpeter@387
   248
  checkArcIds(G);
kpeter@387
   249
  checkGraphNodeMap(G);
kpeter@387
   250
  checkGraphEdgeMap(G);
kpeter@387
   251
  checkGraphArcMap(G);
kpeter@387
   252
kpeter@387
   253
  G.addNode();
kpeter@387
   254
  snapshot.save(G);
kpeter@387
   255
kpeter@387
   256
  G.addEdge(G.addNode(), G.addNode());
kpeter@387
   257
kpeter@387
   258
  snapshot.restore();
kpeter@387
   259
kpeter@387
   260
  checkGraphNodeList(G, 4);
kpeter@387
   261
  checkGraphEdgeList(G, 3);
kpeter@387
   262
  checkGraphArcList(G, 6);
kpeter@387
   263
}
kpeter@387
   264
deba@365
   265
void checkFullGraph(int num) {
deba@365
   266
  typedef FullGraph Graph;
deba@365
   267
  GRAPH_TYPEDEFS(Graph);
deba@365
   268
deba@365
   269
  Graph G(num);
deba@365
   270
  checkGraphNodeList(G, num);
deba@365
   271
  checkGraphEdgeList(G, num * (num - 1) / 2);
deba@365
   272
deba@365
   273
  for (NodeIt n(G); n != INVALID; ++n) {
kpeter@377
   274
    checkGraphOutArcList(G, n, num - 1);
kpeter@377
   275
    checkGraphInArcList(G, n, num - 1);
kpeter@377
   276
    checkGraphIncEdgeList(G, n, num - 1);
deba@365
   277
  }
deba@365
   278
deba@365
   279
  checkGraphConArcList(G, num * (num - 1));
deba@365
   280
  checkGraphConEdgeList(G, num * (num - 1) / 2);
deba@365
   281
deba@365
   282
  checkArcDirections(G);
deba@365
   283
deba@365
   284
  checkNodeIds(G);
deba@365
   285
  checkArcIds(G);
deba@365
   286
  checkEdgeIds(G);
deba@365
   287
  checkGraphNodeMap(G);
deba@365
   288
  checkGraphArcMap(G);
deba@365
   289
  checkGraphEdgeMap(G);
deba@365
   290
kpeter@377
   291
deba@365
   292
  for (int i = 0; i < G.nodeNum(); ++i) {
deba@365
   293
    check(G.index(G(i)) == i, "Wrong index");
deba@365
   294
  }
deba@365
   295
deba@365
   296
  for (NodeIt u(G); u != INVALID; ++u) {
deba@365
   297
    for (NodeIt v(G); v != INVALID; ++v) {
deba@365
   298
      Edge e = G.edge(u, v);
deba@365
   299
      Arc a = G.arc(u, v);
deba@365
   300
      if (u == v) {
deba@365
   301
        check(e == INVALID, "Wrong edge lookup");
deba@365
   302
        check(a == INVALID, "Wrong arc lookup");
deba@365
   303
      } else {
deba@365
   304
        check((G.u(e) == u && G.v(e) == v) ||
deba@365
   305
              (G.u(e) == v && G.v(e) == u), "Wrong edge lookup");
deba@365
   306
        check(G.source(a) == u && G.target(a) == v, "Wrong arc lookup");
deba@365
   307
      }
deba@365
   308
    }
deba@365
   309
  }
deba@365
   310
}
deba@365
   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@365
   341
  { // Checking FullGraph
deba@365
   342
    checkConcept<Graph, FullGraph>();
deba@365
   343
  }
kpeter@346
   344
  { // Checking GridGraph
kpeter@346
   345
    checkConcept<Graph, GridGraph>();
kpeter@346
   346
  }
kpeter@377
   347
  { // Checking HypercubeGraph
kpeter@377
   348
    checkConcept<Graph, HypercubeGraph>();
kpeter@377
   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@347
   406
void checkGridGraph(int width, int height) {
deba@347
   407
  typedef GridGraph Graph;
deba@347
   408
  GRAPH_TYPEDEFS(Graph);
deba@347
   409
  Graph G(width, height);
deba@57
   410
kpeter@348
   411
  check(G.width() == width, "Wrong column number");
kpeter@348
   412
  check(G.height() == height, "Wrong row number");
alpar@209
   413
deba@347
   414
  for (int i = 0; i < width; ++i) {
deba@347
   415
    for (int j = 0; j < height; ++j) {
deba@347
   416
      check(G.col(G(i, j)) == i, "Wrong column");
deba@347
   417
      check(G.row(G(i, j)) == j, "Wrong row");
deba@347
   418
      check(G.pos(G(i, j)).x == i, "Wrong column");
deba@347
   419
      check(G.pos(G(i, j)).y == j, "Wrong row");
kpeter@346
   420
    }
kpeter@346
   421
  }
deba@57
   422
deba@347
   423
  for (int j = 0; j < height; ++j) {
deba@347
   424
    for (int i = 0; i < width - 1; ++i) {
deba@347
   425
      check(G.source(G.right(G(i, j))) == G(i, j), "Wrong right");
deba@347
   426
      check(G.target(G.right(G(i, j))) == G(i + 1, j), "Wrong right");
kpeter@346
   427
    }
deba@347
   428
    check(G.right(G(width - 1, j)) == INVALID, "Wrong right");
kpeter@346
   429
  }
deba@57
   430
deba@347
   431
  for (int j = 0; j < height; ++j) {
deba@347
   432
    for (int i = 1; i < width; ++i) {
deba@347
   433
      check(G.source(G.left(G(i, j))) == G(i, j), "Wrong left");
deba@347
   434
      check(G.target(G.left(G(i, j))) == G(i - 1, j), "Wrong left");
kpeter@346
   435
    }
deba@347
   436
    check(G.left(G(0, j)) == INVALID, "Wrong left");
kpeter@346
   437
  }
deba@57
   438
deba@347
   439
  for (int i = 0; i < width; ++i) {
deba@347
   440
    for (int j = 0; j < height - 1; ++j) {
deba@347
   441
      check(G.source(G.up(G(i, j))) == G(i, j), "Wrong up");
deba@347
   442
      check(G.target(G.up(G(i, j))) == G(i, j + 1), "Wrong up");
kpeter@346
   443
    }
deba@347
   444
    check(G.up(G(i, height - 1)) == INVALID, "Wrong up");
kpeter@346
   445
  }
deba@228
   446
deba@347
   447
  for (int i = 0; i < width; ++i) {
deba@347
   448
    for (int j = 1; j < height; ++j) {
deba@347
   449
      check(G.source(G.down(G(i, j))) == G(i, j), "Wrong down");
deba@347
   450
      check(G.target(G.down(G(i, j))) == G(i, j - 1), "Wrong down");
kpeter@346
   451
    }
deba@347
   452
    check(G.down(G(i, 0)) == INVALID, "Wrong down");
kpeter@346
   453
  }
kpeter@346
   454
deba@347
   455
  checkGraphNodeList(G, width * height);
deba@347
   456
  checkGraphEdgeList(G, width * (height - 1) + (width - 1) * height);
deba@347
   457
  checkGraphArcList(G, 2 * (width * (height - 1) + (width - 1) * height));
kpeter@346
   458
deba@347
   459
  for (NodeIt n(G); n != INVALID; ++n) {
deba@347
   460
    int nb = 4;
deba@347
   461
    if (G.col(n) == 0) --nb;
deba@347
   462
    if (G.col(n) == width - 1) --nb;
deba@347
   463
    if (G.row(n) == 0) --nb;
deba@347
   464
    if (G.row(n) == height - 1) --nb;
kpeter@346
   465
deba@347
   466
    checkGraphOutArcList(G, n, nb);
deba@347
   467
    checkGraphInArcList(G, n, nb);
deba@347
   468
    checkGraphIncEdgeList(G, n, nb);
deba@347
   469
  }
kpeter@346
   470
deba@347
   471
  checkArcDirections(G);
kpeter@346
   472
deba@347
   473
  checkGraphConArcList(G, 2 * (width * (height - 1) + (width - 1) * height));
deba@347
   474
  checkGraphConEdgeList(G, width * (height - 1) + (width - 1) * height);
kpeter@346
   475
deba@347
   476
  checkNodeIds(G);
deba@347
   477
  checkArcIds(G);
deba@347
   478
  checkEdgeIds(G);
deba@347
   479
  checkGraphNodeMap(G);
deba@347
   480
  checkGraphArcMap(G);
deba@347
   481
  checkGraphEdgeMap(G);
kpeter@346
   482
kpeter@346
   483
}
deba@228
   484
kpeter@377
   485
void checkHypercubeGraph(int dim) {
kpeter@377
   486
  GRAPH_TYPEDEFS(HypercubeGraph);
kpeter@377
   487
kpeter@377
   488
  HypercubeGraph G(dim);
kpeter@377
   489
  checkGraphNodeList(G, 1 << dim);
alpar@385
   490
  checkGraphEdgeList(G, dim * (1 << (dim-1)));
kpeter@377
   491
  checkGraphArcList(G, dim * (1 << dim));
kpeter@377
   492
kpeter@377
   493
  Node n = G.nodeFromId(dim);
kpeter@377
   494
kpeter@377
   495
  for (NodeIt n(G); n != INVALID; ++n) {
kpeter@377
   496
    checkGraphIncEdgeList(G, n, dim);
kpeter@377
   497
    for (IncEdgeIt e(G, n); e != INVALID; ++e) {
kpeter@377
   498
      check( (G.u(e) == n &&
alpar@385
   499
              G.id(G.v(e)) == (G.id(n) ^ (1 << G.dimension(e)))) ||
kpeter@377
   500
             (G.v(e) == n &&
alpar@385
   501
              G.id(G.u(e)) == (G.id(n) ^ (1 << G.dimension(e)))),
kpeter@377
   502
             "Wrong edge or wrong dimension");
kpeter@377
   503
    }
kpeter@377
   504
kpeter@377
   505
    checkGraphOutArcList(G, n, dim);
kpeter@377
   506
    for (OutArcIt a(G, n); a != INVALID; ++a) {
kpeter@377
   507
      check(G.source(a) == n &&
alpar@385
   508
            G.id(G.target(a)) == (G.id(n) ^ (1 << G.dimension(a))),
kpeter@377
   509
            "Wrong arc or wrong dimension");
kpeter@377
   510
    }
kpeter@377
   511
kpeter@377
   512
    checkGraphInArcList(G, n, dim);
kpeter@377
   513
    for (InArcIt a(G, n); a != INVALID; ++a) {
kpeter@377
   514
      check(G.target(a) == n &&
alpar@385
   515
            G.id(G.source(a)) == (G.id(n) ^ (1 << G.dimension(a))),
kpeter@377
   516
            "Wrong arc or wrong dimension");
kpeter@377
   517
    }
kpeter@377
   518
  }
kpeter@377
   519
kpeter@377
   520
  checkGraphConArcList(G, (1 << dim) * dim);
alpar@385
   521
  checkGraphConEdgeList(G, dim * (1 << (dim-1)));
kpeter@377
   522
kpeter@377
   523
  checkArcDirections(G);
kpeter@377
   524
kpeter@377
   525
  checkNodeIds(G);
kpeter@377
   526
  checkArcIds(G);
kpeter@377
   527
  checkEdgeIds(G);
kpeter@377
   528
  checkGraphNodeMap(G);
kpeter@377
   529
  checkGraphArcMap(G);
kpeter@377
   530
  checkGraphEdgeMap(G);
kpeter@377
   531
}
deba@57
   532
deba@228
   533
void checkGraphs() {
kpeter@171
   534
  { // Checking ListGraph
kpeter@387
   535
    checkGraphBuild<ListGraph>();
kpeter@387
   536
    checkGraphAlter<ListGraph>();
kpeter@387
   537
    checkGraphErase<ListGraph>();
kpeter@387
   538
    checkGraphSnapshot<ListGraph>();
deba@228
   539
    checkGraphValidityErase<ListGraph>();
kpeter@171
   540
  }
kpeter@171
   541
  { // Checking SmartGraph
kpeter@387
   542
    checkGraphBuild<SmartGraph>();
kpeter@387
   543
    checkGraphSnapshot<SmartGraph>();
deba@228
   544
    checkGraphValidity<SmartGraph>();
kpeter@171
   545
  }
kpeter@377
   546
  { // Checking FullGraph
deba@365
   547
    checkFullGraph(7);
deba@365
   548
    checkFullGraph(8);
deba@365
   549
  }
kpeter@346
   550
  { // Checking GridGraph
deba@347
   551
    checkGridGraph(5, 8);
deba@347
   552
    checkGridGraph(8, 5);
deba@347
   553
    checkGridGraph(5, 5);
deba@347
   554
    checkGridGraph(0, 0);
deba@347
   555
    checkGridGraph(1, 1);
kpeter@346
   556
  }
kpeter@377
   557
  { // Checking HypercubeGraph
kpeter@377
   558
    checkHypercubeGraph(1);
kpeter@377
   559
    checkHypercubeGraph(2);
kpeter@377
   560
    checkHypercubeGraph(3);
kpeter@377
   561
    checkHypercubeGraph(4);
kpeter@377
   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
}