test/digraph_test.cc
author Gabriel Gouvine <gabriel.gouvine.GIT@gmx.com>
Sun, 19 Mar 2017 14:38:08 +0100
changeset 1200 73bd8d5200df
parent 1092 dceba191c00d
permissions -rw-r--r--
CompactDigraph implementation (#377)

Smaller version of StaticDigraph (n+m) if InArcIt is not needed
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@1092
     5
 * Copyright (C) 2003-2013
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>
kpeter@774
    22
#include <lemon/static_graph.h>
gabriel@1200
    23
#include <lemon/compact_graph.h>
deba@353
    24
#include <lemon/full_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 Digraph>
kpeter@374
    33
void checkDigraphBuild() {
deba@228
    34
  TEMPLATE_DIGRAPH_TYPEDEFS(Digraph);
deba@228
    35
  Digraph G;
deba@228
    36
deba@228
    37
  checkGraphNodeList(G, 0);
deba@228
    38
  checkGraphArcList(G, 0);
deba@228
    39
kpeter@736
    40
  G.reserveNode(3);
kpeter@736
    41
  G.reserveArc(4);
kpeter@736
    42
deba@228
    43
  Node
deba@228
    44
    n1 = G.addNode(),
deba@228
    45
    n2 = G.addNode(),
deba@228
    46
    n3 = G.addNode();
deba@228
    47
  checkGraphNodeList(G, 3);
deba@228
    48
  checkGraphArcList(G, 0);
deba@228
    49
deba@228
    50
  Arc a1 = G.addArc(n1, n2);
deba@228
    51
  check(G.source(a1) == n1 && G.target(a1) == n2, "Wrong arc");
deba@228
    52
  checkGraphNodeList(G, 3);
deba@228
    53
  checkGraphArcList(G, 1);
deba@228
    54
deba@228
    55
  checkGraphOutArcList(G, n1, 1);
deba@228
    56
  checkGraphOutArcList(G, n2, 0);
deba@228
    57
  checkGraphOutArcList(G, n3, 0);
deba@228
    58
deba@228
    59
  checkGraphInArcList(G, n1, 0);
deba@228
    60
  checkGraphInArcList(G, n2, 1);
deba@228
    61
  checkGraphInArcList(G, n3, 0);
deba@228
    62
deba@228
    63
  checkGraphConArcList(G, 1);
deba@228
    64
kpeter@374
    65
  Arc a2 = G.addArc(n2, n1),
kpeter@374
    66
      a3 = G.addArc(n2, n3),
kpeter@374
    67
      a4 = G.addArc(n2, n3);
alpar@1083
    68
  ::lemon::ignore_unused_variable_warning(a2,a3,a4);
kpeter@374
    69
kpeter@374
    70
  checkGraphNodeList(G, 3);
kpeter@374
    71
  checkGraphArcList(G, 4);
kpeter@374
    72
kpeter@374
    73
  checkGraphOutArcList(G, n1, 1);
kpeter@374
    74
  checkGraphOutArcList(G, n2, 3);
kpeter@374
    75
  checkGraphOutArcList(G, n3, 0);
kpeter@374
    76
kpeter@374
    77
  checkGraphInArcList(G, n1, 1);
kpeter@374
    78
  checkGraphInArcList(G, n2, 1);
kpeter@374
    79
  checkGraphInArcList(G, n3, 2);
kpeter@374
    80
kpeter@374
    81
  checkGraphConArcList(G, 4);
kpeter@374
    82
kpeter@374
    83
  checkNodeIds(G);
kpeter@374
    84
  checkArcIds(G);
kpeter@374
    85
  checkGraphNodeMap(G);
kpeter@374
    86
  checkGraphArcMap(G);
kpeter@374
    87
}
kpeter@374
    88
kpeter@374
    89
template <class Digraph>
kpeter@374
    90
void checkDigraphSplit() {
kpeter@374
    91
  TEMPLATE_DIGRAPH_TYPEDEFS(Digraph);
kpeter@374
    92
kpeter@374
    93
  Digraph G;
kpeter@374
    94
  Node n1 = G.addNode(), n2 = G.addNode(), n3 = G.addNode();
kpeter@374
    95
  Arc a1 = G.addArc(n1, n2), a2 = G.addArc(n2, n1),
kpeter@374
    96
      a3 = G.addArc(n2, n3), a4 = G.addArc(n2, n3);
alpar@1083
    97
  ::lemon::ignore_unused_variable_warning(a1,a2,a3,a4);
kpeter@374
    98
kpeter@374
    99
  Node n4 = G.split(n2);
kpeter@374
   100
kpeter@374
   101
  check(G.target(OutArcIt(G, n2)) == n4 &&
kpeter@374
   102
        G.source(InArcIt(G, n4)) == n2,
kpeter@374
   103
        "Wrong split.");
kpeter@374
   104
kpeter@374
   105
  checkGraphNodeList(G, 4);
kpeter@374
   106
  checkGraphArcList(G, 5);
kpeter@374
   107
kpeter@374
   108
  checkGraphOutArcList(G, n1, 1);
kpeter@374
   109
  checkGraphOutArcList(G, n2, 1);
kpeter@374
   110
  checkGraphOutArcList(G, n3, 0);
kpeter@374
   111
  checkGraphOutArcList(G, n4, 3);
kpeter@374
   112
kpeter@374
   113
  checkGraphInArcList(G, n1, 1);
kpeter@374
   114
  checkGraphInArcList(G, n2, 1);
kpeter@374
   115
  checkGraphInArcList(G, n3, 2);
kpeter@374
   116
  checkGraphInArcList(G, n4, 1);
kpeter@374
   117
kpeter@374
   118
  checkGraphConArcList(G, 5);
kpeter@374
   119
}
kpeter@374
   120
kpeter@374
   121
template <class Digraph>
kpeter@374
   122
void checkDigraphAlter() {
kpeter@374
   123
  TEMPLATE_DIGRAPH_TYPEDEFS(Digraph);
kpeter@374
   124
kpeter@374
   125
  Digraph G;
kpeter@374
   126
  Node n1 = G.addNode(), n2 = G.addNode(),
kpeter@374
   127
       n3 = G.addNode(), n4 = G.addNode();
kpeter@374
   128
  Arc a1 = G.addArc(n1, n2), a2 = G.addArc(n4, n1),
kpeter@374
   129
      a3 = G.addArc(n4, n3), a4 = G.addArc(n4, n3),
kpeter@374
   130
      a5 = G.addArc(n2, n4);
alpar@1083
   131
  ::lemon::ignore_unused_variable_warning(a1,a2,a3,a5);
kpeter@374
   132
kpeter@374
   133
  checkGraphNodeList(G, 4);
kpeter@374
   134
  checkGraphArcList(G, 5);
kpeter@374
   135
kpeter@374
   136
  // Check changeSource() and changeTarget()
kpeter@374
   137
  G.changeTarget(a4, n1);
kpeter@374
   138
kpeter@374
   139
  checkGraphNodeList(G, 4);
kpeter@374
   140
  checkGraphArcList(G, 5);
kpeter@374
   141
kpeter@374
   142
  checkGraphOutArcList(G, n1, 1);
kpeter@374
   143
  checkGraphOutArcList(G, n2, 1);
kpeter@374
   144
  checkGraphOutArcList(G, n3, 0);
kpeter@374
   145
  checkGraphOutArcList(G, n4, 3);
kpeter@374
   146
kpeter@374
   147
  checkGraphInArcList(G, n1, 2);
kpeter@374
   148
  checkGraphInArcList(G, n2, 1);
kpeter@374
   149
  checkGraphInArcList(G, n3, 1);
kpeter@374
   150
  checkGraphInArcList(G, n4, 1);
kpeter@374
   151
kpeter@374
   152
  checkGraphConArcList(G, 5);
kpeter@374
   153
kpeter@374
   154
  G.changeSource(a4, n3);
kpeter@374
   155
kpeter@374
   156
  checkGraphNodeList(G, 4);
kpeter@374
   157
  checkGraphArcList(G, 5);
kpeter@374
   158
kpeter@374
   159
  checkGraphOutArcList(G, n1, 1);
kpeter@374
   160
  checkGraphOutArcList(G, n2, 1);
kpeter@374
   161
  checkGraphOutArcList(G, n3, 1);
kpeter@374
   162
  checkGraphOutArcList(G, n4, 2);
kpeter@374
   163
kpeter@374
   164
  checkGraphInArcList(G, n1, 2);
kpeter@374
   165
  checkGraphInArcList(G, n2, 1);
kpeter@374
   166
  checkGraphInArcList(G, n3, 1);
kpeter@374
   167
  checkGraphInArcList(G, n4, 1);
kpeter@374
   168
kpeter@374
   169
  checkGraphConArcList(G, 5);
kpeter@374
   170
kpeter@374
   171
  // Check contract()
kpeter@374
   172
  G.contract(n2, n4, false);
kpeter@374
   173
kpeter@374
   174
  checkGraphNodeList(G, 3);
kpeter@374
   175
  checkGraphArcList(G, 5);
kpeter@374
   176
kpeter@374
   177
  checkGraphOutArcList(G, n1, 1);
kpeter@374
   178
  checkGraphOutArcList(G, n2, 3);
kpeter@374
   179
  checkGraphOutArcList(G, n3, 1);
kpeter@374
   180
kpeter@374
   181
  checkGraphInArcList(G, n1, 2);
kpeter@374
   182
  checkGraphInArcList(G, n2, 2);
kpeter@374
   183
  checkGraphInArcList(G, n3, 1);
kpeter@374
   184
kpeter@374
   185
  checkGraphConArcList(G, 5);
kpeter@374
   186
kpeter@374
   187
  G.contract(n2, n1);
kpeter@374
   188
kpeter@374
   189
  checkGraphNodeList(G, 2);
kpeter@374
   190
  checkGraphArcList(G, 3);
kpeter@374
   191
kpeter@374
   192
  checkGraphOutArcList(G, n2, 2);
kpeter@374
   193
  checkGraphOutArcList(G, n3, 1);
kpeter@374
   194
kpeter@374
   195
  checkGraphInArcList(G, n2, 2);
kpeter@374
   196
  checkGraphInArcList(G, n3, 1);
kpeter@374
   197
kpeter@374
   198
  checkGraphConArcList(G, 3);
kpeter@374
   199
}
kpeter@374
   200
kpeter@374
   201
template <class Digraph>
kpeter@374
   202
void checkDigraphErase() {
kpeter@374
   203
  TEMPLATE_DIGRAPH_TYPEDEFS(Digraph);
kpeter@374
   204
kpeter@374
   205
  Digraph G;
kpeter@374
   206
  Node n1 = G.addNode(), n2 = G.addNode(),
kpeter@374
   207
       n3 = G.addNode(), n4 = G.addNode();
kpeter@374
   208
  Arc a1 = G.addArc(n1, n2), a2 = G.addArc(n4, n1),
kpeter@374
   209
      a3 = G.addArc(n4, n3), a4 = G.addArc(n3, n1),
kpeter@374
   210
      a5 = G.addArc(n2, n4);
alpar@1083
   211
  ::lemon::ignore_unused_variable_warning(a2,a3,a4,a5);
kpeter@374
   212
kpeter@374
   213
  // Check arc deletion
kpeter@374
   214
  G.erase(a1);
kpeter@374
   215
kpeter@374
   216
  checkGraphNodeList(G, 4);
kpeter@374
   217
  checkGraphArcList(G, 4);
kpeter@374
   218
kpeter@374
   219
  checkGraphOutArcList(G, n1, 0);
kpeter@374
   220
  checkGraphOutArcList(G, n2, 1);
kpeter@374
   221
  checkGraphOutArcList(G, n3, 1);
kpeter@374
   222
  checkGraphOutArcList(G, n4, 2);
kpeter@374
   223
kpeter@374
   224
  checkGraphInArcList(G, n1, 2);
kpeter@374
   225
  checkGraphInArcList(G, n2, 0);
kpeter@374
   226
  checkGraphInArcList(G, n3, 1);
kpeter@374
   227
  checkGraphInArcList(G, n4, 1);
kpeter@374
   228
kpeter@374
   229
  checkGraphConArcList(G, 4);
kpeter@374
   230
kpeter@374
   231
  // Check node deletion
kpeter@374
   232
  G.erase(n4);
kpeter@374
   233
kpeter@374
   234
  checkGraphNodeList(G, 3);
kpeter@374
   235
  checkGraphArcList(G, 1);
kpeter@374
   236
kpeter@374
   237
  checkGraphOutArcList(G, n1, 0);
kpeter@374
   238
  checkGraphOutArcList(G, n2, 0);
kpeter@374
   239
  checkGraphOutArcList(G, n3, 1);
kpeter@374
   240
  checkGraphOutArcList(G, n4, 0);
kpeter@374
   241
kpeter@374
   242
  checkGraphInArcList(G, n1, 1);
kpeter@374
   243
  checkGraphInArcList(G, n2, 0);
kpeter@374
   244
  checkGraphInArcList(G, n3, 0);
kpeter@374
   245
  checkGraphInArcList(G, n4, 0);
kpeter@374
   246
kpeter@374
   247
  checkGraphConArcList(G, 1);
kpeter@374
   248
}
kpeter@374
   249
kpeter@374
   250
kpeter@374
   251
template <class Digraph>
kpeter@374
   252
void checkDigraphSnapshot() {
kpeter@374
   253
  TEMPLATE_DIGRAPH_TYPEDEFS(Digraph);
kpeter@374
   254
kpeter@374
   255
  Digraph G;
kpeter@374
   256
  Node n1 = G.addNode(), n2 = G.addNode(), n3 = G.addNode();
kpeter@374
   257
  Arc a1 = G.addArc(n1, n2), a2 = G.addArc(n2, n1),
kpeter@374
   258
      a3 = G.addArc(n2, n3), a4 = G.addArc(n2, n3);
alpar@1083
   259
  ::lemon::ignore_unused_variable_warning(a1,a2,a3,a4);
kpeter@374
   260
kpeter@374
   261
  typename Digraph::Snapshot snapshot(G);
kpeter@374
   262
kpeter@374
   263
  Node n = G.addNode();
kpeter@374
   264
  G.addArc(n3, n);
kpeter@374
   265
  G.addArc(n, n3);
kpeter@374
   266
kpeter@374
   267
  checkGraphNodeList(G, 4);
kpeter@374
   268
  checkGraphArcList(G, 6);
kpeter@374
   269
kpeter@374
   270
  snapshot.restore();
kpeter@374
   271
deba@228
   272
  checkGraphNodeList(G, 3);
deba@228
   273
  checkGraphArcList(G, 4);
deba@228
   274
deba@228
   275
  checkGraphOutArcList(G, n1, 1);
deba@228
   276
  checkGraphOutArcList(G, n2, 3);
deba@228
   277
  checkGraphOutArcList(G, n3, 0);
deba@228
   278
deba@228
   279
  checkGraphInArcList(G, n1, 1);
deba@228
   280
  checkGraphInArcList(G, n2, 1);
deba@228
   281
  checkGraphInArcList(G, n3, 2);
deba@228
   282
deba@228
   283
  checkGraphConArcList(G, 4);
deba@228
   284
deba@228
   285
  checkNodeIds(G);
deba@228
   286
  checkArcIds(G);
deba@228
   287
  checkGraphNodeMap(G);
deba@228
   288
  checkGraphArcMap(G);
deba@228
   289
kpeter@374
   290
  G.addNode();
kpeter@374
   291
  snapshot.save(G);
kpeter@374
   292
kpeter@374
   293
  G.addArc(G.addNode(), G.addNode());
kpeter@374
   294
kpeter@374
   295
  snapshot.restore();
kpeter@740
   296
  snapshot.save(G);
kpeter@740
   297
kpeter@740
   298
  checkGraphNodeList(G, 4);
kpeter@740
   299
  checkGraphArcList(G, 4);
kpeter@740
   300
kpeter@740
   301
  G.addArc(G.addNode(), G.addNode());
kpeter@740
   302
kpeter@740
   303
  snapshot.restore();
kpeter@374
   304
kpeter@374
   305
  checkGraphNodeList(G, 4);
kpeter@374
   306
  checkGraphArcList(G, 4);
deba@228
   307
}
deba@228
   308
deba@228
   309
void checkConcepts() {
kpeter@171
   310
  { // Checking digraph components
deba@57
   311
    checkConcept<BaseDigraphComponent, BaseDigraphComponent >();
deba@57
   312
alpar@209
   313
    checkConcept<IDableDigraphComponent<>,
deba@57
   314
      IDableDigraphComponent<> >();
deba@57
   315
alpar@209
   316
    checkConcept<IterableDigraphComponent<>,
deba@57
   317
      IterableDigraphComponent<> >();
deba@57
   318
alpar@209
   319
    checkConcept<MappableDigraphComponent<>,
deba@57
   320
      MappableDigraphComponent<> >();
deba@57
   321
  }
kpeter@171
   322
  { // Checking skeleton digraph
deba@57
   323
    checkConcept<Digraph, Digraph>();
deba@57
   324
  }
kpeter@171
   325
  { // Checking ListDigraph
kpeter@171
   326
    checkConcept<Digraph, ListDigraph>();
deba@57
   327
    checkConcept<AlterableDigraphComponent<>, ListDigraph>();
deba@57
   328
    checkConcept<ExtendableDigraphComponent<>, ListDigraph>();
deba@57
   329
    checkConcept<ClearableDigraphComponent<>, ListDigraph>();
deba@57
   330
    checkConcept<ErasableDigraphComponent<>, ListDigraph>();
kpeter@171
   331
  }
kpeter@171
   332
  { // Checking SmartDigraph
kpeter@171
   333
    checkConcept<Digraph, SmartDigraph>();
kpeter@171
   334
    checkConcept<AlterableDigraphComponent<>, SmartDigraph>();
kpeter@171
   335
    checkConcept<ExtendableDigraphComponent<>, SmartDigraph>();
kpeter@171
   336
    checkConcept<ClearableDigraphComponent<>, SmartDigraph>();
kpeter@171
   337
  }
kpeter@774
   338
  { // Checking StaticDigraph
kpeter@774
   339
    checkConcept<Digraph, StaticDigraph>();
kpeter@774
   340
    checkConcept<ClearableDigraphComponent<>, StaticDigraph>();
kpeter@774
   341
  }
gabriel@1200
   342
  { // Checking CompactDigraph
gabriel@1200
   343
    checkConcept<Digraph, CompactDigraph>();
gabriel@1200
   344
    checkConcept<ClearableDigraphComponent<>, CompactDigraph>();
gabriel@1200
   345
  }
kpeter@354
   346
  { // Checking FullDigraph
kpeter@354
   347
    checkConcept<Digraph, FullDigraph>();
kpeter@354
   348
  }
kpeter@171
   349
}
deba@57
   350
kpeter@171
   351
template <typename Digraph>
deba@228
   352
void checkDigraphValidity() {
kpeter@171
   353
  TEMPLATE_DIGRAPH_TYPEDEFS(Digraph);
kpeter@171
   354
  Digraph g;
kpeter@171
   355
kpeter@171
   356
  Node
kpeter@171
   357
    n1 = g.addNode(),
kpeter@171
   358
    n2 = g.addNode(),
kpeter@171
   359
    n3 = g.addNode();
kpeter@171
   360
kpeter@171
   361
  Arc
kpeter@171
   362
    e1 = g.addArc(n1, n2),
kpeter@171
   363
    e2 = g.addArc(n2, n3);
alpar@1083
   364
  ::lemon::ignore_unused_variable_warning(e2);
kpeter@171
   365
kpeter@171
   366
  check(g.valid(n1), "Wrong validity check");
kpeter@171
   367
  check(g.valid(e1), "Wrong validity check");
kpeter@171
   368
kpeter@171
   369
  check(!g.valid(g.nodeFromId(-1)), "Wrong validity check");
kpeter@171
   370
  check(!g.valid(g.arcFromId(-1)), "Wrong validity check");
kpeter@171
   371
}
kpeter@171
   372
kpeter@171
   373
template <typename Digraph>
deba@228
   374
void checkDigraphValidityErase() {
kpeter@171
   375
  TEMPLATE_DIGRAPH_TYPEDEFS(Digraph);
kpeter@171
   376
  Digraph g;
kpeter@171
   377
kpeter@171
   378
  Node
kpeter@171
   379
    n1 = g.addNode(),
kpeter@171
   380
    n2 = g.addNode(),
kpeter@171
   381
    n3 = g.addNode();
kpeter@171
   382
kpeter@171
   383
  Arc
kpeter@171
   384
    e1 = g.addArc(n1, n2),
kpeter@171
   385
    e2 = g.addArc(n2, n3);
kpeter@171
   386
kpeter@171
   387
  check(g.valid(n1), "Wrong validity check");
kpeter@171
   388
  check(g.valid(e1), "Wrong validity check");
kpeter@171
   389
kpeter@171
   390
  g.erase(n1);
kpeter@171
   391
kpeter@171
   392
  check(!g.valid(n1), "Wrong validity check");
kpeter@171
   393
  check(g.valid(n2), "Wrong validity check");
kpeter@171
   394
  check(g.valid(n3), "Wrong validity check");
kpeter@171
   395
  check(!g.valid(e1), "Wrong validity check");
kpeter@171
   396
  check(g.valid(e2), "Wrong validity check");
kpeter@171
   397
kpeter@171
   398
  check(!g.valid(g.nodeFromId(-1)), "Wrong validity check");
kpeter@171
   399
  check(!g.valid(g.arcFromId(-1)), "Wrong validity check");
kpeter@171
   400
}
kpeter@171
   401
gabriel@1200
   402
template <typename GR>
kpeter@774
   403
void checkStaticDigraph() {
kpeter@774
   404
  SmartDigraph g;
gabriel@1200
   405
  SmartDigraph::NodeMap<typename GR::Node> nref(g);
gabriel@1200
   406
  SmartDigraph::ArcMap<typename GR::Arc> aref(g);
alpar@877
   407
gabriel@1200
   408
  GR G;
alpar@877
   409
kpeter@774
   410
  checkGraphNodeList(G, 0);
kpeter@774
   411
  checkGraphArcList(G, 0);
kpeter@774
   412
kpeter@774
   413
  G.build(g, nref, aref);
kpeter@774
   414
kpeter@774
   415
  checkGraphNodeList(G, 0);
kpeter@774
   416
  checkGraphArcList(G, 0);
kpeter@774
   417
kpeter@774
   418
  SmartDigraph::Node
kpeter@774
   419
    n1 = g.addNode(),
kpeter@774
   420
    n2 = g.addNode(),
kpeter@774
   421
    n3 = g.addNode();
kpeter@774
   422
kpeter@774
   423
  G.build(g, nref, aref);
kpeter@774
   424
kpeter@774
   425
  checkGraphNodeList(G, 3);
kpeter@774
   426
  checkGraphArcList(G, 0);
kpeter@774
   427
kpeter@774
   428
  SmartDigraph::Arc a1 = g.addArc(n1, n2);
kpeter@774
   429
kpeter@774
   430
  G.build(g, nref, aref);
kpeter@774
   431
kpeter@774
   432
  check(G.source(aref[a1]) == nref[n1] && G.target(aref[a1]) == nref[n2],
kpeter@774
   433
        "Wrong arc or wrong references");
kpeter@774
   434
  checkGraphNodeList(G, 3);
kpeter@774
   435
  checkGraphArcList(G, 1);
kpeter@774
   436
kpeter@774
   437
  checkGraphOutArcList(G, nref[n1], 1);
kpeter@774
   438
  checkGraphOutArcList(G, nref[n2], 0);
kpeter@774
   439
  checkGraphOutArcList(G, nref[n3], 0);
kpeter@774
   440
kpeter@774
   441
  checkGraphInArcList(G, nref[n1], 0);
kpeter@774
   442
  checkGraphInArcList(G, nref[n2], 1);
kpeter@774
   443
  checkGraphInArcList(G, nref[n3], 0);
kpeter@774
   444
kpeter@774
   445
  checkGraphConArcList(G, 1);
kpeter@774
   446
kpeter@774
   447
  SmartDigraph::Arc
kpeter@774
   448
    a2 = g.addArc(n2, n1),
kpeter@774
   449
    a3 = g.addArc(n2, n3),
kpeter@774
   450
    a4 = g.addArc(n2, n3);
alpar@1085
   451
  ::lemon::ignore_unused_variable_warning(a2,a3,a4);
kpeter@774
   452
kpeter@774
   453
  digraphCopy(g, G).nodeRef(nref).run();
kpeter@774
   454
kpeter@774
   455
  checkGraphNodeList(G, 3);
kpeter@774
   456
  checkGraphArcList(G, 4);
kpeter@774
   457
kpeter@774
   458
  checkGraphOutArcList(G, nref[n1], 1);
kpeter@774
   459
  checkGraphOutArcList(G, nref[n2], 3);
kpeter@774
   460
  checkGraphOutArcList(G, nref[n3], 0);
kpeter@774
   461
kpeter@774
   462
  checkGraphInArcList(G, nref[n1], 1);
kpeter@774
   463
  checkGraphInArcList(G, nref[n2], 1);
kpeter@774
   464
  checkGraphInArcList(G, nref[n3], 2);
kpeter@774
   465
kpeter@774
   466
  checkGraphConArcList(G, 4);
kpeter@774
   467
kpeter@777
   468
  std::vector<std::pair<int,int> > arcs;
kpeter@777
   469
  arcs.push_back(std::make_pair(0,1));
kpeter@777
   470
  arcs.push_back(std::make_pair(0,2));
kpeter@777
   471
  arcs.push_back(std::make_pair(1,3));
kpeter@777
   472
  arcs.push_back(std::make_pair(1,2));
kpeter@777
   473
  arcs.push_back(std::make_pair(3,0));
kpeter@777
   474
  arcs.push_back(std::make_pair(3,3));
kpeter@777
   475
  arcs.push_back(std::make_pair(4,2));
kpeter@777
   476
  arcs.push_back(std::make_pair(4,3));
kpeter@777
   477
  arcs.push_back(std::make_pair(4,1));
kpeter@777
   478
kpeter@777
   479
  G.build(6, arcs.begin(), arcs.end());
alpar@877
   480
kpeter@777
   481
  checkGraphNodeList(G, 6);
kpeter@777
   482
  checkGraphArcList(G, 9);
kpeter@777
   483
kpeter@777
   484
  checkGraphOutArcList(G, G.node(0), 2);
kpeter@777
   485
  checkGraphOutArcList(G, G.node(1), 2);
kpeter@777
   486
  checkGraphOutArcList(G, G.node(2), 0);
kpeter@777
   487
  checkGraphOutArcList(G, G.node(3), 2);
kpeter@777
   488
  checkGraphOutArcList(G, G.node(4), 3);
kpeter@777
   489
  checkGraphOutArcList(G, G.node(5), 0);
kpeter@777
   490
kpeter@777
   491
  checkGraphInArcList(G, G.node(0), 1);
kpeter@777
   492
  checkGraphInArcList(G, G.node(1), 2);
kpeter@777
   493
  checkGraphInArcList(G, G.node(2), 3);
kpeter@777
   494
  checkGraphInArcList(G, G.node(3), 3);
kpeter@777
   495
  checkGraphInArcList(G, G.node(4), 0);
kpeter@777
   496
  checkGraphInArcList(G, G.node(5), 0);
kpeter@777
   497
kpeter@777
   498
  checkGraphConArcList(G, 9);
kpeter@777
   499
kpeter@774
   500
  checkNodeIds(G);
kpeter@774
   501
  checkArcIds(G);
kpeter@774
   502
  checkGraphNodeMap(G);
kpeter@774
   503
  checkGraphArcMap(G);
alpar@877
   504
kpeter@776
   505
  int n = G.nodeNum();
kpeter@776
   506
  int m = G.arcNum();
kpeter@776
   507
  check(G.index(G.node(n-1)) == n-1, "Wrong index.");
kpeter@776
   508
  check(G.index(G.arc(m-1)) == m-1, "Wrong index.");
kpeter@774
   509
}
kpeter@774
   510
alpar@375
   511
void checkFullDigraph(int num) {
alpar@375
   512
  typedef FullDigraph Digraph;
alpar@375
   513
  DIGRAPH_TYPEDEFS(Digraph);
kpeter@737
   514
alpar@375
   515
  Digraph G(num);
kpeter@737
   516
  check(G.nodeNum() == num && G.arcNum() == num * num, "Wrong size");
kpeter@737
   517
kpeter@737
   518
  G.resize(num);
kpeter@737
   519
  check(G.nodeNum() == num && G.arcNum() == num * num, "Wrong size");
alpar@375
   520
alpar@375
   521
  checkGraphNodeList(G, num);
alpar@375
   522
  checkGraphArcList(G, num * num);
alpar@375
   523
alpar@375
   524
  for (NodeIt n(G); n != INVALID; ++n) {
alpar@375
   525
    checkGraphOutArcList(G, n, num);
alpar@375
   526
    checkGraphInArcList(G, n, num);
alpar@375
   527
  }
alpar@375
   528
alpar@375
   529
  checkGraphConArcList(G, num * num);
alpar@375
   530
alpar@375
   531
  checkNodeIds(G);
alpar@375
   532
  checkArcIds(G);
alpar@375
   533
  checkGraphNodeMap(G);
alpar@375
   534
  checkGraphArcMap(G);
alpar@375
   535
alpar@375
   536
  for (int i = 0; i < G.nodeNum(); ++i) {
alpar@375
   537
    check(G.index(G(i)) == i, "Wrong index");
alpar@375
   538
  }
alpar@375
   539
alpar@375
   540
  for (NodeIt s(G); s != INVALID; ++s) {
alpar@375
   541
    for (NodeIt t(G); t != INVALID; ++t) {
alpar@375
   542
      Arc a = G.arc(s, t);
alpar@375
   543
      check(G.source(a) == s && G.target(a) == t, "Wrong arc lookup");
alpar@375
   544
    }
alpar@375
   545
  }
alpar@375
   546
}
alpar@375
   547
deba@228
   548
void checkDigraphs() {
kpeter@171
   549
  { // Checking ListDigraph
kpeter@374
   550
    checkDigraphBuild<ListDigraph>();
kpeter@374
   551
    checkDigraphSplit<ListDigraph>();
kpeter@374
   552
    checkDigraphAlter<ListDigraph>();
kpeter@374
   553
    checkDigraphErase<ListDigraph>();
kpeter@374
   554
    checkDigraphSnapshot<ListDigraph>();
deba@228
   555
    checkDigraphValidityErase<ListDigraph>();
deba@57
   556
  }
kpeter@171
   557
  { // Checking SmartDigraph
kpeter@374
   558
    checkDigraphBuild<SmartDigraph>();
kpeter@374
   559
    checkDigraphSplit<SmartDigraph>();
kpeter@374
   560
    checkDigraphSnapshot<SmartDigraph>();
deba@228
   561
    checkDigraphValidity<SmartDigraph>();
kpeter@171
   562
  }
kpeter@774
   563
  { // Checking StaticDigraph
gabriel@1200
   564
    checkStaticDigraph<StaticDigraph>();
gabriel@1200
   565
    checkStaticDigraph<CompactDigraph>();
kpeter@774
   566
  }
deba@353
   567
  { // Checking FullDigraph
deba@353
   568
    checkFullDigraph(8);
deba@353
   569
  }
kpeter@171
   570
}
deba@57
   571
kpeter@171
   572
int main() {
deba@228
   573
  checkDigraphs();
deba@228
   574
  checkConcepts();
deba@57
   575
  return 0;
deba@57
   576
}