test/digraph_test.cc
author Peter Kovacs <kpeter@inf.elte.hu>
Wed, 15 Apr 2009 04:26:13 +0200
changeset 586 7c12061bd271
parent 375 2d87dbd7f8c8
child 736 2e20aad15754
child 774 f4b5c2d5449d
child 963 761fe0846f49
permissions -rw-r--r--
Add images + fixes in the doc of connectivity tools (#262)
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/digraph.h>
deba@57
    20
#include <lemon/list_graph.h>
kpeter@171
    21
#include <lemon/smart_graph.h>
deba@353
    22
#include <lemon/full_graph.h>
deba@57
    23
deba@57
    24
#include "test_tools.h"
kpeter@171
    25
#include "graph_test.h"
deba@57
    26
deba@57
    27
using namespace lemon;
deba@57
    28
using namespace lemon::concepts;
deba@57
    29
deba@228
    30
template <class Digraph>
kpeter@374
    31
void checkDigraphBuild() {
deba@228
    32
  TEMPLATE_DIGRAPH_TYPEDEFS(Digraph);
deba@228
    33
  Digraph G;
deba@228
    34
deba@228
    35
  checkGraphNodeList(G, 0);
deba@228
    36
  checkGraphArcList(G, 0);
deba@228
    37
deba@228
    38
  Node
deba@228
    39
    n1 = G.addNode(),
deba@228
    40
    n2 = G.addNode(),
deba@228
    41
    n3 = G.addNode();
deba@228
    42
  checkGraphNodeList(G, 3);
deba@228
    43
  checkGraphArcList(G, 0);
deba@228
    44
deba@228
    45
  Arc a1 = G.addArc(n1, n2);
deba@228
    46
  check(G.source(a1) == n1 && G.target(a1) == n2, "Wrong arc");
deba@228
    47
  checkGraphNodeList(G, 3);
deba@228
    48
  checkGraphArcList(G, 1);
deba@228
    49
deba@228
    50
  checkGraphOutArcList(G, n1, 1);
deba@228
    51
  checkGraphOutArcList(G, n2, 0);
deba@228
    52
  checkGraphOutArcList(G, n3, 0);
deba@228
    53
deba@228
    54
  checkGraphInArcList(G, n1, 0);
deba@228
    55
  checkGraphInArcList(G, n2, 1);
deba@228
    56
  checkGraphInArcList(G, n3, 0);
deba@228
    57
deba@228
    58
  checkGraphConArcList(G, 1);
deba@228
    59
kpeter@374
    60
  Arc a2 = G.addArc(n2, n1),
kpeter@374
    61
      a3 = G.addArc(n2, n3),
kpeter@374
    62
      a4 = G.addArc(n2, n3);
kpeter@374
    63
kpeter@374
    64
  checkGraphNodeList(G, 3);
kpeter@374
    65
  checkGraphArcList(G, 4);
kpeter@374
    66
kpeter@374
    67
  checkGraphOutArcList(G, n1, 1);
kpeter@374
    68
  checkGraphOutArcList(G, n2, 3);
kpeter@374
    69
  checkGraphOutArcList(G, n3, 0);
kpeter@374
    70
kpeter@374
    71
  checkGraphInArcList(G, n1, 1);
kpeter@374
    72
  checkGraphInArcList(G, n2, 1);
kpeter@374
    73
  checkGraphInArcList(G, n3, 2);
kpeter@374
    74
kpeter@374
    75
  checkGraphConArcList(G, 4);
kpeter@374
    76
kpeter@374
    77
  checkNodeIds(G);
kpeter@374
    78
  checkArcIds(G);
kpeter@374
    79
  checkGraphNodeMap(G);
kpeter@374
    80
  checkGraphArcMap(G);
kpeter@374
    81
}
kpeter@374
    82
kpeter@374
    83
template <class Digraph>
kpeter@374
    84
void checkDigraphSplit() {
kpeter@374
    85
  TEMPLATE_DIGRAPH_TYPEDEFS(Digraph);
kpeter@374
    86
kpeter@374
    87
  Digraph G;
kpeter@374
    88
  Node n1 = G.addNode(), n2 = G.addNode(), n3 = G.addNode();
kpeter@374
    89
  Arc a1 = G.addArc(n1, n2), a2 = G.addArc(n2, n1),
kpeter@374
    90
      a3 = G.addArc(n2, n3), a4 = G.addArc(n2, n3);
kpeter@374
    91
kpeter@374
    92
  Node n4 = G.split(n2);
kpeter@374
    93
kpeter@374
    94
  check(G.target(OutArcIt(G, n2)) == n4 &&
kpeter@374
    95
        G.source(InArcIt(G, n4)) == n2,
kpeter@374
    96
        "Wrong split.");
kpeter@374
    97
kpeter@374
    98
  checkGraphNodeList(G, 4);
kpeter@374
    99
  checkGraphArcList(G, 5);
kpeter@374
   100
kpeter@374
   101
  checkGraphOutArcList(G, n1, 1);
kpeter@374
   102
  checkGraphOutArcList(G, n2, 1);
kpeter@374
   103
  checkGraphOutArcList(G, n3, 0);
kpeter@374
   104
  checkGraphOutArcList(G, n4, 3);
kpeter@374
   105
kpeter@374
   106
  checkGraphInArcList(G, n1, 1);
kpeter@374
   107
  checkGraphInArcList(G, n2, 1);
kpeter@374
   108
  checkGraphInArcList(G, n3, 2);
kpeter@374
   109
  checkGraphInArcList(G, n4, 1);
kpeter@374
   110
kpeter@374
   111
  checkGraphConArcList(G, 5);
kpeter@374
   112
}
kpeter@374
   113
kpeter@374
   114
template <class Digraph>
kpeter@374
   115
void checkDigraphAlter() {
kpeter@374
   116
  TEMPLATE_DIGRAPH_TYPEDEFS(Digraph);
kpeter@374
   117
kpeter@374
   118
  Digraph G;
kpeter@374
   119
  Node n1 = G.addNode(), n2 = G.addNode(),
kpeter@374
   120
       n3 = G.addNode(), n4 = G.addNode();
kpeter@374
   121
  Arc a1 = G.addArc(n1, n2), a2 = G.addArc(n4, n1),
kpeter@374
   122
      a3 = G.addArc(n4, n3), a4 = G.addArc(n4, n3),
kpeter@374
   123
      a5 = G.addArc(n2, n4);
kpeter@374
   124
kpeter@374
   125
  checkGraphNodeList(G, 4);
kpeter@374
   126
  checkGraphArcList(G, 5);
kpeter@374
   127
kpeter@374
   128
  // Check changeSource() and changeTarget()
kpeter@374
   129
  G.changeTarget(a4, n1);
kpeter@374
   130
kpeter@374
   131
  checkGraphNodeList(G, 4);
kpeter@374
   132
  checkGraphArcList(G, 5);
kpeter@374
   133
kpeter@374
   134
  checkGraphOutArcList(G, n1, 1);
kpeter@374
   135
  checkGraphOutArcList(G, n2, 1);
kpeter@374
   136
  checkGraphOutArcList(G, n3, 0);
kpeter@374
   137
  checkGraphOutArcList(G, n4, 3);
kpeter@374
   138
kpeter@374
   139
  checkGraphInArcList(G, n1, 2);
kpeter@374
   140
  checkGraphInArcList(G, n2, 1);
kpeter@374
   141
  checkGraphInArcList(G, n3, 1);
kpeter@374
   142
  checkGraphInArcList(G, n4, 1);
kpeter@374
   143
kpeter@374
   144
  checkGraphConArcList(G, 5);
kpeter@374
   145
kpeter@374
   146
  G.changeSource(a4, n3);
kpeter@374
   147
kpeter@374
   148
  checkGraphNodeList(G, 4);
kpeter@374
   149
  checkGraphArcList(G, 5);
kpeter@374
   150
kpeter@374
   151
  checkGraphOutArcList(G, n1, 1);
kpeter@374
   152
  checkGraphOutArcList(G, n2, 1);
kpeter@374
   153
  checkGraphOutArcList(G, n3, 1);
kpeter@374
   154
  checkGraphOutArcList(G, n4, 2);
kpeter@374
   155
kpeter@374
   156
  checkGraphInArcList(G, n1, 2);
kpeter@374
   157
  checkGraphInArcList(G, n2, 1);
kpeter@374
   158
  checkGraphInArcList(G, n3, 1);
kpeter@374
   159
  checkGraphInArcList(G, n4, 1);
kpeter@374
   160
kpeter@374
   161
  checkGraphConArcList(G, 5);
kpeter@374
   162
kpeter@374
   163
  // Check contract()
kpeter@374
   164
  G.contract(n2, n4, false);
kpeter@374
   165
kpeter@374
   166
  checkGraphNodeList(G, 3);
kpeter@374
   167
  checkGraphArcList(G, 5);
kpeter@374
   168
kpeter@374
   169
  checkGraphOutArcList(G, n1, 1);
kpeter@374
   170
  checkGraphOutArcList(G, n2, 3);
kpeter@374
   171
  checkGraphOutArcList(G, n3, 1);
kpeter@374
   172
kpeter@374
   173
  checkGraphInArcList(G, n1, 2);
kpeter@374
   174
  checkGraphInArcList(G, n2, 2);
kpeter@374
   175
  checkGraphInArcList(G, n3, 1);
kpeter@374
   176
kpeter@374
   177
  checkGraphConArcList(G, 5);
kpeter@374
   178
kpeter@374
   179
  G.contract(n2, n1);
kpeter@374
   180
kpeter@374
   181
  checkGraphNodeList(G, 2);
kpeter@374
   182
  checkGraphArcList(G, 3);
kpeter@374
   183
kpeter@374
   184
  checkGraphOutArcList(G, n2, 2);
kpeter@374
   185
  checkGraphOutArcList(G, n3, 1);
kpeter@374
   186
kpeter@374
   187
  checkGraphInArcList(G, n2, 2);
kpeter@374
   188
  checkGraphInArcList(G, n3, 1);
kpeter@374
   189
kpeter@374
   190
  checkGraphConArcList(G, 3);
kpeter@374
   191
}
kpeter@374
   192
kpeter@374
   193
template <class Digraph>
kpeter@374
   194
void checkDigraphErase() {
kpeter@374
   195
  TEMPLATE_DIGRAPH_TYPEDEFS(Digraph);
kpeter@374
   196
kpeter@374
   197
  Digraph G;
kpeter@374
   198
  Node n1 = G.addNode(), n2 = G.addNode(),
kpeter@374
   199
       n3 = G.addNode(), n4 = G.addNode();
kpeter@374
   200
  Arc a1 = G.addArc(n1, n2), a2 = G.addArc(n4, n1),
kpeter@374
   201
      a3 = G.addArc(n4, n3), a4 = G.addArc(n3, n1),
kpeter@374
   202
      a5 = G.addArc(n2, n4);
kpeter@374
   203
kpeter@374
   204
  // Check arc deletion
kpeter@374
   205
  G.erase(a1);
kpeter@374
   206
kpeter@374
   207
  checkGraphNodeList(G, 4);
kpeter@374
   208
  checkGraphArcList(G, 4);
kpeter@374
   209
kpeter@374
   210
  checkGraphOutArcList(G, n1, 0);
kpeter@374
   211
  checkGraphOutArcList(G, n2, 1);
kpeter@374
   212
  checkGraphOutArcList(G, n3, 1);
kpeter@374
   213
  checkGraphOutArcList(G, n4, 2);
kpeter@374
   214
kpeter@374
   215
  checkGraphInArcList(G, n1, 2);
kpeter@374
   216
  checkGraphInArcList(G, n2, 0);
kpeter@374
   217
  checkGraphInArcList(G, n3, 1);
kpeter@374
   218
  checkGraphInArcList(G, n4, 1);
kpeter@374
   219
kpeter@374
   220
  checkGraphConArcList(G, 4);
kpeter@374
   221
kpeter@374
   222
  // Check node deletion
kpeter@374
   223
  G.erase(n4);
kpeter@374
   224
kpeter@374
   225
  checkGraphNodeList(G, 3);
kpeter@374
   226
  checkGraphArcList(G, 1);
kpeter@374
   227
kpeter@374
   228
  checkGraphOutArcList(G, n1, 0);
kpeter@374
   229
  checkGraphOutArcList(G, n2, 0);
kpeter@374
   230
  checkGraphOutArcList(G, n3, 1);
kpeter@374
   231
  checkGraphOutArcList(G, n4, 0);
kpeter@374
   232
kpeter@374
   233
  checkGraphInArcList(G, n1, 1);
kpeter@374
   234
  checkGraphInArcList(G, n2, 0);
kpeter@374
   235
  checkGraphInArcList(G, n3, 0);
kpeter@374
   236
  checkGraphInArcList(G, n4, 0);
kpeter@374
   237
kpeter@374
   238
  checkGraphConArcList(G, 1);
kpeter@374
   239
}
kpeter@374
   240
kpeter@374
   241
kpeter@374
   242
template <class Digraph>
kpeter@374
   243
void checkDigraphSnapshot() {
kpeter@374
   244
  TEMPLATE_DIGRAPH_TYPEDEFS(Digraph);
kpeter@374
   245
kpeter@374
   246
  Digraph G;
kpeter@374
   247
  Node n1 = G.addNode(), n2 = G.addNode(), n3 = G.addNode();
kpeter@374
   248
  Arc a1 = G.addArc(n1, n2), a2 = G.addArc(n2, n1),
kpeter@374
   249
      a3 = G.addArc(n2, n3), a4 = G.addArc(n2, n3);
kpeter@374
   250
kpeter@374
   251
  typename Digraph::Snapshot snapshot(G);
kpeter@374
   252
kpeter@374
   253
  Node n = G.addNode();
kpeter@374
   254
  G.addArc(n3, n);
kpeter@374
   255
  G.addArc(n, n3);
kpeter@374
   256
kpeter@374
   257
  checkGraphNodeList(G, 4);
kpeter@374
   258
  checkGraphArcList(G, 6);
kpeter@374
   259
kpeter@374
   260
  snapshot.restore();
kpeter@374
   261
deba@228
   262
  checkGraphNodeList(G, 3);
deba@228
   263
  checkGraphArcList(G, 4);
deba@228
   264
deba@228
   265
  checkGraphOutArcList(G, n1, 1);
deba@228
   266
  checkGraphOutArcList(G, n2, 3);
deba@228
   267
  checkGraphOutArcList(G, n3, 0);
deba@228
   268
deba@228
   269
  checkGraphInArcList(G, n1, 1);
deba@228
   270
  checkGraphInArcList(G, n2, 1);
deba@228
   271
  checkGraphInArcList(G, n3, 2);
deba@228
   272
deba@228
   273
  checkGraphConArcList(G, 4);
deba@228
   274
deba@228
   275
  checkNodeIds(G);
deba@228
   276
  checkArcIds(G);
deba@228
   277
  checkGraphNodeMap(G);
deba@228
   278
  checkGraphArcMap(G);
deba@228
   279
kpeter@374
   280
  G.addNode();
kpeter@374
   281
  snapshot.save(G);
kpeter@374
   282
kpeter@374
   283
  G.addArc(G.addNode(), G.addNode());
kpeter@374
   284
kpeter@374
   285
  snapshot.restore();
kpeter@374
   286
kpeter@374
   287
  checkGraphNodeList(G, 4);
kpeter@374
   288
  checkGraphArcList(G, 4);
deba@228
   289
}
deba@228
   290
deba@228
   291
void checkConcepts() {
kpeter@171
   292
  { // Checking digraph components
deba@57
   293
    checkConcept<BaseDigraphComponent, BaseDigraphComponent >();
deba@57
   294
alpar@209
   295
    checkConcept<IDableDigraphComponent<>,
deba@57
   296
      IDableDigraphComponent<> >();
deba@57
   297
alpar@209
   298
    checkConcept<IterableDigraphComponent<>,
deba@57
   299
      IterableDigraphComponent<> >();
deba@57
   300
alpar@209
   301
    checkConcept<MappableDigraphComponent<>,
deba@57
   302
      MappableDigraphComponent<> >();
deba@57
   303
  }
kpeter@171
   304
  { // Checking skeleton digraph
deba@57
   305
    checkConcept<Digraph, Digraph>();
deba@57
   306
  }
kpeter@171
   307
  { // Checking ListDigraph
kpeter@171
   308
    checkConcept<Digraph, ListDigraph>();
deba@57
   309
    checkConcept<AlterableDigraphComponent<>, ListDigraph>();
deba@57
   310
    checkConcept<ExtendableDigraphComponent<>, ListDigraph>();
deba@57
   311
    checkConcept<ClearableDigraphComponent<>, ListDigraph>();
deba@57
   312
    checkConcept<ErasableDigraphComponent<>, ListDigraph>();
kpeter@171
   313
  }
kpeter@171
   314
  { // Checking SmartDigraph
kpeter@171
   315
    checkConcept<Digraph, SmartDigraph>();
kpeter@171
   316
    checkConcept<AlterableDigraphComponent<>, SmartDigraph>();
kpeter@171
   317
    checkConcept<ExtendableDigraphComponent<>, SmartDigraph>();
kpeter@171
   318
    checkConcept<ClearableDigraphComponent<>, SmartDigraph>();
kpeter@171
   319
  }
kpeter@354
   320
  { // Checking FullDigraph
kpeter@354
   321
    checkConcept<Digraph, FullDigraph>();
kpeter@354
   322
  }
kpeter@171
   323
}
deba@57
   324
kpeter@171
   325
template <typename Digraph>
deba@228
   326
void checkDigraphValidity() {
kpeter@171
   327
  TEMPLATE_DIGRAPH_TYPEDEFS(Digraph);
kpeter@171
   328
  Digraph g;
kpeter@171
   329
kpeter@171
   330
  Node
kpeter@171
   331
    n1 = g.addNode(),
kpeter@171
   332
    n2 = g.addNode(),
kpeter@171
   333
    n3 = g.addNode();
kpeter@171
   334
kpeter@171
   335
  Arc
kpeter@171
   336
    e1 = g.addArc(n1, n2),
kpeter@171
   337
    e2 = g.addArc(n2, n3);
kpeter@171
   338
kpeter@171
   339
  check(g.valid(n1), "Wrong validity check");
kpeter@171
   340
  check(g.valid(e1), "Wrong validity check");
kpeter@171
   341
kpeter@171
   342
  check(!g.valid(g.nodeFromId(-1)), "Wrong validity check");
kpeter@171
   343
  check(!g.valid(g.arcFromId(-1)), "Wrong validity check");
kpeter@171
   344
}
kpeter@171
   345
kpeter@171
   346
template <typename Digraph>
deba@228
   347
void checkDigraphValidityErase() {
kpeter@171
   348
  TEMPLATE_DIGRAPH_TYPEDEFS(Digraph);
kpeter@171
   349
  Digraph g;
kpeter@171
   350
kpeter@171
   351
  Node
kpeter@171
   352
    n1 = g.addNode(),
kpeter@171
   353
    n2 = g.addNode(),
kpeter@171
   354
    n3 = g.addNode();
kpeter@171
   355
kpeter@171
   356
  Arc
kpeter@171
   357
    e1 = g.addArc(n1, n2),
kpeter@171
   358
    e2 = g.addArc(n2, n3);
kpeter@171
   359
kpeter@171
   360
  check(g.valid(n1), "Wrong validity check");
kpeter@171
   361
  check(g.valid(e1), "Wrong validity check");
kpeter@171
   362
kpeter@171
   363
  g.erase(n1);
kpeter@171
   364
kpeter@171
   365
  check(!g.valid(n1), "Wrong validity check");
kpeter@171
   366
  check(g.valid(n2), "Wrong validity check");
kpeter@171
   367
  check(g.valid(n3), "Wrong validity check");
kpeter@171
   368
  check(!g.valid(e1), "Wrong validity check");
kpeter@171
   369
  check(g.valid(e2), "Wrong validity check");
kpeter@171
   370
kpeter@171
   371
  check(!g.valid(g.nodeFromId(-1)), "Wrong validity check");
kpeter@171
   372
  check(!g.valid(g.arcFromId(-1)), "Wrong validity check");
kpeter@171
   373
}
kpeter@171
   374
alpar@375
   375
void checkFullDigraph(int num) {
alpar@375
   376
  typedef FullDigraph Digraph;
alpar@375
   377
  DIGRAPH_TYPEDEFS(Digraph);
alpar@375
   378
  Digraph G(num);
alpar@375
   379
alpar@375
   380
  checkGraphNodeList(G, num);
alpar@375
   381
  checkGraphArcList(G, num * num);
alpar@375
   382
alpar@375
   383
  for (NodeIt n(G); n != INVALID; ++n) {
alpar@375
   384
    checkGraphOutArcList(G, n, num);
alpar@375
   385
    checkGraphInArcList(G, n, num);
alpar@375
   386
  }
alpar@375
   387
alpar@375
   388
  checkGraphConArcList(G, num * num);
alpar@375
   389
alpar@375
   390
  checkNodeIds(G);
alpar@375
   391
  checkArcIds(G);
alpar@375
   392
  checkGraphNodeMap(G);
alpar@375
   393
  checkGraphArcMap(G);
alpar@375
   394
alpar@375
   395
  for (int i = 0; i < G.nodeNum(); ++i) {
alpar@375
   396
    check(G.index(G(i)) == i, "Wrong index");
alpar@375
   397
  }
alpar@375
   398
alpar@375
   399
  for (NodeIt s(G); s != INVALID; ++s) {
alpar@375
   400
    for (NodeIt t(G); t != INVALID; ++t) {
alpar@375
   401
      Arc a = G.arc(s, t);
alpar@375
   402
      check(G.source(a) == s && G.target(a) == t, "Wrong arc lookup");
alpar@375
   403
    }
alpar@375
   404
  }
alpar@375
   405
}
alpar@375
   406
deba@228
   407
void checkDigraphs() {
kpeter@171
   408
  { // Checking ListDigraph
kpeter@374
   409
    checkDigraphBuild<ListDigraph>();
kpeter@374
   410
    checkDigraphSplit<ListDigraph>();
kpeter@374
   411
    checkDigraphAlter<ListDigraph>();
kpeter@374
   412
    checkDigraphErase<ListDigraph>();
kpeter@374
   413
    checkDigraphSnapshot<ListDigraph>();
deba@228
   414
    checkDigraphValidityErase<ListDigraph>();
deba@57
   415
  }
kpeter@171
   416
  { // Checking SmartDigraph
kpeter@374
   417
    checkDigraphBuild<SmartDigraph>();
kpeter@374
   418
    checkDigraphSplit<SmartDigraph>();
kpeter@374
   419
    checkDigraphSnapshot<SmartDigraph>();
deba@228
   420
    checkDigraphValidity<SmartDigraph>();
kpeter@171
   421
  }
deba@353
   422
  { // Checking FullDigraph
deba@353
   423
    checkFullDigraph(8);
deba@353
   424
  }
kpeter@171
   425
}
deba@57
   426
kpeter@171
   427
int main() {
deba@228
   428
  checkDigraphs();
deba@228
   429
  checkConcepts();
deba@57
   430
  return 0;
deba@57
   431
}