test/graph_adaptor_test.cc
changeset 465 2b5496c62ccd
parent 464 acfb0f24d178
child 466 4f1431aeef42
     1.1 --- a/test/graph_adaptor_test.cc	Mon Jan 12 08:05:30 2009 +0100
     1.2 +++ /dev/null	Thu Jan 01 00:00:00 1970 +0000
     1.3 @@ -1,1486 +0,0 @@
     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 -}