test/graph_adaptor_test.cc
changeset 465 2b5496c62ccd
parent 463 a2fd8b8d0b30
equal deleted inserted replaced
5:7df98024f76d -1:000000000000
     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< ReverseDigraph< const Orienter<
       
  1381             const GridGraph, GridGraph::EdgeMap<bool> > > >
       
  1382     RevSplitGridGraph;
       
  1383   typedef ReverseDigraph<const RevSplitGridGraph> SplitGridGraph;
       
  1384   typedef Undirector<const SplitGridGraph> USplitGridGraph;
       
  1385   typedef Undirector<const USplitGridGraph> UUSplitGridGraph;
       
  1386   checkConcept<concepts::Digraph, RevSplitGridGraph>();
       
  1387   checkConcept<concepts::Digraph, SplitGridGraph>();
       
  1388   checkConcept<concepts::Graph, USplitGridGraph>();
       
  1389   checkConcept<concepts::Graph, UUSplitGridGraph>();
       
  1390 
       
  1391   RevSplitGridGraph rev_adaptor =
       
  1392     splitNodes(reverseDigraph(orienter(graph, dir_map)));
       
  1393   SplitGridGraph adaptor = reverseDigraph(rev_adaptor);
       
  1394   USplitGridGraph uadaptor = undirector(adaptor);
       
  1395   UUSplitGridGraph uuadaptor = undirector(uadaptor);
       
  1396 
       
  1397   // Check adaptor
       
  1398   checkGraphNodeList(adaptor, 8);
       
  1399   checkGraphArcList(adaptor, 8);
       
  1400   checkGraphConArcList(adaptor, 8);
       
  1401 
       
  1402   checkGraphOutArcList(adaptor, rev_adaptor.inNode(n1), 1);
       
  1403   checkGraphOutArcList(adaptor, rev_adaptor.outNode(n1), 1);
       
  1404   checkGraphOutArcList(adaptor, rev_adaptor.inNode(n2), 2);
       
  1405   checkGraphOutArcList(adaptor, rev_adaptor.outNode(n2), 1);
       
  1406   checkGraphOutArcList(adaptor, rev_adaptor.inNode(n3), 1);
       
  1407   checkGraphOutArcList(adaptor, rev_adaptor.outNode(n3), 1);
       
  1408   checkGraphOutArcList(adaptor, rev_adaptor.inNode(n4), 0);
       
  1409   checkGraphOutArcList(adaptor, rev_adaptor.outNode(n4), 1);
       
  1410 
       
  1411   checkGraphInArcList(adaptor, rev_adaptor.inNode(n1), 1);
       
  1412   checkGraphInArcList(adaptor, rev_adaptor.outNode(n1), 1);
       
  1413   checkGraphInArcList(adaptor, rev_adaptor.inNode(n2), 1);
       
  1414   checkGraphInArcList(adaptor, rev_adaptor.outNode(n2), 0);
       
  1415   checkGraphInArcList(adaptor, rev_adaptor.inNode(n3), 1);
       
  1416   checkGraphInArcList(adaptor, rev_adaptor.outNode(n3), 1);
       
  1417   checkGraphInArcList(adaptor, rev_adaptor.inNode(n4), 1);
       
  1418   checkGraphInArcList(adaptor, rev_adaptor.outNode(n4), 2);
       
  1419 
       
  1420   checkNodeIds(adaptor);
       
  1421   checkArcIds(adaptor);
       
  1422 
       
  1423   checkGraphNodeMap(adaptor);
       
  1424   checkGraphArcMap(adaptor);
       
  1425 
       
  1426   // Check uadaptor
       
  1427   checkGraphNodeList(uadaptor, 8);
       
  1428   checkGraphEdgeList(uadaptor, 8);
       
  1429   checkGraphArcList(uadaptor, 16);
       
  1430   checkGraphConEdgeList(uadaptor, 8);
       
  1431   checkGraphConArcList(uadaptor, 16);
       
  1432 
       
  1433   checkNodeIds(uadaptor);
       
  1434   checkEdgeIds(uadaptor);
       
  1435   checkArcIds(uadaptor);
       
  1436 
       
  1437   checkGraphNodeMap(uadaptor);
       
  1438   checkGraphEdgeMap(uadaptor);
       
  1439   checkGraphArcMap(uadaptor);
       
  1440 
       
  1441   checkGraphIncEdgeArcLists(uadaptor, rev_adaptor.inNode(n1), 2);
       
  1442   checkGraphIncEdgeArcLists(uadaptor, rev_adaptor.outNode(n1), 2);
       
  1443   checkGraphIncEdgeArcLists(uadaptor, rev_adaptor.inNode(n2), 3);
       
  1444   checkGraphIncEdgeArcLists(uadaptor, rev_adaptor.outNode(n2), 1);
       
  1445   checkGraphIncEdgeArcLists(uadaptor, rev_adaptor.inNode(n3), 2);
       
  1446   checkGraphIncEdgeArcLists(uadaptor, rev_adaptor.outNode(n3), 2);
       
  1447   checkGraphIncEdgeArcLists(uadaptor, rev_adaptor.inNode(n4), 1);
       
  1448   checkGraphIncEdgeArcLists(uadaptor, rev_adaptor.outNode(n4), 3);
       
  1449 
       
  1450   // Check uuadaptor
       
  1451   checkGraphNodeList(uuadaptor, 8);
       
  1452   checkGraphEdgeList(uuadaptor, 16);
       
  1453   checkGraphArcList(uuadaptor, 32);
       
  1454   checkGraphConEdgeList(uuadaptor, 16);
       
  1455   checkGraphConArcList(uuadaptor, 32);
       
  1456 
       
  1457   checkNodeIds(uuadaptor);
       
  1458   checkEdgeIds(uuadaptor);
       
  1459   checkArcIds(uuadaptor);
       
  1460 
       
  1461   checkGraphNodeMap(uuadaptor);
       
  1462   checkGraphEdgeMap(uuadaptor);
       
  1463   checkGraphArcMap(uuadaptor);
       
  1464 }
       
  1465 
       
  1466 int main(int, const char **) {
       
  1467   // Check the digraph adaptors (using ListDigraph)
       
  1468   checkReverseDigraph();
       
  1469   checkSubDigraph();
       
  1470   checkFilterNodes1();
       
  1471   checkFilterArcs();
       
  1472   checkUndirector();
       
  1473   checkResidualDigraph();
       
  1474   checkSplitNodes();
       
  1475 
       
  1476   // Check the graph adaptors (using ListGraph)
       
  1477   checkSubGraph();
       
  1478   checkFilterNodes2();
       
  1479   checkFilterEdges();
       
  1480   checkOrienter();
       
  1481 
       
  1482   // Combine adaptors (using GridGraph)
       
  1483   checkCombiningAdaptors();
       
  1484 
       
  1485   return 0;
       
  1486 }