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