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