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