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