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