test/graph_adaptor_test.cc
author Alpar Juttner <alpar@cs.elte.hu>
Fri, 05 Dec 2008 13:10:16 +0000
changeset 422 62c1ed05e83f
parent 415 4b6112235fad
child 440 88ed40ad0d4f
permissions -rw-r--r--
chg-len.py does not scan any hg config file now
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
 *
deba@414
     5
 * Copyright (C) 2003-2008
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
deba@414
    19
#include<iostream>
deba@414
    20
#include<lemon/concept_check.h>
deba@414
    21
deba@414
    22
#include<lemon/list_graph.h>
deba@414
    23
#include<lemon/smart_graph.h>
deba@414
    24
deba@414
    25
#include<lemon/concepts/digraph.h>
deba@414
    26
#include<lemon/concepts/graph.h>
deba@414
    27
deba@416
    28
#include<lemon/adaptors.h>
deba@414
    29
deba@414
    30
#include <limits>
deba@414
    31
#include <lemon/bfs.h>
deba@414
    32
#include <lemon/path.h>
deba@414
    33
deba@414
    34
#include"test/test_tools.h"
deba@414
    35
#include"test/graph_test.h"
deba@414
    36
deba@414
    37
using namespace lemon;
deba@414
    38
deba@416
    39
void checkReverseDigraph() {
deba@416
    40
  checkConcept<concepts::Digraph, ReverseDigraph<concepts::Digraph> >();
deba@414
    41
deba@414
    42
  typedef ListDigraph Digraph;
deba@416
    43
  typedef ReverseDigraph<Digraph> Adaptor;
deba@414
    44
deba@414
    45
  Digraph digraph;
deba@414
    46
  Adaptor adaptor(digraph);
deba@414
    47
deba@414
    48
  Digraph::Node n1 = digraph.addNode();
deba@414
    49
  Digraph::Node n2 = digraph.addNode();
deba@414
    50
  Digraph::Node n3 = digraph.addNode();
deba@414
    51
deba@414
    52
  Digraph::Arc a1 = digraph.addArc(n1, n2);
deba@414
    53
  Digraph::Arc a2 = digraph.addArc(n1, n3);
deba@414
    54
  Digraph::Arc a3 = digraph.addArc(n2, n3);
deba@416
    55
deba@414
    56
  checkGraphNodeList(adaptor, 3);
deba@414
    57
  checkGraphArcList(adaptor, 3);
deba@414
    58
  checkGraphConArcList(adaptor, 3);
deba@414
    59
deba@414
    60
  checkGraphOutArcList(adaptor, n1, 0);
deba@414
    61
  checkGraphOutArcList(adaptor, n2, 1);
deba@414
    62
  checkGraphOutArcList(adaptor, n3, 2);
deba@414
    63
deba@414
    64
  checkGraphInArcList(adaptor, n1, 2);
deba@414
    65
  checkGraphInArcList(adaptor, n2, 1);
deba@414
    66
  checkGraphInArcList(adaptor, n3, 0);
deba@414
    67
deba@414
    68
  checkNodeIds(adaptor);
deba@414
    69
  checkArcIds(adaptor);
deba@414
    70
deba@414
    71
  checkGraphNodeMap(adaptor);
deba@414
    72
  checkGraphArcMap(adaptor);
deba@414
    73
deba@414
    74
  for (Adaptor::ArcIt a(adaptor); a != INVALID; ++a) {
deba@414
    75
    check(adaptor.source(a) == digraph.target(a), "Wrong reverse");
deba@414
    76
    check(adaptor.target(a) == digraph.source(a), "Wrong reverse");
deba@414
    77
  }
deba@414
    78
}
deba@414
    79
deba@416
    80
void checkSubDigraph() {
deba@416
    81
  checkConcept<concepts::Digraph,
deba@416
    82
    SubDigraph<concepts::Digraph,
deba@414
    83
    concepts::Digraph::NodeMap<bool>,
deba@414
    84
    concepts::Digraph::ArcMap<bool> > >();
deba@414
    85
deba@414
    86
  typedef ListDigraph Digraph;
deba@414
    87
  typedef Digraph::NodeMap<bool> NodeFilter;
deba@414
    88
  typedef Digraph::ArcMap<bool> ArcFilter;
deba@416
    89
  typedef SubDigraph<Digraph, NodeFilter, ArcFilter> Adaptor;
deba@414
    90
deba@414
    91
  Digraph digraph;
deba@414
    92
  NodeFilter node_filter(digraph);
deba@414
    93
  ArcFilter arc_filter(digraph);
deba@414
    94
  Adaptor adaptor(digraph, node_filter, arc_filter);
deba@414
    95
deba@414
    96
  Digraph::Node n1 = digraph.addNode();
deba@414
    97
  Digraph::Node n2 = digraph.addNode();
deba@414
    98
  Digraph::Node n3 = digraph.addNode();
deba@414
    99
deba@414
   100
  Digraph::Arc a1 = digraph.addArc(n1, n2);
deba@414
   101
  Digraph::Arc a2 = digraph.addArc(n1, n3);
deba@414
   102
  Digraph::Arc a3 = digraph.addArc(n2, n3);
deba@414
   103
deba@414
   104
  node_filter[n1] = node_filter[n2] = node_filter[n3] = true;
deba@414
   105
  arc_filter[a1] = arc_filter[a2] = arc_filter[a3] = true;
deba@414
   106
  
deba@414
   107
  checkGraphNodeList(adaptor, 3);
deba@414
   108
  checkGraphArcList(adaptor, 3);
deba@414
   109
  checkGraphConArcList(adaptor, 3);
deba@414
   110
deba@414
   111
  checkGraphOutArcList(adaptor, n1, 2);
deba@414
   112
  checkGraphOutArcList(adaptor, n2, 1);
deba@414
   113
  checkGraphOutArcList(adaptor, n3, 0);
deba@414
   114
deba@414
   115
  checkGraphInArcList(adaptor, n1, 0);
deba@414
   116
  checkGraphInArcList(adaptor, n2, 1);
deba@414
   117
  checkGraphInArcList(adaptor, n3, 2);
deba@414
   118
deba@414
   119
  checkNodeIds(adaptor);
deba@414
   120
  checkArcIds(adaptor);
deba@414
   121
deba@414
   122
  checkGraphNodeMap(adaptor);
deba@414
   123
  checkGraphArcMap(adaptor);
deba@414
   124
deba@416
   125
  arc_filter[a2] = false;
deba@414
   126
deba@414
   127
  checkGraphNodeList(adaptor, 3);
deba@414
   128
  checkGraphArcList(adaptor, 2);
deba@414
   129
  checkGraphConArcList(adaptor, 2);
deba@414
   130
deba@414
   131
  checkGraphOutArcList(adaptor, n1, 1);
deba@414
   132
  checkGraphOutArcList(adaptor, n2, 1);
deba@414
   133
  checkGraphOutArcList(adaptor, n3, 0);
deba@414
   134
deba@414
   135
  checkGraphInArcList(adaptor, n1, 0);
deba@414
   136
  checkGraphInArcList(adaptor, n2, 1);
deba@414
   137
  checkGraphInArcList(adaptor, n3, 1);
deba@414
   138
deba@414
   139
  checkNodeIds(adaptor);
deba@414
   140
  checkArcIds(adaptor);
deba@414
   141
deba@414
   142
  checkGraphNodeMap(adaptor);
deba@414
   143
  checkGraphArcMap(adaptor);
deba@414
   144
deba@416
   145
  node_filter[n1] = false;
deba@414
   146
deba@414
   147
  checkGraphNodeList(adaptor, 2);
deba@414
   148
  checkGraphArcList(adaptor, 1);
deba@414
   149
  checkGraphConArcList(adaptor, 1);
deba@414
   150
deba@414
   151
  checkGraphOutArcList(adaptor, n2, 1);
deba@414
   152
  checkGraphOutArcList(adaptor, n3, 0);
deba@414
   153
deba@414
   154
  checkGraphInArcList(adaptor, n2, 0);
deba@414
   155
  checkGraphInArcList(adaptor, n3, 1);
deba@414
   156
deba@414
   157
  checkNodeIds(adaptor);
deba@414
   158
  checkArcIds(adaptor);
deba@414
   159
deba@414
   160
  checkGraphNodeMap(adaptor);
deba@414
   161
  checkGraphArcMap(adaptor);
deba@414
   162
deba@414
   163
  node_filter[n1] = node_filter[n2] = node_filter[n3] = false;
deba@414
   164
  arc_filter[a1] = arc_filter[a2] = arc_filter[a3] = false;
deba@414
   165
deba@414
   166
  checkGraphNodeList(adaptor, 0);
deba@414
   167
  checkGraphArcList(adaptor, 0);
deba@414
   168
  checkGraphConArcList(adaptor, 0);
deba@414
   169
deba@414
   170
  checkNodeIds(adaptor);
deba@414
   171
  checkArcIds(adaptor);
deba@414
   172
deba@414
   173
  checkGraphNodeMap(adaptor);
deba@414
   174
  checkGraphArcMap(adaptor);
deba@414
   175
}
deba@414
   176
deba@416
   177
void checkFilterNodes1() {
deba@416
   178
  checkConcept<concepts::Digraph,
deba@416
   179
    FilterNodes<concepts::Digraph,
deba@414
   180
      concepts::Digraph::NodeMap<bool> > >();
deba@414
   181
deba@414
   182
  typedef ListDigraph Digraph;
deba@414
   183
  typedef Digraph::NodeMap<bool> NodeFilter;
deba@416
   184
  typedef FilterNodes<Digraph, NodeFilter> Adaptor;
deba@414
   185
deba@414
   186
  Digraph digraph;
deba@414
   187
  NodeFilter node_filter(digraph);
deba@414
   188
  Adaptor adaptor(digraph, node_filter);
deba@414
   189
deba@414
   190
  Digraph::Node n1 = digraph.addNode();
deba@414
   191
  Digraph::Node n2 = digraph.addNode();
deba@414
   192
  Digraph::Node n3 = digraph.addNode();
deba@414
   193
deba@414
   194
  Digraph::Arc a1 = digraph.addArc(n1, n2);
deba@414
   195
  Digraph::Arc a2 = digraph.addArc(n1, n3);
deba@414
   196
  Digraph::Arc a3 = digraph.addArc(n2, n3);
deba@414
   197
deba@414
   198
  node_filter[n1] = node_filter[n2] = node_filter[n3] = true;
deba@414
   199
  
deba@414
   200
  checkGraphNodeList(adaptor, 3);
deba@414
   201
  checkGraphArcList(adaptor, 3);
deba@414
   202
  checkGraphConArcList(adaptor, 3);
deba@414
   203
deba@414
   204
  checkGraphOutArcList(adaptor, n1, 2);
deba@414
   205
  checkGraphOutArcList(adaptor, n2, 1);
deba@414
   206
  checkGraphOutArcList(adaptor, n3, 0);
deba@414
   207
deba@414
   208
  checkGraphInArcList(adaptor, n1, 0);
deba@414
   209
  checkGraphInArcList(adaptor, n2, 1);
deba@414
   210
  checkGraphInArcList(adaptor, n3, 2);
deba@414
   211
deba@414
   212
  checkNodeIds(adaptor);
deba@414
   213
  checkArcIds(adaptor);
deba@414
   214
deba@414
   215
  checkGraphNodeMap(adaptor);
deba@414
   216
  checkGraphArcMap(adaptor);
deba@414
   217
deba@416
   218
  node_filter[n1] = false;
deba@414
   219
deba@414
   220
  checkGraphNodeList(adaptor, 2);
deba@414
   221
  checkGraphArcList(adaptor, 1);
deba@414
   222
  checkGraphConArcList(adaptor, 1);
deba@414
   223
deba@414
   224
  checkGraphOutArcList(adaptor, n2, 1);
deba@414
   225
  checkGraphOutArcList(adaptor, n3, 0);
deba@414
   226
deba@414
   227
  checkGraphInArcList(adaptor, n2, 0);
deba@414
   228
  checkGraphInArcList(adaptor, n3, 1);
deba@414
   229
deba@414
   230
  checkNodeIds(adaptor);
deba@414
   231
  checkArcIds(adaptor);
deba@414
   232
deba@414
   233
  checkGraphNodeMap(adaptor);
deba@414
   234
  checkGraphArcMap(adaptor);
deba@414
   235
deba@414
   236
  node_filter[n1] = node_filter[n2] = node_filter[n3] = false;
deba@414
   237
deba@414
   238
  checkGraphNodeList(adaptor, 0);
deba@414
   239
  checkGraphArcList(adaptor, 0);
deba@414
   240
  checkGraphConArcList(adaptor, 0);
deba@414
   241
deba@414
   242
  checkNodeIds(adaptor);
deba@414
   243
  checkArcIds(adaptor);
deba@414
   244
deba@414
   245
  checkGraphNodeMap(adaptor);
deba@414
   246
  checkGraphArcMap(adaptor);
deba@414
   247
}
deba@414
   248
deba@416
   249
void checkFilterArcs() {
deba@416
   250
  checkConcept<concepts::Digraph,
deba@416
   251
    FilterArcs<concepts::Digraph,
deba@414
   252
    concepts::Digraph::ArcMap<bool> > >();
deba@414
   253
deba@414
   254
  typedef ListDigraph Digraph;
deba@414
   255
  typedef Digraph::ArcMap<bool> ArcFilter;
deba@416
   256
  typedef FilterArcs<Digraph, ArcFilter> Adaptor;
deba@414
   257
deba@414
   258
  Digraph digraph;
deba@414
   259
  ArcFilter arc_filter(digraph);
deba@414
   260
  Adaptor adaptor(digraph, arc_filter);
deba@414
   261
deba@414
   262
  Digraph::Node n1 = digraph.addNode();
deba@414
   263
  Digraph::Node n2 = digraph.addNode();
deba@414
   264
  Digraph::Node n3 = digraph.addNode();
deba@414
   265
deba@414
   266
  Digraph::Arc a1 = digraph.addArc(n1, n2);
deba@414
   267
  Digraph::Arc a2 = digraph.addArc(n1, n3);
deba@414
   268
  Digraph::Arc a3 = digraph.addArc(n2, n3);
deba@414
   269
deba@414
   270
  arc_filter[a1] = arc_filter[a2] = arc_filter[a3] = true;
deba@414
   271
  
deba@414
   272
  checkGraphNodeList(adaptor, 3);
deba@414
   273
  checkGraphArcList(adaptor, 3);
deba@414
   274
  checkGraphConArcList(adaptor, 3);
deba@414
   275
deba@414
   276
  checkGraphOutArcList(adaptor, n1, 2);
deba@414
   277
  checkGraphOutArcList(adaptor, n2, 1);
deba@414
   278
  checkGraphOutArcList(adaptor, n3, 0);
deba@414
   279
deba@414
   280
  checkGraphInArcList(adaptor, n1, 0);
deba@414
   281
  checkGraphInArcList(adaptor, n2, 1);
deba@414
   282
  checkGraphInArcList(adaptor, n3, 2);
deba@414
   283
deba@414
   284
  checkNodeIds(adaptor);
deba@414
   285
  checkArcIds(adaptor);
deba@414
   286
deba@414
   287
  checkGraphNodeMap(adaptor);
deba@414
   288
  checkGraphArcMap(adaptor);
deba@414
   289
deba@416
   290
  arc_filter[a2] = false;
deba@414
   291
deba@414
   292
  checkGraphNodeList(adaptor, 3);
deba@414
   293
  checkGraphArcList(adaptor, 2);
deba@414
   294
  checkGraphConArcList(adaptor, 2);
deba@414
   295
deba@414
   296
  checkGraphOutArcList(adaptor, n1, 1);
deba@414
   297
  checkGraphOutArcList(adaptor, n2, 1);
deba@414
   298
  checkGraphOutArcList(adaptor, n3, 0);
deba@414
   299
deba@414
   300
  checkGraphInArcList(adaptor, n1, 0);
deba@414
   301
  checkGraphInArcList(adaptor, n2, 1);
deba@414
   302
  checkGraphInArcList(adaptor, n3, 1);
deba@414
   303
deba@414
   304
  checkNodeIds(adaptor);
deba@414
   305
  checkArcIds(adaptor);
deba@414
   306
deba@414
   307
  checkGraphNodeMap(adaptor);
deba@414
   308
  checkGraphArcMap(adaptor);
deba@414
   309
deba@414
   310
  arc_filter[a1] = arc_filter[a2] = arc_filter[a3] = false;
deba@414
   311
deba@414
   312
  checkGraphNodeList(adaptor, 3);
deba@414
   313
  checkGraphArcList(adaptor, 0);
deba@414
   314
  checkGraphConArcList(adaptor, 0);
deba@414
   315
deba@414
   316
  checkNodeIds(adaptor);
deba@414
   317
  checkArcIds(adaptor);
deba@414
   318
deba@414
   319
  checkGraphNodeMap(adaptor);
deba@414
   320
  checkGraphArcMap(adaptor);
deba@414
   321
}
deba@414
   322
deba@416
   323
void checkUndirector() {
deba@416
   324
  checkConcept<concepts::Graph, Undirector<concepts::Digraph> >();
deba@414
   325
deba@414
   326
  typedef ListDigraph Digraph;
deba@416
   327
  typedef Undirector<Digraph> Adaptor;
deba@414
   328
deba@414
   329
  Digraph digraph;
deba@414
   330
  Adaptor adaptor(digraph);
deba@414
   331
deba@414
   332
  Digraph::Node n1 = digraph.addNode();
deba@414
   333
  Digraph::Node n2 = digraph.addNode();
deba@414
   334
  Digraph::Node n3 = digraph.addNode();
deba@414
   335
deba@414
   336
  Digraph::Arc a1 = digraph.addArc(n1, n2);
deba@414
   337
  Digraph::Arc a2 = digraph.addArc(n1, n3);
deba@414
   338
  Digraph::Arc a3 = digraph.addArc(n2, n3);
deba@416
   339
deba@414
   340
  checkGraphNodeList(adaptor, 3);
deba@414
   341
  checkGraphArcList(adaptor, 6);
deba@414
   342
  checkGraphEdgeList(adaptor, 3);
deba@414
   343
  checkGraphConArcList(adaptor, 6);
deba@414
   344
  checkGraphConEdgeList(adaptor, 3);
deba@414
   345
deba@414
   346
  checkGraphOutArcList(adaptor, n1, 2);
deba@414
   347
  checkGraphOutArcList(adaptor, n2, 2);
deba@414
   348
  checkGraphOutArcList(adaptor, n3, 2);
deba@414
   349
deba@414
   350
  checkGraphInArcList(adaptor, n1, 2);
deba@414
   351
  checkGraphInArcList(adaptor, n2, 2);
deba@414
   352
  checkGraphInArcList(adaptor, n3, 2);
deba@414
   353
deba@414
   354
  checkGraphIncEdgeList(adaptor, n1, 2);
deba@414
   355
  checkGraphIncEdgeList(adaptor, n2, 2);
deba@414
   356
  checkGraphIncEdgeList(adaptor, n3, 2);
deba@414
   357
deba@414
   358
  checkNodeIds(adaptor);
deba@414
   359
  checkArcIds(adaptor);
deba@414
   360
  checkEdgeIds(adaptor);
deba@414
   361
deba@414
   362
  checkGraphNodeMap(adaptor);
deba@414
   363
  checkGraphArcMap(adaptor);
deba@414
   364
  checkGraphEdgeMap(adaptor);
deba@414
   365
deba@414
   366
  for (Adaptor::EdgeIt e(adaptor); e != INVALID; ++e) {
deba@414
   367
    check(adaptor.u(e) == digraph.source(e), "Wrong undir");
deba@414
   368
    check(adaptor.v(e) == digraph.target(e), "Wrong undir");
deba@414
   369
  }
deba@414
   370
deba@414
   371
}
deba@414
   372
deba@416
   373
void checkResidual() {
deba@416
   374
  checkConcept<concepts::Digraph,
deba@416
   375
    Residual<concepts::Digraph,
deba@416
   376
    concepts::Digraph::ArcMap<int>,
deba@414
   377
    concepts::Digraph::ArcMap<int> > >();
deba@414
   378
deba@414
   379
  typedef ListDigraph Digraph;
deba@414
   380
  typedef Digraph::ArcMap<int> IntArcMap;
deba@416
   381
  typedef Residual<Digraph, IntArcMap> Adaptor;
deba@414
   382
deba@414
   383
  Digraph digraph;
deba@414
   384
  IntArcMap capacity(digraph), flow(digraph);
deba@414
   385
  Adaptor adaptor(digraph, capacity, flow);
deba@414
   386
deba@414
   387
  Digraph::Node n1 = digraph.addNode();
deba@414
   388
  Digraph::Node n2 = digraph.addNode();
deba@414
   389
  Digraph::Node n3 = digraph.addNode();
deba@414
   390
  Digraph::Node n4 = digraph.addNode();
deba@414
   391
deba@414
   392
  Digraph::Arc a1 = digraph.addArc(n1, n2);
deba@414
   393
  Digraph::Arc a2 = digraph.addArc(n1, n3);
deba@414
   394
  Digraph::Arc a3 = digraph.addArc(n1, n4);
deba@414
   395
  Digraph::Arc a4 = digraph.addArc(n2, n3);
deba@414
   396
  Digraph::Arc a5 = digraph.addArc(n2, n4);
deba@414
   397
  Digraph::Arc a6 = digraph.addArc(n3, n4);
deba@414
   398
deba@414
   399
  capacity[a1] = 8;
deba@414
   400
  capacity[a2] = 6;
deba@414
   401
  capacity[a3] = 4;
deba@414
   402
  capacity[a4] = 4;
deba@414
   403
  capacity[a5] = 6;
deba@414
   404
  capacity[a6] = 10;
deba@414
   405
deba@414
   406
  for (Adaptor::ArcIt a(adaptor); a != INVALID; ++a) {
deba@414
   407
    flow[a] = 0;
deba@414
   408
  }
deba@416
   409
deba@414
   410
  checkGraphNodeList(adaptor, 4);
deba@414
   411
  checkGraphArcList(adaptor, 6);
deba@414
   412
  checkGraphConArcList(adaptor, 6);
deba@414
   413
deba@414
   414
  checkGraphOutArcList(adaptor, n1, 3);
deba@414
   415
  checkGraphOutArcList(adaptor, n2, 2);
deba@414
   416
  checkGraphOutArcList(adaptor, n3, 1);
deba@414
   417
  checkGraphOutArcList(adaptor, n4, 0);
deba@414
   418
deba@414
   419
  checkGraphInArcList(adaptor, n1, 0);
deba@414
   420
  checkGraphInArcList(adaptor, n2, 1);
deba@414
   421
  checkGraphInArcList(adaptor, n3, 2);
deba@414
   422
  checkGraphInArcList(adaptor, n4, 3);
deba@414
   423
deba@414
   424
  for (Adaptor::ArcIt a(adaptor); a != INVALID; ++a) {
deba@414
   425
    flow[a] = capacity[a] / 2;
deba@414
   426
  }
deba@416
   427
deba@414
   428
  checkGraphNodeList(adaptor, 4);
deba@414
   429
  checkGraphArcList(adaptor, 12);
deba@414
   430
  checkGraphConArcList(adaptor, 12);
deba@414
   431
deba@414
   432
  checkGraphOutArcList(adaptor, n1, 3);
deba@414
   433
  checkGraphOutArcList(adaptor, n2, 3);
deba@414
   434
  checkGraphOutArcList(adaptor, n3, 3);
deba@414
   435
  checkGraphOutArcList(adaptor, n4, 3);
deba@414
   436
deba@414
   437
  checkGraphInArcList(adaptor, n1, 3);
deba@414
   438
  checkGraphInArcList(adaptor, n2, 3);
deba@414
   439
  checkGraphInArcList(adaptor, n3, 3);
deba@414
   440
  checkGraphInArcList(adaptor, n4, 3);
deba@414
   441
deba@414
   442
  checkNodeIds(adaptor);
deba@414
   443
  checkArcIds(adaptor);
deba@414
   444
deba@414
   445
  checkGraphNodeMap(adaptor);
deba@414
   446
  checkGraphArcMap(adaptor);
deba@414
   447
deba@414
   448
  for (Adaptor::ArcIt a(adaptor); a != INVALID; ++a) {
deba@414
   449
    flow[a] = capacity[a];
deba@414
   450
  }
deba@416
   451
deba@414
   452
  checkGraphNodeList(adaptor, 4);
deba@414
   453
  checkGraphArcList(adaptor, 6);
deba@414
   454
  checkGraphConArcList(adaptor, 6);
deba@414
   455
deba@414
   456
  checkGraphOutArcList(adaptor, n1, 0);
deba@414
   457
  checkGraphOutArcList(adaptor, n2, 1);
deba@414
   458
  checkGraphOutArcList(adaptor, n3, 2);
deba@414
   459
  checkGraphOutArcList(adaptor, n4, 3);
deba@414
   460
deba@414
   461
  checkGraphInArcList(adaptor, n1, 3);
deba@414
   462
  checkGraphInArcList(adaptor, n2, 2);
deba@414
   463
  checkGraphInArcList(adaptor, n3, 1);
deba@414
   464
  checkGraphInArcList(adaptor, n4, 0);
deba@414
   465
deba@414
   466
  for (Adaptor::ArcIt a(adaptor); a != INVALID; ++a) {
deba@414
   467
    flow[a] = 0;
deba@414
   468
  }
deba@414
   469
deba@414
   470
  int flow_value = 0;
deba@414
   471
  while (true) {
deba@416
   472
deba@414
   473
    Bfs<Adaptor> bfs(adaptor);
deba@414
   474
    bfs.run(n1, n4);
deba@416
   475
deba@414
   476
    if (!bfs.reached(n4)) break;
deba@414
   477
deba@414
   478
    Path<Adaptor> p = bfs.path(n4);
deba@416
   479
deba@414
   480
    int min = std::numeric_limits<int>::max();
deba@414
   481
    for (Path<Adaptor>::ArcIt a(p); a != INVALID; ++a) {
deba@416
   482
      if (adaptor.residualCapacity(a) < min)
deba@416
   483
        min = adaptor.residualCapacity(a);
deba@414
   484
    }
deba@414
   485
deba@414
   486
    for (Path<Adaptor>::ArcIt a(p); a != INVALID; ++a) {
deba@414
   487
      adaptor.augment(a, min);
deba@414
   488
    }
deba@414
   489
    flow_value += min;
deba@414
   490
  }
deba@414
   491
deba@414
   492
  check(flow_value == 18, "Wrong flow with res graph adaptor");
deba@414
   493
deba@414
   494
}
deba@414
   495
deba@416
   496
void checkSplitNodes() {
deba@416
   497
  checkConcept<concepts::Digraph, SplitNodes<concepts::Digraph> >();
deba@414
   498
deba@414
   499
  typedef ListDigraph Digraph;
deba@416
   500
  typedef SplitNodes<Digraph> Adaptor;
deba@414
   501
deba@414
   502
  Digraph digraph;
deba@414
   503
  Adaptor adaptor(digraph);
deba@414
   504
deba@414
   505
  Digraph::Node n1 = digraph.addNode();
deba@414
   506
  Digraph::Node n2 = digraph.addNode();
deba@414
   507
  Digraph::Node n3 = digraph.addNode();
deba@414
   508
deba@414
   509
  Digraph::Arc a1 = digraph.addArc(n1, n2);
deba@414
   510
  Digraph::Arc a2 = digraph.addArc(n1, n3);
deba@414
   511
  Digraph::Arc a3 = digraph.addArc(n2, n3);
deba@416
   512
deba@414
   513
  checkGraphNodeList(adaptor, 6);
deba@414
   514
  checkGraphArcList(adaptor, 6);
deba@414
   515
  checkGraphConArcList(adaptor, 6);
deba@414
   516
deba@414
   517
  checkGraphOutArcList(adaptor, adaptor.inNode(n1), 1);
deba@414
   518
  checkGraphOutArcList(adaptor, adaptor.outNode(n1), 2);
deba@414
   519
  checkGraphOutArcList(adaptor, adaptor.inNode(n2), 1);
deba@414
   520
  checkGraphOutArcList(adaptor, adaptor.outNode(n2), 1);
deba@414
   521
  checkGraphOutArcList(adaptor, adaptor.inNode(n3), 1);
deba@414
   522
  checkGraphOutArcList(adaptor, adaptor.outNode(n3), 0);
deba@414
   523
deba@414
   524
  checkGraphInArcList(adaptor, adaptor.inNode(n1), 0);
deba@414
   525
  checkGraphInArcList(adaptor, adaptor.outNode(n1), 1);
deba@414
   526
  checkGraphInArcList(adaptor, adaptor.inNode(n2), 1);
deba@414
   527
  checkGraphInArcList(adaptor, adaptor.outNode(n2), 1);
deba@414
   528
  checkGraphInArcList(adaptor, adaptor.inNode(n3), 2);
deba@414
   529
  checkGraphInArcList(adaptor, adaptor.outNode(n3), 1);
deba@414
   530
deba@414
   531
  checkNodeIds(adaptor);
deba@414
   532
  checkArcIds(adaptor);
deba@416
   533
deba@414
   534
  checkGraphNodeMap(adaptor);
deba@414
   535
  checkGraphArcMap(adaptor);
deba@414
   536
deba@414
   537
  for (Adaptor::ArcIt a(adaptor); a != INVALID; ++a) {
deba@414
   538
    if (adaptor.origArc(a)) {
deba@414
   539
      Digraph::Arc oa = a;
deba@416
   540
      check(adaptor.source(a) == adaptor.outNode(digraph.source(oa)),
deba@416
   541
            "Wrong split");
deba@416
   542
      check(adaptor.target(a) == adaptor.inNode(digraph.target(oa)),
deba@416
   543
            "Wrong split");
deba@414
   544
    } else {
deba@414
   545
      Digraph::Node on = a;
deba@414
   546
      check(adaptor.source(a) == adaptor.inNode(on), "Wrong split");
deba@414
   547
      check(adaptor.target(a) == adaptor.outNode(on), "Wrong split");
deba@414
   548
    }
deba@414
   549
  }
deba@414
   550
}
deba@414
   551
deba@416
   552
void checkSubGraph() {
deba@416
   553
  checkConcept<concepts::Graph,
deba@416
   554
    SubGraph<concepts::Graph,
deba@414
   555
    concepts::Graph::NodeMap<bool>,
deba@414
   556
    concepts::Graph::EdgeMap<bool> > >();
deba@414
   557
deba@414
   558
  typedef ListGraph Graph;
deba@414
   559
  typedef Graph::NodeMap<bool> NodeFilter;
deba@414
   560
  typedef Graph::EdgeMap<bool> EdgeFilter;
deba@416
   561
  typedef SubGraph<Graph, NodeFilter, EdgeFilter> Adaptor;
deba@414
   562
deba@414
   563
  Graph graph;
deba@414
   564
  NodeFilter node_filter(graph);
deba@414
   565
  EdgeFilter edge_filter(graph);
deba@414
   566
  Adaptor adaptor(graph, node_filter, edge_filter);
deba@414
   567
deba@414
   568
  Graph::Node n1 = graph.addNode();
deba@414
   569
  Graph::Node n2 = graph.addNode();
deba@414
   570
  Graph::Node n3 = graph.addNode();
deba@414
   571
  Graph::Node n4 = graph.addNode();
deba@414
   572
deba@414
   573
  Graph::Edge e1 = graph.addEdge(n1, n2);
deba@414
   574
  Graph::Edge e2 = graph.addEdge(n1, n3);
deba@414
   575
  Graph::Edge e3 = graph.addEdge(n2, n3);
deba@414
   576
  Graph::Edge e4 = graph.addEdge(n3, n4);
deba@414
   577
deba@414
   578
  node_filter[n1] = node_filter[n2] = node_filter[n3] = node_filter[n4] = true;
deba@414
   579
  edge_filter[e1] = edge_filter[e2] = edge_filter[e3] = edge_filter[e4] = true;
deba@414
   580
  
deba@414
   581
  checkGraphNodeList(adaptor, 4);
deba@414
   582
  checkGraphArcList(adaptor, 8);
deba@414
   583
  checkGraphEdgeList(adaptor, 4);
deba@414
   584
  checkGraphConArcList(adaptor, 8);
deba@414
   585
  checkGraphConEdgeList(adaptor, 4);
deba@414
   586
deba@414
   587
  checkGraphOutArcList(adaptor, n1, 2);
deba@414
   588
  checkGraphOutArcList(adaptor, n2, 2);
deba@414
   589
  checkGraphOutArcList(adaptor, n3, 3);
deba@414
   590
  checkGraphOutArcList(adaptor, n4, 1);
deba@414
   591
deba@414
   592
  checkGraphInArcList(adaptor, n1, 2);
deba@414
   593
  checkGraphInArcList(adaptor, n2, 2);
deba@414
   594
  checkGraphInArcList(adaptor, n3, 3);
deba@414
   595
  checkGraphInArcList(adaptor, n4, 1);
deba@414
   596
deba@414
   597
  checkGraphIncEdgeList(adaptor, n1, 2);
deba@414
   598
  checkGraphIncEdgeList(adaptor, n2, 2);
deba@414
   599
  checkGraphIncEdgeList(adaptor, n3, 3);
deba@414
   600
  checkGraphIncEdgeList(adaptor, n4, 1);
deba@414
   601
deba@414
   602
  checkNodeIds(adaptor);
deba@414
   603
  checkArcIds(adaptor);
deba@414
   604
  checkEdgeIds(adaptor);
deba@414
   605
deba@414
   606
  checkGraphNodeMap(adaptor);
deba@414
   607
  checkGraphArcMap(adaptor);
deba@414
   608
  checkGraphEdgeMap(adaptor);
deba@414
   609
deba@416
   610
  edge_filter[e2] = false;
deba@414
   611
deba@414
   612
  checkGraphNodeList(adaptor, 4);
deba@414
   613
  checkGraphArcList(adaptor, 6);
deba@414
   614
  checkGraphEdgeList(adaptor, 3);
deba@414
   615
  checkGraphConArcList(adaptor, 6);
deba@414
   616
  checkGraphConEdgeList(adaptor, 3);
deba@414
   617
deba@414
   618
  checkGraphOutArcList(adaptor, n1, 1);
deba@414
   619
  checkGraphOutArcList(adaptor, n2, 2);
deba@414
   620
  checkGraphOutArcList(adaptor, n3, 2);
deba@414
   621
  checkGraphOutArcList(adaptor, n4, 1);
deba@414
   622
deba@414
   623
  checkGraphInArcList(adaptor, n1, 1);
deba@414
   624
  checkGraphInArcList(adaptor, n2, 2);
deba@414
   625
  checkGraphInArcList(adaptor, n3, 2);
deba@414
   626
  checkGraphInArcList(adaptor, n4, 1);
deba@414
   627
deba@414
   628
  checkGraphIncEdgeList(adaptor, n1, 1);
deba@414
   629
  checkGraphIncEdgeList(adaptor, n2, 2);
deba@414
   630
  checkGraphIncEdgeList(adaptor, n3, 2);
deba@414
   631
  checkGraphIncEdgeList(adaptor, n4, 1);
deba@414
   632
deba@414
   633
  checkNodeIds(adaptor);
deba@414
   634
  checkArcIds(adaptor);
deba@414
   635
  checkEdgeIds(adaptor);
deba@414
   636
deba@414
   637
  checkGraphNodeMap(adaptor);
deba@414
   638
  checkGraphArcMap(adaptor);
deba@414
   639
  checkGraphEdgeMap(adaptor);
deba@414
   640
deba@416
   641
  node_filter[n1] = false;
deba@414
   642
deba@414
   643
  checkGraphNodeList(adaptor, 3);
deba@414
   644
  checkGraphArcList(adaptor, 4);
deba@414
   645
  checkGraphEdgeList(adaptor, 2);
deba@414
   646
  checkGraphConArcList(adaptor, 4);
deba@414
   647
  checkGraphConEdgeList(adaptor, 2);
deba@414
   648
deba@414
   649
  checkGraphOutArcList(adaptor, n2, 1);
deba@414
   650
  checkGraphOutArcList(adaptor, n3, 2);
deba@414
   651
  checkGraphOutArcList(adaptor, n4, 1);
deba@414
   652
deba@414
   653
  checkGraphInArcList(adaptor, n2, 1);
deba@414
   654
  checkGraphInArcList(adaptor, n3, 2);
deba@414
   655
  checkGraphInArcList(adaptor, n4, 1);
deba@414
   656
deba@414
   657
  checkGraphIncEdgeList(adaptor, n2, 1);
deba@414
   658
  checkGraphIncEdgeList(adaptor, n3, 2);
deba@414
   659
  checkGraphIncEdgeList(adaptor, n4, 1);
deba@414
   660
deba@414
   661
  checkNodeIds(adaptor);
deba@414
   662
  checkArcIds(adaptor);
deba@414
   663
  checkEdgeIds(adaptor);
deba@414
   664
deba@414
   665
  checkGraphNodeMap(adaptor);
deba@414
   666
  checkGraphArcMap(adaptor);
deba@414
   667
  checkGraphEdgeMap(adaptor);
deba@414
   668
deba@414
   669
  node_filter[n1] = node_filter[n2] = node_filter[n3] = node_filter[n4] = false;
deba@414
   670
  edge_filter[e1] = edge_filter[e2] = edge_filter[e3] = edge_filter[e4] = false;
deba@414
   671
deba@414
   672
  checkGraphNodeList(adaptor, 0);
deba@414
   673
  checkGraphArcList(adaptor, 0);
deba@414
   674
  checkGraphEdgeList(adaptor, 0);
deba@414
   675
  checkGraphConArcList(adaptor, 0);
deba@414
   676
  checkGraphConEdgeList(adaptor, 0);
deba@414
   677
deba@414
   678
  checkNodeIds(adaptor);
deba@414
   679
  checkArcIds(adaptor);
deba@414
   680
  checkEdgeIds(adaptor);
deba@414
   681
deba@414
   682
  checkGraphNodeMap(adaptor);
deba@414
   683
  checkGraphArcMap(adaptor);
deba@414
   684
  checkGraphEdgeMap(adaptor);
deba@414
   685
}
deba@414
   686
deba@416
   687
void checkFilterNodes2() {
deba@416
   688
  checkConcept<concepts::Graph,
deba@416
   689
    FilterNodes<concepts::Graph,
deba@414
   690
      concepts::Graph::NodeMap<bool> > >();
deba@414
   691
deba@414
   692
  typedef ListGraph Graph;
deba@414
   693
  typedef Graph::NodeMap<bool> NodeFilter;
deba@416
   694
  typedef FilterNodes<Graph, NodeFilter> Adaptor;
deba@414
   695
deba@414
   696
  Graph graph;
deba@414
   697
  NodeFilter node_filter(graph);
deba@414
   698
  Adaptor adaptor(graph, node_filter);
deba@414
   699
deba@414
   700
  Graph::Node n1 = graph.addNode();
deba@414
   701
  Graph::Node n2 = graph.addNode();
deba@414
   702
  Graph::Node n3 = graph.addNode();
deba@414
   703
  Graph::Node n4 = graph.addNode();
deba@414
   704
deba@414
   705
  Graph::Edge e1 = graph.addEdge(n1, n2);
deba@414
   706
  Graph::Edge e2 = graph.addEdge(n1, n3);
deba@414
   707
  Graph::Edge e3 = graph.addEdge(n2, n3);
deba@414
   708
  Graph::Edge e4 = graph.addEdge(n3, n4);
deba@414
   709
deba@414
   710
  node_filter[n1] = node_filter[n2] = node_filter[n3] = node_filter[n4] = true;
deba@414
   711
  
deba@414
   712
  checkGraphNodeList(adaptor, 4);
deba@414
   713
  checkGraphArcList(adaptor, 8);
deba@414
   714
  checkGraphEdgeList(adaptor, 4);
deba@414
   715
  checkGraphConArcList(adaptor, 8);
deba@414
   716
  checkGraphConEdgeList(adaptor, 4);
deba@414
   717
deba@414
   718
  checkGraphOutArcList(adaptor, n1, 2);
deba@414
   719
  checkGraphOutArcList(adaptor, n2, 2);
deba@414
   720
  checkGraphOutArcList(adaptor, n3, 3);
deba@414
   721
  checkGraphOutArcList(adaptor, n4, 1);
deba@414
   722
deba@414
   723
  checkGraphInArcList(adaptor, n1, 2);
deba@414
   724
  checkGraphInArcList(adaptor, n2, 2);
deba@414
   725
  checkGraphInArcList(adaptor, n3, 3);
deba@414
   726
  checkGraphInArcList(adaptor, n4, 1);
deba@414
   727
deba@414
   728
  checkGraphIncEdgeList(adaptor, n1, 2);
deba@414
   729
  checkGraphIncEdgeList(adaptor, n2, 2);
deba@414
   730
  checkGraphIncEdgeList(adaptor, n3, 3);
deba@414
   731
  checkGraphIncEdgeList(adaptor, n4, 1);
deba@414
   732
deba@414
   733
  checkNodeIds(adaptor);
deba@414
   734
  checkArcIds(adaptor);
deba@414
   735
  checkEdgeIds(adaptor);
deba@414
   736
deba@414
   737
  checkGraphNodeMap(adaptor);
deba@414
   738
  checkGraphArcMap(adaptor);
deba@414
   739
  checkGraphEdgeMap(adaptor);
deba@414
   740
deba@416
   741
  node_filter[n1] = false;
deba@414
   742
deba@414
   743
  checkGraphNodeList(adaptor, 3);
deba@414
   744
  checkGraphArcList(adaptor, 4);
deba@414
   745
  checkGraphEdgeList(adaptor, 2);
deba@414
   746
  checkGraphConArcList(adaptor, 4);
deba@414
   747
  checkGraphConEdgeList(adaptor, 2);
deba@414
   748
deba@414
   749
  checkGraphOutArcList(adaptor, n2, 1);
deba@414
   750
  checkGraphOutArcList(adaptor, n3, 2);
deba@414
   751
  checkGraphOutArcList(adaptor, n4, 1);
deba@414
   752
deba@414
   753
  checkGraphInArcList(adaptor, n2, 1);
deba@414
   754
  checkGraphInArcList(adaptor, n3, 2);
deba@414
   755
  checkGraphInArcList(adaptor, n4, 1);
deba@414
   756
deba@414
   757
  checkGraphIncEdgeList(adaptor, n2, 1);
deba@414
   758
  checkGraphIncEdgeList(adaptor, n3, 2);
deba@414
   759
  checkGraphIncEdgeList(adaptor, n4, 1);
deba@414
   760
deba@414
   761
  checkNodeIds(adaptor);
deba@414
   762
  checkArcIds(adaptor);
deba@414
   763
  checkEdgeIds(adaptor);
deba@414
   764
deba@414
   765
  checkGraphNodeMap(adaptor);
deba@414
   766
  checkGraphArcMap(adaptor);
deba@414
   767
  checkGraphEdgeMap(adaptor);
deba@414
   768
deba@414
   769
  node_filter[n1] = node_filter[n2] = node_filter[n3] = node_filter[n4] = false;
deba@414
   770
deba@414
   771
  checkGraphNodeList(adaptor, 0);
deba@414
   772
  checkGraphArcList(adaptor, 0);
deba@414
   773
  checkGraphEdgeList(adaptor, 0);
deba@414
   774
  checkGraphConArcList(adaptor, 0);
deba@414
   775
  checkGraphConEdgeList(adaptor, 0);
deba@414
   776
deba@414
   777
  checkNodeIds(adaptor);
deba@414
   778
  checkArcIds(adaptor);
deba@414
   779
  checkEdgeIds(adaptor);
deba@414
   780
deba@414
   781
  checkGraphNodeMap(adaptor);
deba@414
   782
  checkGraphArcMap(adaptor);
deba@414
   783
  checkGraphEdgeMap(adaptor);
deba@414
   784
}
deba@414
   785
deba@416
   786
void checkFilterEdges() {
deba@416
   787
  checkConcept<concepts::Graph,
deba@416
   788
    FilterEdges<concepts::Graph,
deba@414
   789
    concepts::Graph::EdgeMap<bool> > >();
deba@414
   790
deba@414
   791
  typedef ListGraph Graph;
deba@414
   792
  typedef Graph::EdgeMap<bool> EdgeFilter;
deba@416
   793
  typedef FilterEdges<Graph, EdgeFilter> Adaptor;
deba@414
   794
deba@414
   795
  Graph graph;
deba@414
   796
  EdgeFilter edge_filter(graph);
deba@414
   797
  Adaptor adaptor(graph, edge_filter);
deba@414
   798
deba@414
   799
  Graph::Node n1 = graph.addNode();
deba@414
   800
  Graph::Node n2 = graph.addNode();
deba@414
   801
  Graph::Node n3 = graph.addNode();
deba@414
   802
  Graph::Node n4 = graph.addNode();
deba@414
   803
deba@414
   804
  Graph::Edge e1 = graph.addEdge(n1, n2);
deba@414
   805
  Graph::Edge e2 = graph.addEdge(n1, n3);
deba@414
   806
  Graph::Edge e3 = graph.addEdge(n2, n3);
deba@414
   807
  Graph::Edge e4 = graph.addEdge(n3, n4);
deba@414
   808
deba@414
   809
  edge_filter[e1] = edge_filter[e2] = edge_filter[e3] = edge_filter[e4] = true;
deba@414
   810
  
deba@414
   811
  checkGraphNodeList(adaptor, 4);
deba@414
   812
  checkGraphArcList(adaptor, 8);
deba@414
   813
  checkGraphEdgeList(adaptor, 4);
deba@414
   814
  checkGraphConArcList(adaptor, 8);
deba@414
   815
  checkGraphConEdgeList(adaptor, 4);
deba@414
   816
deba@414
   817
  checkGraphOutArcList(adaptor, n1, 2);
deba@414
   818
  checkGraphOutArcList(adaptor, n2, 2);
deba@414
   819
  checkGraphOutArcList(adaptor, n3, 3);
deba@414
   820
  checkGraphOutArcList(adaptor, n4, 1);
deba@414
   821
deba@414
   822
  checkGraphInArcList(adaptor, n1, 2);
deba@414
   823
  checkGraphInArcList(adaptor, n2, 2);
deba@414
   824
  checkGraphInArcList(adaptor, n3, 3);
deba@414
   825
  checkGraphInArcList(adaptor, n4, 1);
deba@414
   826
deba@414
   827
  checkGraphIncEdgeList(adaptor, n1, 2);
deba@414
   828
  checkGraphIncEdgeList(adaptor, n2, 2);
deba@414
   829
  checkGraphIncEdgeList(adaptor, n3, 3);
deba@414
   830
  checkGraphIncEdgeList(adaptor, n4, 1);
deba@414
   831
deba@414
   832
  checkNodeIds(adaptor);
deba@414
   833
  checkArcIds(adaptor);
deba@414
   834
  checkEdgeIds(adaptor);
deba@414
   835
deba@414
   836
  checkGraphNodeMap(adaptor);
deba@414
   837
  checkGraphArcMap(adaptor);
deba@414
   838
  checkGraphEdgeMap(adaptor);
deba@414
   839
deba@416
   840
  edge_filter[e2] = false;
deba@414
   841
deba@414
   842
  checkGraphNodeList(adaptor, 4);
deba@414
   843
  checkGraphArcList(adaptor, 6);
deba@414
   844
  checkGraphEdgeList(adaptor, 3);
deba@414
   845
  checkGraphConArcList(adaptor, 6);
deba@414
   846
  checkGraphConEdgeList(adaptor, 3);
deba@414
   847
deba@414
   848
  checkGraphOutArcList(adaptor, n1, 1);
deba@414
   849
  checkGraphOutArcList(adaptor, n2, 2);
deba@414
   850
  checkGraphOutArcList(adaptor, n3, 2);
deba@414
   851
  checkGraphOutArcList(adaptor, n4, 1);
deba@414
   852
deba@414
   853
  checkGraphInArcList(adaptor, n1, 1);
deba@414
   854
  checkGraphInArcList(adaptor, n2, 2);
deba@414
   855
  checkGraphInArcList(adaptor, n3, 2);
deba@414
   856
  checkGraphInArcList(adaptor, n4, 1);
deba@414
   857
deba@414
   858
  checkGraphIncEdgeList(adaptor, n1, 1);
deba@414
   859
  checkGraphIncEdgeList(adaptor, n2, 2);
deba@414
   860
  checkGraphIncEdgeList(adaptor, n3, 2);
deba@414
   861
  checkGraphIncEdgeList(adaptor, n4, 1);
deba@414
   862
deba@414
   863
  checkNodeIds(adaptor);
deba@414
   864
  checkArcIds(adaptor);
deba@414
   865
  checkEdgeIds(adaptor);
deba@414
   866
deba@414
   867
  checkGraphNodeMap(adaptor);
deba@414
   868
  checkGraphArcMap(adaptor);
deba@414
   869
  checkGraphEdgeMap(adaptor);
deba@414
   870
deba@414
   871
  edge_filter[e1] = edge_filter[e2] = edge_filter[e3] = edge_filter[e4] = false;
deba@414
   872
deba@414
   873
  checkGraphNodeList(adaptor, 4);
deba@414
   874
  checkGraphArcList(adaptor, 0);
deba@414
   875
  checkGraphEdgeList(adaptor, 0);
deba@414
   876
  checkGraphConArcList(adaptor, 0);
deba@414
   877
  checkGraphConEdgeList(adaptor, 0);
deba@414
   878
deba@414
   879
  checkNodeIds(adaptor);
deba@414
   880
  checkArcIds(adaptor);
deba@414
   881
  checkEdgeIds(adaptor);
deba@414
   882
deba@414
   883
  checkGraphNodeMap(adaptor);
deba@414
   884
  checkGraphArcMap(adaptor);
deba@414
   885
  checkGraphEdgeMap(adaptor);
deba@414
   886
}
deba@414
   887
deba@416
   888
void checkOrienter() {
deba@416
   889
  checkConcept<concepts::Digraph,
deba@416
   890
    Orienter<concepts::Graph, concepts::Graph::EdgeMap<bool> > >();
deba@414
   891
deba@414
   892
  typedef ListGraph Graph;
deba@414
   893
  typedef ListGraph::EdgeMap<bool> DirMap;
deba@416
   894
  typedef Orienter<Graph> Adaptor;
deba@414
   895
deba@414
   896
  Graph graph;
deba@414
   897
  DirMap dir(graph, true);
deba@414
   898
  Adaptor adaptor(graph, dir);
deba@414
   899
deba@414
   900
  Graph::Node n1 = graph.addNode();
deba@414
   901
  Graph::Node n2 = graph.addNode();
deba@414
   902
  Graph::Node n3 = graph.addNode();
deba@414
   903
deba@414
   904
  Graph::Edge e1 = graph.addEdge(n1, n2);
deba@414
   905
  Graph::Edge e2 = graph.addEdge(n1, n3);
deba@414
   906
  Graph::Edge e3 = graph.addEdge(n2, n3);
deba@416
   907
deba@414
   908
  checkGraphNodeList(adaptor, 3);
deba@414
   909
  checkGraphArcList(adaptor, 3);
deba@414
   910
  checkGraphConArcList(adaptor, 3);
deba@416
   911
deba@414
   912
  {
deba@414
   913
    dir[e1] = true;
deba@414
   914
    Adaptor::Node u = adaptor.source(e1);
deba@414
   915
    Adaptor::Node v = adaptor.target(e1);
deba@416
   916
deba@414
   917
    dir[e1] = false;
deba@414
   918
    check (u == adaptor.target(e1), "Wrong dir");
deba@414
   919
    check (v == adaptor.source(e1), "Wrong dir");
deba@414
   920
deba@414
   921
    check ((u == n1 && v == n2) || (u == n2 && v == n1), "Wrong dir");
deba@414
   922
    dir[e1] = n1 == u;
deba@414
   923
  }
deba@414
   924
deba@414
   925
  {
deba@414
   926
    dir[e2] = true;
deba@414
   927
    Adaptor::Node u = adaptor.source(e2);
deba@414
   928
    Adaptor::Node v = adaptor.target(e2);
deba@416
   929
deba@414
   930
    dir[e2] = false;
deba@414
   931
    check (u == adaptor.target(e2), "Wrong dir");
deba@414
   932
    check (v == adaptor.source(e2), "Wrong dir");
deba@414
   933
deba@414
   934
    check ((u == n1 && v == n3) || (u == n3 && v == n1), "Wrong dir");
deba@414
   935
    dir[e2] = n3 == u;
deba@414
   936
  }
deba@414
   937
deba@414
   938
  {
deba@414
   939
    dir[e3] = true;
deba@414
   940
    Adaptor::Node u = adaptor.source(e3);
deba@414
   941
    Adaptor::Node v = adaptor.target(e3);
deba@416
   942
deba@414
   943
    dir[e3] = false;
deba@414
   944
    check (u == adaptor.target(e3), "Wrong dir");
deba@414
   945
    check (v == adaptor.source(e3), "Wrong dir");
deba@414
   946
deba@414
   947
    check ((u == n2 && v == n3) || (u == n3 && v == n2), "Wrong dir");
deba@414
   948
    dir[e3] = n2 == u;
deba@414
   949
  }
deba@414
   950
deba@414
   951
  checkGraphOutArcList(adaptor, n1, 1);
deba@414
   952
  checkGraphOutArcList(adaptor, n2, 1);
deba@414
   953
  checkGraphOutArcList(adaptor, n3, 1);
deba@414
   954
deba@414
   955
  checkGraphInArcList(adaptor, n1, 1);
deba@414
   956
  checkGraphInArcList(adaptor, n2, 1);
deba@414
   957
  checkGraphInArcList(adaptor, n3, 1);
deba@414
   958
deba@414
   959
  checkNodeIds(adaptor);
deba@414
   960
  checkArcIds(adaptor);
deba@414
   961
deba@414
   962
  checkGraphNodeMap(adaptor);
deba@414
   963
  checkGraphArcMap(adaptor);
deba@414
   964
deba@414
   965
}
deba@414
   966
deba@414
   967
deba@414
   968
int main(int, const char **) {
deba@414
   969
deba@416
   970
  checkReverseDigraph();
deba@416
   971
  checkSubDigraph();
deba@416
   972
  checkFilterNodes1();
deba@416
   973
  checkFilterArcs();
deba@416
   974
  checkUndirector();
deba@416
   975
  checkResidual();
deba@416
   976
  checkSplitNodes();
deba@414
   977
deba@416
   978
  checkSubGraph();
deba@416
   979
  checkFilterNodes2();
deba@416
   980
  checkFilterEdges();
deba@416
   981
  checkOrienter();
deba@414
   982
deba@414
   983
  return 0;
deba@414
   984
}