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