test/adaptors_test.cc
changeset 467 a1155a9e8e09
parent 464 acfb0f24d178
child 515 c35afa9e89e7
child 997 761fe0846f49
     1.1 --- /dev/null	Thu Jan 01 00:00:00 1970 +0000
     1.2 +++ b/test/adaptors_test.cc	Mon Jan 12 13:18:03 2009 +0000
     1.3 @@ -0,0 +1,1486 @@
     1.4 +/* -*- mode: C++; indent-tabs-mode: nil; -*-
     1.5 + *
     1.6 + * This file is a part of LEMON, a generic C++ optimization library.
     1.7 + *
     1.8 + * Copyright (C) 2003-2009
     1.9 + * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    1.10 + * (Egervary Research Group on Combinatorial Optimization, EGRES).
    1.11 + *
    1.12 + * Permission to use, modify and distribute this software is granted
    1.13 + * provided that this copyright notice appears in all copies. For
    1.14 + * precise terms see the accompanying LICENSE file.
    1.15 + *
    1.16 + * This software is provided "AS IS" with no warranty of any kind,
    1.17 + * express or implied, and with no claim as to its suitability for any
    1.18 + * purpose.
    1.19 + *
    1.20 + */
    1.21 +
    1.22 +#include <iostream>
    1.23 +#include <limits>
    1.24 +
    1.25 +#include <lemon/list_graph.h>
    1.26 +#include <lemon/grid_graph.h>
    1.27 +#include <lemon/bfs.h>
    1.28 +#include <lemon/path.h>
    1.29 +
    1.30 +#include <lemon/concepts/digraph.h>
    1.31 +#include <lemon/concepts/graph.h>
    1.32 +#include <lemon/concepts/graph_components.h>
    1.33 +#include <lemon/concepts/maps.h>
    1.34 +#include <lemon/concept_check.h>
    1.35 +
    1.36 +#include <lemon/adaptors.h>
    1.37 +
    1.38 +#include "test/test_tools.h"
    1.39 +#include "test/graph_test.h"
    1.40 +
    1.41 +using namespace lemon;
    1.42 +
    1.43 +void checkReverseDigraph() {
    1.44 +  // Check concepts
    1.45 +  checkConcept<concepts::Digraph, ReverseDigraph<concepts::Digraph> >();
    1.46 +  checkConcept<concepts::Digraph, ReverseDigraph<ListDigraph> >();
    1.47 +  checkConcept<concepts::AlterableDigraphComponent<>,
    1.48 +               ReverseDigraph<ListDigraph> >();
    1.49 +  checkConcept<concepts::ExtendableDigraphComponent<>,
    1.50 +               ReverseDigraph<ListDigraph> >();
    1.51 +  checkConcept<concepts::ErasableDigraphComponent<>,
    1.52 +               ReverseDigraph<ListDigraph> >();
    1.53 +  checkConcept<concepts::ClearableDigraphComponent<>,
    1.54 +               ReverseDigraph<ListDigraph> >();
    1.55 +
    1.56 +  // Create a digraph and an adaptor
    1.57 +  typedef ListDigraph Digraph;
    1.58 +  typedef ReverseDigraph<Digraph> Adaptor;
    1.59 +
    1.60 +  Digraph digraph;
    1.61 +  Adaptor adaptor(digraph);
    1.62 +
    1.63 +  // Add nodes and arcs to the original digraph
    1.64 +  Digraph::Node n1 = digraph.addNode();
    1.65 +  Digraph::Node n2 = digraph.addNode();
    1.66 +  Digraph::Node n3 = digraph.addNode();
    1.67 +
    1.68 +  Digraph::Arc a1 = digraph.addArc(n1, n2);
    1.69 +  Digraph::Arc a2 = digraph.addArc(n1, n3);
    1.70 +  Digraph::Arc a3 = digraph.addArc(n2, n3);
    1.71 +
    1.72 +  // Check the adaptor
    1.73 +  checkGraphNodeList(adaptor, 3);
    1.74 +  checkGraphArcList(adaptor, 3);
    1.75 +  checkGraphConArcList(adaptor, 3);
    1.76 +
    1.77 +  checkGraphOutArcList(adaptor, n1, 0);
    1.78 +  checkGraphOutArcList(adaptor, n2, 1);
    1.79 +  checkGraphOutArcList(adaptor, n3, 2);
    1.80 +
    1.81 +  checkGraphInArcList(adaptor, n1, 2);
    1.82 +  checkGraphInArcList(adaptor, n2, 1);
    1.83 +  checkGraphInArcList(adaptor, n3, 0);
    1.84 +
    1.85 +  checkNodeIds(adaptor);
    1.86 +  checkArcIds(adaptor);
    1.87 +
    1.88 +  checkGraphNodeMap(adaptor);
    1.89 +  checkGraphArcMap(adaptor);
    1.90 +
    1.91 +  // Check the orientation of the arcs
    1.92 +  for (Adaptor::ArcIt a(adaptor); a != INVALID; ++a) {
    1.93 +    check(adaptor.source(a) == digraph.target(a), "Wrong reverse");
    1.94 +    check(adaptor.target(a) == digraph.source(a), "Wrong reverse");
    1.95 +  }
    1.96 +
    1.97 +  // Add and erase nodes and arcs in the digraph through the adaptor
    1.98 +  Adaptor::Node n4 = adaptor.addNode();
    1.99 +
   1.100 +  Adaptor::Arc a4 = adaptor.addArc(n4, n3);
   1.101 +  Adaptor::Arc a5 = adaptor.addArc(n2, n4);
   1.102 +  Adaptor::Arc a6 = adaptor.addArc(n2, n4);
   1.103 +  Adaptor::Arc a7 = adaptor.addArc(n1, n4);
   1.104 +  Adaptor::Arc a8 = adaptor.addArc(n1, n2);
   1.105 +
   1.106 +  adaptor.erase(a1);
   1.107 +  adaptor.erase(n3);
   1.108 +
   1.109 +  // Check the adaptor
   1.110 +  checkGraphNodeList(adaptor, 3);
   1.111 +  checkGraphArcList(adaptor, 4);
   1.112 +  checkGraphConArcList(adaptor, 4);
   1.113 +
   1.114 +  checkGraphOutArcList(adaptor, n1, 2);
   1.115 +  checkGraphOutArcList(adaptor, n2, 2);
   1.116 +  checkGraphOutArcList(adaptor, n4, 0);
   1.117 +
   1.118 +  checkGraphInArcList(adaptor, n1, 0);
   1.119 +  checkGraphInArcList(adaptor, n2, 1);
   1.120 +  checkGraphInArcList(adaptor, n4, 3);
   1.121 +
   1.122 +  checkNodeIds(adaptor);
   1.123 +  checkArcIds(adaptor);
   1.124 +
   1.125 +  checkGraphNodeMap(adaptor);
   1.126 +  checkGraphArcMap(adaptor);
   1.127 +
   1.128 +  // Check the digraph
   1.129 +  checkGraphNodeList(digraph, 3);
   1.130 +  checkGraphArcList(digraph, 4);
   1.131 +  checkGraphConArcList(digraph, 4);
   1.132 +
   1.133 +  checkGraphOutArcList(digraph, n1, 0);
   1.134 +  checkGraphOutArcList(digraph, n2, 1);
   1.135 +  checkGraphOutArcList(digraph, n4, 3);
   1.136 +
   1.137 +  checkGraphInArcList(digraph, n1, 2);
   1.138 +  checkGraphInArcList(digraph, n2, 2);
   1.139 +  checkGraphInArcList(digraph, n4, 0);
   1.140 +
   1.141 +  checkNodeIds(digraph);
   1.142 +  checkArcIds(digraph);
   1.143 +
   1.144 +  checkGraphNodeMap(digraph);
   1.145 +  checkGraphArcMap(digraph);
   1.146 +
   1.147 +  // Check the conversion of nodes and arcs
   1.148 +  Digraph::Node nd = n4;
   1.149 +  nd = n4;
   1.150 +  Adaptor::Node na = n1;
   1.151 +  na = n2;
   1.152 +  Digraph::Arc ad = a4;
   1.153 +  ad = a5;
   1.154 +  Adaptor::Arc aa = a1;
   1.155 +  aa = a2;
   1.156 +}
   1.157 +
   1.158 +void checkSubDigraph() {
   1.159 +  // Check concepts
   1.160 +  checkConcept<concepts::Digraph, SubDigraph<concepts::Digraph> >();
   1.161 +  checkConcept<concepts::Digraph, SubDigraph<ListDigraph> >();
   1.162 +  checkConcept<concepts::AlterableDigraphComponent<>,
   1.163 +               SubDigraph<ListDigraph> >();
   1.164 +  checkConcept<concepts::ExtendableDigraphComponent<>,
   1.165 +               SubDigraph<ListDigraph> >();
   1.166 +  checkConcept<concepts::ErasableDigraphComponent<>,
   1.167 +               SubDigraph<ListDigraph> >();
   1.168 +  checkConcept<concepts::ClearableDigraphComponent<>,
   1.169 +               SubDigraph<ListDigraph> >();
   1.170 +
   1.171 +  // Create a digraph and an adaptor
   1.172 +  typedef ListDigraph Digraph;
   1.173 +  typedef Digraph::NodeMap<bool> NodeFilter;
   1.174 +  typedef Digraph::ArcMap<bool> ArcFilter;
   1.175 +  typedef SubDigraph<Digraph, NodeFilter, ArcFilter> Adaptor;
   1.176 +
   1.177 +  Digraph digraph;
   1.178 +  NodeFilter node_filter(digraph);
   1.179 +  ArcFilter arc_filter(digraph);
   1.180 +  Adaptor adaptor(digraph, node_filter, arc_filter);
   1.181 +
   1.182 +  // Add nodes and arcs to the original digraph and the adaptor
   1.183 +  Digraph::Node n1 = digraph.addNode();
   1.184 +  Digraph::Node n2 = digraph.addNode();
   1.185 +  Adaptor::Node n3 = adaptor.addNode();
   1.186 +
   1.187 +  node_filter[n1] = node_filter[n2] = node_filter[n3] = true;
   1.188 +
   1.189 +  Digraph::Arc a1 = digraph.addArc(n1, n2);
   1.190 +  Digraph::Arc a2 = digraph.addArc(n1, n3);
   1.191 +  Adaptor::Arc a3 = adaptor.addArc(n2, n3);
   1.192 +
   1.193 +  arc_filter[a1] = arc_filter[a2] = arc_filter[a3] = true;
   1.194 +
   1.195 +  checkGraphNodeList(adaptor, 3);
   1.196 +  checkGraphArcList(adaptor, 3);
   1.197 +  checkGraphConArcList(adaptor, 3);
   1.198 +
   1.199 +  checkGraphOutArcList(adaptor, n1, 2);
   1.200 +  checkGraphOutArcList(adaptor, n2, 1);
   1.201 +  checkGraphOutArcList(adaptor, n3, 0);
   1.202 +
   1.203 +  checkGraphInArcList(adaptor, n1, 0);
   1.204 +  checkGraphInArcList(adaptor, n2, 1);
   1.205 +  checkGraphInArcList(adaptor, n3, 2);
   1.206 +
   1.207 +  checkNodeIds(adaptor);
   1.208 +  checkArcIds(adaptor);
   1.209 +
   1.210 +  checkGraphNodeMap(adaptor);
   1.211 +  checkGraphArcMap(adaptor);
   1.212 +
   1.213 +  // Hide an arc
   1.214 +  adaptor.status(a2, false);
   1.215 +  adaptor.disable(a3);
   1.216 +  if (!adaptor.status(a3)) adaptor.enable(a3);
   1.217 +
   1.218 +  checkGraphNodeList(adaptor, 3);
   1.219 +  checkGraphArcList(adaptor, 2);
   1.220 +  checkGraphConArcList(adaptor, 2);
   1.221 +
   1.222 +  checkGraphOutArcList(adaptor, n1, 1);
   1.223 +  checkGraphOutArcList(adaptor, n2, 1);
   1.224 +  checkGraphOutArcList(adaptor, n3, 0);
   1.225 +
   1.226 +  checkGraphInArcList(adaptor, n1, 0);
   1.227 +  checkGraphInArcList(adaptor, n2, 1);
   1.228 +  checkGraphInArcList(adaptor, n3, 1);
   1.229 +
   1.230 +  checkNodeIds(adaptor);
   1.231 +  checkArcIds(adaptor);
   1.232 +
   1.233 +  checkGraphNodeMap(adaptor);
   1.234 +  checkGraphArcMap(adaptor);
   1.235 +
   1.236 +  // Hide a node
   1.237 +  adaptor.status(n1, false);
   1.238 +  adaptor.disable(n3);
   1.239 +  if (!adaptor.status(n3)) adaptor.enable(n3);
   1.240 +
   1.241 +  checkGraphNodeList(adaptor, 2);
   1.242 +  checkGraphArcList(adaptor, 1);
   1.243 +  checkGraphConArcList(adaptor, 1);
   1.244 +
   1.245 +  checkGraphOutArcList(adaptor, n2, 1);
   1.246 +  checkGraphOutArcList(adaptor, n3, 0);
   1.247 +
   1.248 +  checkGraphInArcList(adaptor, n2, 0);
   1.249 +  checkGraphInArcList(adaptor, n3, 1);
   1.250 +
   1.251 +  checkNodeIds(adaptor);
   1.252 +  checkArcIds(adaptor);
   1.253 +
   1.254 +  checkGraphNodeMap(adaptor);
   1.255 +  checkGraphArcMap(adaptor);
   1.256 +
   1.257 +  // Hide all nodes and arcs
   1.258 +  node_filter[n1] = node_filter[n2] = node_filter[n3] = false;
   1.259 +  arc_filter[a1] = arc_filter[a2] = arc_filter[a3] = false;
   1.260 +
   1.261 +  checkGraphNodeList(adaptor, 0);
   1.262 +  checkGraphArcList(adaptor, 0);
   1.263 +  checkGraphConArcList(adaptor, 0);
   1.264 +
   1.265 +  checkNodeIds(adaptor);
   1.266 +  checkArcIds(adaptor);
   1.267 +
   1.268 +  checkGraphNodeMap(adaptor);
   1.269 +  checkGraphArcMap(adaptor);
   1.270 +
   1.271 +  // Check the conversion of nodes and arcs
   1.272 +  Digraph::Node nd = n3;
   1.273 +  nd = n3;
   1.274 +  Adaptor::Node na = n1;
   1.275 +  na = n2;
   1.276 +  Digraph::Arc ad = a3;
   1.277 +  ad = a3;
   1.278 +  Adaptor::Arc aa = a1;
   1.279 +  aa = a2;
   1.280 +}
   1.281 +
   1.282 +void checkFilterNodes1() {
   1.283 +  // Check concepts
   1.284 +  checkConcept<concepts::Digraph, FilterNodes<concepts::Digraph> >();
   1.285 +  checkConcept<concepts::Digraph, FilterNodes<ListDigraph> >();
   1.286 +  checkConcept<concepts::AlterableDigraphComponent<>,
   1.287 +               FilterNodes<ListDigraph> >();
   1.288 +  checkConcept<concepts::ExtendableDigraphComponent<>,
   1.289 +               FilterNodes<ListDigraph> >();
   1.290 +  checkConcept<concepts::ErasableDigraphComponent<>,
   1.291 +               FilterNodes<ListDigraph> >();
   1.292 +  checkConcept<concepts::ClearableDigraphComponent<>,
   1.293 +               FilterNodes<ListDigraph> >();
   1.294 +
   1.295 +  // Create a digraph and an adaptor
   1.296 +  typedef ListDigraph Digraph;
   1.297 +  typedef Digraph::NodeMap<bool> NodeFilter;
   1.298 +  typedef FilterNodes<Digraph, NodeFilter> Adaptor;
   1.299 +
   1.300 +  Digraph digraph;
   1.301 +  NodeFilter node_filter(digraph);
   1.302 +  Adaptor adaptor(digraph, node_filter);
   1.303 +
   1.304 +  // Add nodes and arcs to the original digraph and the adaptor
   1.305 +  Digraph::Node n1 = digraph.addNode();
   1.306 +  Digraph::Node n2 = digraph.addNode();
   1.307 +  Adaptor::Node n3 = adaptor.addNode();
   1.308 +
   1.309 +  node_filter[n1] = node_filter[n2] = node_filter[n3] = true;
   1.310 +
   1.311 +  Digraph::Arc a1 = digraph.addArc(n1, n2);
   1.312 +  Digraph::Arc a2 = digraph.addArc(n1, n3);
   1.313 +  Adaptor::Arc a3 = adaptor.addArc(n2, n3);
   1.314 +
   1.315 +  checkGraphNodeList(adaptor, 3);
   1.316 +  checkGraphArcList(adaptor, 3);
   1.317 +  checkGraphConArcList(adaptor, 3);
   1.318 +
   1.319 +  checkGraphOutArcList(adaptor, n1, 2);
   1.320 +  checkGraphOutArcList(adaptor, n2, 1);
   1.321 +  checkGraphOutArcList(adaptor, n3, 0);
   1.322 +
   1.323 +  checkGraphInArcList(adaptor, n1, 0);
   1.324 +  checkGraphInArcList(adaptor, n2, 1);
   1.325 +  checkGraphInArcList(adaptor, n3, 2);
   1.326 +
   1.327 +  checkNodeIds(adaptor);
   1.328 +  checkArcIds(adaptor);
   1.329 +
   1.330 +  checkGraphNodeMap(adaptor);
   1.331 +  checkGraphArcMap(adaptor);
   1.332 +
   1.333 +  // Hide a node
   1.334 +  adaptor.status(n1, false);
   1.335 +  adaptor.disable(n3);
   1.336 +  if (!adaptor.status(n3)) adaptor.enable(n3);
   1.337 +
   1.338 +  checkGraphNodeList(adaptor, 2);
   1.339 +  checkGraphArcList(adaptor, 1);
   1.340 +  checkGraphConArcList(adaptor, 1);
   1.341 +
   1.342 +  checkGraphOutArcList(adaptor, n2, 1);
   1.343 +  checkGraphOutArcList(adaptor, n3, 0);
   1.344 +
   1.345 +  checkGraphInArcList(adaptor, n2, 0);
   1.346 +  checkGraphInArcList(adaptor, n3, 1);
   1.347 +
   1.348 +  checkNodeIds(adaptor);
   1.349 +  checkArcIds(adaptor);
   1.350 +
   1.351 +  checkGraphNodeMap(adaptor);
   1.352 +  checkGraphArcMap(adaptor);
   1.353 +
   1.354 +  // Hide all nodes
   1.355 +  node_filter[n1] = node_filter[n2] = node_filter[n3] = false;
   1.356 +
   1.357 +  checkGraphNodeList(adaptor, 0);
   1.358 +  checkGraphArcList(adaptor, 0);
   1.359 +  checkGraphConArcList(adaptor, 0);
   1.360 +
   1.361 +  checkNodeIds(adaptor);
   1.362 +  checkArcIds(adaptor);
   1.363 +
   1.364 +  checkGraphNodeMap(adaptor);
   1.365 +  checkGraphArcMap(adaptor);
   1.366 +
   1.367 +  // Check the conversion of nodes and arcs
   1.368 +  Digraph::Node nd = n3;
   1.369 +  nd = n3;
   1.370 +  Adaptor::Node na = n1;
   1.371 +  na = n2;
   1.372 +  Digraph::Arc ad = a3;
   1.373 +  ad = a3;
   1.374 +  Adaptor::Arc aa = a1;
   1.375 +  aa = a2;
   1.376 +}
   1.377 +
   1.378 +void checkFilterArcs() {
   1.379 +  // Check concepts
   1.380 +  checkConcept<concepts::Digraph, FilterArcs<concepts::Digraph> >();
   1.381 +  checkConcept<concepts::Digraph, FilterArcs<ListDigraph> >();
   1.382 +  checkConcept<concepts::AlterableDigraphComponent<>,
   1.383 +               FilterArcs<ListDigraph> >();
   1.384 +  checkConcept<concepts::ExtendableDigraphComponent<>,
   1.385 +               FilterArcs<ListDigraph> >();
   1.386 +  checkConcept<concepts::ErasableDigraphComponent<>,
   1.387 +               FilterArcs<ListDigraph> >();
   1.388 +  checkConcept<concepts::ClearableDigraphComponent<>,
   1.389 +               FilterArcs<ListDigraph> >();
   1.390 +
   1.391 +  // Create a digraph and an adaptor
   1.392 +  typedef ListDigraph Digraph;
   1.393 +  typedef Digraph::ArcMap<bool> ArcFilter;
   1.394 +  typedef FilterArcs<Digraph, ArcFilter> Adaptor;
   1.395 +
   1.396 +  Digraph digraph;
   1.397 +  ArcFilter arc_filter(digraph);
   1.398 +  Adaptor adaptor(digraph, arc_filter);
   1.399 +
   1.400 +  // Add nodes and arcs to the original digraph and the adaptor
   1.401 +  Digraph::Node n1 = digraph.addNode();
   1.402 +  Digraph::Node n2 = digraph.addNode();
   1.403 +  Adaptor::Node n3 = adaptor.addNode();
   1.404 +
   1.405 +  Digraph::Arc a1 = digraph.addArc(n1, n2);
   1.406 +  Digraph::Arc a2 = digraph.addArc(n1, n3);
   1.407 +  Adaptor::Arc a3 = adaptor.addArc(n2, n3);
   1.408 +
   1.409 +  arc_filter[a1] = arc_filter[a2] = arc_filter[a3] = true;
   1.410 +
   1.411 +  checkGraphNodeList(adaptor, 3);
   1.412 +  checkGraphArcList(adaptor, 3);
   1.413 +  checkGraphConArcList(adaptor, 3);
   1.414 +
   1.415 +  checkGraphOutArcList(adaptor, n1, 2);
   1.416 +  checkGraphOutArcList(adaptor, n2, 1);
   1.417 +  checkGraphOutArcList(adaptor, n3, 0);
   1.418 +
   1.419 +  checkGraphInArcList(adaptor, n1, 0);
   1.420 +  checkGraphInArcList(adaptor, n2, 1);
   1.421 +  checkGraphInArcList(adaptor, n3, 2);
   1.422 +
   1.423 +  checkNodeIds(adaptor);
   1.424 +  checkArcIds(adaptor);
   1.425 +
   1.426 +  checkGraphNodeMap(adaptor);
   1.427 +  checkGraphArcMap(adaptor);
   1.428 +
   1.429 +  // Hide an arc
   1.430 +  adaptor.status(a2, false);
   1.431 +  adaptor.disable(a3);
   1.432 +  if (!adaptor.status(a3)) adaptor.enable(a3);
   1.433 +
   1.434 +  checkGraphNodeList(adaptor, 3);
   1.435 +  checkGraphArcList(adaptor, 2);
   1.436 +  checkGraphConArcList(adaptor, 2);
   1.437 +
   1.438 +  checkGraphOutArcList(adaptor, n1, 1);
   1.439 +  checkGraphOutArcList(adaptor, n2, 1);
   1.440 +  checkGraphOutArcList(adaptor, n3, 0);
   1.441 +
   1.442 +  checkGraphInArcList(adaptor, n1, 0);
   1.443 +  checkGraphInArcList(adaptor, n2, 1);
   1.444 +  checkGraphInArcList(adaptor, n3, 1);
   1.445 +
   1.446 +  checkNodeIds(adaptor);
   1.447 +  checkArcIds(adaptor);
   1.448 +
   1.449 +  checkGraphNodeMap(adaptor);
   1.450 +  checkGraphArcMap(adaptor);
   1.451 +
   1.452 +  // Hide all arcs
   1.453 +  arc_filter[a1] = arc_filter[a2] = arc_filter[a3] = false;
   1.454 +
   1.455 +  checkGraphNodeList(adaptor, 3);
   1.456 +  checkGraphArcList(adaptor, 0);
   1.457 +  checkGraphConArcList(adaptor, 0);
   1.458 +
   1.459 +  checkNodeIds(adaptor);
   1.460 +  checkArcIds(adaptor);
   1.461 +
   1.462 +  checkGraphNodeMap(adaptor);
   1.463 +  checkGraphArcMap(adaptor);
   1.464 +
   1.465 +  // Check the conversion of nodes and arcs
   1.466 +  Digraph::Node nd = n3;
   1.467 +  nd = n3;
   1.468 +  Adaptor::Node na = n1;
   1.469 +  na = n2;
   1.470 +  Digraph::Arc ad = a3;
   1.471 +  ad = a3;
   1.472 +  Adaptor::Arc aa = a1;
   1.473 +  aa = a2;
   1.474 +}
   1.475 +
   1.476 +void checkUndirector() {
   1.477 +  // Check concepts
   1.478 +  checkConcept<concepts::Graph, Undirector<concepts::Digraph> >();
   1.479 +  checkConcept<concepts::Graph, Undirector<ListDigraph> >();
   1.480 +  checkConcept<concepts::AlterableGraphComponent<>,
   1.481 +               Undirector<ListDigraph> >();
   1.482 +  checkConcept<concepts::ExtendableGraphComponent<>,
   1.483 +               Undirector<ListDigraph> >();
   1.484 +  checkConcept<concepts::ErasableGraphComponent<>,
   1.485 +               Undirector<ListDigraph> >();
   1.486 +  checkConcept<concepts::ClearableGraphComponent<>,
   1.487 +               Undirector<ListDigraph> >();
   1.488 +
   1.489 +
   1.490 +  // Create a digraph and an adaptor
   1.491 +  typedef ListDigraph Digraph;
   1.492 +  typedef Undirector<Digraph> Adaptor;
   1.493 +
   1.494 +  Digraph digraph;
   1.495 +  Adaptor adaptor(digraph);
   1.496 +
   1.497 +  // Add nodes and arcs/edges to the original digraph and the adaptor
   1.498 +  Digraph::Node n1 = digraph.addNode();
   1.499 +  Digraph::Node n2 = digraph.addNode();
   1.500 +  Adaptor::Node n3 = adaptor.addNode();
   1.501 +
   1.502 +  Digraph::Arc a1 = digraph.addArc(n1, n2);
   1.503 +  Digraph::Arc a2 = digraph.addArc(n1, n3);
   1.504 +  Adaptor::Edge e3 = adaptor.addEdge(n2, n3);
   1.505 +
   1.506 +  // Check the original digraph
   1.507 +  checkGraphNodeList(digraph, 3);
   1.508 +  checkGraphArcList(digraph, 3);
   1.509 +  checkGraphConArcList(digraph, 3);
   1.510 +
   1.511 +  checkGraphOutArcList(digraph, n1, 2);
   1.512 +  checkGraphOutArcList(digraph, n2, 1);
   1.513 +  checkGraphOutArcList(digraph, n3, 0);
   1.514 +
   1.515 +  checkGraphInArcList(digraph, n1, 0);
   1.516 +  checkGraphInArcList(digraph, n2, 1);
   1.517 +  checkGraphInArcList(digraph, n3, 2);
   1.518 +
   1.519 +  checkNodeIds(digraph);
   1.520 +  checkArcIds(digraph);
   1.521 +
   1.522 +  checkGraphNodeMap(digraph);
   1.523 +  checkGraphArcMap(digraph);
   1.524 +
   1.525 +  // Check the adaptor
   1.526 +  checkGraphNodeList(adaptor, 3);
   1.527 +  checkGraphArcList(adaptor, 6);
   1.528 +  checkGraphEdgeList(adaptor, 3);
   1.529 +  checkGraphConArcList(adaptor, 6);
   1.530 +  checkGraphConEdgeList(adaptor, 3);
   1.531 +
   1.532 +  checkGraphIncEdgeArcLists(adaptor, n1, 2);
   1.533 +  checkGraphIncEdgeArcLists(adaptor, n2, 2);
   1.534 +  checkGraphIncEdgeArcLists(adaptor, n3, 2);
   1.535 +
   1.536 +  checkNodeIds(adaptor);
   1.537 +  checkArcIds(adaptor);
   1.538 +  checkEdgeIds(adaptor);
   1.539 +
   1.540 +  checkGraphNodeMap(adaptor);
   1.541 +  checkGraphArcMap(adaptor);
   1.542 +  checkGraphEdgeMap(adaptor);
   1.543 +
   1.544 +  // Check the edges of the adaptor
   1.545 +  for (Adaptor::EdgeIt e(adaptor); e != INVALID; ++e) {
   1.546 +    check(adaptor.u(e) == digraph.source(e), "Wrong undir");
   1.547 +    check(adaptor.v(e) == digraph.target(e), "Wrong undir");
   1.548 +  }
   1.549 +
   1.550 +  // Check CombinedArcMap
   1.551 +  typedef Adaptor::CombinedArcMap
   1.552 +    <Digraph::ArcMap<int>, Digraph::ArcMap<int> > IntCombinedMap;
   1.553 +  typedef Adaptor::CombinedArcMap
   1.554 +    <Digraph::ArcMap<bool>, Digraph::ArcMap<bool> > BoolCombinedMap;
   1.555 +  checkConcept<concepts::ReferenceMap<Adaptor::Arc, int, int&, const int&>,
   1.556 +    IntCombinedMap>();
   1.557 +  checkConcept<concepts::ReferenceMap<Adaptor::Arc, bool, bool&, const bool&>,
   1.558 +    BoolCombinedMap>();
   1.559 +
   1.560 +  Digraph::ArcMap<int> fw_map(digraph), bk_map(digraph);
   1.561 +  for (Digraph::ArcIt a(digraph); a != INVALID; ++a) {
   1.562 +    fw_map[a] = digraph.id(a);
   1.563 +    bk_map[a] = -digraph.id(a);
   1.564 +  }
   1.565 +
   1.566 +  Adaptor::CombinedArcMap<Digraph::ArcMap<int>, Digraph::ArcMap<int> >
   1.567 +    comb_map(fw_map, bk_map);
   1.568 +  for (Adaptor::ArcIt a(adaptor); a != INVALID; ++a) {
   1.569 +    if (adaptor.source(a) == digraph.source(a)) {
   1.570 +      check(comb_map[a] == fw_map[a], "Wrong combined map");
   1.571 +    } else {
   1.572 +      check(comb_map[a] == bk_map[a], "Wrong combined map");
   1.573 +    }
   1.574 +  }
   1.575 +
   1.576 +  // Check the conversion of nodes and arcs/edges
   1.577 +  Digraph::Node nd = n3;
   1.578 +  nd = n3;
   1.579 +  Adaptor::Node na = n1;
   1.580 +  na = n2;
   1.581 +  Digraph::Arc ad = e3;
   1.582 +  ad = e3;
   1.583 +  Adaptor::Edge ea = a1;
   1.584 +  ea = a2;
   1.585 +}
   1.586 +
   1.587 +void checkResidualDigraph() {
   1.588 +  // Check concepts
   1.589 +  checkConcept<concepts::Digraph, ResidualDigraph<concepts::Digraph> >();
   1.590 +  checkConcept<concepts::Digraph, ResidualDigraph<ListDigraph> >();
   1.591 +
   1.592 +  // Create a digraph and an adaptor
   1.593 +  typedef ListDigraph Digraph;
   1.594 +  typedef Digraph::ArcMap<int> IntArcMap;
   1.595 +  typedef ResidualDigraph<Digraph, IntArcMap> Adaptor;
   1.596 +
   1.597 +  Digraph digraph;
   1.598 +  IntArcMap capacity(digraph), flow(digraph);
   1.599 +  Adaptor adaptor(digraph, capacity, flow);
   1.600 +
   1.601 +  Digraph::Node n1 = digraph.addNode();
   1.602 +  Digraph::Node n2 = digraph.addNode();
   1.603 +  Digraph::Node n3 = digraph.addNode();
   1.604 +  Digraph::Node n4 = digraph.addNode();
   1.605 +
   1.606 +  Digraph::Arc a1 = digraph.addArc(n1, n2);
   1.607 +  Digraph::Arc a2 = digraph.addArc(n1, n3);
   1.608 +  Digraph::Arc a3 = digraph.addArc(n1, n4);
   1.609 +  Digraph::Arc a4 = digraph.addArc(n2, n3);
   1.610 +  Digraph::Arc a5 = digraph.addArc(n2, n4);
   1.611 +  Digraph::Arc a6 = digraph.addArc(n3, n4);
   1.612 +
   1.613 +  capacity[a1] = 8;
   1.614 +  capacity[a2] = 6;
   1.615 +  capacity[a3] = 4;
   1.616 +  capacity[a4] = 4;
   1.617 +  capacity[a5] = 6;
   1.618 +  capacity[a6] = 10;
   1.619 +
   1.620 +  // Check the adaptor with various flow values
   1.621 +  for (Digraph::ArcIt a(digraph); a != INVALID; ++a) {
   1.622 +    flow[a] = 0;
   1.623 +  }
   1.624 +
   1.625 +  checkGraphNodeList(adaptor, 4);
   1.626 +  checkGraphArcList(adaptor, 6);
   1.627 +  checkGraphConArcList(adaptor, 6);
   1.628 +
   1.629 +  checkGraphOutArcList(adaptor, n1, 3);
   1.630 +  checkGraphOutArcList(adaptor, n2, 2);
   1.631 +  checkGraphOutArcList(adaptor, n3, 1);
   1.632 +  checkGraphOutArcList(adaptor, n4, 0);
   1.633 +
   1.634 +  checkGraphInArcList(adaptor, n1, 0);
   1.635 +  checkGraphInArcList(adaptor, n2, 1);
   1.636 +  checkGraphInArcList(adaptor, n3, 2);
   1.637 +  checkGraphInArcList(adaptor, n4, 3);
   1.638 +
   1.639 +  for (Digraph::ArcIt a(digraph); a != INVALID; ++a) {
   1.640 +    flow[a] = capacity[a] / 2;
   1.641 +  }
   1.642 +
   1.643 +  checkGraphNodeList(adaptor, 4);
   1.644 +  checkGraphArcList(adaptor, 12);
   1.645 +  checkGraphConArcList(adaptor, 12);
   1.646 +
   1.647 +  checkGraphOutArcList(adaptor, n1, 3);
   1.648 +  checkGraphOutArcList(adaptor, n2, 3);
   1.649 +  checkGraphOutArcList(adaptor, n3, 3);
   1.650 +  checkGraphOutArcList(adaptor, n4, 3);
   1.651 +
   1.652 +  checkGraphInArcList(adaptor, n1, 3);
   1.653 +  checkGraphInArcList(adaptor, n2, 3);
   1.654 +  checkGraphInArcList(adaptor, n3, 3);
   1.655 +  checkGraphInArcList(adaptor, n4, 3);
   1.656 +
   1.657 +  checkNodeIds(adaptor);
   1.658 +  checkArcIds(adaptor);
   1.659 +
   1.660 +  checkGraphNodeMap(adaptor);
   1.661 +  checkGraphArcMap(adaptor);
   1.662 +
   1.663 +  for (Digraph::ArcIt a(digraph); a != INVALID; ++a) {
   1.664 +    flow[a] = capacity[a];
   1.665 +  }
   1.666 +
   1.667 +  checkGraphNodeList(adaptor, 4);
   1.668 +  checkGraphArcList(adaptor, 6);
   1.669 +  checkGraphConArcList(adaptor, 6);
   1.670 +
   1.671 +  checkGraphOutArcList(adaptor, n1, 0);
   1.672 +  checkGraphOutArcList(adaptor, n2, 1);
   1.673 +  checkGraphOutArcList(adaptor, n3, 2);
   1.674 +  checkGraphOutArcList(adaptor, n4, 3);
   1.675 +
   1.676 +  checkGraphInArcList(adaptor, n1, 3);
   1.677 +  checkGraphInArcList(adaptor, n2, 2);
   1.678 +  checkGraphInArcList(adaptor, n3, 1);
   1.679 +  checkGraphInArcList(adaptor, n4, 0);
   1.680 +
   1.681 +  // Saturate all backward arcs
   1.682 +  // (set the flow to zero on all forward arcs)
   1.683 +  for (Adaptor::ArcIt a(adaptor); a != INVALID; ++a) {
   1.684 +    if (adaptor.backward(a))
   1.685 +      adaptor.augment(a, adaptor.residualCapacity(a));
   1.686 +  }
   1.687 +
   1.688 +  checkGraphNodeList(adaptor, 4);
   1.689 +  checkGraphArcList(adaptor, 6);
   1.690 +  checkGraphConArcList(adaptor, 6);
   1.691 +
   1.692 +  checkGraphOutArcList(adaptor, n1, 3);
   1.693 +  checkGraphOutArcList(adaptor, n2, 2);
   1.694 +  checkGraphOutArcList(adaptor, n3, 1);
   1.695 +  checkGraphOutArcList(adaptor, n4, 0);
   1.696 +
   1.697 +  checkGraphInArcList(adaptor, n1, 0);
   1.698 +  checkGraphInArcList(adaptor, n2, 1);
   1.699 +  checkGraphInArcList(adaptor, n3, 2);
   1.700 +  checkGraphInArcList(adaptor, n4, 3);
   1.701 +
   1.702 +  // Find maximum flow by augmenting along shortest paths
   1.703 +  int flow_value = 0;
   1.704 +  Adaptor::ResidualCapacity res_cap(adaptor);
   1.705 +  while (true) {
   1.706 +
   1.707 +    Bfs<Adaptor> bfs(adaptor);
   1.708 +    bfs.run(n1, n4);
   1.709 +
   1.710 +    if (!bfs.reached(n4)) break;
   1.711 +
   1.712 +    Path<Adaptor> p = bfs.path(n4);
   1.713 +
   1.714 +    int min = std::numeric_limits<int>::max();
   1.715 +    for (Path<Adaptor>::ArcIt a(p); a != INVALID; ++a) {
   1.716 +      if (res_cap[a] < min) min = res_cap[a];
   1.717 +    }
   1.718 +
   1.719 +    for (Path<Adaptor>::ArcIt a(p); a != INVALID; ++a) {
   1.720 +      adaptor.augment(a, min);
   1.721 +    }
   1.722 +    flow_value += min;
   1.723 +  }
   1.724 +
   1.725 +  check(flow_value == 18, "Wrong flow with res graph adaptor");
   1.726 +
   1.727 +  // Check forward() and backward()
   1.728 +  for (Adaptor::ArcIt a(adaptor); a != INVALID; ++a) {
   1.729 +    check(adaptor.forward(a) != adaptor.backward(a),
   1.730 +          "Wrong forward() or backward()");
   1.731 +    check((adaptor.forward(a) && adaptor.forward(Digraph::Arc(a)) == a) ||
   1.732 +          (adaptor.backward(a) && adaptor.backward(Digraph::Arc(a)) == a),
   1.733 +          "Wrong forward() or backward()");
   1.734 +  }
   1.735 +
   1.736 +  // Check the conversion of nodes and arcs
   1.737 +  Digraph::Node nd = Adaptor::NodeIt(adaptor);
   1.738 +  nd = ++Adaptor::NodeIt(adaptor);
   1.739 +  Adaptor::Node na = n1;
   1.740 +  na = n2;
   1.741 +  Digraph::Arc ad = Adaptor::ArcIt(adaptor);
   1.742 +  ad = ++Adaptor::ArcIt(adaptor);
   1.743 +}
   1.744 +
   1.745 +void checkSplitNodes() {
   1.746 +  // Check concepts
   1.747 +  checkConcept<concepts::Digraph, SplitNodes<concepts::Digraph> >();
   1.748 +  checkConcept<concepts::Digraph, SplitNodes<ListDigraph> >();
   1.749 +
   1.750 +  // Create a digraph and an adaptor
   1.751 +  typedef ListDigraph Digraph;
   1.752 +  typedef SplitNodes<Digraph> Adaptor;
   1.753 +
   1.754 +  Digraph digraph;
   1.755 +  Adaptor adaptor(digraph);
   1.756 +
   1.757 +  Digraph::Node n1 = digraph.addNode();
   1.758 +  Digraph::Node n2 = digraph.addNode();
   1.759 +  Digraph::Node n3 = digraph.addNode();
   1.760 +
   1.761 +  Digraph::Arc a1 = digraph.addArc(n1, n2);
   1.762 +  Digraph::Arc a2 = digraph.addArc(n1, n3);
   1.763 +  Digraph::Arc a3 = digraph.addArc(n2, n3);
   1.764 +
   1.765 +  checkGraphNodeList(adaptor, 6);
   1.766 +  checkGraphArcList(adaptor, 6);
   1.767 +  checkGraphConArcList(adaptor, 6);
   1.768 +
   1.769 +  checkGraphOutArcList(adaptor, adaptor.inNode(n1), 1);
   1.770 +  checkGraphOutArcList(adaptor, adaptor.outNode(n1), 2);
   1.771 +  checkGraphOutArcList(adaptor, adaptor.inNode(n2), 1);
   1.772 +  checkGraphOutArcList(adaptor, adaptor.outNode(n2), 1);
   1.773 +  checkGraphOutArcList(adaptor, adaptor.inNode(n3), 1);
   1.774 +  checkGraphOutArcList(adaptor, adaptor.outNode(n3), 0);
   1.775 +
   1.776 +  checkGraphInArcList(adaptor, adaptor.inNode(n1), 0);
   1.777 +  checkGraphInArcList(adaptor, adaptor.outNode(n1), 1);
   1.778 +  checkGraphInArcList(adaptor, adaptor.inNode(n2), 1);
   1.779 +  checkGraphInArcList(adaptor, adaptor.outNode(n2), 1);
   1.780 +  checkGraphInArcList(adaptor, adaptor.inNode(n3), 2);
   1.781 +  checkGraphInArcList(adaptor, adaptor.outNode(n3), 1);
   1.782 +
   1.783 +  checkNodeIds(adaptor);
   1.784 +  checkArcIds(adaptor);
   1.785 +
   1.786 +  checkGraphNodeMap(adaptor);
   1.787 +  checkGraphArcMap(adaptor);
   1.788 +
   1.789 +  // Check split
   1.790 +  for (Adaptor::ArcIt a(adaptor); a != INVALID; ++a) {
   1.791 +    if (adaptor.origArc(a)) {
   1.792 +      Digraph::Arc oa = a;
   1.793 +      check(adaptor.source(a) == adaptor.outNode(digraph.source(oa)),
   1.794 +            "Wrong split");
   1.795 +      check(adaptor.target(a) == adaptor.inNode(digraph.target(oa)),
   1.796 +            "Wrong split");
   1.797 +    } else {
   1.798 +      Digraph::Node on = a;
   1.799 +      check(adaptor.source(a) == adaptor.inNode(on), "Wrong split");
   1.800 +      check(adaptor.target(a) == adaptor.outNode(on), "Wrong split");
   1.801 +    }
   1.802 +  }
   1.803 +
   1.804 +  // Check combined node map
   1.805 +  typedef Adaptor::CombinedNodeMap
   1.806 +    <Digraph::NodeMap<int>, Digraph::NodeMap<int> > IntCombinedNodeMap;
   1.807 +  typedef Adaptor::CombinedNodeMap
   1.808 +    <Digraph::NodeMap<bool>, Digraph::NodeMap<bool> > BoolCombinedNodeMap;
   1.809 +  checkConcept<concepts::ReferenceMap<Adaptor::Node, int, int&, const int&>,
   1.810 +    IntCombinedNodeMap>();
   1.811 +//checkConcept<concepts::ReferenceMap<Adaptor::Node, bool, bool&, const bool&>,
   1.812 +//  BoolCombinedNodeMap>();
   1.813 +  checkConcept<concepts::ReadWriteMap<Adaptor::Node, bool>,
   1.814 +    BoolCombinedNodeMap>();
   1.815 +
   1.816 +  Digraph::NodeMap<int> in_map(digraph), out_map(digraph);
   1.817 +  for (Digraph::NodeIt n(digraph); n != INVALID; ++n) {
   1.818 +    in_map[n] = digraph.id(n);
   1.819 +    out_map[n] = -digraph.id(n);
   1.820 +  }
   1.821 +
   1.822 +  Adaptor::CombinedNodeMap<Digraph::NodeMap<int>, Digraph::NodeMap<int> >
   1.823 +    node_map(in_map, out_map);
   1.824 +  for (Adaptor::NodeIt n(adaptor); n != INVALID; ++n) {
   1.825 +    if (adaptor.inNode(n)) {
   1.826 +      check(node_map[n] == in_map[n], "Wrong combined node map");
   1.827 +    } else {
   1.828 +      check(node_map[n] == out_map[n], "Wrong combined node map");
   1.829 +    }
   1.830 +  }
   1.831 +
   1.832 +  // Check combined arc map
   1.833 +  typedef Adaptor::CombinedArcMap
   1.834 +    <Digraph::ArcMap<int>, Digraph::NodeMap<int> > IntCombinedArcMap;
   1.835 +  typedef Adaptor::CombinedArcMap
   1.836 +    <Digraph::ArcMap<bool>, Digraph::NodeMap<bool> > BoolCombinedArcMap;
   1.837 +  checkConcept<concepts::ReferenceMap<Adaptor::Arc, int, int&, const int&>,
   1.838 +    IntCombinedArcMap>();
   1.839 +//checkConcept<concepts::ReferenceMap<Adaptor::Arc, bool, bool&, const bool&>,
   1.840 +//  BoolCombinedArcMap>();
   1.841 +  checkConcept<concepts::ReadWriteMap<Adaptor::Arc, bool>,
   1.842 +    BoolCombinedArcMap>();
   1.843 +
   1.844 +  Digraph::ArcMap<int> a_map(digraph);
   1.845 +  for (Digraph::ArcIt a(digraph); a != INVALID; ++a) {
   1.846 +    a_map[a] = digraph.id(a);
   1.847 +  }
   1.848 +
   1.849 +  Adaptor::CombinedArcMap<Digraph::ArcMap<int>, Digraph::NodeMap<int> >
   1.850 +    arc_map(a_map, out_map);
   1.851 +  for (Digraph::ArcIt a(digraph); a != INVALID; ++a) {
   1.852 +    check(arc_map[adaptor.arc(a)] == a_map[a],  "Wrong combined arc map");
   1.853 +  }
   1.854 +  for (Digraph::NodeIt n(digraph); n != INVALID; ++n) {
   1.855 +    check(arc_map[adaptor.arc(n)] == out_map[n],  "Wrong combined arc map");
   1.856 +  }
   1.857 +
   1.858 +  // Check the conversion of nodes
   1.859 +  Digraph::Node nd = adaptor.inNode(n1);
   1.860 +  check (nd == n1, "Wrong node conversion");
   1.861 +  nd = adaptor.outNode(n2);
   1.862 +  check (nd == n2, "Wrong node conversion");
   1.863 +}
   1.864 +
   1.865 +void checkSubGraph() {
   1.866 +  // Check concepts
   1.867 +  checkConcept<concepts::Graph, SubGraph<concepts::Graph> >();
   1.868 +  checkConcept<concepts::Graph, SubGraph<ListGraph> >();
   1.869 +  checkConcept<concepts::AlterableGraphComponent<>,
   1.870 +               SubGraph<ListGraph> >();
   1.871 +  checkConcept<concepts::ExtendableGraphComponent<>,
   1.872 +               SubGraph<ListGraph> >();
   1.873 +  checkConcept<concepts::ErasableGraphComponent<>,
   1.874 +               SubGraph<ListGraph> >();
   1.875 +  checkConcept<concepts::ClearableGraphComponent<>,
   1.876 +               SubGraph<ListGraph> >();
   1.877 +
   1.878 +  // Create a graph and an adaptor
   1.879 +  typedef ListGraph Graph;
   1.880 +  typedef Graph::NodeMap<bool> NodeFilter;
   1.881 +  typedef Graph::EdgeMap<bool> EdgeFilter;
   1.882 +  typedef SubGraph<Graph, NodeFilter, EdgeFilter> Adaptor;
   1.883 +
   1.884 +  Graph graph;
   1.885 +  NodeFilter node_filter(graph);
   1.886 +  EdgeFilter edge_filter(graph);
   1.887 +  Adaptor adaptor(graph, node_filter, edge_filter);
   1.888 +
   1.889 +  // Add nodes and edges to the original graph and the adaptor
   1.890 +  Graph::Node n1 = graph.addNode();
   1.891 +  Graph::Node n2 = graph.addNode();
   1.892 +  Adaptor::Node n3 = adaptor.addNode();
   1.893 +  Adaptor::Node n4 = adaptor.addNode();
   1.894 +
   1.895 +  node_filter[n1] = node_filter[n2] = node_filter[n3] = node_filter[n4] = true;
   1.896 +
   1.897 +  Graph::Edge e1 = graph.addEdge(n1, n2);
   1.898 +  Graph::Edge e2 = graph.addEdge(n1, n3);
   1.899 +  Adaptor::Edge e3 = adaptor.addEdge(n2, n3);
   1.900 +  Adaptor::Edge e4 = adaptor.addEdge(n3, n4);
   1.901 +
   1.902 +  edge_filter[e1] = edge_filter[e2] = edge_filter[e3] = edge_filter[e4] = true;
   1.903 +
   1.904 +  checkGraphNodeList(adaptor, 4);
   1.905 +  checkGraphArcList(adaptor, 8);
   1.906 +  checkGraphEdgeList(adaptor, 4);
   1.907 +  checkGraphConArcList(adaptor, 8);
   1.908 +  checkGraphConEdgeList(adaptor, 4);
   1.909 +
   1.910 +  checkGraphIncEdgeArcLists(adaptor, n1, 2);
   1.911 +  checkGraphIncEdgeArcLists(adaptor, n2, 2);
   1.912 +  checkGraphIncEdgeArcLists(adaptor, n3, 3);
   1.913 +  checkGraphIncEdgeArcLists(adaptor, n4, 1);
   1.914 +
   1.915 +  checkNodeIds(adaptor);
   1.916 +  checkArcIds(adaptor);
   1.917 +  checkEdgeIds(adaptor);
   1.918 +
   1.919 +  checkGraphNodeMap(adaptor);
   1.920 +  checkGraphArcMap(adaptor);
   1.921 +  checkGraphEdgeMap(adaptor);
   1.922 +
   1.923 +  // Hide an edge
   1.924 +  adaptor.status(e2, false);
   1.925 +  adaptor.disable(e3);
   1.926 +  if (!adaptor.status(e3)) adaptor.enable(e3);
   1.927 +
   1.928 +  checkGraphNodeList(adaptor, 4);
   1.929 +  checkGraphArcList(adaptor, 6);
   1.930 +  checkGraphEdgeList(adaptor, 3);
   1.931 +  checkGraphConArcList(adaptor, 6);
   1.932 +  checkGraphConEdgeList(adaptor, 3);
   1.933 +
   1.934 +  checkGraphIncEdgeArcLists(adaptor, n1, 1);
   1.935 +  checkGraphIncEdgeArcLists(adaptor, n2, 2);
   1.936 +  checkGraphIncEdgeArcLists(adaptor, n3, 2);
   1.937 +  checkGraphIncEdgeArcLists(adaptor, n4, 1);
   1.938 +
   1.939 +  checkNodeIds(adaptor);
   1.940 +  checkArcIds(adaptor);
   1.941 +  checkEdgeIds(adaptor);
   1.942 +
   1.943 +  checkGraphNodeMap(adaptor);
   1.944 +  checkGraphArcMap(adaptor);
   1.945 +  checkGraphEdgeMap(adaptor);
   1.946 +
   1.947 +  // Hide a node
   1.948 +  adaptor.status(n1, false);
   1.949 +  adaptor.disable(n3);
   1.950 +  if (!adaptor.status(n3)) adaptor.enable(n3);
   1.951 +
   1.952 +  checkGraphNodeList(adaptor, 3);
   1.953 +  checkGraphArcList(adaptor, 4);
   1.954 +  checkGraphEdgeList(adaptor, 2);
   1.955 +  checkGraphConArcList(adaptor, 4);
   1.956 +  checkGraphConEdgeList(adaptor, 2);
   1.957 +
   1.958 +  checkGraphIncEdgeArcLists(adaptor, n2, 1);
   1.959 +  checkGraphIncEdgeArcLists(adaptor, n3, 2);
   1.960 +  checkGraphIncEdgeArcLists(adaptor, n4, 1);
   1.961 +
   1.962 +  checkNodeIds(adaptor);
   1.963 +  checkArcIds(adaptor);
   1.964 +  checkEdgeIds(adaptor);
   1.965 +
   1.966 +  checkGraphNodeMap(adaptor);
   1.967 +  checkGraphArcMap(adaptor);
   1.968 +  checkGraphEdgeMap(adaptor);
   1.969 +
   1.970 +  // Hide all nodes and edges
   1.971 +  node_filter[n1] = node_filter[n2] = node_filter[n3] = node_filter[n4] = false;
   1.972 +  edge_filter[e1] = edge_filter[e2] = edge_filter[e3] = edge_filter[e4] = false;
   1.973 +
   1.974 +  checkGraphNodeList(adaptor, 0);
   1.975 +  checkGraphArcList(adaptor, 0);
   1.976 +  checkGraphEdgeList(adaptor, 0);
   1.977 +  checkGraphConArcList(adaptor, 0);
   1.978 +  checkGraphConEdgeList(adaptor, 0);
   1.979 +
   1.980 +  checkNodeIds(adaptor);
   1.981 +  checkArcIds(adaptor);
   1.982 +  checkEdgeIds(adaptor);
   1.983 +
   1.984 +  checkGraphNodeMap(adaptor);
   1.985 +  checkGraphArcMap(adaptor);
   1.986 +  checkGraphEdgeMap(adaptor);
   1.987 +
   1.988 +  // Check the conversion of nodes and edges
   1.989 +  Graph::Node ng = n3;
   1.990 +  ng = n4;
   1.991 +  Adaptor::Node na = n1;
   1.992 +  na = n2;
   1.993 +  Graph::Edge eg = e3;
   1.994 +  eg = e4;
   1.995 +  Adaptor::Edge ea = e1;
   1.996 +  ea = e2;
   1.997 +}
   1.998 +
   1.999 +void checkFilterNodes2() {
  1.1000 +  // Check concepts
  1.1001 +  checkConcept<concepts::Graph, FilterNodes<concepts::Graph> >();
  1.1002 +  checkConcept<concepts::Graph, FilterNodes<ListGraph> >();
  1.1003 +  checkConcept<concepts::AlterableGraphComponent<>,
  1.1004 +               FilterNodes<ListGraph> >();
  1.1005 +  checkConcept<concepts::ExtendableGraphComponent<>,
  1.1006 +               FilterNodes<ListGraph> >();
  1.1007 +  checkConcept<concepts::ErasableGraphComponent<>,
  1.1008 +               FilterNodes<ListGraph> >();
  1.1009 +  checkConcept<concepts::ClearableGraphComponent<>,
  1.1010 +               FilterNodes<ListGraph> >();
  1.1011 +
  1.1012 +  // Create a graph and an adaptor
  1.1013 +  typedef ListGraph Graph;
  1.1014 +  typedef Graph::NodeMap<bool> NodeFilter;
  1.1015 +  typedef FilterNodes<Graph, NodeFilter> Adaptor;
  1.1016 +
  1.1017 +  // Add nodes and edges to the original graph and the adaptor
  1.1018 +  Graph graph;
  1.1019 +  NodeFilter node_filter(graph);
  1.1020 +  Adaptor adaptor(graph, node_filter);
  1.1021 +
  1.1022 +  Graph::Node n1 = graph.addNode();
  1.1023 +  Graph::Node n2 = graph.addNode();
  1.1024 +  Adaptor::Node n3 = adaptor.addNode();
  1.1025 +  Adaptor::Node n4 = adaptor.addNode();
  1.1026 +
  1.1027 +  node_filter[n1] = node_filter[n2] = node_filter[n3] = node_filter[n4] = true;
  1.1028 +
  1.1029 +  Graph::Edge e1 = graph.addEdge(n1, n2);
  1.1030 +  Graph::Edge e2 = graph.addEdge(n1, n3);
  1.1031 +  Adaptor::Edge e3 = adaptor.addEdge(n2, n3);
  1.1032 +  Adaptor::Edge e4 = adaptor.addEdge(n3, n4);
  1.1033 +
  1.1034 +  checkGraphNodeList(adaptor, 4);
  1.1035 +  checkGraphArcList(adaptor, 8);
  1.1036 +  checkGraphEdgeList(adaptor, 4);
  1.1037 +  checkGraphConArcList(adaptor, 8);
  1.1038 +  checkGraphConEdgeList(adaptor, 4);
  1.1039 +
  1.1040 +  checkGraphIncEdgeArcLists(adaptor, n1, 2);
  1.1041 +  checkGraphIncEdgeArcLists(adaptor, n2, 2);
  1.1042 +  checkGraphIncEdgeArcLists(adaptor, n3, 3);
  1.1043 +  checkGraphIncEdgeArcLists(adaptor, n4, 1);
  1.1044 +
  1.1045 +  checkNodeIds(adaptor);
  1.1046 +  checkArcIds(adaptor);
  1.1047 +  checkEdgeIds(adaptor);
  1.1048 +
  1.1049 +  checkGraphNodeMap(adaptor);
  1.1050 +  checkGraphArcMap(adaptor);
  1.1051 +  checkGraphEdgeMap(adaptor);
  1.1052 +
  1.1053 +  // Hide a node
  1.1054 +  adaptor.status(n1, false);
  1.1055 +  adaptor.disable(n3);
  1.1056 +  if (!adaptor.status(n3)) adaptor.enable(n3);
  1.1057 +
  1.1058 +  checkGraphNodeList(adaptor, 3);
  1.1059 +  checkGraphArcList(adaptor, 4);
  1.1060 +  checkGraphEdgeList(adaptor, 2);
  1.1061 +  checkGraphConArcList(adaptor, 4);
  1.1062 +  checkGraphConEdgeList(adaptor, 2);
  1.1063 +
  1.1064 +  checkGraphIncEdgeArcLists(adaptor, n2, 1);
  1.1065 +  checkGraphIncEdgeArcLists(adaptor, n3, 2);
  1.1066 +  checkGraphIncEdgeArcLists(adaptor, n4, 1);
  1.1067 +
  1.1068 +  checkNodeIds(adaptor);
  1.1069 +  checkArcIds(adaptor);
  1.1070 +  checkEdgeIds(adaptor);
  1.1071 +
  1.1072 +  checkGraphNodeMap(adaptor);
  1.1073 +  checkGraphArcMap(adaptor);
  1.1074 +  checkGraphEdgeMap(adaptor);
  1.1075 +
  1.1076 +  // Hide all nodes
  1.1077 +  node_filter[n1] = node_filter[n2] = node_filter[n3] = node_filter[n4] = false;
  1.1078 +
  1.1079 +  checkGraphNodeList(adaptor, 0);
  1.1080 +  checkGraphArcList(adaptor, 0);
  1.1081 +  checkGraphEdgeList(adaptor, 0);
  1.1082 +  checkGraphConArcList(adaptor, 0);
  1.1083 +  checkGraphConEdgeList(adaptor, 0);
  1.1084 +
  1.1085 +  checkNodeIds(adaptor);
  1.1086 +  checkArcIds(adaptor);
  1.1087 +  checkEdgeIds(adaptor);
  1.1088 +
  1.1089 +  checkGraphNodeMap(adaptor);
  1.1090 +  checkGraphArcMap(adaptor);
  1.1091 +  checkGraphEdgeMap(adaptor);
  1.1092 +
  1.1093 +  // Check the conversion of nodes and edges
  1.1094 +  Graph::Node ng = n3;
  1.1095 +  ng = n4;
  1.1096 +  Adaptor::Node na = n1;
  1.1097 +  na = n2;
  1.1098 +  Graph::Edge eg = e3;
  1.1099 +  eg = e4;
  1.1100 +  Adaptor::Edge ea = e1;
  1.1101 +  ea = e2;
  1.1102 +}
  1.1103 +
  1.1104 +void checkFilterEdges() {
  1.1105 +  // Check concepts
  1.1106 +  checkConcept<concepts::Graph, FilterEdges<concepts::Graph> >();
  1.1107 +  checkConcept<concepts::Graph, FilterEdges<ListGraph> >();
  1.1108 +  checkConcept<concepts::AlterableGraphComponent<>,
  1.1109 +               FilterEdges<ListGraph> >();
  1.1110 +  checkConcept<concepts::ExtendableGraphComponent<>,
  1.1111 +               FilterEdges<ListGraph> >();
  1.1112 +  checkConcept<concepts::ErasableGraphComponent<>,
  1.1113 +               FilterEdges<ListGraph> >();
  1.1114 +  checkConcept<concepts::ClearableGraphComponent<>,
  1.1115 +               FilterEdges<ListGraph> >();
  1.1116 +
  1.1117 +  // Create a graph and an adaptor
  1.1118 +  typedef ListGraph Graph;
  1.1119 +  typedef Graph::EdgeMap<bool> EdgeFilter;
  1.1120 +  typedef FilterEdges<Graph, EdgeFilter> Adaptor;
  1.1121 +
  1.1122 +  Graph graph;
  1.1123 +  EdgeFilter edge_filter(graph);
  1.1124 +  Adaptor adaptor(graph, edge_filter);
  1.1125 +
  1.1126 +  // Add nodes and edges to the original graph and the adaptor
  1.1127 +  Graph::Node n1 = graph.addNode();
  1.1128 +  Graph::Node n2 = graph.addNode();
  1.1129 +  Adaptor::Node n3 = adaptor.addNode();
  1.1130 +  Adaptor::Node n4 = adaptor.addNode();
  1.1131 +
  1.1132 +  Graph::Edge e1 = graph.addEdge(n1, n2);
  1.1133 +  Graph::Edge e2 = graph.addEdge(n1, n3);
  1.1134 +  Adaptor::Edge e3 = adaptor.addEdge(n2, n3);
  1.1135 +  Adaptor::Edge e4 = adaptor.addEdge(n3, n4);
  1.1136 +
  1.1137 +  edge_filter[e1] = edge_filter[e2] = edge_filter[e3] = edge_filter[e4] = true;
  1.1138 +
  1.1139 +  checkGraphNodeList(adaptor, 4);
  1.1140 +  checkGraphArcList(adaptor, 8);
  1.1141 +  checkGraphEdgeList(adaptor, 4);
  1.1142 +  checkGraphConArcList(adaptor, 8);
  1.1143 +  checkGraphConEdgeList(adaptor, 4);
  1.1144 +
  1.1145 +  checkGraphIncEdgeArcLists(adaptor, n1, 2);
  1.1146 +  checkGraphIncEdgeArcLists(adaptor, n2, 2);
  1.1147 +  checkGraphIncEdgeArcLists(adaptor, n3, 3);
  1.1148 +  checkGraphIncEdgeArcLists(adaptor, n4, 1);
  1.1149 +
  1.1150 +  checkNodeIds(adaptor);
  1.1151 +  checkArcIds(adaptor);
  1.1152 +  checkEdgeIds(adaptor);
  1.1153 +
  1.1154 +  checkGraphNodeMap(adaptor);
  1.1155 +  checkGraphArcMap(adaptor);
  1.1156 +  checkGraphEdgeMap(adaptor);
  1.1157 +
  1.1158 +  // Hide an edge
  1.1159 +  adaptor.status(e2, false);
  1.1160 +  adaptor.disable(e3);
  1.1161 +  if (!adaptor.status(e3)) adaptor.enable(e3);
  1.1162 +
  1.1163 +  checkGraphNodeList(adaptor, 4);
  1.1164 +  checkGraphArcList(adaptor, 6);
  1.1165 +  checkGraphEdgeList(adaptor, 3);
  1.1166 +  checkGraphConArcList(adaptor, 6);
  1.1167 +  checkGraphConEdgeList(adaptor, 3);
  1.1168 +
  1.1169 +  checkGraphIncEdgeArcLists(adaptor, n1, 1);
  1.1170 +  checkGraphIncEdgeArcLists(adaptor, n2, 2);
  1.1171 +  checkGraphIncEdgeArcLists(adaptor, n3, 2);
  1.1172 +  checkGraphIncEdgeArcLists(adaptor, n4, 1);
  1.1173 +
  1.1174 +  checkNodeIds(adaptor);
  1.1175 +  checkArcIds(adaptor);
  1.1176 +  checkEdgeIds(adaptor);
  1.1177 +
  1.1178 +  checkGraphNodeMap(adaptor);
  1.1179 +  checkGraphArcMap(adaptor);
  1.1180 +  checkGraphEdgeMap(adaptor);
  1.1181 +
  1.1182 +  // Hide all edges
  1.1183 +  edge_filter[e1] = edge_filter[e2] = edge_filter[e3] = edge_filter[e4] = false;
  1.1184 +
  1.1185 +  checkGraphNodeList(adaptor, 4);
  1.1186 +  checkGraphArcList(adaptor, 0);
  1.1187 +  checkGraphEdgeList(adaptor, 0);
  1.1188 +  checkGraphConArcList(adaptor, 0);
  1.1189 +  checkGraphConEdgeList(adaptor, 0);
  1.1190 +
  1.1191 +  checkNodeIds(adaptor);
  1.1192 +  checkArcIds(adaptor);
  1.1193 +  checkEdgeIds(adaptor);
  1.1194 +
  1.1195 +  checkGraphNodeMap(adaptor);
  1.1196 +  checkGraphArcMap(adaptor);
  1.1197 +  checkGraphEdgeMap(adaptor);
  1.1198 +
  1.1199 +  // Check the conversion of nodes and edges
  1.1200 +  Graph::Node ng = n3;
  1.1201 +  ng = n4;
  1.1202 +  Adaptor::Node na = n1;
  1.1203 +  na = n2;
  1.1204 +  Graph::Edge eg = e3;
  1.1205 +  eg = e4;
  1.1206 +  Adaptor::Edge ea = e1;
  1.1207 +  ea = e2;
  1.1208 +}
  1.1209 +
  1.1210 +void checkOrienter() {
  1.1211 +  // Check concepts
  1.1212 +  checkConcept<concepts::Digraph, Orienter<concepts::Graph> >();
  1.1213 +  checkConcept<concepts::Digraph, Orienter<ListGraph> >();
  1.1214 +  checkConcept<concepts::AlterableDigraphComponent<>,
  1.1215 +               Orienter<ListGraph> >();
  1.1216 +  checkConcept<concepts::ExtendableDigraphComponent<>,
  1.1217 +               Orienter<ListGraph> >();
  1.1218 +  checkConcept<concepts::ErasableDigraphComponent<>,
  1.1219 +               Orienter<ListGraph> >();
  1.1220 +  checkConcept<concepts::ClearableDigraphComponent<>,
  1.1221 +               Orienter<ListGraph> >();
  1.1222 +
  1.1223 +  // Create a graph and an adaptor
  1.1224 +  typedef ListGraph Graph;
  1.1225 +  typedef ListGraph::EdgeMap<bool> DirMap;
  1.1226 +  typedef Orienter<Graph> Adaptor;
  1.1227 +
  1.1228 +  Graph graph;
  1.1229 +  DirMap dir(graph);
  1.1230 +  Adaptor adaptor(graph, dir);
  1.1231 +
  1.1232 +  // Add nodes and edges to the original graph and the adaptor
  1.1233 +  Graph::Node n1 = graph.addNode();
  1.1234 +  Graph::Node n2 = graph.addNode();
  1.1235 +  Adaptor::Node n3 = adaptor.addNode();
  1.1236 +
  1.1237 +  Graph::Edge e1 = graph.addEdge(n1, n2);
  1.1238 +  Graph::Edge e2 = graph.addEdge(n1, n3);
  1.1239 +  Adaptor::Arc e3 = adaptor.addArc(n2, n3);
  1.1240 +
  1.1241 +  dir[e1] = dir[e2] = dir[e3] = true;
  1.1242 +
  1.1243 +  // Check the original graph
  1.1244 +  checkGraphNodeList(graph, 3);
  1.1245 +  checkGraphArcList(graph, 6);
  1.1246 +  checkGraphConArcList(graph, 6);
  1.1247 +  checkGraphEdgeList(graph, 3);
  1.1248 +  checkGraphConEdgeList(graph, 3);
  1.1249 +
  1.1250 +  checkGraphIncEdgeArcLists(graph, n1, 2);
  1.1251 +  checkGraphIncEdgeArcLists(graph, n2, 2);
  1.1252 +  checkGraphIncEdgeArcLists(graph, n3, 2);
  1.1253 +
  1.1254 +  checkNodeIds(graph);
  1.1255 +  checkArcIds(graph);
  1.1256 +  checkEdgeIds(graph);
  1.1257 +
  1.1258 +  checkGraphNodeMap(graph);
  1.1259 +  checkGraphArcMap(graph);
  1.1260 +  checkGraphEdgeMap(graph);
  1.1261 +
  1.1262 +  // Check the adaptor
  1.1263 +  checkGraphNodeList(adaptor, 3);
  1.1264 +  checkGraphArcList(adaptor, 3);
  1.1265 +  checkGraphConArcList(adaptor, 3);
  1.1266 +
  1.1267 +  checkGraphOutArcList(adaptor, n1, 2);
  1.1268 +  checkGraphOutArcList(adaptor, n2, 1);
  1.1269 +  checkGraphOutArcList(adaptor, n3, 0);
  1.1270 +
  1.1271 +  checkGraphInArcList(adaptor, n1, 0);
  1.1272 +  checkGraphInArcList(adaptor, n2, 1);
  1.1273 +  checkGraphInArcList(adaptor, n3, 2);
  1.1274 +
  1.1275 +  checkNodeIds(adaptor);
  1.1276 +  checkArcIds(adaptor);
  1.1277 +
  1.1278 +  checkGraphNodeMap(adaptor);
  1.1279 +  checkGraphArcMap(adaptor);
  1.1280 +
  1.1281 +  // Check direction changing
  1.1282 +  {
  1.1283 +    dir[e1] = true;
  1.1284 +    Adaptor::Node u = adaptor.source(e1);
  1.1285 +    Adaptor::Node v = adaptor.target(e1);
  1.1286 +
  1.1287 +    dir[e1] = false;
  1.1288 +    check (u == adaptor.target(e1), "Wrong dir");
  1.1289 +    check (v == adaptor.source(e1), "Wrong dir");
  1.1290 +
  1.1291 +    check ((u == n1 && v == n2) || (u == n2 && v == n1), "Wrong dir");
  1.1292 +    dir[e1] = n1 == u;
  1.1293 +  }
  1.1294 +
  1.1295 +  {
  1.1296 +    dir[e2] = true;
  1.1297 +    Adaptor::Node u = adaptor.source(e2);
  1.1298 +    Adaptor::Node v = adaptor.target(e2);
  1.1299 +
  1.1300 +    dir[e2] = false;
  1.1301 +    check (u == adaptor.target(e2), "Wrong dir");
  1.1302 +    check (v == adaptor.source(e2), "Wrong dir");
  1.1303 +
  1.1304 +    check ((u == n1 && v == n3) || (u == n3 && v == n1), "Wrong dir");
  1.1305 +    dir[e2] = n3 == u;
  1.1306 +  }
  1.1307 +
  1.1308 +  {
  1.1309 +    dir[e3] = true;
  1.1310 +    Adaptor::Node u = adaptor.source(e3);
  1.1311 +    Adaptor::Node v = adaptor.target(e3);
  1.1312 +
  1.1313 +    dir[e3] = false;
  1.1314 +    check (u == adaptor.target(e3), "Wrong dir");
  1.1315 +    check (v == adaptor.source(e3), "Wrong dir");
  1.1316 +
  1.1317 +    check ((u == n2 && v == n3) || (u == n3 && v == n2), "Wrong dir");
  1.1318 +    dir[e3] = n2 == u;
  1.1319 +  }
  1.1320 +
  1.1321 +  // Check the adaptor again
  1.1322 +  checkGraphNodeList(adaptor, 3);
  1.1323 +  checkGraphArcList(adaptor, 3);
  1.1324 +  checkGraphConArcList(adaptor, 3);
  1.1325 +
  1.1326 +  checkGraphOutArcList(adaptor, n1, 1);
  1.1327 +  checkGraphOutArcList(adaptor, n2, 1);
  1.1328 +  checkGraphOutArcList(adaptor, n3, 1);
  1.1329 +
  1.1330 +  checkGraphInArcList(adaptor, n1, 1);
  1.1331 +  checkGraphInArcList(adaptor, n2, 1);
  1.1332 +  checkGraphInArcList(adaptor, n3, 1);
  1.1333 +
  1.1334 +  checkNodeIds(adaptor);
  1.1335 +  checkArcIds(adaptor);
  1.1336 +
  1.1337 +  checkGraphNodeMap(adaptor);
  1.1338 +  checkGraphArcMap(adaptor);
  1.1339 +
  1.1340 +  // Check reverseArc()
  1.1341 +  adaptor.reverseArc(e2);
  1.1342 +  adaptor.reverseArc(e3);
  1.1343 +  adaptor.reverseArc(e2);
  1.1344 +
  1.1345 +  checkGraphNodeList(adaptor, 3);
  1.1346 +  checkGraphArcList(adaptor, 3);
  1.1347 +  checkGraphConArcList(adaptor, 3);
  1.1348 +
  1.1349 +  checkGraphOutArcList(adaptor, n1, 1);
  1.1350 +  checkGraphOutArcList(adaptor, n2, 0);
  1.1351 +  checkGraphOutArcList(adaptor, n3, 2);
  1.1352 +
  1.1353 +  checkGraphInArcList(adaptor, n1, 1);
  1.1354 +  checkGraphInArcList(adaptor, n2, 2);
  1.1355 +  checkGraphInArcList(adaptor, n3, 0);
  1.1356 +
  1.1357 +  // Check the conversion of nodes and arcs/edges
  1.1358 +  Graph::Node ng = n3;
  1.1359 +  ng = n3;
  1.1360 +  Adaptor::Node na = n1;
  1.1361 +  na = n2;
  1.1362 +  Graph::Edge eg = e3;
  1.1363 +  eg = e3;
  1.1364 +  Adaptor::Arc aa = e1;
  1.1365 +  aa = e2;
  1.1366 +}
  1.1367 +
  1.1368 +void checkCombiningAdaptors() {
  1.1369 +  // Create a grid graph
  1.1370 +  GridGraph graph(2,2);
  1.1371 +  GridGraph::Node n1 = graph(0,0);
  1.1372 +  GridGraph::Node n2 = graph(0,1);
  1.1373 +  GridGraph::Node n3 = graph(1,0);
  1.1374 +  GridGraph::Node n4 = graph(1,1);
  1.1375 +
  1.1376 +  GridGraph::EdgeMap<bool> dir_map(graph);
  1.1377 +  dir_map[graph.right(n1)] = graph.u(graph.right(n1)) == n1;
  1.1378 +  dir_map[graph.up(n1)] = graph.u(graph.up(n1)) != n1;
  1.1379 +  dir_map[graph.left(n4)] = graph.u(graph.left(n4)) != n4;
  1.1380 +  dir_map[graph.down(n4)] = graph.u(graph.down(n4)) != n4;
  1.1381 +
  1.1382 +  // Apply several adaptors on the grid graph
  1.1383 +  typedef SplitNodes< ReverseDigraph< const Orienter<
  1.1384 +            const GridGraph, GridGraph::EdgeMap<bool> > > >
  1.1385 +    RevSplitGridGraph;
  1.1386 +  typedef ReverseDigraph<const RevSplitGridGraph> SplitGridGraph;
  1.1387 +  typedef Undirector<const SplitGridGraph> USplitGridGraph;
  1.1388 +  typedef Undirector<const USplitGridGraph> UUSplitGridGraph;
  1.1389 +  checkConcept<concepts::Digraph, RevSplitGridGraph>();
  1.1390 +  checkConcept<concepts::Digraph, SplitGridGraph>();
  1.1391 +  checkConcept<concepts::Graph, USplitGridGraph>();
  1.1392 +  checkConcept<concepts::Graph, UUSplitGridGraph>();
  1.1393 +
  1.1394 +  RevSplitGridGraph rev_adaptor =
  1.1395 +    splitNodes(reverseDigraph(orienter(graph, dir_map)));
  1.1396 +  SplitGridGraph adaptor = reverseDigraph(rev_adaptor);
  1.1397 +  USplitGridGraph uadaptor = undirector(adaptor);
  1.1398 +  UUSplitGridGraph uuadaptor = undirector(uadaptor);
  1.1399 +
  1.1400 +  // Check adaptor
  1.1401 +  checkGraphNodeList(adaptor, 8);
  1.1402 +  checkGraphArcList(adaptor, 8);
  1.1403 +  checkGraphConArcList(adaptor, 8);
  1.1404 +
  1.1405 +  checkGraphOutArcList(adaptor, rev_adaptor.inNode(n1), 1);
  1.1406 +  checkGraphOutArcList(adaptor, rev_adaptor.outNode(n1), 1);
  1.1407 +  checkGraphOutArcList(adaptor, rev_adaptor.inNode(n2), 2);
  1.1408 +  checkGraphOutArcList(adaptor, rev_adaptor.outNode(n2), 1);
  1.1409 +  checkGraphOutArcList(adaptor, rev_adaptor.inNode(n3), 1);
  1.1410 +  checkGraphOutArcList(adaptor, rev_adaptor.outNode(n3), 1);
  1.1411 +  checkGraphOutArcList(adaptor, rev_adaptor.inNode(n4), 0);
  1.1412 +  checkGraphOutArcList(adaptor, rev_adaptor.outNode(n4), 1);
  1.1413 +
  1.1414 +  checkGraphInArcList(adaptor, rev_adaptor.inNode(n1), 1);
  1.1415 +  checkGraphInArcList(adaptor, rev_adaptor.outNode(n1), 1);
  1.1416 +  checkGraphInArcList(adaptor, rev_adaptor.inNode(n2), 1);
  1.1417 +  checkGraphInArcList(adaptor, rev_adaptor.outNode(n2), 0);
  1.1418 +  checkGraphInArcList(adaptor, rev_adaptor.inNode(n3), 1);
  1.1419 +  checkGraphInArcList(adaptor, rev_adaptor.outNode(n3), 1);
  1.1420 +  checkGraphInArcList(adaptor, rev_adaptor.inNode(n4), 1);
  1.1421 +  checkGraphInArcList(adaptor, rev_adaptor.outNode(n4), 2);
  1.1422 +
  1.1423 +  checkNodeIds(adaptor);
  1.1424 +  checkArcIds(adaptor);
  1.1425 +
  1.1426 +  checkGraphNodeMap(adaptor);
  1.1427 +  checkGraphArcMap(adaptor);
  1.1428 +
  1.1429 +  // Check uadaptor
  1.1430 +  checkGraphNodeList(uadaptor, 8);
  1.1431 +  checkGraphEdgeList(uadaptor, 8);
  1.1432 +  checkGraphArcList(uadaptor, 16);
  1.1433 +  checkGraphConEdgeList(uadaptor, 8);
  1.1434 +  checkGraphConArcList(uadaptor, 16);
  1.1435 +
  1.1436 +  checkNodeIds(uadaptor);
  1.1437 +  checkEdgeIds(uadaptor);
  1.1438 +  checkArcIds(uadaptor);
  1.1439 +
  1.1440 +  checkGraphNodeMap(uadaptor);
  1.1441 +  checkGraphEdgeMap(uadaptor);
  1.1442 +  checkGraphArcMap(uadaptor);
  1.1443 +
  1.1444 +  checkGraphIncEdgeArcLists(uadaptor, rev_adaptor.inNode(n1), 2);
  1.1445 +  checkGraphIncEdgeArcLists(uadaptor, rev_adaptor.outNode(n1), 2);
  1.1446 +  checkGraphIncEdgeArcLists(uadaptor, rev_adaptor.inNode(n2), 3);
  1.1447 +  checkGraphIncEdgeArcLists(uadaptor, rev_adaptor.outNode(n2), 1);
  1.1448 +  checkGraphIncEdgeArcLists(uadaptor, rev_adaptor.inNode(n3), 2);
  1.1449 +  checkGraphIncEdgeArcLists(uadaptor, rev_adaptor.outNode(n3), 2);
  1.1450 +  checkGraphIncEdgeArcLists(uadaptor, rev_adaptor.inNode(n4), 1);
  1.1451 +  checkGraphIncEdgeArcLists(uadaptor, rev_adaptor.outNode(n4), 3);
  1.1452 +
  1.1453 +  // Check uuadaptor
  1.1454 +  checkGraphNodeList(uuadaptor, 8);
  1.1455 +  checkGraphEdgeList(uuadaptor, 16);
  1.1456 +  checkGraphArcList(uuadaptor, 32);
  1.1457 +  checkGraphConEdgeList(uuadaptor, 16);
  1.1458 +  checkGraphConArcList(uuadaptor, 32);
  1.1459 +
  1.1460 +  checkNodeIds(uuadaptor);
  1.1461 +  checkEdgeIds(uuadaptor);
  1.1462 +  checkArcIds(uuadaptor);
  1.1463 +
  1.1464 +  checkGraphNodeMap(uuadaptor);
  1.1465 +  checkGraphEdgeMap(uuadaptor);
  1.1466 +  checkGraphArcMap(uuadaptor);
  1.1467 +}
  1.1468 +
  1.1469 +int main(int, const char **) {
  1.1470 +  // Check the digraph adaptors (using ListDigraph)
  1.1471 +  checkReverseDigraph();
  1.1472 +  checkSubDigraph();
  1.1473 +  checkFilterNodes1();
  1.1474 +  checkFilterArcs();
  1.1475 +  checkUndirector();
  1.1476 +  checkResidualDigraph();
  1.1477 +  checkSplitNodes();
  1.1478 +
  1.1479 +  // Check the graph adaptors (using ListGraph)
  1.1480 +  checkSubGraph();
  1.1481 +  checkFilterNodes2();
  1.1482 +  checkFilterEdges();
  1.1483 +  checkOrienter();
  1.1484 +
  1.1485 +  // Combine adaptors (using GridGraph)
  1.1486 +  checkCombiningAdaptors();
  1.1487 +
  1.1488 +  return 0;
  1.1489 +}