test/digraph_test.cc
author Peter Kovacs <kpeter@inf.elte.hu>
Fri, 17 Apr 2009 18:04:36 +0200
changeset 609 e6927fe719e6
parent 375 2d87dbd7f8c8
child 736 2e20aad15754
child 774 f4b5c2d5449d
child 997 761fe0846f49
permissions -rw-r--r--
Support >= and <= constraints in NetworkSimplex (#219, #234)

By default the same inequality constraints are supported as by
Circulation (the GEQ form), but the LEQ form can also be selected
using the problemType() function.

The documentation of the min. cost flow module is reworked and
extended with important notes and explanations about the different
variants of the problem and about the dual solution and optimality
conditions.
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
}