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