test/edge_set_test.cc
author Peter Kovacs <kpeter@inf.elte.hu>
Fri, 13 Nov 2009 00:24:39 +0100
changeset 819 d93490b861e9
parent 468 68fe66e2b34a
child 877 141f9c0db4a3
child 963 761fe0846f49
permissions -rw-r--r--
Adds tests for the new MCF algorithms (#180)
deba@468
     1
/* -*- mode: C++; indent-tabs-mode: nil; -*-
deba@468
     2
 *
deba@468
     3
 * This file is a part of LEMON, a generic C++ optimization library.
deba@468
     4
 *
deba@468
     5
 * Copyright (C) 2003-2008
deba@468
     6
 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
deba@468
     7
 * (Egervary Research Group on Combinatorial Optimization, EGRES).
deba@468
     8
 *
deba@468
     9
 * Permission to use, modify and distribute this software is granted
deba@468
    10
 * provided that this copyright notice appears in all copies. For
deba@468
    11
 * precise terms see the accompanying LICENSE file.
deba@468
    12
 *
deba@468
    13
 * This software is provided "AS IS" with no warranty of any kind,
deba@468
    14
 * express or implied, and with no claim as to its suitability for any
deba@468
    15
 * purpose.
deba@468
    16
 *
deba@468
    17
 */
deba@468
    18
deba@468
    19
#include <iostream>
deba@468
    20
#include <vector>
deba@468
    21
deba@468
    22
#include <lemon/concepts/digraph.h>
deba@468
    23
#include <lemon/concepts/graph.h>
deba@468
    24
#include <lemon/concept_check.h>
deba@468
    25
deba@468
    26
#include <lemon/list_graph.h>
deba@468
    27
deba@468
    28
#include <lemon/edge_set.h>
deba@468
    29
deba@468
    30
#include "graph_test.h"
deba@468
    31
#include "test_tools.h"
deba@468
    32
deba@468
    33
using namespace lemon;
deba@468
    34
deba@468
    35
void checkSmartArcSet() {
deba@512
    36
  checkConcept<concepts::Digraph, SmartArcSet<ListDigraph> >();
deba@468
    37
deba@468
    38
  typedef ListDigraph Digraph;
deba@468
    39
  typedef SmartArcSet<Digraph> ArcSet;
deba@468
    40
deba@468
    41
  Digraph digraph;
deba@468
    42
  Digraph::Node
deba@468
    43
    n1 = digraph.addNode(),
deba@468
    44
    n2 = digraph.addNode();
deba@468
    45
deba@468
    46
  Digraph::Arc ga1 = digraph.addArc(n1, n2);
deba@468
    47
deba@468
    48
  ArcSet arc_set(digraph);
deba@468
    49
deba@468
    50
  Digraph::Arc ga2 = digraph.addArc(n2, n1);
deba@468
    51
deba@468
    52
  checkGraphNodeList(arc_set, 2);
deba@468
    53
  checkGraphArcList(arc_set, 0);
deba@468
    54
deba@468
    55
  Digraph::Node
deba@468
    56
    n3 = digraph.addNode();
deba@468
    57
  checkGraphNodeList(arc_set, 3);
deba@468
    58
  checkGraphArcList(arc_set, 0);
deba@468
    59
deba@468
    60
  ArcSet::Arc a1 = arc_set.addArc(n1, n2);
deba@468
    61
  check(arc_set.source(a1) == n1 && arc_set.target(a1) == n2, "Wrong arc");
deba@468
    62
  checkGraphNodeList(arc_set, 3);
deba@468
    63
  checkGraphArcList(arc_set, 1);
deba@468
    64
deba@468
    65
  checkGraphOutArcList(arc_set, n1, 1);
deba@468
    66
  checkGraphOutArcList(arc_set, n2, 0);
deba@468
    67
  checkGraphOutArcList(arc_set, n3, 0);
deba@468
    68
deba@468
    69
  checkGraphInArcList(arc_set, n1, 0);
deba@468
    70
  checkGraphInArcList(arc_set, n2, 1);
deba@468
    71
  checkGraphInArcList(arc_set, n3, 0);
deba@468
    72
deba@468
    73
  checkGraphConArcList(arc_set, 1);
deba@468
    74
deba@468
    75
  ArcSet::Arc a2 = arc_set.addArc(n2, n1),
deba@468
    76
    a3 = arc_set.addArc(n2, n3),
deba@468
    77
    a4 = arc_set.addArc(n2, n3);
deba@468
    78
  checkGraphNodeList(arc_set, 3);
deba@468
    79
  checkGraphArcList(arc_set, 4);
deba@468
    80
deba@468
    81
  checkGraphOutArcList(arc_set, n1, 1);
deba@468
    82
  checkGraphOutArcList(arc_set, n2, 3);
deba@468
    83
  checkGraphOutArcList(arc_set, n3, 0);
deba@468
    84
deba@468
    85
  checkGraphInArcList(arc_set, n1, 1);
deba@468
    86
  checkGraphInArcList(arc_set, n2, 1);
deba@468
    87
  checkGraphInArcList(arc_set, n3, 2);
deba@468
    88
deba@468
    89
  checkGraphConArcList(arc_set, 4);
deba@468
    90
deba@468
    91
  checkNodeIds(arc_set);
deba@468
    92
  checkArcIds(arc_set);
deba@468
    93
  checkGraphNodeMap(arc_set);
deba@468
    94
  checkGraphArcMap(arc_set);
deba@468
    95
deba@468
    96
  check(arc_set.valid(), "Wrong validity");
deba@468
    97
  digraph.erase(n1);
deba@468
    98
  check(!arc_set.valid(), "Wrong validity");
deba@468
    99
}
deba@468
   100
deba@468
   101
void checkListArcSet() {
deba@512
   102
  checkConcept<concepts::Digraph, SmartArcSet<ListDigraph> >();
deba@468
   103
deba@468
   104
  typedef ListDigraph Digraph;
deba@468
   105
  typedef ListArcSet<Digraph> ArcSet;
deba@468
   106
deba@468
   107
  Digraph digraph;
deba@468
   108
  Digraph::Node
deba@468
   109
    n1 = digraph.addNode(),
deba@468
   110
    n2 = digraph.addNode();
deba@468
   111
deba@468
   112
  Digraph::Arc ga1 = digraph.addArc(n1, n2);
deba@468
   113
deba@468
   114
  ArcSet arc_set(digraph);
deba@468
   115
deba@468
   116
  Digraph::Arc ga2 = digraph.addArc(n2, n1);
deba@468
   117
deba@468
   118
  checkGraphNodeList(arc_set, 2);
deba@468
   119
  checkGraphArcList(arc_set, 0);
deba@468
   120
deba@468
   121
  Digraph::Node
deba@468
   122
    n3 = digraph.addNode();
deba@468
   123
  checkGraphNodeList(arc_set, 3);
deba@468
   124
  checkGraphArcList(arc_set, 0);
deba@468
   125
deba@468
   126
  ArcSet::Arc a1 = arc_set.addArc(n1, n2);
deba@468
   127
  check(arc_set.source(a1) == n1 && arc_set.target(a1) == n2, "Wrong arc");
deba@468
   128
  checkGraphNodeList(arc_set, 3);
deba@468
   129
  checkGraphArcList(arc_set, 1);
deba@468
   130
deba@468
   131
  checkGraphOutArcList(arc_set, n1, 1);
deba@468
   132
  checkGraphOutArcList(arc_set, n2, 0);
deba@468
   133
  checkGraphOutArcList(arc_set, n3, 0);
deba@468
   134
deba@468
   135
  checkGraphInArcList(arc_set, n1, 0);
deba@468
   136
  checkGraphInArcList(arc_set, n2, 1);
deba@468
   137
  checkGraphInArcList(arc_set, n3, 0);
deba@468
   138
deba@468
   139
  checkGraphConArcList(arc_set, 1);
deba@468
   140
deba@468
   141
  ArcSet::Arc a2 = arc_set.addArc(n2, n1),
deba@468
   142
    a3 = arc_set.addArc(n2, n3),
deba@468
   143
    a4 = arc_set.addArc(n2, n3);
deba@468
   144
  checkGraphNodeList(arc_set, 3);
deba@468
   145
  checkGraphArcList(arc_set, 4);
deba@468
   146
deba@468
   147
  checkGraphOutArcList(arc_set, n1, 1);
deba@468
   148
  checkGraphOutArcList(arc_set, n2, 3);
deba@468
   149
  checkGraphOutArcList(arc_set, n3, 0);
deba@468
   150
deba@468
   151
  checkGraphInArcList(arc_set, n1, 1);
deba@468
   152
  checkGraphInArcList(arc_set, n2, 1);
deba@468
   153
  checkGraphInArcList(arc_set, n3, 2);
deba@468
   154
deba@468
   155
  checkGraphConArcList(arc_set, 4);
deba@468
   156
deba@468
   157
  checkNodeIds(arc_set);
deba@468
   158
  checkArcIds(arc_set);
deba@468
   159
  checkGraphNodeMap(arc_set);
deba@468
   160
  checkGraphArcMap(arc_set);
deba@468
   161
deba@468
   162
  digraph.erase(n1);
deba@468
   163
deba@468
   164
  checkGraphNodeList(arc_set, 2);
deba@468
   165
  checkGraphArcList(arc_set, 2);
deba@468
   166
deba@468
   167
  checkGraphOutArcList(arc_set, n2, 2);
deba@468
   168
  checkGraphOutArcList(arc_set, n3, 0);
deba@468
   169
deba@468
   170
  checkGraphInArcList(arc_set, n2, 0);
deba@468
   171
  checkGraphInArcList(arc_set, n3, 2);
deba@468
   172
deba@468
   173
  checkNodeIds(arc_set);
deba@468
   174
  checkArcIds(arc_set);
deba@468
   175
  checkGraphNodeMap(arc_set);
deba@468
   176
  checkGraphArcMap(arc_set);
deba@468
   177
deba@468
   178
  checkGraphConArcList(arc_set, 2);
deba@468
   179
}
deba@468
   180
deba@468
   181
void checkSmartEdgeSet() {
deba@512
   182
  checkConcept<concepts::Digraph, SmartEdgeSet<ListDigraph> >();
deba@468
   183
deba@468
   184
  typedef ListDigraph Digraph;
deba@468
   185
  typedef SmartEdgeSet<Digraph> EdgeSet;
deba@468
   186
deba@468
   187
  Digraph digraph;
deba@468
   188
  Digraph::Node
deba@468
   189
    n1 = digraph.addNode(),
deba@468
   190
    n2 = digraph.addNode();
deba@468
   191
deba@468
   192
  Digraph::Arc ga1 = digraph.addArc(n1, n2);
deba@468
   193
deba@468
   194
  EdgeSet edge_set(digraph);
deba@468
   195
deba@468
   196
  Digraph::Arc ga2 = digraph.addArc(n2, n1);
deba@468
   197
deba@468
   198
  checkGraphNodeList(edge_set, 2);
deba@468
   199
  checkGraphArcList(edge_set, 0);
deba@468
   200
  checkGraphEdgeList(edge_set, 0);
deba@468
   201
deba@468
   202
  Digraph::Node
deba@468
   203
    n3 = digraph.addNode();
deba@468
   204
  checkGraphNodeList(edge_set, 3);
deba@468
   205
  checkGraphArcList(edge_set, 0);
deba@468
   206
  checkGraphEdgeList(edge_set, 0);
deba@468
   207
deba@468
   208
  EdgeSet::Edge e1 = edge_set.addEdge(n1, n2);
deba@468
   209
  check((edge_set.u(e1) == n1 && edge_set.v(e1) == n2) ||
deba@468
   210
        (edge_set.v(e1) == n1 && edge_set.u(e1) == n2), "Wrong edge");
deba@468
   211
  checkGraphNodeList(edge_set, 3);
deba@468
   212
  checkGraphArcList(edge_set, 2);
deba@468
   213
  checkGraphEdgeList(edge_set, 1);
deba@468
   214
deba@468
   215
  checkGraphOutArcList(edge_set, n1, 1);
deba@468
   216
  checkGraphOutArcList(edge_set, n2, 1);
deba@468
   217
  checkGraphOutArcList(edge_set, n3, 0);
deba@468
   218
deba@468
   219
  checkGraphInArcList(edge_set, n1, 1);
deba@468
   220
  checkGraphInArcList(edge_set, n2, 1);
deba@468
   221
  checkGraphInArcList(edge_set, n3, 0);
deba@468
   222
deba@468
   223
  checkGraphIncEdgeList(edge_set, n1, 1);
deba@468
   224
  checkGraphIncEdgeList(edge_set, n2, 1);
deba@468
   225
  checkGraphIncEdgeList(edge_set, n3, 0);
deba@468
   226
deba@468
   227
  checkGraphConEdgeList(edge_set, 1);
deba@468
   228
  checkGraphConArcList(edge_set, 2);
deba@468
   229
deba@468
   230
  EdgeSet::Edge e2 = edge_set.addEdge(n2, n1),
deba@468
   231
    e3 = edge_set.addEdge(n2, n3),
deba@468
   232
    e4 = edge_set.addEdge(n2, n3);
deba@468
   233
  checkGraphNodeList(edge_set, 3);
deba@468
   234
  checkGraphEdgeList(edge_set, 4);
deba@468
   235
deba@468
   236
  checkGraphOutArcList(edge_set, n1, 2);
deba@468
   237
  checkGraphOutArcList(edge_set, n2, 4);
deba@468
   238
  checkGraphOutArcList(edge_set, n3, 2);
deba@468
   239
deba@468
   240
  checkGraphInArcList(edge_set, n1, 2);
deba@468
   241
  checkGraphInArcList(edge_set, n2, 4);
deba@468
   242
  checkGraphInArcList(edge_set, n3, 2);
deba@468
   243
deba@468
   244
  checkGraphIncEdgeList(edge_set, n1, 2);
deba@468
   245
  checkGraphIncEdgeList(edge_set, n2, 4);
deba@468
   246
  checkGraphIncEdgeList(edge_set, n3, 2);
deba@468
   247
deba@468
   248
  checkGraphConEdgeList(edge_set, 4);
deba@468
   249
  checkGraphConArcList(edge_set, 8);
deba@468
   250
deba@468
   251
  checkArcDirections(edge_set);
deba@468
   252
deba@468
   253
  checkNodeIds(edge_set);
deba@468
   254
  checkArcIds(edge_set);
deba@468
   255
  checkEdgeIds(edge_set);
deba@468
   256
  checkGraphNodeMap(edge_set);
deba@468
   257
  checkGraphArcMap(edge_set);
deba@468
   258
  checkGraphEdgeMap(edge_set);
deba@468
   259
deba@468
   260
  check(edge_set.valid(), "Wrong validity");
deba@468
   261
  digraph.erase(n1);
deba@468
   262
  check(!edge_set.valid(), "Wrong validity");
deba@468
   263
}
deba@468
   264
deba@468
   265
void checkListEdgeSet() {
deba@512
   266
  checkConcept<concepts::Digraph, ListEdgeSet<ListDigraph> >();
deba@468
   267
deba@468
   268
  typedef ListDigraph Digraph;
deba@468
   269
  typedef ListEdgeSet<Digraph> EdgeSet;
deba@468
   270
deba@468
   271
  Digraph digraph;
deba@468
   272
  Digraph::Node
deba@468
   273
    n1 = digraph.addNode(),
deba@468
   274
    n2 = digraph.addNode();
deba@468
   275
deba@468
   276
  Digraph::Arc ga1 = digraph.addArc(n1, n2);
deba@468
   277
deba@468
   278
  EdgeSet edge_set(digraph);
deba@468
   279
deba@468
   280
  Digraph::Arc ga2 = digraph.addArc(n2, n1);
deba@468
   281
deba@468
   282
  checkGraphNodeList(edge_set, 2);
deba@468
   283
  checkGraphArcList(edge_set, 0);
deba@468
   284
  checkGraphEdgeList(edge_set, 0);
deba@468
   285
deba@468
   286
  Digraph::Node
deba@468
   287
    n3 = digraph.addNode();
deba@468
   288
  checkGraphNodeList(edge_set, 3);
deba@468
   289
  checkGraphArcList(edge_set, 0);
deba@468
   290
  checkGraphEdgeList(edge_set, 0);
deba@468
   291
deba@468
   292
  EdgeSet::Edge e1 = edge_set.addEdge(n1, n2);
deba@468
   293
  check((edge_set.u(e1) == n1 && edge_set.v(e1) == n2) ||
deba@468
   294
        (edge_set.v(e1) == n1 && edge_set.u(e1) == n2), "Wrong edge");
deba@468
   295
  checkGraphNodeList(edge_set, 3);
deba@468
   296
  checkGraphArcList(edge_set, 2);
deba@468
   297
  checkGraphEdgeList(edge_set, 1);
deba@468
   298
deba@468
   299
  checkGraphOutArcList(edge_set, n1, 1);
deba@468
   300
  checkGraphOutArcList(edge_set, n2, 1);
deba@468
   301
  checkGraphOutArcList(edge_set, n3, 0);
deba@468
   302
deba@468
   303
  checkGraphInArcList(edge_set, n1, 1);
deba@468
   304
  checkGraphInArcList(edge_set, n2, 1);
deba@468
   305
  checkGraphInArcList(edge_set, n3, 0);
deba@468
   306
deba@468
   307
  checkGraphIncEdgeList(edge_set, n1, 1);
deba@468
   308
  checkGraphIncEdgeList(edge_set, n2, 1);
deba@468
   309
  checkGraphIncEdgeList(edge_set, n3, 0);
deba@468
   310
deba@468
   311
  checkGraphConEdgeList(edge_set, 1);
deba@468
   312
  checkGraphConArcList(edge_set, 2);
deba@468
   313
deba@468
   314
  EdgeSet::Edge e2 = edge_set.addEdge(n2, n1),
deba@468
   315
    e3 = edge_set.addEdge(n2, n3),
deba@468
   316
    e4 = edge_set.addEdge(n2, n3);
deba@468
   317
  checkGraphNodeList(edge_set, 3);
deba@468
   318
  checkGraphEdgeList(edge_set, 4);
deba@468
   319
deba@468
   320
  checkGraphOutArcList(edge_set, n1, 2);
deba@468
   321
  checkGraphOutArcList(edge_set, n2, 4);
deba@468
   322
  checkGraphOutArcList(edge_set, n3, 2);
deba@468
   323
deba@468
   324
  checkGraphInArcList(edge_set, n1, 2);
deba@468
   325
  checkGraphInArcList(edge_set, n2, 4);
deba@468
   326
  checkGraphInArcList(edge_set, n3, 2);
deba@468
   327
deba@468
   328
  checkGraphIncEdgeList(edge_set, n1, 2);
deba@468
   329
  checkGraphIncEdgeList(edge_set, n2, 4);
deba@468
   330
  checkGraphIncEdgeList(edge_set, n3, 2);
deba@468
   331
deba@468
   332
  checkGraphConEdgeList(edge_set, 4);
deba@468
   333
  checkGraphConArcList(edge_set, 8);
deba@468
   334
deba@468
   335
  checkArcDirections(edge_set);
deba@468
   336
deba@468
   337
  checkNodeIds(edge_set);
deba@468
   338
  checkArcIds(edge_set);
deba@468
   339
  checkEdgeIds(edge_set);
deba@468
   340
  checkGraphNodeMap(edge_set);
deba@468
   341
  checkGraphArcMap(edge_set);
deba@468
   342
  checkGraphEdgeMap(edge_set);
deba@468
   343
deba@468
   344
  digraph.erase(n1);
deba@468
   345
deba@468
   346
  checkGraphNodeList(edge_set, 2);
deba@468
   347
  checkGraphArcList(edge_set, 4);
deba@468
   348
  checkGraphEdgeList(edge_set, 2);
deba@468
   349
deba@468
   350
  checkGraphOutArcList(edge_set, n2, 2);
deba@468
   351
  checkGraphOutArcList(edge_set, n3, 2);
deba@468
   352
deba@468
   353
  checkGraphInArcList(edge_set, n2, 2);
deba@468
   354
  checkGraphInArcList(edge_set, n3, 2);
deba@468
   355
deba@468
   356
  checkGraphIncEdgeList(edge_set, n2, 2);
deba@468
   357
  checkGraphIncEdgeList(edge_set, n3, 2);
deba@468
   358
deba@468
   359
  checkNodeIds(edge_set);
deba@468
   360
  checkArcIds(edge_set);
deba@468
   361
  checkEdgeIds(edge_set);
deba@468
   362
  checkGraphNodeMap(edge_set);
deba@468
   363
  checkGraphArcMap(edge_set);
deba@468
   364
  checkGraphEdgeMap(edge_set);
deba@468
   365
deba@468
   366
  checkGraphConEdgeList(edge_set, 2);
deba@468
   367
  checkGraphConArcList(edge_set, 4);
deba@468
   368
deba@468
   369
}
deba@468
   370
deba@468
   371
deba@468
   372
int main() {
deba@468
   373
deba@468
   374
  checkSmartArcSet();
deba@468
   375
  checkListArcSet();
deba@468
   376
  checkSmartEdgeSet();
deba@468
   377
  checkListEdgeSet();
deba@468
   378
deba@468
   379
  return 0;
deba@468
   380
}