Greatly extend and improve the test file for adaptors (#67)
authorPeter Kovacs <kpeter@inf.elte.hu>
Mon, 12 Jan 2009 07:52:48 +0100
changeset 486a2fd8b8d0b30
parent 478 5a1e9fdcfd3a
child 487 acfb0f24d178
Greatly extend and improve the test file for adaptors (#67)

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