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