test/adaptors_test.cc
author Balazs Dezso <deba@google.com>
Sat, 27 Oct 2018 13:00:48 +0200
changeset 1203 8c567e298d7f
parent 1092 dceba191c00d
permissions -rw-r--r--
Paremeter to stop matching calculation when only single node is unmatched
deba@416
     1
/* -*- mode: C++; indent-tabs-mode: nil; -*-
deba@414
     2
 *
deba@416
     3
 * This file is a part of LEMON, a generic C++ optimization library.
deba@414
     4
 *
alpar@1092
     5
 * Copyright (C) 2003-2013
deba@414
     6
 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
deba@414
     7
 * (Egervary Research Group on Combinatorial Optimization, EGRES).
deba@414
     8
 *
deba@414
     9
 * Permission to use, modify and distribute this software is granted
deba@414
    10
 * provided that this copyright notice appears in all copies. For
deba@414
    11
 * precise terms see the accompanying LICENSE file.
deba@414
    12
 *
deba@414
    13
 * This software is provided "AS IS" with no warranty of any kind,
deba@414
    14
 * express or implied, and with no claim as to its suitability for any
deba@414
    15
 * purpose.
deba@414
    16
 *
deba@414
    17
 */
deba@414
    18
kpeter@463
    19
#include <iostream>
kpeter@463
    20
#include <limits>
deba@414
    21
kpeter@463
    22
#include <lemon/list_graph.h>
kpeter@463
    23
#include <lemon/grid_graph.h>
deba@414
    24
#include <lemon/bfs.h>
deba@414
    25
#include <lemon/path.h>
deba@414
    26
kpeter@463
    27
#include <lemon/concepts/digraph.h>
kpeter@463
    28
#include <lemon/concepts/graph.h>
kpeter@463
    29
#include <lemon/concepts/graph_components.h>
kpeter@463
    30
#include <lemon/concepts/maps.h>
kpeter@463
    31
#include <lemon/concept_check.h>
kpeter@463
    32
kpeter@463
    33
#include <lemon/adaptors.h>
kpeter@463
    34
kpeter@463
    35
#include "test/test_tools.h"
kpeter@463
    36
#include "test/graph_test.h"
deba@414
    37
deba@414
    38
using namespace lemon;
deba@414
    39
deba@416
    40
void checkReverseDigraph() {
kpeter@463
    41
  // Check concepts
deba@416
    42
  checkConcept<concepts::Digraph, ReverseDigraph<concepts::Digraph> >();
kpeter@463
    43
  checkConcept<concepts::Digraph, ReverseDigraph<ListDigraph> >();
kpeter@463
    44
  checkConcept<concepts::AlterableDigraphComponent<>,
kpeter@463
    45
               ReverseDigraph<ListDigraph> >();
kpeter@463
    46
  checkConcept<concepts::ExtendableDigraphComponent<>,
kpeter@463
    47
               ReverseDigraph<ListDigraph> >();
kpeter@463
    48
  checkConcept<concepts::ErasableDigraphComponent<>,
kpeter@463
    49
               ReverseDigraph<ListDigraph> >();
kpeter@463
    50
  checkConcept<concepts::ClearableDigraphComponent<>,
kpeter@463
    51
               ReverseDigraph<ListDigraph> >();
deba@414
    52
kpeter@463
    53
  // Create a digraph and an adaptor
deba@414
    54
  typedef ListDigraph Digraph;
deba@416
    55
  typedef ReverseDigraph<Digraph> Adaptor;
deba@414
    56
deba@414
    57
  Digraph digraph;
deba@414
    58
  Adaptor adaptor(digraph);
deba@414
    59
kpeter@463
    60
  // Add nodes and arcs to the original digraph
deba@414
    61
  Digraph::Node n1 = digraph.addNode();
deba@414
    62
  Digraph::Node n2 = digraph.addNode();
deba@414
    63
  Digraph::Node n3 = digraph.addNode();
deba@414
    64
deba@414
    65
  Digraph::Arc a1 = digraph.addArc(n1, n2);
deba@414
    66
  Digraph::Arc a2 = digraph.addArc(n1, n3);
deba@414
    67
  Digraph::Arc a3 = digraph.addArc(n2, n3);
alpar@1083
    68
  ::lemon::ignore_unused_variable_warning(a3);
deba@416
    69
kpeter@463
    70
  // Check the adaptor
deba@414
    71
  checkGraphNodeList(adaptor, 3);
deba@414
    72
  checkGraphArcList(adaptor, 3);
deba@414
    73
  checkGraphConArcList(adaptor, 3);
deba@414
    74
deba@414
    75
  checkGraphOutArcList(adaptor, n1, 0);
deba@414
    76
  checkGraphOutArcList(adaptor, n2, 1);
deba@414
    77
  checkGraphOutArcList(adaptor, n3, 2);
deba@414
    78
deba@414
    79
  checkGraphInArcList(adaptor, n1, 2);
deba@414
    80
  checkGraphInArcList(adaptor, n2, 1);
deba@414
    81
  checkGraphInArcList(adaptor, n3, 0);
deba@414
    82
deba@414
    83
  checkNodeIds(adaptor);
deba@414
    84
  checkArcIds(adaptor);
deba@414
    85
deba@414
    86
  checkGraphNodeMap(adaptor);
deba@414
    87
  checkGraphArcMap(adaptor);
deba@414
    88
kpeter@463
    89
  // Check the orientation of the arcs
deba@414
    90
  for (Adaptor::ArcIt a(adaptor); a != INVALID; ++a) {
deba@414
    91
    check(adaptor.source(a) == digraph.target(a), "Wrong reverse");
deba@414
    92
    check(adaptor.target(a) == digraph.source(a), "Wrong reverse");
deba@414
    93
  }
kpeter@463
    94
kpeter@463
    95
  // Add and erase nodes and arcs in the digraph through the adaptor
kpeter@463
    96
  Adaptor::Node n4 = adaptor.addNode();
kpeter@463
    97
kpeter@463
    98
  Adaptor::Arc a4 = adaptor.addArc(n4, n3);
kpeter@463
    99
  Adaptor::Arc a5 = adaptor.addArc(n2, n4);
kpeter@463
   100
  Adaptor::Arc a6 = adaptor.addArc(n2, n4);
kpeter@463
   101
  Adaptor::Arc a7 = adaptor.addArc(n1, n4);
kpeter@463
   102
  Adaptor::Arc a8 = adaptor.addArc(n1, n2);
alpar@1083
   103
  ::lemon::ignore_unused_variable_warning(a6,a7,a8);
kpeter@463
   104
kpeter@463
   105
  adaptor.erase(a1);
kpeter@463
   106
  adaptor.erase(n3);
kpeter@463
   107
kpeter@463
   108
  // Check the adaptor
kpeter@463
   109
  checkGraphNodeList(adaptor, 3);
kpeter@463
   110
  checkGraphArcList(adaptor, 4);
kpeter@463
   111
  checkGraphConArcList(adaptor, 4);
kpeter@463
   112
kpeter@463
   113
  checkGraphOutArcList(adaptor, n1, 2);
kpeter@463
   114
  checkGraphOutArcList(adaptor, n2, 2);
kpeter@463
   115
  checkGraphOutArcList(adaptor, n4, 0);
kpeter@463
   116
kpeter@463
   117
  checkGraphInArcList(adaptor, n1, 0);
kpeter@463
   118
  checkGraphInArcList(adaptor, n2, 1);
kpeter@463
   119
  checkGraphInArcList(adaptor, n4, 3);
kpeter@463
   120
kpeter@463
   121
  checkNodeIds(adaptor);
kpeter@463
   122
  checkArcIds(adaptor);
kpeter@463
   123
kpeter@463
   124
  checkGraphNodeMap(adaptor);
kpeter@463
   125
  checkGraphArcMap(adaptor);
kpeter@463
   126
kpeter@463
   127
  // Check the digraph
kpeter@463
   128
  checkGraphNodeList(digraph, 3);
kpeter@463
   129
  checkGraphArcList(digraph, 4);
kpeter@463
   130
  checkGraphConArcList(digraph, 4);
kpeter@463
   131
kpeter@463
   132
  checkGraphOutArcList(digraph, n1, 0);
kpeter@463
   133
  checkGraphOutArcList(digraph, n2, 1);
kpeter@463
   134
  checkGraphOutArcList(digraph, n4, 3);
kpeter@463
   135
kpeter@463
   136
  checkGraphInArcList(digraph, n1, 2);
kpeter@463
   137
  checkGraphInArcList(digraph, n2, 2);
kpeter@463
   138
  checkGraphInArcList(digraph, n4, 0);
kpeter@463
   139
kpeter@463
   140
  checkNodeIds(digraph);
kpeter@463
   141
  checkArcIds(digraph);
kpeter@463
   142
kpeter@463
   143
  checkGraphNodeMap(digraph);
kpeter@463
   144
  checkGraphArcMap(digraph);
kpeter@463
   145
kpeter@463
   146
  // Check the conversion of nodes and arcs
kpeter@463
   147
  Digraph::Node nd = n4;
kpeter@1197
   148
  ::lemon::ignore_unused_variable_warning(nd);
kpeter@463
   149
  nd = n4;
kpeter@463
   150
  Adaptor::Node na = n1;
kpeter@1197
   151
  ::lemon::ignore_unused_variable_warning(na);
kpeter@463
   152
  na = n2;
kpeter@463
   153
  Digraph::Arc ad = a4;
kpeter@1197
   154
  ::lemon::ignore_unused_variable_warning(ad);
kpeter@463
   155
  ad = a5;
kpeter@463
   156
  Adaptor::Arc aa = a1;
kpeter@1197
   157
  ::lemon::ignore_unused_variable_warning(aa);
kpeter@463
   158
  aa = a2;
deba@414
   159
}
deba@414
   160
deba@416
   161
void checkSubDigraph() {
kpeter@463
   162
  // Check concepts
kpeter@463
   163
  checkConcept<concepts::Digraph, SubDigraph<concepts::Digraph> >();
kpeter@463
   164
  checkConcept<concepts::Digraph, SubDigraph<ListDigraph> >();
kpeter@463
   165
  checkConcept<concepts::AlterableDigraphComponent<>,
kpeter@463
   166
               SubDigraph<ListDigraph> >();
kpeter@463
   167
  checkConcept<concepts::ExtendableDigraphComponent<>,
kpeter@463
   168
               SubDigraph<ListDigraph> >();
kpeter@463
   169
  checkConcept<concepts::ErasableDigraphComponent<>,
kpeter@463
   170
               SubDigraph<ListDigraph> >();
kpeter@463
   171
  checkConcept<concepts::ClearableDigraphComponent<>,
kpeter@463
   172
               SubDigraph<ListDigraph> >();
deba@414
   173
kpeter@463
   174
  // Create a digraph and an adaptor
deba@414
   175
  typedef ListDigraph Digraph;
deba@414
   176
  typedef Digraph::NodeMap<bool> NodeFilter;
deba@414
   177
  typedef Digraph::ArcMap<bool> ArcFilter;
deba@416
   178
  typedef SubDigraph<Digraph, NodeFilter, ArcFilter> Adaptor;
deba@414
   179
deba@414
   180
  Digraph digraph;
deba@414
   181
  NodeFilter node_filter(digraph);
deba@414
   182
  ArcFilter arc_filter(digraph);
deba@414
   183
  Adaptor adaptor(digraph, node_filter, arc_filter);
deba@414
   184
kpeter@463
   185
  // Add nodes and arcs to the original digraph and the adaptor
deba@414
   186
  Digraph::Node n1 = digraph.addNode();
deba@414
   187
  Digraph::Node n2 = digraph.addNode();
kpeter@463
   188
  Adaptor::Node n3 = adaptor.addNode();
kpeter@463
   189
kpeter@463
   190
  node_filter[n1] = node_filter[n2] = node_filter[n3] = true;
deba@414
   191
deba@414
   192
  Digraph::Arc a1 = digraph.addArc(n1, n2);
deba@414
   193
  Digraph::Arc a2 = digraph.addArc(n1, n3);
kpeter@463
   194
  Adaptor::Arc a3 = adaptor.addArc(n2, n3);
deba@414
   195
deba@414
   196
  arc_filter[a1] = arc_filter[a2] = arc_filter[a3] = true;
alpar@440
   197
deba@414
   198
  checkGraphNodeList(adaptor, 3);
deba@414
   199
  checkGraphArcList(adaptor, 3);
deba@414
   200
  checkGraphConArcList(adaptor, 3);
deba@414
   201
deba@414
   202
  checkGraphOutArcList(adaptor, n1, 2);
deba@414
   203
  checkGraphOutArcList(adaptor, n2, 1);
deba@414
   204
  checkGraphOutArcList(adaptor, n3, 0);
deba@414
   205
deba@414
   206
  checkGraphInArcList(adaptor, n1, 0);
deba@414
   207
  checkGraphInArcList(adaptor, n2, 1);
deba@414
   208
  checkGraphInArcList(adaptor, n3, 2);
deba@414
   209
deba@414
   210
  checkNodeIds(adaptor);
deba@414
   211
  checkArcIds(adaptor);
deba@414
   212
deba@414
   213
  checkGraphNodeMap(adaptor);
deba@414
   214
  checkGraphArcMap(adaptor);
deba@414
   215
kpeter@463
   216
  // Hide an arc
kpeter@463
   217
  adaptor.status(a2, false);
kpeter@463
   218
  adaptor.disable(a3);
kpeter@463
   219
  if (!adaptor.status(a3)) adaptor.enable(a3);
deba@414
   220
deba@414
   221
  checkGraphNodeList(adaptor, 3);
deba@414
   222
  checkGraphArcList(adaptor, 2);
deba@414
   223
  checkGraphConArcList(adaptor, 2);
deba@414
   224
deba@414
   225
  checkGraphOutArcList(adaptor, n1, 1);
deba@414
   226
  checkGraphOutArcList(adaptor, n2, 1);
deba@414
   227
  checkGraphOutArcList(adaptor, n3, 0);
deba@414
   228
deba@414
   229
  checkGraphInArcList(adaptor, n1, 0);
deba@414
   230
  checkGraphInArcList(adaptor, n2, 1);
deba@414
   231
  checkGraphInArcList(adaptor, n3, 1);
deba@414
   232
deba@414
   233
  checkNodeIds(adaptor);
deba@414
   234
  checkArcIds(adaptor);
deba@414
   235
deba@414
   236
  checkGraphNodeMap(adaptor);
deba@414
   237
  checkGraphArcMap(adaptor);
deba@414
   238
kpeter@463
   239
  // Hide a node
kpeter@463
   240
  adaptor.status(n1, false);
kpeter@463
   241
  adaptor.disable(n3);
kpeter@463
   242
  if (!adaptor.status(n3)) adaptor.enable(n3);
kpeter@463
   243
kpeter@463
   244
  checkGraphNodeList(adaptor, 2);
kpeter@463
   245
  checkGraphArcList(adaptor, 1);
kpeter@463
   246
  checkGraphConArcList(adaptor, 1);
kpeter@463
   247
kpeter@463
   248
  checkGraphOutArcList(adaptor, n2, 1);
kpeter@463
   249
  checkGraphOutArcList(adaptor, n3, 0);
kpeter@463
   250
kpeter@463
   251
  checkGraphInArcList(adaptor, n2, 0);
kpeter@463
   252
  checkGraphInArcList(adaptor, n3, 1);
kpeter@463
   253
kpeter@463
   254
  checkNodeIds(adaptor);
kpeter@463
   255
  checkArcIds(adaptor);
kpeter@463
   256
kpeter@463
   257
  checkGraphNodeMap(adaptor);
kpeter@463
   258
  checkGraphArcMap(adaptor);
kpeter@463
   259
kpeter@463
   260
  // Hide all nodes and arcs
kpeter@463
   261
  node_filter[n1] = node_filter[n2] = node_filter[n3] = false;
kpeter@463
   262
  arc_filter[a1] = arc_filter[a2] = arc_filter[a3] = false;
kpeter@463
   263
kpeter@463
   264
  checkGraphNodeList(adaptor, 0);
kpeter@463
   265
  checkGraphArcList(adaptor, 0);
kpeter@463
   266
  checkGraphConArcList(adaptor, 0);
kpeter@463
   267
kpeter@463
   268
  checkNodeIds(adaptor);
kpeter@463
   269
  checkArcIds(adaptor);
kpeter@463
   270
kpeter@463
   271
  checkGraphNodeMap(adaptor);
kpeter@463
   272
  checkGraphArcMap(adaptor);
kpeter@463
   273
kpeter@463
   274
  // Check the conversion of nodes and arcs
kpeter@463
   275
  Digraph::Node nd = n3;
kpeter@1197
   276
  ::lemon::ignore_unused_variable_warning(nd);
kpeter@463
   277
  nd = n3;
kpeter@463
   278
  Adaptor::Node na = n1;
kpeter@1197
   279
  ::lemon::ignore_unused_variable_warning(na);
kpeter@463
   280
  na = n2;
kpeter@463
   281
  Digraph::Arc ad = a3;
kpeter@1197
   282
  ::lemon::ignore_unused_variable_warning(ad);
kpeter@463
   283
  ad = a3;
kpeter@463
   284
  Adaptor::Arc aa = a1;
kpeter@1197
   285
  ::lemon::ignore_unused_variable_warning(aa);
kpeter@463
   286
  aa = a2;
kpeter@463
   287
}
kpeter@463
   288
kpeter@463
   289
void checkFilterNodes1() {
kpeter@463
   290
  // Check concepts
kpeter@463
   291
  checkConcept<concepts::Digraph, FilterNodes<concepts::Digraph> >();
kpeter@463
   292
  checkConcept<concepts::Digraph, FilterNodes<ListDigraph> >();
kpeter@463
   293
  checkConcept<concepts::AlterableDigraphComponent<>,
kpeter@463
   294
               FilterNodes<ListDigraph> >();
kpeter@463
   295
  checkConcept<concepts::ExtendableDigraphComponent<>,
kpeter@463
   296
               FilterNodes<ListDigraph> >();
kpeter@463
   297
  checkConcept<concepts::ErasableDigraphComponent<>,
kpeter@463
   298
               FilterNodes<ListDigraph> >();
kpeter@463
   299
  checkConcept<concepts::ClearableDigraphComponent<>,
kpeter@463
   300
               FilterNodes<ListDigraph> >();
kpeter@463
   301
kpeter@463
   302
  // Create a digraph and an adaptor
kpeter@463
   303
  typedef ListDigraph Digraph;
kpeter@463
   304
  typedef Digraph::NodeMap<bool> NodeFilter;
kpeter@463
   305
  typedef FilterNodes<Digraph, NodeFilter> Adaptor;
kpeter@463
   306
kpeter@463
   307
  Digraph digraph;
kpeter@463
   308
  NodeFilter node_filter(digraph);
kpeter@463
   309
  Adaptor adaptor(digraph, node_filter);
kpeter@463
   310
kpeter@463
   311
  // Add nodes and arcs to the original digraph and the adaptor
kpeter@463
   312
  Digraph::Node n1 = digraph.addNode();
kpeter@463
   313
  Digraph::Node n2 = digraph.addNode();
kpeter@463
   314
  Adaptor::Node n3 = adaptor.addNode();
kpeter@463
   315
kpeter@463
   316
  node_filter[n1] = node_filter[n2] = node_filter[n3] = true;
kpeter@463
   317
kpeter@463
   318
  Digraph::Arc a1 = digraph.addArc(n1, n2);
kpeter@463
   319
  Digraph::Arc a2 = digraph.addArc(n1, n3);
kpeter@463
   320
  Adaptor::Arc a3 = adaptor.addArc(n2, n3);
kpeter@463
   321
kpeter@463
   322
  checkGraphNodeList(adaptor, 3);
kpeter@463
   323
  checkGraphArcList(adaptor, 3);
kpeter@463
   324
  checkGraphConArcList(adaptor, 3);
kpeter@463
   325
kpeter@463
   326
  checkGraphOutArcList(adaptor, n1, 2);
kpeter@463
   327
  checkGraphOutArcList(adaptor, n2, 1);
kpeter@463
   328
  checkGraphOutArcList(adaptor, n3, 0);
kpeter@463
   329
kpeter@463
   330
  checkGraphInArcList(adaptor, n1, 0);
kpeter@463
   331
  checkGraphInArcList(adaptor, n2, 1);
kpeter@463
   332
  checkGraphInArcList(adaptor, n3, 2);
kpeter@463
   333
kpeter@463
   334
  checkNodeIds(adaptor);
kpeter@463
   335
  checkArcIds(adaptor);
kpeter@463
   336
kpeter@463
   337
  checkGraphNodeMap(adaptor);
kpeter@463
   338
  checkGraphArcMap(adaptor);
kpeter@463
   339
kpeter@463
   340
  // Hide a node
kpeter@463
   341
  adaptor.status(n1, false);
kpeter@463
   342
  adaptor.disable(n3);
kpeter@463
   343
  if (!adaptor.status(n3)) adaptor.enable(n3);
kpeter@463
   344
kpeter@463
   345
  checkGraphNodeList(adaptor, 2);
kpeter@463
   346
  checkGraphArcList(adaptor, 1);
kpeter@463
   347
  checkGraphConArcList(adaptor, 1);
kpeter@463
   348
kpeter@463
   349
  checkGraphOutArcList(adaptor, n2, 1);
kpeter@463
   350
  checkGraphOutArcList(adaptor, n3, 0);
kpeter@463
   351
kpeter@463
   352
  checkGraphInArcList(adaptor, n2, 0);
kpeter@463
   353
  checkGraphInArcList(adaptor, n3, 1);
kpeter@463
   354
kpeter@463
   355
  checkNodeIds(adaptor);
kpeter@463
   356
  checkArcIds(adaptor);
kpeter@463
   357
kpeter@463
   358
  checkGraphNodeMap(adaptor);
kpeter@463
   359
  checkGraphArcMap(adaptor);
kpeter@463
   360
kpeter@463
   361
  // Hide all nodes
kpeter@463
   362
  node_filter[n1] = node_filter[n2] = node_filter[n3] = false;
kpeter@463
   363
kpeter@463
   364
  checkGraphNodeList(adaptor, 0);
kpeter@463
   365
  checkGraphArcList(adaptor, 0);
kpeter@463
   366
  checkGraphConArcList(adaptor, 0);
kpeter@463
   367
kpeter@463
   368
  checkNodeIds(adaptor);
kpeter@463
   369
  checkArcIds(adaptor);
kpeter@463
   370
kpeter@463
   371
  checkGraphNodeMap(adaptor);
kpeter@463
   372
  checkGraphArcMap(adaptor);
kpeter@463
   373
kpeter@463
   374
  // Check the conversion of nodes and arcs
kpeter@463
   375
  Digraph::Node nd = n3;
kpeter@1197
   376
  ::lemon::ignore_unused_variable_warning(nd);
kpeter@463
   377
  nd = n3;
kpeter@463
   378
  Adaptor::Node na = n1;
kpeter@1197
   379
  ::lemon::ignore_unused_variable_warning(na);
kpeter@463
   380
  na = n2;
kpeter@463
   381
  Digraph::Arc ad = a3;
kpeter@1197
   382
  ::lemon::ignore_unused_variable_warning(ad);
kpeter@463
   383
  ad = a3;
kpeter@463
   384
  Adaptor::Arc aa = a1;
kpeter@1197
   385
  ::lemon::ignore_unused_variable_warning(aa);
kpeter@463
   386
  aa = a2;
kpeter@463
   387
}
kpeter@463
   388
kpeter@463
   389
void checkFilterArcs() {
kpeter@463
   390
  // Check concepts
kpeter@463
   391
  checkConcept<concepts::Digraph, FilterArcs<concepts::Digraph> >();
kpeter@463
   392
  checkConcept<concepts::Digraph, FilterArcs<ListDigraph> >();
kpeter@463
   393
  checkConcept<concepts::AlterableDigraphComponent<>,
kpeter@463
   394
               FilterArcs<ListDigraph> >();
kpeter@463
   395
  checkConcept<concepts::ExtendableDigraphComponent<>,
kpeter@463
   396
               FilterArcs<ListDigraph> >();
kpeter@463
   397
  checkConcept<concepts::ErasableDigraphComponent<>,
kpeter@463
   398
               FilterArcs<ListDigraph> >();
kpeter@463
   399
  checkConcept<concepts::ClearableDigraphComponent<>,
kpeter@463
   400
               FilterArcs<ListDigraph> >();
kpeter@463
   401
kpeter@463
   402
  // Create a digraph and an adaptor
kpeter@463
   403
  typedef ListDigraph Digraph;
kpeter@463
   404
  typedef Digraph::ArcMap<bool> ArcFilter;
kpeter@463
   405
  typedef FilterArcs<Digraph, ArcFilter> Adaptor;
kpeter@463
   406
kpeter@463
   407
  Digraph digraph;
kpeter@463
   408
  ArcFilter arc_filter(digraph);
kpeter@463
   409
  Adaptor adaptor(digraph, arc_filter);
kpeter@463
   410
kpeter@463
   411
  // Add nodes and arcs to the original digraph and the adaptor
kpeter@463
   412
  Digraph::Node n1 = digraph.addNode();
kpeter@463
   413
  Digraph::Node n2 = digraph.addNode();
kpeter@463
   414
  Adaptor::Node n3 = adaptor.addNode();
kpeter@463
   415
kpeter@463
   416
  Digraph::Arc a1 = digraph.addArc(n1, n2);
kpeter@463
   417
  Digraph::Arc a2 = digraph.addArc(n1, n3);
kpeter@463
   418
  Adaptor::Arc a3 = adaptor.addArc(n2, n3);
kpeter@463
   419
kpeter@463
   420
  arc_filter[a1] = arc_filter[a2] = arc_filter[a3] = true;
kpeter@463
   421
kpeter@463
   422
  checkGraphNodeList(adaptor, 3);
kpeter@463
   423
  checkGraphArcList(adaptor, 3);
kpeter@463
   424
  checkGraphConArcList(adaptor, 3);
kpeter@463
   425
kpeter@463
   426
  checkGraphOutArcList(adaptor, n1, 2);
kpeter@463
   427
  checkGraphOutArcList(adaptor, n2, 1);
kpeter@463
   428
  checkGraphOutArcList(adaptor, n3, 0);
kpeter@463
   429
kpeter@463
   430
  checkGraphInArcList(adaptor, n1, 0);
kpeter@463
   431
  checkGraphInArcList(adaptor, n2, 1);
kpeter@463
   432
  checkGraphInArcList(adaptor, n3, 2);
kpeter@463
   433
kpeter@463
   434
  checkNodeIds(adaptor);
kpeter@463
   435
  checkArcIds(adaptor);
kpeter@463
   436
kpeter@463
   437
  checkGraphNodeMap(adaptor);
kpeter@463
   438
  checkGraphArcMap(adaptor);
kpeter@463
   439
kpeter@463
   440
  // Hide an arc
kpeter@463
   441
  adaptor.status(a2, false);
kpeter@463
   442
  adaptor.disable(a3);
kpeter@463
   443
  if (!adaptor.status(a3)) adaptor.enable(a3);
kpeter@463
   444
kpeter@463
   445
  checkGraphNodeList(adaptor, 3);
kpeter@463
   446
  checkGraphArcList(adaptor, 2);
kpeter@463
   447
  checkGraphConArcList(adaptor, 2);
kpeter@463
   448
kpeter@463
   449
  checkGraphOutArcList(adaptor, n1, 1);
kpeter@463
   450
  checkGraphOutArcList(adaptor, n2, 1);
kpeter@463
   451
  checkGraphOutArcList(adaptor, n3, 0);
kpeter@463
   452
kpeter@463
   453
  checkGraphInArcList(adaptor, n1, 0);
kpeter@463
   454
  checkGraphInArcList(adaptor, n2, 1);
kpeter@463
   455
  checkGraphInArcList(adaptor, n3, 1);
kpeter@463
   456
kpeter@463
   457
  checkNodeIds(adaptor);
kpeter@463
   458
  checkArcIds(adaptor);
kpeter@463
   459
kpeter@463
   460
  checkGraphNodeMap(adaptor);
kpeter@463
   461
  checkGraphArcMap(adaptor);
kpeter@463
   462
kpeter@463
   463
  // Hide all arcs
deba@414
   464
  arc_filter[a1] = arc_filter[a2] = arc_filter[a3] = false;
deba@414
   465
deba@414
   466
  checkGraphNodeList(adaptor, 3);
deba@414
   467
  checkGraphArcList(adaptor, 0);
deba@414
   468
  checkGraphConArcList(adaptor, 0);
deba@414
   469
deba@414
   470
  checkNodeIds(adaptor);
deba@414
   471
  checkArcIds(adaptor);
deba@414
   472
deba@414
   473
  checkGraphNodeMap(adaptor);
deba@414
   474
  checkGraphArcMap(adaptor);
kpeter@463
   475
kpeter@463
   476
  // Check the conversion of nodes and arcs
kpeter@463
   477
  Digraph::Node nd = n3;
kpeter@1197
   478
  ::lemon::ignore_unused_variable_warning(nd);
kpeter@463
   479
  nd = n3;
kpeter@463
   480
  Adaptor::Node na = n1;
kpeter@1197
   481
  ::lemon::ignore_unused_variable_warning(na);
kpeter@463
   482
  na = n2;
kpeter@463
   483
  Digraph::Arc ad = a3;
kpeter@1197
   484
  ::lemon::ignore_unused_variable_warning(ad);
kpeter@463
   485
  ad = a3;
kpeter@463
   486
  Adaptor::Arc aa = a1;
kpeter@1197
   487
  ::lemon::ignore_unused_variable_warning(aa);
kpeter@463
   488
  aa = a2;
deba@414
   489
}
deba@414
   490
deba@416
   491
void checkUndirector() {
kpeter@463
   492
  // Check concepts
deba@416
   493
  checkConcept<concepts::Graph, Undirector<concepts::Digraph> >();
kpeter@463
   494
  checkConcept<concepts::Graph, Undirector<ListDigraph> >();
kpeter@463
   495
  checkConcept<concepts::AlterableGraphComponent<>,
kpeter@463
   496
               Undirector<ListDigraph> >();
kpeter@463
   497
  checkConcept<concepts::ExtendableGraphComponent<>,
kpeter@463
   498
               Undirector<ListDigraph> >();
kpeter@463
   499
  checkConcept<concepts::ErasableGraphComponent<>,
kpeter@463
   500
               Undirector<ListDigraph> >();
kpeter@463
   501
  checkConcept<concepts::ClearableGraphComponent<>,
kpeter@463
   502
               Undirector<ListDigraph> >();
deba@414
   503
kpeter@463
   504
kpeter@463
   505
  // Create a digraph and an adaptor
deba@414
   506
  typedef ListDigraph Digraph;
deba@416
   507
  typedef Undirector<Digraph> Adaptor;
deba@414
   508
deba@414
   509
  Digraph digraph;
deba@414
   510
  Adaptor adaptor(digraph);
deba@414
   511
kpeter@463
   512
  // Add nodes and arcs/edges to the original digraph and the adaptor
deba@414
   513
  Digraph::Node n1 = digraph.addNode();
deba@414
   514
  Digraph::Node n2 = digraph.addNode();
kpeter@463
   515
  Adaptor::Node n3 = adaptor.addNode();
deba@414
   516
deba@414
   517
  Digraph::Arc a1 = digraph.addArc(n1, n2);
deba@414
   518
  Digraph::Arc a2 = digraph.addArc(n1, n3);
kpeter@463
   519
  Adaptor::Edge e3 = adaptor.addEdge(n2, n3);
deba@416
   520
kpeter@463
   521
  // Check the original digraph
kpeter@463
   522
  checkGraphNodeList(digraph, 3);
kpeter@463
   523
  checkGraphArcList(digraph, 3);
kpeter@463
   524
  checkGraphConArcList(digraph, 3);
kpeter@463
   525
kpeter@463
   526
  checkGraphOutArcList(digraph, n1, 2);
kpeter@463
   527
  checkGraphOutArcList(digraph, n2, 1);
kpeter@463
   528
  checkGraphOutArcList(digraph, n3, 0);
kpeter@463
   529
kpeter@463
   530
  checkGraphInArcList(digraph, n1, 0);
kpeter@463
   531
  checkGraphInArcList(digraph, n2, 1);
kpeter@463
   532
  checkGraphInArcList(digraph, n3, 2);
kpeter@463
   533
kpeter@463
   534
  checkNodeIds(digraph);
kpeter@463
   535
  checkArcIds(digraph);
kpeter@463
   536
kpeter@463
   537
  checkGraphNodeMap(digraph);
kpeter@463
   538
  checkGraphArcMap(digraph);
kpeter@463
   539
kpeter@463
   540
  // Check the adaptor
deba@414
   541
  checkGraphNodeList(adaptor, 3);
deba@414
   542
  checkGraphArcList(adaptor, 6);
deba@414
   543
  checkGraphEdgeList(adaptor, 3);
deba@414
   544
  checkGraphConArcList(adaptor, 6);
deba@414
   545
  checkGraphConEdgeList(adaptor, 3);
deba@414
   546
kpeter@463
   547
  checkGraphIncEdgeArcLists(adaptor, n1, 2);
kpeter@463
   548
  checkGraphIncEdgeArcLists(adaptor, n2, 2);
kpeter@463
   549
  checkGraphIncEdgeArcLists(adaptor, n3, 2);
deba@414
   550
deba@414
   551
  checkNodeIds(adaptor);
deba@414
   552
  checkArcIds(adaptor);
deba@414
   553
  checkEdgeIds(adaptor);
deba@414
   554
deba@414
   555
  checkGraphNodeMap(adaptor);
deba@414
   556
  checkGraphArcMap(adaptor);
deba@414
   557
  checkGraphEdgeMap(adaptor);
deba@414
   558
kpeter@463
   559
  // Check the edges of the adaptor
deba@414
   560
  for (Adaptor::EdgeIt e(adaptor); e != INVALID; ++e) {
deba@414
   561
    check(adaptor.u(e) == digraph.source(e), "Wrong undir");
deba@414
   562
    check(adaptor.v(e) == digraph.target(e), "Wrong undir");
deba@414
   563
  }
deba@414
   564
kpeter@463
   565
  // Check CombinedArcMap
kpeter@463
   566
  typedef Adaptor::CombinedArcMap
kpeter@463
   567
    <Digraph::ArcMap<int>, Digraph::ArcMap<int> > IntCombinedMap;
kpeter@463
   568
  typedef Adaptor::CombinedArcMap
kpeter@463
   569
    <Digraph::ArcMap<bool>, Digraph::ArcMap<bool> > BoolCombinedMap;
kpeter@463
   570
  checkConcept<concepts::ReferenceMap<Adaptor::Arc, int, int&, const int&>,
kpeter@463
   571
    IntCombinedMap>();
kpeter@463
   572
  checkConcept<concepts::ReferenceMap<Adaptor::Arc, bool, bool&, const bool&>,
kpeter@463
   573
    BoolCombinedMap>();
kpeter@463
   574
kpeter@463
   575
  Digraph::ArcMap<int> fw_map(digraph), bk_map(digraph);
kpeter@463
   576
  for (Digraph::ArcIt a(digraph); a != INVALID; ++a) {
kpeter@463
   577
    fw_map[a] = digraph.id(a);
kpeter@463
   578
    bk_map[a] = -digraph.id(a);
kpeter@463
   579
  }
kpeter@463
   580
kpeter@463
   581
  Adaptor::CombinedArcMap<Digraph::ArcMap<int>, Digraph::ArcMap<int> >
kpeter@463
   582
    comb_map(fw_map, bk_map);
kpeter@463
   583
  for (Adaptor::ArcIt a(adaptor); a != INVALID; ++a) {
kpeter@463
   584
    if (adaptor.source(a) == digraph.source(a)) {
kpeter@463
   585
      check(comb_map[a] == fw_map[a], "Wrong combined map");
kpeter@463
   586
    } else {
kpeter@463
   587
      check(comb_map[a] == bk_map[a], "Wrong combined map");
kpeter@463
   588
    }
kpeter@463
   589
  }
kpeter@463
   590
kpeter@463
   591
  // Check the conversion of nodes and arcs/edges
kpeter@463
   592
  Digraph::Node nd = n3;
kpeter@1197
   593
  ::lemon::ignore_unused_variable_warning(nd);
kpeter@463
   594
  nd = n3;
kpeter@463
   595
  Adaptor::Node na = n1;
kpeter@1197
   596
  ::lemon::ignore_unused_variable_warning(na);
kpeter@463
   597
  na = n2;
kpeter@463
   598
  Digraph::Arc ad = e3;
kpeter@1197
   599
  ::lemon::ignore_unused_variable_warning(ad);
kpeter@463
   600
  ad = e3;
kpeter@463
   601
  Adaptor::Edge ea = a1;
kpeter@1197
   602
  ::lemon::ignore_unused_variable_warning(ea);
kpeter@463
   603
  ea = a2;
deba@414
   604
}
deba@414
   605
kpeter@464
   606
void checkResidualDigraph() {
kpeter@463
   607
  // Check concepts
kpeter@464
   608
  checkConcept<concepts::Digraph, ResidualDigraph<concepts::Digraph> >();
kpeter@464
   609
  checkConcept<concepts::Digraph, ResidualDigraph<ListDigraph> >();
deba@414
   610
kpeter@463
   611
  // Create a digraph and an adaptor
deba@414
   612
  typedef ListDigraph Digraph;
deba@414
   613
  typedef Digraph::ArcMap<int> IntArcMap;
kpeter@464
   614
  typedef ResidualDigraph<Digraph, IntArcMap> Adaptor;
deba@414
   615
deba@414
   616
  Digraph digraph;
deba@414
   617
  IntArcMap capacity(digraph), flow(digraph);
deba@414
   618
  Adaptor adaptor(digraph, capacity, flow);
deba@414
   619
deba@414
   620
  Digraph::Node n1 = digraph.addNode();
deba@414
   621
  Digraph::Node n2 = digraph.addNode();
deba@414
   622
  Digraph::Node n3 = digraph.addNode();
deba@414
   623
  Digraph::Node n4 = digraph.addNode();
deba@414
   624
deba@414
   625
  Digraph::Arc a1 = digraph.addArc(n1, n2);
deba@414
   626
  Digraph::Arc a2 = digraph.addArc(n1, n3);
deba@414
   627
  Digraph::Arc a3 = digraph.addArc(n1, n4);
deba@414
   628
  Digraph::Arc a4 = digraph.addArc(n2, n3);
deba@414
   629
  Digraph::Arc a5 = digraph.addArc(n2, n4);
deba@414
   630
  Digraph::Arc a6 = digraph.addArc(n3, n4);
deba@414
   631
deba@414
   632
  capacity[a1] = 8;
deba@414
   633
  capacity[a2] = 6;
deba@414
   634
  capacity[a3] = 4;
deba@414
   635
  capacity[a4] = 4;
deba@414
   636
  capacity[a5] = 6;
deba@414
   637
  capacity[a6] = 10;
deba@414
   638
kpeter@463
   639
  // Check the adaptor with various flow values
kpeter@463
   640
  for (Digraph::ArcIt a(digraph); a != INVALID; ++a) {
deba@414
   641
    flow[a] = 0;
deba@414
   642
  }
deba@416
   643
deba@414
   644
  checkGraphNodeList(adaptor, 4);
deba@414
   645
  checkGraphArcList(adaptor, 6);
deba@414
   646
  checkGraphConArcList(adaptor, 6);
deba@414
   647
deba@414
   648
  checkGraphOutArcList(adaptor, n1, 3);
deba@414
   649
  checkGraphOutArcList(adaptor, n2, 2);
deba@414
   650
  checkGraphOutArcList(adaptor, n3, 1);
deba@414
   651
  checkGraphOutArcList(adaptor, n4, 0);
deba@414
   652
deba@414
   653
  checkGraphInArcList(adaptor, n1, 0);
deba@414
   654
  checkGraphInArcList(adaptor, n2, 1);
deba@414
   655
  checkGraphInArcList(adaptor, n3, 2);
deba@414
   656
  checkGraphInArcList(adaptor, n4, 3);
deba@414
   657
kpeter@463
   658
  for (Digraph::ArcIt a(digraph); a != INVALID; ++a) {
deba@414
   659
    flow[a] = capacity[a] / 2;
deba@414
   660
  }
deba@416
   661
deba@414
   662
  checkGraphNodeList(adaptor, 4);
deba@414
   663
  checkGraphArcList(adaptor, 12);
deba@414
   664
  checkGraphConArcList(adaptor, 12);
deba@414
   665
deba@414
   666
  checkGraphOutArcList(adaptor, n1, 3);
deba@414
   667
  checkGraphOutArcList(adaptor, n2, 3);
deba@414
   668
  checkGraphOutArcList(adaptor, n3, 3);
deba@414
   669
  checkGraphOutArcList(adaptor, n4, 3);
deba@414
   670
deba@414
   671
  checkGraphInArcList(adaptor, n1, 3);
deba@414
   672
  checkGraphInArcList(adaptor, n2, 3);
deba@414
   673
  checkGraphInArcList(adaptor, n3, 3);
deba@414
   674
  checkGraphInArcList(adaptor, n4, 3);
deba@414
   675
deba@414
   676
  checkNodeIds(adaptor);
deba@414
   677
  checkArcIds(adaptor);
deba@414
   678
deba@414
   679
  checkGraphNodeMap(adaptor);
deba@414
   680
  checkGraphArcMap(adaptor);
deba@414
   681
kpeter@463
   682
  for (Digraph::ArcIt a(digraph); a != INVALID; ++a) {
deba@414
   683
    flow[a] = capacity[a];
deba@414
   684
  }
deba@416
   685
deba@414
   686
  checkGraphNodeList(adaptor, 4);
deba@414
   687
  checkGraphArcList(adaptor, 6);
deba@414
   688
  checkGraphConArcList(adaptor, 6);
deba@414
   689
deba@414
   690
  checkGraphOutArcList(adaptor, n1, 0);
deba@414
   691
  checkGraphOutArcList(adaptor, n2, 1);
deba@414
   692
  checkGraphOutArcList(adaptor, n3, 2);
deba@414
   693
  checkGraphOutArcList(adaptor, n4, 3);
deba@414
   694
deba@414
   695
  checkGraphInArcList(adaptor, n1, 3);
deba@414
   696
  checkGraphInArcList(adaptor, n2, 2);
deba@414
   697
  checkGraphInArcList(adaptor, n3, 1);
deba@414
   698
  checkGraphInArcList(adaptor, n4, 0);
deba@414
   699
kpeter@463
   700
  // Saturate all backward arcs
kpeter@463
   701
  // (set the flow to zero on all forward arcs)
deba@414
   702
  for (Adaptor::ArcIt a(adaptor); a != INVALID; ++a) {
kpeter@463
   703
    if (adaptor.backward(a))
kpeter@463
   704
      adaptor.augment(a, adaptor.residualCapacity(a));
deba@414
   705
  }
deba@414
   706
kpeter@463
   707
  checkGraphNodeList(adaptor, 4);
kpeter@463
   708
  checkGraphArcList(adaptor, 6);
kpeter@463
   709
  checkGraphConArcList(adaptor, 6);
kpeter@463
   710
kpeter@463
   711
  checkGraphOutArcList(adaptor, n1, 3);
kpeter@463
   712
  checkGraphOutArcList(adaptor, n2, 2);
kpeter@463
   713
  checkGraphOutArcList(adaptor, n3, 1);
kpeter@463
   714
  checkGraphOutArcList(adaptor, n4, 0);
kpeter@463
   715
kpeter@463
   716
  checkGraphInArcList(adaptor, n1, 0);
kpeter@463
   717
  checkGraphInArcList(adaptor, n2, 1);
kpeter@463
   718
  checkGraphInArcList(adaptor, n3, 2);
kpeter@463
   719
  checkGraphInArcList(adaptor, n4, 3);
kpeter@463
   720
kpeter@463
   721
  // Find maximum flow by augmenting along shortest paths
deba@414
   722
  int flow_value = 0;
kpeter@463
   723
  Adaptor::ResidualCapacity res_cap(adaptor);
deba@414
   724
  while (true) {
deba@416
   725
deba@414
   726
    Bfs<Adaptor> bfs(adaptor);
deba@414
   727
    bfs.run(n1, n4);
deba@416
   728
deba@414
   729
    if (!bfs.reached(n4)) break;
deba@414
   730
deba@414
   731
    Path<Adaptor> p = bfs.path(n4);
deba@416
   732
deba@414
   733
    int min = std::numeric_limits<int>::max();
deba@414
   734
    for (Path<Adaptor>::ArcIt a(p); a != INVALID; ++a) {
kpeter@463
   735
      if (res_cap[a] < min) min = res_cap[a];
deba@414
   736
    }
deba@414
   737
deba@414
   738
    for (Path<Adaptor>::ArcIt a(p); a != INVALID; ++a) {
deba@414
   739
      adaptor.augment(a, min);
deba@414
   740
    }
deba@414
   741
    flow_value += min;
deba@414
   742
  }
deba@414
   743
deba@414
   744
  check(flow_value == 18, "Wrong flow with res graph adaptor");
deba@414
   745
kpeter@463
   746
  // Check forward() and backward()
kpeter@463
   747
  for (Adaptor::ArcIt a(adaptor); a != INVALID; ++a) {
kpeter@463
   748
    check(adaptor.forward(a) != adaptor.backward(a),
kpeter@463
   749
          "Wrong forward() or backward()");
kpeter@463
   750
    check((adaptor.forward(a) && adaptor.forward(Digraph::Arc(a)) == a) ||
kpeter@463
   751
          (adaptor.backward(a) && adaptor.backward(Digraph::Arc(a)) == a),
kpeter@463
   752
          "Wrong forward() or backward()");
kpeter@463
   753
  }
kpeter@463
   754
kpeter@463
   755
  // Check the conversion of nodes and arcs
kpeter@463
   756
  Digraph::Node nd = Adaptor::NodeIt(adaptor);
kpeter@1197
   757
  ::lemon::ignore_unused_variable_warning(nd);
kpeter@463
   758
  nd = ++Adaptor::NodeIt(adaptor);
kpeter@463
   759
  Adaptor::Node na = n1;
kpeter@1197
   760
  ::lemon::ignore_unused_variable_warning(na);
kpeter@463
   761
  na = n2;
kpeter@463
   762
  Digraph::Arc ad = Adaptor::ArcIt(adaptor);
kpeter@1197
   763
  ::lemon::ignore_unused_variable_warning(ad);
kpeter@463
   764
  ad = ++Adaptor::ArcIt(adaptor);
deba@414
   765
}
deba@414
   766
deba@416
   767
void checkSplitNodes() {
kpeter@463
   768
  // Check concepts
deba@416
   769
  checkConcept<concepts::Digraph, SplitNodes<concepts::Digraph> >();
kpeter@463
   770
  checkConcept<concepts::Digraph, SplitNodes<ListDigraph> >();
deba@414
   771
kpeter@463
   772
  // Create a digraph and an adaptor
deba@414
   773
  typedef ListDigraph Digraph;
deba@416
   774
  typedef SplitNodes<Digraph> Adaptor;
deba@414
   775
deba@414
   776
  Digraph digraph;
deba@414
   777
  Adaptor adaptor(digraph);
deba@414
   778
deba@414
   779
  Digraph::Node n1 = digraph.addNode();
deba@414
   780
  Digraph::Node n2 = digraph.addNode();
deba@414
   781
  Digraph::Node n3 = digraph.addNode();
deba@414
   782
deba@414
   783
  Digraph::Arc a1 = digraph.addArc(n1, n2);
deba@414
   784
  Digraph::Arc a2 = digraph.addArc(n1, n3);
deba@414
   785
  Digraph::Arc a3 = digraph.addArc(n2, n3);
alpar@1083
   786
  ::lemon::ignore_unused_variable_warning(a1,a2,a3);
deba@416
   787
deba@414
   788
  checkGraphNodeList(adaptor, 6);
deba@414
   789
  checkGraphArcList(adaptor, 6);
deba@414
   790
  checkGraphConArcList(adaptor, 6);
deba@414
   791
deba@414
   792
  checkGraphOutArcList(adaptor, adaptor.inNode(n1), 1);
deba@414
   793
  checkGraphOutArcList(adaptor, adaptor.outNode(n1), 2);
deba@414
   794
  checkGraphOutArcList(adaptor, adaptor.inNode(n2), 1);
deba@414
   795
  checkGraphOutArcList(adaptor, adaptor.outNode(n2), 1);
deba@414
   796
  checkGraphOutArcList(adaptor, adaptor.inNode(n3), 1);
deba@414
   797
  checkGraphOutArcList(adaptor, adaptor.outNode(n3), 0);
deba@414
   798
deba@414
   799
  checkGraphInArcList(adaptor, adaptor.inNode(n1), 0);
deba@414
   800
  checkGraphInArcList(adaptor, adaptor.outNode(n1), 1);
deba@414
   801
  checkGraphInArcList(adaptor, adaptor.inNode(n2), 1);
deba@414
   802
  checkGraphInArcList(adaptor, adaptor.outNode(n2), 1);
deba@414
   803
  checkGraphInArcList(adaptor, adaptor.inNode(n3), 2);
deba@414
   804
  checkGraphInArcList(adaptor, adaptor.outNode(n3), 1);
deba@414
   805
deba@414
   806
  checkNodeIds(adaptor);
deba@414
   807
  checkArcIds(adaptor);
deba@416
   808
deba@414
   809
  checkGraphNodeMap(adaptor);
deba@414
   810
  checkGraphArcMap(adaptor);
deba@414
   811
kpeter@463
   812
  // Check split
deba@414
   813
  for (Adaptor::ArcIt a(adaptor); a != INVALID; ++a) {
deba@414
   814
    if (adaptor.origArc(a)) {
deba@414
   815
      Digraph::Arc oa = a;
deba@416
   816
      check(adaptor.source(a) == adaptor.outNode(digraph.source(oa)),
deba@416
   817
            "Wrong split");
deba@416
   818
      check(adaptor.target(a) == adaptor.inNode(digraph.target(oa)),
deba@416
   819
            "Wrong split");
deba@414
   820
    } else {
deba@414
   821
      Digraph::Node on = a;
deba@414
   822
      check(adaptor.source(a) == adaptor.inNode(on), "Wrong split");
deba@414
   823
      check(adaptor.target(a) == adaptor.outNode(on), "Wrong split");
deba@414
   824
    }
deba@414
   825
  }
kpeter@463
   826
kpeter@463
   827
  // Check combined node map
kpeter@463
   828
  typedef Adaptor::CombinedNodeMap
kpeter@463
   829
    <Digraph::NodeMap<int>, Digraph::NodeMap<int> > IntCombinedNodeMap;
kpeter@463
   830
  typedef Adaptor::CombinedNodeMap
kpeter@463
   831
    <Digraph::NodeMap<bool>, Digraph::NodeMap<bool> > BoolCombinedNodeMap;
kpeter@463
   832
  checkConcept<concepts::ReferenceMap<Adaptor::Node, int, int&, const int&>,
kpeter@463
   833
    IntCombinedNodeMap>();
kpeter@463
   834
//checkConcept<concepts::ReferenceMap<Adaptor::Node, bool, bool&, const bool&>,
kpeter@463
   835
//  BoolCombinedNodeMap>();
kpeter@463
   836
  checkConcept<concepts::ReadWriteMap<Adaptor::Node, bool>,
kpeter@463
   837
    BoolCombinedNodeMap>();
kpeter@463
   838
kpeter@463
   839
  Digraph::NodeMap<int> in_map(digraph), out_map(digraph);
kpeter@463
   840
  for (Digraph::NodeIt n(digraph); n != INVALID; ++n) {
kpeter@463
   841
    in_map[n] = digraph.id(n);
kpeter@463
   842
    out_map[n] = -digraph.id(n);
kpeter@463
   843
  }
kpeter@463
   844
kpeter@463
   845
  Adaptor::CombinedNodeMap<Digraph::NodeMap<int>, Digraph::NodeMap<int> >
kpeter@463
   846
    node_map(in_map, out_map);
kpeter@463
   847
  for (Adaptor::NodeIt n(adaptor); n != INVALID; ++n) {
kpeter@463
   848
    if (adaptor.inNode(n)) {
kpeter@463
   849
      check(node_map[n] == in_map[n], "Wrong combined node map");
kpeter@463
   850
    } else {
kpeter@463
   851
      check(node_map[n] == out_map[n], "Wrong combined node map");
kpeter@463
   852
    }
kpeter@463
   853
  }
kpeter@463
   854
kpeter@463
   855
  // Check combined arc map
kpeter@463
   856
  typedef Adaptor::CombinedArcMap
kpeter@463
   857
    <Digraph::ArcMap<int>, Digraph::NodeMap<int> > IntCombinedArcMap;
kpeter@463
   858
  typedef Adaptor::CombinedArcMap
kpeter@463
   859
    <Digraph::ArcMap<bool>, Digraph::NodeMap<bool> > BoolCombinedArcMap;
kpeter@463
   860
  checkConcept<concepts::ReferenceMap<Adaptor::Arc, int, int&, const int&>,
kpeter@463
   861
    IntCombinedArcMap>();
kpeter@463
   862
//checkConcept<concepts::ReferenceMap<Adaptor::Arc, bool, bool&, const bool&>,
kpeter@463
   863
//  BoolCombinedArcMap>();
kpeter@463
   864
  checkConcept<concepts::ReadWriteMap<Adaptor::Arc, bool>,
kpeter@463
   865
    BoolCombinedArcMap>();
kpeter@463
   866
kpeter@463
   867
  Digraph::ArcMap<int> a_map(digraph);
kpeter@463
   868
  for (Digraph::ArcIt a(digraph); a != INVALID; ++a) {
kpeter@463
   869
    a_map[a] = digraph.id(a);
kpeter@463
   870
  }
kpeter@463
   871
kpeter@463
   872
  Adaptor::CombinedArcMap<Digraph::ArcMap<int>, Digraph::NodeMap<int> >
kpeter@463
   873
    arc_map(a_map, out_map);
kpeter@463
   874
  for (Digraph::ArcIt a(digraph); a != INVALID; ++a) {
kpeter@463
   875
    check(arc_map[adaptor.arc(a)] == a_map[a],  "Wrong combined arc map");
kpeter@463
   876
  }
kpeter@463
   877
  for (Digraph::NodeIt n(digraph); n != INVALID; ++n) {
kpeter@463
   878
    check(arc_map[adaptor.arc(n)] == out_map[n],  "Wrong combined arc map");
kpeter@463
   879
  }
kpeter@463
   880
kpeter@463
   881
  // Check the conversion of nodes
kpeter@463
   882
  Digraph::Node nd = adaptor.inNode(n1);
kpeter@463
   883
  check (nd == n1, "Wrong node conversion");
kpeter@463
   884
  nd = adaptor.outNode(n2);
kpeter@463
   885
  check (nd == n2, "Wrong node conversion");
deba@414
   886
}
deba@414
   887
deba@416
   888
void checkSubGraph() {
kpeter@463
   889
  // Check concepts
kpeter@463
   890
  checkConcept<concepts::Graph, SubGraph<concepts::Graph> >();
kpeter@463
   891
  checkConcept<concepts::Graph, SubGraph<ListGraph> >();
kpeter@463
   892
  checkConcept<concepts::AlterableGraphComponent<>,
kpeter@463
   893
               SubGraph<ListGraph> >();
kpeter@463
   894
  checkConcept<concepts::ExtendableGraphComponent<>,
kpeter@463
   895
               SubGraph<ListGraph> >();
kpeter@463
   896
  checkConcept<concepts::ErasableGraphComponent<>,
kpeter@463
   897
               SubGraph<ListGraph> >();
kpeter@463
   898
  checkConcept<concepts::ClearableGraphComponent<>,
kpeter@463
   899
               SubGraph<ListGraph> >();
deba@414
   900
kpeter@463
   901
  // Create a graph and an adaptor
deba@414
   902
  typedef ListGraph Graph;
deba@414
   903
  typedef Graph::NodeMap<bool> NodeFilter;
deba@414
   904
  typedef Graph::EdgeMap<bool> EdgeFilter;
deba@416
   905
  typedef SubGraph<Graph, NodeFilter, EdgeFilter> Adaptor;
deba@414
   906
deba@414
   907
  Graph graph;
deba@414
   908
  NodeFilter node_filter(graph);
deba@414
   909
  EdgeFilter edge_filter(graph);
deba@414
   910
  Adaptor adaptor(graph, node_filter, edge_filter);
deba@414
   911
kpeter@463
   912
  // Add nodes and edges to the original graph and the adaptor
deba@414
   913
  Graph::Node n1 = graph.addNode();
deba@414
   914
  Graph::Node n2 = graph.addNode();
kpeter@463
   915
  Adaptor::Node n3 = adaptor.addNode();
kpeter@463
   916
  Adaptor::Node n4 = adaptor.addNode();
kpeter@463
   917
kpeter@463
   918
  node_filter[n1] = node_filter[n2] = node_filter[n3] = node_filter[n4] = true;
deba@414
   919
deba@414
   920
  Graph::Edge e1 = graph.addEdge(n1, n2);
deba@414
   921
  Graph::Edge e2 = graph.addEdge(n1, n3);
kpeter@463
   922
  Adaptor::Edge e3 = adaptor.addEdge(n2, n3);
kpeter@463
   923
  Adaptor::Edge e4 = adaptor.addEdge(n3, n4);
deba@414
   924
deba@414
   925
  edge_filter[e1] = edge_filter[e2] = edge_filter[e3] = edge_filter[e4] = true;
alpar@440
   926
deba@414
   927
  checkGraphNodeList(adaptor, 4);
deba@414
   928
  checkGraphArcList(adaptor, 8);
deba@414
   929
  checkGraphEdgeList(adaptor, 4);
deba@414
   930
  checkGraphConArcList(adaptor, 8);
deba@414
   931
  checkGraphConEdgeList(adaptor, 4);
deba@414
   932
kpeter@463
   933
  checkGraphIncEdgeArcLists(adaptor, n1, 2);
kpeter@463
   934
  checkGraphIncEdgeArcLists(adaptor, n2, 2);
kpeter@463
   935
  checkGraphIncEdgeArcLists(adaptor, n3, 3);
kpeter@463
   936
  checkGraphIncEdgeArcLists(adaptor, n4, 1);
deba@414
   937
deba@414
   938
  checkNodeIds(adaptor);
deba@414
   939
  checkArcIds(adaptor);
deba@414
   940
  checkEdgeIds(adaptor);
deba@414
   941
deba@414
   942
  checkGraphNodeMap(adaptor);
deba@414
   943
  checkGraphArcMap(adaptor);
deba@414
   944
  checkGraphEdgeMap(adaptor);
deba@414
   945
kpeter@463
   946
  // Hide an edge
kpeter@463
   947
  adaptor.status(e2, false);
kpeter@463
   948
  adaptor.disable(e3);
kpeter@463
   949
  if (!adaptor.status(e3)) adaptor.enable(e3);
deba@414
   950
deba@414
   951
  checkGraphNodeList(adaptor, 4);
deba@414
   952
  checkGraphArcList(adaptor, 6);
deba@414
   953
  checkGraphEdgeList(adaptor, 3);
deba@414
   954
  checkGraphConArcList(adaptor, 6);
deba@414
   955
  checkGraphConEdgeList(adaptor, 3);
deba@414
   956
kpeter@463
   957
  checkGraphIncEdgeArcLists(adaptor, n1, 1);
kpeter@463
   958
  checkGraphIncEdgeArcLists(adaptor, n2, 2);
kpeter@463
   959
  checkGraphIncEdgeArcLists(adaptor, n3, 2);
kpeter@463
   960
  checkGraphIncEdgeArcLists(adaptor, n4, 1);
deba@414
   961
deba@414
   962
  checkNodeIds(adaptor);
deba@414
   963
  checkArcIds(adaptor);
deba@414
   964
  checkEdgeIds(adaptor);
deba@414
   965
deba@414
   966
  checkGraphNodeMap(adaptor);
deba@414
   967
  checkGraphArcMap(adaptor);
deba@414
   968
  checkGraphEdgeMap(adaptor);
deba@414
   969
kpeter@463
   970
  // Hide a node
kpeter@463
   971
  adaptor.status(n1, false);
kpeter@463
   972
  adaptor.disable(n3);
kpeter@463
   973
  if (!adaptor.status(n3)) adaptor.enable(n3);
deba@414
   974
deba@414
   975
  checkGraphNodeList(adaptor, 3);
deba@414
   976
  checkGraphArcList(adaptor, 4);
deba@414
   977
  checkGraphEdgeList(adaptor, 2);
deba@414
   978
  checkGraphConArcList(adaptor, 4);
deba@414
   979
  checkGraphConEdgeList(adaptor, 2);
deba@414
   980
kpeter@463
   981
  checkGraphIncEdgeArcLists(adaptor, n2, 1);
kpeter@463
   982
  checkGraphIncEdgeArcLists(adaptor, n3, 2);
kpeter@463
   983
  checkGraphIncEdgeArcLists(adaptor, n4, 1);
deba@414
   984
deba@414
   985
  checkNodeIds(adaptor);
deba@414
   986
  checkArcIds(adaptor);
deba@414
   987
  checkEdgeIds(adaptor);
deba@414
   988
deba@414
   989
  checkGraphNodeMap(adaptor);
deba@414
   990
  checkGraphArcMap(adaptor);
deba@414
   991
  checkGraphEdgeMap(adaptor);
deba@414
   992
kpeter@463
   993
  // Hide all nodes and edges
deba@414
   994
  node_filter[n1] = node_filter[n2] = node_filter[n3] = node_filter[n4] = false;
deba@414
   995
  edge_filter[e1] = edge_filter[e2] = edge_filter[e3] = edge_filter[e4] = false;
deba@414
   996
deba@414
   997
  checkGraphNodeList(adaptor, 0);
deba@414
   998
  checkGraphArcList(adaptor, 0);
deba@414
   999
  checkGraphEdgeList(adaptor, 0);
deba@414
  1000
  checkGraphConArcList(adaptor, 0);
deba@414
  1001
  checkGraphConEdgeList(adaptor, 0);
deba@414
  1002
deba@414
  1003
  checkNodeIds(adaptor);
deba@414
  1004
  checkArcIds(adaptor);
deba@414
  1005
  checkEdgeIds(adaptor);
deba@414
  1006
deba@414
  1007
  checkGraphNodeMap(adaptor);
deba@414
  1008
  checkGraphArcMap(adaptor);
deba@414
  1009
  checkGraphEdgeMap(adaptor);
kpeter@463
  1010
kpeter@463
  1011
  // Check the conversion of nodes and edges
kpeter@463
  1012
  Graph::Node ng = n3;
kpeter@1197
  1013
  ::lemon::ignore_unused_variable_warning(ng);
kpeter@463
  1014
  ng = n4;
kpeter@463
  1015
  Adaptor::Node na = n1;
kpeter@1197
  1016
  ::lemon::ignore_unused_variable_warning(na);
kpeter@463
  1017
  na = n2;
kpeter@463
  1018
  Graph::Edge eg = e3;
kpeter@1197
  1019
  ::lemon::ignore_unused_variable_warning(eg);
kpeter@463
  1020
  eg = e4;
kpeter@463
  1021
  Adaptor::Edge ea = e1;
kpeter@1197
  1022
  ::lemon::ignore_unused_variable_warning(ea);
kpeter@463
  1023
  ea = e2;
deba@414
  1024
}
deba@414
  1025
deba@416
  1026
void checkFilterNodes2() {
kpeter@463
  1027
  // Check concepts
kpeter@463
  1028
  checkConcept<concepts::Graph, FilterNodes<concepts::Graph> >();
kpeter@463
  1029
  checkConcept<concepts::Graph, FilterNodes<ListGraph> >();
kpeter@463
  1030
  checkConcept<concepts::AlterableGraphComponent<>,
kpeter@463
  1031
               FilterNodes<ListGraph> >();
kpeter@463
  1032
  checkConcept<concepts::ExtendableGraphComponent<>,
kpeter@463
  1033
               FilterNodes<ListGraph> >();
kpeter@463
  1034
  checkConcept<concepts::ErasableGraphComponent<>,
kpeter@463
  1035
               FilterNodes<ListGraph> >();
kpeter@463
  1036
  checkConcept<concepts::ClearableGraphComponent<>,
kpeter@463
  1037
               FilterNodes<ListGraph> >();
deba@414
  1038
kpeter@463
  1039
  // Create a graph and an adaptor
deba@414
  1040
  typedef ListGraph Graph;
deba@414
  1041
  typedef Graph::NodeMap<bool> NodeFilter;
deba@416
  1042
  typedef FilterNodes<Graph, NodeFilter> Adaptor;
deba@414
  1043
kpeter@463
  1044
  // Add nodes and edges to the original graph and the adaptor
deba@414
  1045
  Graph graph;
deba@414
  1046
  NodeFilter node_filter(graph);
deba@414
  1047
  Adaptor adaptor(graph, node_filter);
deba@414
  1048
deba@414
  1049
  Graph::Node n1 = graph.addNode();
deba@414
  1050
  Graph::Node n2 = graph.addNode();
kpeter@463
  1051
  Adaptor::Node n3 = adaptor.addNode();
kpeter@463
  1052
  Adaptor::Node n4 = adaptor.addNode();
kpeter@463
  1053
kpeter@463
  1054
  node_filter[n1] = node_filter[n2] = node_filter[n3] = node_filter[n4] = true;
deba@414
  1055
deba@414
  1056
  Graph::Edge e1 = graph.addEdge(n1, n2);
deba@414
  1057
  Graph::Edge e2 = graph.addEdge(n1, n3);
kpeter@463
  1058
  Adaptor::Edge e3 = adaptor.addEdge(n2, n3);
kpeter@463
  1059
  Adaptor::Edge e4 = adaptor.addEdge(n3, n4);
alpar@440
  1060
deba@414
  1061
  checkGraphNodeList(adaptor, 4);
deba@414
  1062
  checkGraphArcList(adaptor, 8);
deba@414
  1063
  checkGraphEdgeList(adaptor, 4);
deba@414
  1064
  checkGraphConArcList(adaptor, 8);
deba@414
  1065
  checkGraphConEdgeList(adaptor, 4);
deba@414
  1066
kpeter@463
  1067
  checkGraphIncEdgeArcLists(adaptor, n1, 2);
kpeter@463
  1068
  checkGraphIncEdgeArcLists(adaptor, n2, 2);
kpeter@463
  1069
  checkGraphIncEdgeArcLists(adaptor, n3, 3);
kpeter@463
  1070
  checkGraphIncEdgeArcLists(adaptor, n4, 1);
deba@414
  1071
deba@414
  1072
  checkNodeIds(adaptor);
deba@414
  1073
  checkArcIds(adaptor);
deba@414
  1074
  checkEdgeIds(adaptor);
deba@414
  1075
deba@414
  1076
  checkGraphNodeMap(adaptor);
deba@414
  1077
  checkGraphArcMap(adaptor);
deba@414
  1078
  checkGraphEdgeMap(adaptor);
deba@414
  1079
kpeter@463
  1080
  // Hide a node
kpeter@463
  1081
  adaptor.status(n1, false);
kpeter@463
  1082
  adaptor.disable(n3);
kpeter@463
  1083
  if (!adaptor.status(n3)) adaptor.enable(n3);
deba@414
  1084
deba@414
  1085
  checkGraphNodeList(adaptor, 3);
deba@414
  1086
  checkGraphArcList(adaptor, 4);
deba@414
  1087
  checkGraphEdgeList(adaptor, 2);
deba@414
  1088
  checkGraphConArcList(adaptor, 4);
deba@414
  1089
  checkGraphConEdgeList(adaptor, 2);
deba@414
  1090
kpeter@463
  1091
  checkGraphIncEdgeArcLists(adaptor, n2, 1);
kpeter@463
  1092
  checkGraphIncEdgeArcLists(adaptor, n3, 2);
kpeter@463
  1093
  checkGraphIncEdgeArcLists(adaptor, n4, 1);
deba@414
  1094
deba@414
  1095
  checkNodeIds(adaptor);
deba@414
  1096
  checkArcIds(adaptor);
deba@414
  1097
  checkEdgeIds(adaptor);
deba@414
  1098
deba@414
  1099
  checkGraphNodeMap(adaptor);
deba@414
  1100
  checkGraphArcMap(adaptor);
deba@414
  1101
  checkGraphEdgeMap(adaptor);
deba@414
  1102
kpeter@463
  1103
  // Hide all nodes
deba@414
  1104
  node_filter[n1] = node_filter[n2] = node_filter[n3] = node_filter[n4] = false;
deba@414
  1105
deba@414
  1106
  checkGraphNodeList(adaptor, 0);
deba@414
  1107
  checkGraphArcList(adaptor, 0);
deba@414
  1108
  checkGraphEdgeList(adaptor, 0);
deba@414
  1109
  checkGraphConArcList(adaptor, 0);
deba@414
  1110
  checkGraphConEdgeList(adaptor, 0);
deba@414
  1111
deba@414
  1112
  checkNodeIds(adaptor);
deba@414
  1113
  checkArcIds(adaptor);
deba@414
  1114
  checkEdgeIds(adaptor);
deba@414
  1115
deba@414
  1116
  checkGraphNodeMap(adaptor);
deba@414
  1117
  checkGraphArcMap(adaptor);
deba@414
  1118
  checkGraphEdgeMap(adaptor);
kpeter@463
  1119
kpeter@463
  1120
  // Check the conversion of nodes and edges
kpeter@463
  1121
  Graph::Node ng = n3;
kpeter@1197
  1122
  ::lemon::ignore_unused_variable_warning(ng);
kpeter@463
  1123
  ng = n4;
kpeter@463
  1124
  Adaptor::Node na = n1;
kpeter@1197
  1125
  ::lemon::ignore_unused_variable_warning(na);
kpeter@463
  1126
  na = n2;
kpeter@463
  1127
  Graph::Edge eg = e3;
kpeter@1197
  1128
  ::lemon::ignore_unused_variable_warning(eg);
kpeter@463
  1129
  eg = e4;
kpeter@463
  1130
  Adaptor::Edge ea = e1;
kpeter@1197
  1131
  ::lemon::ignore_unused_variable_warning(ea);
kpeter@463
  1132
  ea = e2;
deba@414
  1133
}
deba@414
  1134
deba@416
  1135
void checkFilterEdges() {
kpeter@463
  1136
  // Check concepts
kpeter@463
  1137
  checkConcept<concepts::Graph, FilterEdges<concepts::Graph> >();
kpeter@463
  1138
  checkConcept<concepts::Graph, FilterEdges<ListGraph> >();
kpeter@463
  1139
  checkConcept<concepts::AlterableGraphComponent<>,
kpeter@463
  1140
               FilterEdges<ListGraph> >();
kpeter@463
  1141
  checkConcept<concepts::ExtendableGraphComponent<>,
kpeter@463
  1142
               FilterEdges<ListGraph> >();
kpeter@463
  1143
  checkConcept<concepts::ErasableGraphComponent<>,
kpeter@463
  1144
               FilterEdges<ListGraph> >();
kpeter@463
  1145
  checkConcept<concepts::ClearableGraphComponent<>,
kpeter@463
  1146
               FilterEdges<ListGraph> >();
deba@414
  1147
kpeter@463
  1148
  // Create a graph and an adaptor
deba@414
  1149
  typedef ListGraph Graph;
deba@414
  1150
  typedef Graph::EdgeMap<bool> EdgeFilter;
deba@416
  1151
  typedef FilterEdges<Graph, EdgeFilter> Adaptor;
deba@414
  1152
deba@414
  1153
  Graph graph;
deba@414
  1154
  EdgeFilter edge_filter(graph);
deba@414
  1155
  Adaptor adaptor(graph, edge_filter);
deba@414
  1156
kpeter@463
  1157
  // Add nodes and edges to the original graph and the adaptor
deba@414
  1158
  Graph::Node n1 = graph.addNode();
deba@414
  1159
  Graph::Node n2 = graph.addNode();
kpeter@463
  1160
  Adaptor::Node n3 = adaptor.addNode();
kpeter@463
  1161
  Adaptor::Node n4 = adaptor.addNode();
deba@414
  1162
deba@414
  1163
  Graph::Edge e1 = graph.addEdge(n1, n2);
deba@414
  1164
  Graph::Edge e2 = graph.addEdge(n1, n3);
kpeter@463
  1165
  Adaptor::Edge e3 = adaptor.addEdge(n2, n3);
kpeter@463
  1166
  Adaptor::Edge e4 = adaptor.addEdge(n3, n4);
deba@414
  1167
deba@414
  1168
  edge_filter[e1] = edge_filter[e2] = edge_filter[e3] = edge_filter[e4] = true;
alpar@440
  1169
deba@414
  1170
  checkGraphNodeList(adaptor, 4);
deba@414
  1171
  checkGraphArcList(adaptor, 8);
deba@414
  1172
  checkGraphEdgeList(adaptor, 4);
deba@414
  1173
  checkGraphConArcList(adaptor, 8);
deba@414
  1174
  checkGraphConEdgeList(adaptor, 4);
deba@414
  1175
kpeter@463
  1176
  checkGraphIncEdgeArcLists(adaptor, n1, 2);
kpeter@463
  1177
  checkGraphIncEdgeArcLists(adaptor, n2, 2);
kpeter@463
  1178
  checkGraphIncEdgeArcLists(adaptor, n3, 3);
kpeter@463
  1179
  checkGraphIncEdgeArcLists(adaptor, n4, 1);
deba@414
  1180
deba@414
  1181
  checkNodeIds(adaptor);
deba@414
  1182
  checkArcIds(adaptor);
deba@414
  1183
  checkEdgeIds(adaptor);
deba@414
  1184
deba@414
  1185
  checkGraphNodeMap(adaptor);
deba@414
  1186
  checkGraphArcMap(adaptor);
deba@414
  1187
  checkGraphEdgeMap(adaptor);
deba@414
  1188
kpeter@463
  1189
  // Hide an edge
kpeter@463
  1190
  adaptor.status(e2, false);
kpeter@463
  1191
  adaptor.disable(e3);
kpeter@463
  1192
  if (!adaptor.status(e3)) adaptor.enable(e3);
deba@414
  1193
deba@414
  1194
  checkGraphNodeList(adaptor, 4);
deba@414
  1195
  checkGraphArcList(adaptor, 6);
deba@414
  1196
  checkGraphEdgeList(adaptor, 3);
deba@414
  1197
  checkGraphConArcList(adaptor, 6);
deba@414
  1198
  checkGraphConEdgeList(adaptor, 3);
deba@414
  1199
kpeter@463
  1200
  checkGraphIncEdgeArcLists(adaptor, n1, 1);
kpeter@463
  1201
  checkGraphIncEdgeArcLists(adaptor, n2, 2);
kpeter@463
  1202
  checkGraphIncEdgeArcLists(adaptor, n3, 2);
kpeter@463
  1203
  checkGraphIncEdgeArcLists(adaptor, n4, 1);
deba@414
  1204
deba@414
  1205
  checkNodeIds(adaptor);
deba@414
  1206
  checkArcIds(adaptor);
deba@414
  1207
  checkEdgeIds(adaptor);
deba@414
  1208
deba@414
  1209
  checkGraphNodeMap(adaptor);
deba@414
  1210
  checkGraphArcMap(adaptor);
deba@414
  1211
  checkGraphEdgeMap(adaptor);
deba@414
  1212
kpeter@463
  1213
  // Hide all edges
deba@414
  1214
  edge_filter[e1] = edge_filter[e2] = edge_filter[e3] = edge_filter[e4] = false;
deba@414
  1215
deba@414
  1216
  checkGraphNodeList(adaptor, 4);
deba@414
  1217
  checkGraphArcList(adaptor, 0);
deba@414
  1218
  checkGraphEdgeList(adaptor, 0);
deba@414
  1219
  checkGraphConArcList(adaptor, 0);
deba@414
  1220
  checkGraphConEdgeList(adaptor, 0);
deba@414
  1221
deba@414
  1222
  checkNodeIds(adaptor);
deba@414
  1223
  checkArcIds(adaptor);
deba@414
  1224
  checkEdgeIds(adaptor);
deba@414
  1225
deba@414
  1226
  checkGraphNodeMap(adaptor);
deba@414
  1227
  checkGraphArcMap(adaptor);
deba@414
  1228
  checkGraphEdgeMap(adaptor);
kpeter@463
  1229
kpeter@463
  1230
  // Check the conversion of nodes and edges
kpeter@463
  1231
  Graph::Node ng = n3;
kpeter@1197
  1232
  ::lemon::ignore_unused_variable_warning(ng);
kpeter@463
  1233
  ng = n4;
kpeter@463
  1234
  Adaptor::Node na = n1;
kpeter@1197
  1235
  ::lemon::ignore_unused_variable_warning(na);
kpeter@463
  1236
  na = n2;
kpeter@463
  1237
  Graph::Edge eg = e3;
kpeter@1197
  1238
  ::lemon::ignore_unused_variable_warning(eg);
kpeter@463
  1239
  eg = e4;
kpeter@463
  1240
  Adaptor::Edge ea = e1;
kpeter@1197
  1241
  ::lemon::ignore_unused_variable_warning(ea);
kpeter@463
  1242
  ea = e2;
deba@414
  1243
}
deba@414
  1244
deba@416
  1245
void checkOrienter() {
kpeter@463
  1246
  // Check concepts
kpeter@463
  1247
  checkConcept<concepts::Digraph, Orienter<concepts::Graph> >();
kpeter@463
  1248
  checkConcept<concepts::Digraph, Orienter<ListGraph> >();
kpeter@463
  1249
  checkConcept<concepts::AlterableDigraphComponent<>,
kpeter@463
  1250
               Orienter<ListGraph> >();
kpeter@463
  1251
  checkConcept<concepts::ExtendableDigraphComponent<>,
kpeter@463
  1252
               Orienter<ListGraph> >();
kpeter@463
  1253
  checkConcept<concepts::ErasableDigraphComponent<>,
kpeter@463
  1254
               Orienter<ListGraph> >();
kpeter@463
  1255
  checkConcept<concepts::ClearableDigraphComponent<>,
kpeter@463
  1256
               Orienter<ListGraph> >();
deba@414
  1257
kpeter@463
  1258
  // Create a graph and an adaptor
deba@414
  1259
  typedef ListGraph Graph;
deba@414
  1260
  typedef ListGraph::EdgeMap<bool> DirMap;
deba@416
  1261
  typedef Orienter<Graph> Adaptor;
deba@414
  1262
deba@414
  1263
  Graph graph;
kpeter@463
  1264
  DirMap dir(graph);
deba@414
  1265
  Adaptor adaptor(graph, dir);
deba@414
  1266
kpeter@463
  1267
  // Add nodes and edges to the original graph and the adaptor
deba@414
  1268
  Graph::Node n1 = graph.addNode();
deba@414
  1269
  Graph::Node n2 = graph.addNode();
kpeter@463
  1270
  Adaptor::Node n3 = adaptor.addNode();
deba@414
  1271
deba@414
  1272
  Graph::Edge e1 = graph.addEdge(n1, n2);
deba@414
  1273
  Graph::Edge e2 = graph.addEdge(n1, n3);
kpeter@463
  1274
  Adaptor::Arc e3 = adaptor.addArc(n2, n3);
deba@416
  1275
kpeter@463
  1276
  dir[e1] = dir[e2] = dir[e3] = true;
kpeter@463
  1277
kpeter@463
  1278
  // Check the original graph
kpeter@463
  1279
  checkGraphNodeList(graph, 3);
kpeter@463
  1280
  checkGraphArcList(graph, 6);
kpeter@463
  1281
  checkGraphConArcList(graph, 6);
kpeter@463
  1282
  checkGraphEdgeList(graph, 3);
kpeter@463
  1283
  checkGraphConEdgeList(graph, 3);
kpeter@463
  1284
kpeter@463
  1285
  checkGraphIncEdgeArcLists(graph, n1, 2);
kpeter@463
  1286
  checkGraphIncEdgeArcLists(graph, n2, 2);
kpeter@463
  1287
  checkGraphIncEdgeArcLists(graph, n3, 2);
kpeter@463
  1288
kpeter@463
  1289
  checkNodeIds(graph);
kpeter@463
  1290
  checkArcIds(graph);
kpeter@463
  1291
  checkEdgeIds(graph);
kpeter@463
  1292
kpeter@463
  1293
  checkGraphNodeMap(graph);
kpeter@463
  1294
  checkGraphArcMap(graph);
kpeter@463
  1295
  checkGraphEdgeMap(graph);
kpeter@463
  1296
kpeter@463
  1297
  // Check the adaptor
deba@414
  1298
  checkGraphNodeList(adaptor, 3);
deba@414
  1299
  checkGraphArcList(adaptor, 3);
deba@414
  1300
  checkGraphConArcList(adaptor, 3);
deba@416
  1301
kpeter@463
  1302
  checkGraphOutArcList(adaptor, n1, 2);
kpeter@463
  1303
  checkGraphOutArcList(adaptor, n2, 1);
kpeter@463
  1304
  checkGraphOutArcList(adaptor, n3, 0);
kpeter@463
  1305
kpeter@463
  1306
  checkGraphInArcList(adaptor, n1, 0);
kpeter@463
  1307
  checkGraphInArcList(adaptor, n2, 1);
kpeter@463
  1308
  checkGraphInArcList(adaptor, n3, 2);
kpeter@463
  1309
kpeter@463
  1310
  checkNodeIds(adaptor);
kpeter@463
  1311
  checkArcIds(adaptor);
kpeter@463
  1312
kpeter@463
  1313
  checkGraphNodeMap(adaptor);
kpeter@463
  1314
  checkGraphArcMap(adaptor);
kpeter@463
  1315
kpeter@463
  1316
  // Check direction changing
deba@414
  1317
  {
deba@414
  1318
    dir[e1] = true;
deba@414
  1319
    Adaptor::Node u = adaptor.source(e1);
deba@414
  1320
    Adaptor::Node v = adaptor.target(e1);
deba@416
  1321
deba@414
  1322
    dir[e1] = false;
deba@414
  1323
    check (u == adaptor.target(e1), "Wrong dir");
deba@414
  1324
    check (v == adaptor.source(e1), "Wrong dir");
deba@414
  1325
deba@414
  1326
    check ((u == n1 && v == n2) || (u == n2 && v == n1), "Wrong dir");
deba@414
  1327
    dir[e1] = n1 == u;
deba@414
  1328
  }
deba@414
  1329
deba@414
  1330
  {
deba@414
  1331
    dir[e2] = true;
deba@414
  1332
    Adaptor::Node u = adaptor.source(e2);
deba@414
  1333
    Adaptor::Node v = adaptor.target(e2);
deba@416
  1334
deba@414
  1335
    dir[e2] = false;
deba@414
  1336
    check (u == adaptor.target(e2), "Wrong dir");
deba@414
  1337
    check (v == adaptor.source(e2), "Wrong dir");
deba@414
  1338
deba@414
  1339
    check ((u == n1 && v == n3) || (u == n3 && v == n1), "Wrong dir");
deba@414
  1340
    dir[e2] = n3 == u;
deba@414
  1341
  }
deba@414
  1342
deba@414
  1343
  {
deba@414
  1344
    dir[e3] = true;
deba@414
  1345
    Adaptor::Node u = adaptor.source(e3);
deba@414
  1346
    Adaptor::Node v = adaptor.target(e3);
deba@416
  1347
deba@414
  1348
    dir[e3] = false;
deba@414
  1349
    check (u == adaptor.target(e3), "Wrong dir");
deba@414
  1350
    check (v == adaptor.source(e3), "Wrong dir");
deba@414
  1351
deba@414
  1352
    check ((u == n2 && v == n3) || (u == n3 && v == n2), "Wrong dir");
deba@414
  1353
    dir[e3] = n2 == u;
deba@414
  1354
  }
deba@414
  1355
kpeter@463
  1356
  // Check the adaptor again
kpeter@463
  1357
  checkGraphNodeList(adaptor, 3);
kpeter@463
  1358
  checkGraphArcList(adaptor, 3);
kpeter@463
  1359
  checkGraphConArcList(adaptor, 3);
kpeter@463
  1360
deba@414
  1361
  checkGraphOutArcList(adaptor, n1, 1);
deba@414
  1362
  checkGraphOutArcList(adaptor, n2, 1);
deba@414
  1363
  checkGraphOutArcList(adaptor, n3, 1);
deba@414
  1364
deba@414
  1365
  checkGraphInArcList(adaptor, n1, 1);
deba@414
  1366
  checkGraphInArcList(adaptor, n2, 1);
deba@414
  1367
  checkGraphInArcList(adaptor, n3, 1);
deba@414
  1368
deba@414
  1369
  checkNodeIds(adaptor);
deba@414
  1370
  checkArcIds(adaptor);
deba@414
  1371
deba@414
  1372
  checkGraphNodeMap(adaptor);
deba@414
  1373
  checkGraphArcMap(adaptor);
deba@414
  1374
kpeter@463
  1375
  // Check reverseArc()
kpeter@463
  1376
  adaptor.reverseArc(e2);
kpeter@463
  1377
  adaptor.reverseArc(e3);
kpeter@463
  1378
  adaptor.reverseArc(e2);
kpeter@463
  1379
kpeter@463
  1380
  checkGraphNodeList(adaptor, 3);
kpeter@463
  1381
  checkGraphArcList(adaptor, 3);
kpeter@463
  1382
  checkGraphConArcList(adaptor, 3);
kpeter@463
  1383
kpeter@463
  1384
  checkGraphOutArcList(adaptor, n1, 1);
kpeter@463
  1385
  checkGraphOutArcList(adaptor, n2, 0);
kpeter@463
  1386
  checkGraphOutArcList(adaptor, n3, 2);
kpeter@463
  1387
kpeter@463
  1388
  checkGraphInArcList(adaptor, n1, 1);
kpeter@463
  1389
  checkGraphInArcList(adaptor, n2, 2);
kpeter@463
  1390
  checkGraphInArcList(adaptor, n3, 0);
kpeter@463
  1391
kpeter@463
  1392
  // Check the conversion of nodes and arcs/edges
kpeter@463
  1393
  Graph::Node ng = n3;
kpeter@1197
  1394
  ::lemon::ignore_unused_variable_warning(ng);
kpeter@463
  1395
  ng = n3;
kpeter@463
  1396
  Adaptor::Node na = n1;
kpeter@1197
  1397
  ::lemon::ignore_unused_variable_warning(na);
kpeter@463
  1398
  na = n2;
kpeter@463
  1399
  Graph::Edge eg = e3;
kpeter@1197
  1400
  ::lemon::ignore_unused_variable_warning(eg);
kpeter@463
  1401
  eg = e3;
kpeter@463
  1402
  Adaptor::Arc aa = e1;
kpeter@1197
  1403
  ::lemon::ignore_unused_variable_warning(aa);
kpeter@463
  1404
  aa = e2;
deba@414
  1405
}
deba@414
  1406
kpeter@463
  1407
void checkCombiningAdaptors() {
kpeter@463
  1408
  // Create a grid graph
kpeter@463
  1409
  GridGraph graph(2,2);
kpeter@463
  1410
  GridGraph::Node n1 = graph(0,0);
kpeter@463
  1411
  GridGraph::Node n2 = graph(0,1);
kpeter@463
  1412
  GridGraph::Node n3 = graph(1,0);
kpeter@463
  1413
  GridGraph::Node n4 = graph(1,1);
kpeter@463
  1414
kpeter@463
  1415
  GridGraph::EdgeMap<bool> dir_map(graph);
kpeter@515
  1416
  dir_map[graph.right(n1)] = graph.u(graph.right(n1)) != n1;
kpeter@515
  1417
  dir_map[graph.up(n1)] = graph.u(graph.up(n1)) == n1;
kpeter@515
  1418
  dir_map[graph.left(n4)] = graph.u(graph.left(n4)) == n4;
kpeter@515
  1419
  dir_map[graph.down(n4)] = graph.u(graph.down(n4)) == n4;
kpeter@463
  1420
kpeter@463
  1421
  // Apply several adaptors on the grid graph
alpar@995
  1422
  typedef Orienter< const GridGraph, GridGraph::EdgeMap<bool> >
alpar@995
  1423
    OrientedGridGraph;
alpar@995
  1424
  typedef SplitNodes<OrientedGridGraph> SplitGridGraph;
kpeter@463
  1425
  typedef Undirector<const SplitGridGraph> USplitGridGraph;
kpeter@463
  1426
  checkConcept<concepts::Digraph, SplitGridGraph>();
kpeter@463
  1427
  checkConcept<concepts::Graph, USplitGridGraph>();
kpeter@463
  1428
alpar@995
  1429
  OrientedGridGraph oadaptor = orienter(graph, dir_map);
alpar@995
  1430
  SplitGridGraph adaptor = splitNodes(oadaptor);
kpeter@463
  1431
  USplitGridGraph uadaptor = undirector(adaptor);
kpeter@463
  1432
kpeter@463
  1433
  // Check adaptor
kpeter@463
  1434
  checkGraphNodeList(adaptor, 8);
kpeter@463
  1435
  checkGraphArcList(adaptor, 8);
kpeter@463
  1436
  checkGraphConArcList(adaptor, 8);
kpeter@463
  1437
kpeter@515
  1438
  checkGraphOutArcList(adaptor, adaptor.inNode(n1), 1);
kpeter@515
  1439
  checkGraphOutArcList(adaptor, adaptor.outNode(n1), 1);
kpeter@515
  1440
  checkGraphOutArcList(adaptor, adaptor.inNode(n2), 1);
kpeter@515
  1441
  checkGraphOutArcList(adaptor, adaptor.outNode(n2), 0);
kpeter@515
  1442
  checkGraphOutArcList(adaptor, adaptor.inNode(n3), 1);
kpeter@515
  1443
  checkGraphOutArcList(adaptor, adaptor.outNode(n3), 1);
kpeter@515
  1444
  checkGraphOutArcList(adaptor, adaptor.inNode(n4), 1);
kpeter@515
  1445
  checkGraphOutArcList(adaptor, adaptor.outNode(n4), 2);
kpeter@463
  1446
kpeter@515
  1447
  checkGraphInArcList(adaptor, adaptor.inNode(n1), 1);
kpeter@515
  1448
  checkGraphInArcList(adaptor, adaptor.outNode(n1), 1);
kpeter@515
  1449
  checkGraphInArcList(adaptor, adaptor.inNode(n2), 2);
kpeter@515
  1450
  checkGraphInArcList(adaptor, adaptor.outNode(n2), 1);
kpeter@515
  1451
  checkGraphInArcList(adaptor, adaptor.inNode(n3), 1);
kpeter@515
  1452
  checkGraphInArcList(adaptor, adaptor.outNode(n3), 1);
kpeter@515
  1453
  checkGraphInArcList(adaptor, adaptor.inNode(n4), 0);
kpeter@515
  1454
  checkGraphInArcList(adaptor, adaptor.outNode(n4), 1);
kpeter@463
  1455
kpeter@463
  1456
  checkNodeIds(adaptor);
kpeter@463
  1457
  checkArcIds(adaptor);
kpeter@463
  1458
kpeter@463
  1459
  checkGraphNodeMap(adaptor);
kpeter@463
  1460
  checkGraphArcMap(adaptor);
kpeter@463
  1461
kpeter@463
  1462
  // Check uadaptor
kpeter@463
  1463
  checkGraphNodeList(uadaptor, 8);
kpeter@463
  1464
  checkGraphEdgeList(uadaptor, 8);
kpeter@463
  1465
  checkGraphArcList(uadaptor, 16);
kpeter@463
  1466
  checkGraphConEdgeList(uadaptor, 8);
kpeter@463
  1467
  checkGraphConArcList(uadaptor, 16);
kpeter@463
  1468
kpeter@463
  1469
  checkNodeIds(uadaptor);
kpeter@463
  1470
  checkEdgeIds(uadaptor);
kpeter@463
  1471
  checkArcIds(uadaptor);
kpeter@463
  1472
kpeter@463
  1473
  checkGraphNodeMap(uadaptor);
kpeter@463
  1474
  checkGraphEdgeMap(uadaptor);
kpeter@463
  1475
  checkGraphArcMap(uadaptor);
kpeter@463
  1476
kpeter@515
  1477
  checkGraphIncEdgeArcLists(uadaptor, adaptor.inNode(n1), 2);
kpeter@515
  1478
  checkGraphIncEdgeArcLists(uadaptor, adaptor.outNode(n1), 2);
kpeter@515
  1479
  checkGraphIncEdgeArcLists(uadaptor, adaptor.inNode(n2), 3);
kpeter@515
  1480
  checkGraphIncEdgeArcLists(uadaptor, adaptor.outNode(n2), 1);
kpeter@515
  1481
  checkGraphIncEdgeArcLists(uadaptor, adaptor.inNode(n3), 2);
kpeter@515
  1482
  checkGraphIncEdgeArcLists(uadaptor, adaptor.outNode(n3), 2);
kpeter@515
  1483
  checkGraphIncEdgeArcLists(uadaptor, adaptor.inNode(n4), 1);
kpeter@515
  1484
  checkGraphIncEdgeArcLists(uadaptor, adaptor.outNode(n4), 3);
kpeter@463
  1485
}
deba@414
  1486
deba@414
  1487
int main(int, const char **) {
kpeter@463
  1488
  // Check the digraph adaptors (using ListDigraph)
deba@416
  1489
  checkReverseDigraph();
deba@416
  1490
  checkSubDigraph();
deba@416
  1491
  checkFilterNodes1();
deba@416
  1492
  checkFilterArcs();
deba@416
  1493
  checkUndirector();
kpeter@464
  1494
  checkResidualDigraph();
deba@416
  1495
  checkSplitNodes();
deba@414
  1496
kpeter@463
  1497
  // Check the graph adaptors (using ListGraph)
deba@416
  1498
  checkSubGraph();
deba@416
  1499
  checkFilterNodes2();
deba@416
  1500
  checkFilterEdges();
deba@416
  1501
  checkOrienter();
deba@414
  1502
kpeter@463
  1503
  // Combine adaptors (using GridGraph)
kpeter@463
  1504
  checkCombiningAdaptors();
kpeter@463
  1505
deba@414
  1506
  return 0;
deba@414
  1507
}