Mercuriallemon-1.2 / comparison
summary | shortlog | changelog | graph | tags | bookmarks | branches | files | changeset | file | latest | revisions | annotate | diff | comparison | raw | help
test/graph_adaptor_test.cc
changeset 463 a2fd8b8d0b30
parent 440 88ed40ad0d4f
child 464 acfb0f24d178
equal deleted inserted replaced
3:7681ddaf6cf2 4:a9caef1336c0 
    14  * express or implied, and with no claim as to its suitability for any
 
    14  * express or implied, and with no claim as to its suitability for any
 
    15  * purpose.
 
    15  * purpose.
 
    16  *
 
    16  *
 
    17  */
 
    17  */
 
    18 
    18 
    19 #include<iostream>
 
    19 #include <iostream>
 
    20 #include<lemon/concept_check.h>
 
       
    21 
       
    22 #include<lemon/list_graph.h>
 
       
    23 #include<lemon/smart_graph.h>
 
       
    24 
       
    25 #include<lemon/concepts/digraph.h>
 
       
    26 #include<lemon/concepts/graph.h>
 
       
    27 
       
    28 #include<lemon/adaptors.h>
 
       
    29 
       
    30 #include <limits>
 
    20 #include <limits>
 
       
    21 
       
    22 #include <lemon/list_graph.h>
 
       
    23 #include <lemon/grid_graph.h>
 
    31 #include <lemon/bfs.h>
 
    24 #include <lemon/bfs.h>
 
    32 #include <lemon/path.h>
 
    25 #include <lemon/path.h>
 
    33 
    26 
    34 #include"test/test_tools.h"
 
    27 #include <lemon/concepts/digraph.h>
 
    35 #include"test/graph_test.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"
 
    36 
    37 
    37 using namespace lemon;
 
    38 using namespace lemon;
 
    38 
    39 
    39 void checkReverseDigraph() {
 
    40 void checkReverseDigraph() {
 
       
    41   // Check concepts
 
    40   checkConcept<concepts::Digraph, ReverseDigraph<concepts::Digraph> >();
 
    42   checkConcept<concepts::Digraph, ReverseDigraph<concepts::Digraph> >();
 
    41 
    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
 
    42   typedef ListDigraph Digraph;
 
    54   typedef ListDigraph Digraph;
 
    43   typedef ReverseDigraph<Digraph> Adaptor;
 
    55   typedef ReverseDigraph<Digraph> Adaptor;
 
    44 
    56 
    45   Digraph digraph;
 
    57   Digraph digraph;
 
    46   Adaptor adaptor(digraph);
 
    58   Adaptor adaptor(digraph);
 
    47 
    59 
       
    60   // Add nodes and arcs to the original digraph
 
    48   Digraph::Node n1 = digraph.addNode();
 
    61   Digraph::Node n1 = digraph.addNode();
 
    49   Digraph::Node n2 = digraph.addNode();
 
    62   Digraph::Node n2 = digraph.addNode();
 
    50   Digraph::Node n3 = digraph.addNode();
 
    63   Digraph::Node n3 = digraph.addNode();
 
    51 
    64 
    52   Digraph::Arc a1 = digraph.addArc(n1, n2);
 
    65   Digraph::Arc a1 = digraph.addArc(n1, n2);
 
    53   Digraph::Arc a2 = digraph.addArc(n1, n3);
 
    66   Digraph::Arc a2 = digraph.addArc(n1, n3);
 
    54   Digraph::Arc a3 = digraph.addArc(n2, n3);
 
    67   Digraph::Arc a3 = digraph.addArc(n2, n3);
 
    55 
    68 
       
    69   // Check the adaptor
 
    56   checkGraphNodeList(adaptor, 3);
 
    70   checkGraphNodeList(adaptor, 3);
 
    57   checkGraphArcList(adaptor, 3);
 
    71   checkGraphArcList(adaptor, 3);
 
    58   checkGraphConArcList(adaptor, 3);
 
    72   checkGraphConArcList(adaptor, 3);
 
    59 
    73 
    60   checkGraphOutArcList(adaptor, n1, 0);
 
    74   checkGraphOutArcList(adaptor, n1, 0);
 
    69   checkArcIds(adaptor);
 
    83   checkArcIds(adaptor);
 
    70 
    84 
    71   checkGraphNodeMap(adaptor);
 
    85   checkGraphNodeMap(adaptor);
 
    72   checkGraphArcMap(adaptor);
 
    86   checkGraphArcMap(adaptor);
 
    73 
    87 
       
    88   // Check the orientation of the arcs
 
    74   for (Adaptor::ArcIt a(adaptor); a != INVALID; ++a) {
 
    89   for (Adaptor::ArcIt a(adaptor); a != INVALID; ++a) {
 
    75     check(adaptor.source(a) == digraph.target(a), "Wrong reverse");
 
    90     check(adaptor.source(a) == digraph.target(a), "Wrong reverse");
 
    76     check(adaptor.target(a) == digraph.source(a), "Wrong reverse");
 
    91     check(adaptor.target(a) == digraph.source(a), "Wrong reverse");
 
    77   }
 
    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;
 
    78 }
 
   153 }
 
    79 
   154 
    80 void checkSubDigraph() {
 
   155 void checkSubDigraph() {
 
    81   checkConcept<concepts::Digraph,
 
   156   // Check concepts
 
    82     SubDigraph<concepts::Digraph,
 
   157   checkConcept<concepts::Digraph, SubDigraph<concepts::Digraph> >();
 
    83     concepts::Digraph::NodeMap<bool>,
 
   158   checkConcept<concepts::Digraph, SubDigraph<ListDigraph> >();
 
    84     concepts::Digraph::ArcMap<bool> > >();
 
   159   checkConcept<concepts::AlterableDigraphComponent<>,
 
    85 
   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
 
    86   typedef ListDigraph Digraph;
 
   169   typedef ListDigraph Digraph;
 
    87   typedef Digraph::NodeMap<bool> NodeFilter;
 
   170   typedef Digraph::NodeMap<bool> NodeFilter;
 
    88   typedef Digraph::ArcMap<bool> ArcFilter;
 
   171   typedef Digraph::ArcMap<bool> ArcFilter;
 
    89   typedef SubDigraph<Digraph, NodeFilter, ArcFilter> Adaptor;
 
   172   typedef SubDigraph<Digraph, NodeFilter, ArcFilter> Adaptor;
 
    90 
   173 
    91   Digraph digraph;
 
   174   Digraph digraph;
 
    92   NodeFilter node_filter(digraph);
 
   175   NodeFilter node_filter(digraph);
 
    93   ArcFilter arc_filter(digraph);
 
   176   ArcFilter arc_filter(digraph);
 
    94   Adaptor adaptor(digraph, node_filter, arc_filter);
 
   177   Adaptor adaptor(digraph, node_filter, arc_filter);
 
    95 
   178 
       
   179   // Add nodes and arcs to the original digraph and the adaptor
 
    96   Digraph::Node n1 = digraph.addNode();
 
   180   Digraph::Node n1 = digraph.addNode();
 
    97   Digraph::Node n2 = digraph.addNode();
 
   181   Digraph::Node n2 = digraph.addNode();
 
    98   Digraph::Node n3 = digraph.addNode();
 
   182   Adaptor::Node n3 = adaptor.addNode();
 
       
   183 
       
   184   node_filter[n1] = node_filter[n2] = node_filter[n3] = true;
 
    99 
   185 
   100   Digraph::Arc a1 = digraph.addArc(n1, n2);
 
   186   Digraph::Arc a1 = digraph.addArc(n1, n2);
 
   101   Digraph::Arc a2 = digraph.addArc(n1, n3);
 
   187   Digraph::Arc a2 = digraph.addArc(n1, n3);
 
   102   Digraph::Arc a3 = digraph.addArc(n2, n3);
 
   188   Adaptor::Arc a3 = adaptor.addArc(n2, n3);
 
   103 
   189 
   104   node_filter[n1] = node_filter[n2] = node_filter[n3] = true;
 
       
   105   arc_filter[a1] = arc_filter[a2] = arc_filter[a3] = true;
 
   190   arc_filter[a1] = arc_filter[a2] = arc_filter[a3] = true;
 
   106 
   191 
   107   checkGraphNodeList(adaptor, 3);
 
   192   checkGraphNodeList(adaptor, 3);
 
   108   checkGraphArcList(adaptor, 3);
 
   193   checkGraphArcList(adaptor, 3);
 
   109   checkGraphConArcList(adaptor, 3);
 
   194   checkGraphConArcList(adaptor, 3);
 
   120   checkArcIds(adaptor);
 
   205   checkArcIds(adaptor);
 
   121 
   206 
   122   checkGraphNodeMap(adaptor);
 
   207   checkGraphNodeMap(adaptor);
 
   123   checkGraphArcMap(adaptor);
 
   208   checkGraphArcMap(adaptor);
 
   124 
   209 
   125   arc_filter[a2] = false;
 
   210   // Hide an arc
 
       
   211   adaptor.status(a2, false);
 
       
   212   adaptor.disable(a3);
 
       
   213   if (!adaptor.status(a3)) adaptor.enable(a3);
 
   126 
   214 
   127   checkGraphNodeList(adaptor, 3);
 
   215   checkGraphNodeList(adaptor, 3);
 
   128   checkGraphArcList(adaptor, 2);
 
   216   checkGraphArcList(adaptor, 2);
 
   129   checkGraphConArcList(adaptor, 2);
 
   217   checkGraphConArcList(adaptor, 2);
 
   130 
   218 
   140   checkArcIds(adaptor);
 
   228   checkArcIds(adaptor);
 
   141 
   229 
   142   checkGraphNodeMap(adaptor);
 
   230   checkGraphNodeMap(adaptor);
 
   143   checkGraphArcMap(adaptor);
 
   231   checkGraphArcMap(adaptor);
 
   144 
   232 
   145   node_filter[n1] = false;
 
   233   // Hide a node
 
       
   234   adaptor.status(n1, false);
 
       
   235   adaptor.disable(n3);
 
       
   236   if (!adaptor.status(n3)) adaptor.enable(n3);
 
   146 
   237 
   147   checkGraphNodeList(adaptor, 2);
 
   238   checkGraphNodeList(adaptor, 2);
 
   148   checkGraphArcList(adaptor, 1);
 
   239   checkGraphArcList(adaptor, 1);
 
   149   checkGraphConArcList(adaptor, 1);
 
   240   checkGraphConArcList(adaptor, 1);
 
   150 
   241 
   158   checkArcIds(adaptor);
 
   249   checkArcIds(adaptor);
 
   159 
   250 
   160   checkGraphNodeMap(adaptor);
 
   251   checkGraphNodeMap(adaptor);
 
   161   checkGraphArcMap(adaptor);
 
   252   checkGraphArcMap(adaptor);
 
   162 
   253 
       
   254   // Hide all nodes and arcs
 
   163   node_filter[n1] = node_filter[n2] = node_filter[n3] = false;
 
   255   node_filter[n1] = node_filter[n2] = node_filter[n3] = false;
 
   164   arc_filter[a1] = arc_filter[a2] = arc_filter[a3] = false;
 
   256   arc_filter[a1] = arc_filter[a2] = arc_filter[a3] = false;
 
   165 
   257 
   166   checkGraphNodeList(adaptor, 0);
 
   258   checkGraphNodeList(adaptor, 0);
 
   167   checkGraphArcList(adaptor, 0);
 
   259   checkGraphArcList(adaptor, 0);
 
   170   checkNodeIds(adaptor);
 
   262   checkNodeIds(adaptor);
 
   171   checkArcIds(adaptor);
 
   263   checkArcIds(adaptor);
 
   172 
   264 
   173   checkGraphNodeMap(adaptor);
 
   265   checkGraphNodeMap(adaptor);
 
   174   checkGraphArcMap(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;
 
   175 }
 
   277 }
 
   176 
   278 
   177 void checkFilterNodes1() {
 
   279 void checkFilterNodes1() {
 
   178   checkConcept<concepts::Digraph,
 
   280   // Check concepts
 
   179     FilterNodes<concepts::Digraph,
 
   281   checkConcept<concepts::Digraph, FilterNodes<concepts::Digraph> >();
 
   180       concepts::Digraph::NodeMap<bool> > >();
 
   282   checkConcept<concepts::Digraph, FilterNodes<ListDigraph> >();
 
   181 
   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
 
   182   typedef ListDigraph Digraph;
 
   293   typedef ListDigraph Digraph;
 
   183   typedef Digraph::NodeMap<bool> NodeFilter;
 
   294   typedef Digraph::NodeMap<bool> NodeFilter;
 
   184   typedef FilterNodes<Digraph, NodeFilter> Adaptor;
 
   295   typedef FilterNodes<Digraph, NodeFilter> Adaptor;
 
   185 
   296 
   186   Digraph digraph;
 
   297   Digraph digraph;
 
   187   NodeFilter node_filter(digraph);
 
   298   NodeFilter node_filter(digraph);
 
   188   Adaptor adaptor(digraph, node_filter);
 
   299   Adaptor adaptor(digraph, node_filter);
 
   189 
   300 
       
   301   // Add nodes and arcs to the original digraph and the adaptor
 
   190   Digraph::Node n1 = digraph.addNode();
 
   302   Digraph::Node n1 = digraph.addNode();
 
   191   Digraph::Node n2 = digraph.addNode();
 
   303   Digraph::Node n2 = digraph.addNode();
 
   192   Digraph::Node n3 = digraph.addNode();
 
   304   Adaptor::Node n3 = adaptor.addNode();
 
       
   305 
       
   306   node_filter[n1] = node_filter[n2] = node_filter[n3] = true;
 
   193 
   307 
   194   Digraph::Arc a1 = digraph.addArc(n1, n2);
 
   308   Digraph::Arc a1 = digraph.addArc(n1, n2);
 
   195   Digraph::Arc a2 = digraph.addArc(n1, n3);
 
   309   Digraph::Arc a2 = digraph.addArc(n1, n3);
 
   196   Digraph::Arc a3 = digraph.addArc(n2, n3);
 
   310   Adaptor::Arc a3 = adaptor.addArc(n2, n3);
 
   197 
       
   198   node_filter[n1] = node_filter[n2] = node_filter[n3] = true;
 
       
   199 
   311 
   200   checkGraphNodeList(adaptor, 3);
 
   312   checkGraphNodeList(adaptor, 3);
 
   201   checkGraphArcList(adaptor, 3);
 
   313   checkGraphArcList(adaptor, 3);
 
   202   checkGraphConArcList(adaptor, 3);
 
   314   checkGraphConArcList(adaptor, 3);
 
   203 
   315 
   213   checkArcIds(adaptor);
 
   325   checkArcIds(adaptor);
 
   214 
   326 
   215   checkGraphNodeMap(adaptor);
 
   327   checkGraphNodeMap(adaptor);
 
   216   checkGraphArcMap(adaptor);
 
   328   checkGraphArcMap(adaptor);
 
   217 
   329 
   218   node_filter[n1] = false;
 
   330   // Hide a node
 
       
   331   adaptor.status(n1, false);
 
       
   332   adaptor.disable(n3);
 
       
   333   if (!adaptor.status(n3)) adaptor.enable(n3);
 
   219 
   334 
   220   checkGraphNodeList(adaptor, 2);
 
   335   checkGraphNodeList(adaptor, 2);
 
   221   checkGraphArcList(adaptor, 1);
 
   336   checkGraphArcList(adaptor, 1);
 
   222   checkGraphConArcList(adaptor, 1);
 
   337   checkGraphConArcList(adaptor, 1);
 
   223 
   338 
   231   checkArcIds(adaptor);
 
   346   checkArcIds(adaptor);
 
   232 
   347 
   233   checkGraphNodeMap(adaptor);
 
   348   checkGraphNodeMap(adaptor);
 
   234   checkGraphArcMap(adaptor);
 
   349   checkGraphArcMap(adaptor);
 
   235 
   350 
       
   351   // Hide all nodes
 
   236   node_filter[n1] = node_filter[n2] = node_filter[n3] = false;
 
   352   node_filter[n1] = node_filter[n2] = node_filter[n3] = false;
 
   237 
   353 
   238   checkGraphNodeList(adaptor, 0);
 
   354   checkGraphNodeList(adaptor, 0);
 
   239   checkGraphArcList(adaptor, 0);
 
   355   checkGraphArcList(adaptor, 0);
 
   240   checkGraphConArcList(adaptor, 0);
 
   356   checkGraphConArcList(adaptor, 0);
 
   242   checkNodeIds(adaptor);
 
   358   checkNodeIds(adaptor);
 
   243   checkArcIds(adaptor);
 
   359   checkArcIds(adaptor);
 
   244 
   360 
   245   checkGraphNodeMap(adaptor);
 
   361   checkGraphNodeMap(adaptor);
 
   246   checkGraphArcMap(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;
 
   247 }
 
   373 }
 
   248 
   374 
   249 void checkFilterArcs() {
 
   375 void checkFilterArcs() {
 
   250   checkConcept<concepts::Digraph,
 
   376   // Check concepts
 
   251     FilterArcs<concepts::Digraph,
 
   377   checkConcept<concepts::Digraph, FilterArcs<concepts::Digraph> >();
 
   252     concepts::Digraph::ArcMap<bool> > >();
 
   378   checkConcept<concepts::Digraph, FilterArcs<ListDigraph> >();
 
   253 
   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
 
   254   typedef ListDigraph Digraph;
 
   389   typedef ListDigraph Digraph;
 
   255   typedef Digraph::ArcMap<bool> ArcFilter;
 
   390   typedef Digraph::ArcMap<bool> ArcFilter;
 
   256   typedef FilterArcs<Digraph, ArcFilter> Adaptor;
 
   391   typedef FilterArcs<Digraph, ArcFilter> Adaptor;
 
   257 
   392 
   258   Digraph digraph;
 
   393   Digraph digraph;
 
   259   ArcFilter arc_filter(digraph);
 
   394   ArcFilter arc_filter(digraph);
 
   260   Adaptor adaptor(digraph, arc_filter);
 
   395   Adaptor adaptor(digraph, arc_filter);
 
   261 
   396 
       
   397   // Add nodes and arcs to the original digraph and the adaptor
 
   262   Digraph::Node n1 = digraph.addNode();
 
   398   Digraph::Node n1 = digraph.addNode();
 
   263   Digraph::Node n2 = digraph.addNode();
 
   399   Digraph::Node n2 = digraph.addNode();
 
   264   Digraph::Node n3 = digraph.addNode();
 
   400   Adaptor::Node n3 = adaptor.addNode();
 
   265 
   401 
   266   Digraph::Arc a1 = digraph.addArc(n1, n2);
 
   402   Digraph::Arc a1 = digraph.addArc(n1, n2);
 
   267   Digraph::Arc a2 = digraph.addArc(n1, n3);
 
   403   Digraph::Arc a2 = digraph.addArc(n1, n3);
 
   268   Digraph::Arc a3 = digraph.addArc(n2, n3);
 
   404   Adaptor::Arc a3 = adaptor.addArc(n2, n3);
 
   269 
   405 
   270   arc_filter[a1] = arc_filter[a2] = arc_filter[a3] = true;
 
   406   arc_filter[a1] = arc_filter[a2] = arc_filter[a3] = true;
 
   271 
   407 
   272   checkGraphNodeList(adaptor, 3);
 
   408   checkGraphNodeList(adaptor, 3);
 
   273   checkGraphArcList(adaptor, 3);
 
   409   checkGraphArcList(adaptor, 3);
 
   285   checkArcIds(adaptor);
 
   421   checkArcIds(adaptor);
 
   286 
   422 
   287   checkGraphNodeMap(adaptor);
 
   423   checkGraphNodeMap(adaptor);
 
   288   checkGraphArcMap(adaptor);
 
   424   checkGraphArcMap(adaptor);
 
   289 
   425 
   290   arc_filter[a2] = false;
 
   426   // Hide an arc
 
       
   427   adaptor.status(a2, false);
 
       
   428   adaptor.disable(a3);
 
       
   429   if (!adaptor.status(a3)) adaptor.enable(a3);
 
   291 
   430 
   292   checkGraphNodeList(adaptor, 3);
 
   431   checkGraphNodeList(adaptor, 3);
 
   293   checkGraphArcList(adaptor, 2);
 
   432   checkGraphArcList(adaptor, 2);
 
   294   checkGraphConArcList(adaptor, 2);
 
   433   checkGraphConArcList(adaptor, 2);
 
   295 
   434 
   305   checkArcIds(adaptor);
 
   444   checkArcIds(adaptor);
 
   306 
   445 
   307   checkGraphNodeMap(adaptor);
 
   446   checkGraphNodeMap(adaptor);
 
   308   checkGraphArcMap(adaptor);
 
   447   checkGraphArcMap(adaptor);
 
   309 
   448 
       
   449   // Hide all arcs
 
   310   arc_filter[a1] = arc_filter[a2] = arc_filter[a3] = false;
 
   450   arc_filter[a1] = arc_filter[a2] = arc_filter[a3] = false;
 
   311 
   451 
   312   checkGraphNodeList(adaptor, 3);
 
   452   checkGraphNodeList(adaptor, 3);
 
   313   checkGraphArcList(adaptor, 0);
 
   453   checkGraphArcList(adaptor, 0);
 
   314   checkGraphConArcList(adaptor, 0);
 
   454   checkGraphConArcList(adaptor, 0);
 
   316   checkNodeIds(adaptor);
 
   456   checkNodeIds(adaptor);
 
   317   checkArcIds(adaptor);
 
   457   checkArcIds(adaptor);
 
   318 
   458 
   319   checkGraphNodeMap(adaptor);
 
   459   checkGraphNodeMap(adaptor);
 
   320   checkGraphArcMap(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;
 
   321 }
 
   471 }
 
   322 
   472 
   323 void checkUndirector() {
 
   473 void checkUndirector() {
 
       
   474   // Check concepts
 
   324   checkConcept<concepts::Graph, Undirector<concepts::Digraph> >();
 
   475   checkConcept<concepts::Graph, Undirector<concepts::Digraph> >();
 
   325 
   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
 
   326   typedef ListDigraph Digraph;
 
   488   typedef ListDigraph Digraph;
 
   327   typedef Undirector<Digraph> Adaptor;
 
   489   typedef Undirector<Digraph> Adaptor;
 
   328 
   490 
   329   Digraph digraph;
 
   491   Digraph digraph;
 
   330   Adaptor adaptor(digraph);
 
   492   Adaptor adaptor(digraph);
 
   331 
   493 
       
   494   // Add nodes and arcs/edges to the original digraph and the adaptor
 
   332   Digraph::Node n1 = digraph.addNode();
 
   495   Digraph::Node n1 = digraph.addNode();
 
   333   Digraph::Node n2 = digraph.addNode();
 
   496   Digraph::Node n2 = digraph.addNode();
 
   334   Digraph::Node n3 = digraph.addNode();
 
   497   Adaptor::Node n3 = adaptor.addNode();
 
   335 
   498 
   336   Digraph::Arc a1 = digraph.addArc(n1, n2);
 
   499   Digraph::Arc a1 = digraph.addArc(n1, n2);
 
   337   Digraph::Arc a2 = digraph.addArc(n1, n3);
 
   500   Digraph::Arc a2 = digraph.addArc(n1, n3);
 
   338   Digraph::Arc a3 = digraph.addArc(n2, n3);
 
   501   Adaptor::Edge e3 = adaptor.addEdge(n2, n3);
 
   339 
   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
 
   340   checkGraphNodeList(adaptor, 3);
 
   523   checkGraphNodeList(adaptor, 3);
 
   341   checkGraphArcList(adaptor, 6);
 
   524   checkGraphArcList(adaptor, 6);
 
   342   checkGraphEdgeList(adaptor, 3);
 
   525   checkGraphEdgeList(adaptor, 3);
 
   343   checkGraphConArcList(adaptor, 6);
 
   526   checkGraphConArcList(adaptor, 6);
 
   344   checkGraphConEdgeList(adaptor, 3);
 
   527   checkGraphConEdgeList(adaptor, 3);
 
   345 
   528 
   346   checkGraphOutArcList(adaptor, n1, 2);
 
   529   checkGraphIncEdgeArcLists(adaptor, n1, 2);
 
   347   checkGraphOutArcList(adaptor, n2, 2);
 
   530   checkGraphIncEdgeArcLists(adaptor, n2, 2);
 
   348   checkGraphOutArcList(adaptor, n3, 2);
 
   531   checkGraphIncEdgeArcLists(adaptor, n3, 2);
 
   349 
       
   350   checkGraphInArcList(adaptor, n1, 2);
 
       
   351   checkGraphInArcList(adaptor, n2, 2);
 
       
   352   checkGraphInArcList(adaptor, n3, 2);
 
       
   353 
       
   354   checkGraphIncEdgeList(adaptor, n1, 2);
 
       
   355   checkGraphIncEdgeList(adaptor, n2, 2);
 
       
   356   checkGraphIncEdgeList(adaptor, n3, 2);
 
       
   357 
   532 
   358   checkNodeIds(adaptor);
 
   533   checkNodeIds(adaptor);
 
   359   checkArcIds(adaptor);
 
   534   checkArcIds(adaptor);
 
   360   checkEdgeIds(adaptor);
 
   535   checkEdgeIds(adaptor);
 
   361 
   536 
   362   checkGraphNodeMap(adaptor);
 
   537   checkGraphNodeMap(adaptor);
 
   363   checkGraphArcMap(adaptor);
 
   538   checkGraphArcMap(adaptor);
 
   364   checkGraphEdgeMap(adaptor);
 
   539   checkGraphEdgeMap(adaptor);
 
   365 
   540 
       
   541   // Check the edges of the adaptor
 
   366   for (Adaptor::EdgeIt e(adaptor); e != INVALID; ++e) {
 
   542   for (Adaptor::EdgeIt e(adaptor); e != INVALID; ++e) {
 
   367     check(adaptor.u(e) == digraph.source(e), "Wrong undir");
 
   543     check(adaptor.u(e) == digraph.source(e), "Wrong undir");
 
   368     check(adaptor.v(e) == digraph.target(e), "Wrong undir");
 
   544     check(adaptor.v(e) == digraph.target(e), "Wrong undir");
 
   369   }
 
   545   }
 
   370 
   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;
 
   371 }
 
   582 }
 
   372 
   583 
   373 void checkResidual() {
 
   584 void checkResidual() {
 
   374   checkConcept<concepts::Digraph,
 
   585   // Check concepts
 
   375     Residual<concepts::Digraph,
 
   586   checkConcept<concepts::Digraph, Residual<concepts::Digraph> >();
 
   376     concepts::Digraph::ArcMap<int>,
 
   587   checkConcept<concepts::Digraph, Residual<ListDigraph> >();
 
   377     concepts::Digraph::ArcMap<int> > >();
 
   588 
   378 
   589   // Create a digraph and an adaptor
 
   379   typedef ListDigraph Digraph;
 
   590   typedef ListDigraph Digraph;
 
   380   typedef Digraph::ArcMap<int> IntArcMap;
 
   591   typedef Digraph::ArcMap<int> IntArcMap;
 
   381   typedef Residual<Digraph, IntArcMap> Adaptor;
 
   592   typedef Residual<Digraph, IntArcMap> Adaptor;
 
   382 
   593 
   383   Digraph digraph;
 
   594   Digraph digraph;
 
   401   capacity[a3] = 4;
 
   612   capacity[a3] = 4;
 
   402   capacity[a4] = 4;
 
   613   capacity[a4] = 4;
 
   403   capacity[a5] = 6;
 
   614   capacity[a5] = 6;
 
   404   capacity[a6] = 10;
 
   615   capacity[a6] = 10;
 
   405 
   616 
   406   for (Adaptor::ArcIt a(adaptor); a != INVALID; ++a) {
 
   617   // Check the adaptor with various flow values
 
       
   618   for (Digraph::ArcIt a(digraph); a != INVALID; ++a) {
 
   407     flow[a] = 0;
 
   619     flow[a] = 0;
 
   408   }
 
   620   }
 
   409 
   621 
   410   checkGraphNodeList(adaptor, 4);
 
   622   checkGraphNodeList(adaptor, 4);
 
   411   checkGraphArcList(adaptor, 6);
 
   623   checkGraphArcList(adaptor, 6);
 
   419   checkGraphInArcList(adaptor, n1, 0);
 
   631   checkGraphInArcList(adaptor, n1, 0);
 
   420   checkGraphInArcList(adaptor, n2, 1);
 
   632   checkGraphInArcList(adaptor, n2, 1);
 
   421   checkGraphInArcList(adaptor, n3, 2);
 
   633   checkGraphInArcList(adaptor, n3, 2);
 
   422   checkGraphInArcList(adaptor, n4, 3);
 
   634   checkGraphInArcList(adaptor, n4, 3);
 
   423 
   635 
   424   for (Adaptor::ArcIt a(adaptor); a != INVALID; ++a) {
 
   636   for (Digraph::ArcIt a(digraph); a != INVALID; ++a) {
 
   425     flow[a] = capacity[a] / 2;
 
   637     flow[a] = capacity[a] / 2;
 
   426   }
 
   638   }
 
   427 
   639 
   428   checkGraphNodeList(adaptor, 4);
 
   640   checkGraphNodeList(adaptor, 4);
 
   429   checkGraphArcList(adaptor, 12);
 
   641   checkGraphArcList(adaptor, 12);
 
   443   checkArcIds(adaptor);
 
   655   checkArcIds(adaptor);
 
   444 
   656 
   445   checkGraphNodeMap(adaptor);
 
   657   checkGraphNodeMap(adaptor);
 
   446   checkGraphArcMap(adaptor);
 
   658   checkGraphArcMap(adaptor);
 
   447 
   659 
   448   for (Adaptor::ArcIt a(adaptor); a != INVALID; ++a) {
 
   660   for (Digraph::ArcIt a(digraph); a != INVALID; ++a) {
 
   449     flow[a] = capacity[a];
 
   661     flow[a] = capacity[a];
 
   450   }
 
   662   }
 
   451 
   663 
   452   checkGraphNodeList(adaptor, 4);
 
   664   checkGraphNodeList(adaptor, 4);
 
   453   checkGraphArcList(adaptor, 6);
 
   665   checkGraphArcList(adaptor, 6);
 
   461   checkGraphInArcList(adaptor, n1, 3);
 
   673   checkGraphInArcList(adaptor, n1, 3);
 
   462   checkGraphInArcList(adaptor, n2, 2);
 
   674   checkGraphInArcList(adaptor, n2, 2);
 
   463   checkGraphInArcList(adaptor, n3, 1);
 
   675   checkGraphInArcList(adaptor, n3, 1);
 
   464   checkGraphInArcList(adaptor, n4, 0);
 
   676   checkGraphInArcList(adaptor, n4, 0);
 
   465 
   677 
       
   678   // Saturate all backward arcs
 
       
   679   // (set the flow to zero on all forward arcs)
 
   466   for (Adaptor::ArcIt a(adaptor); a != INVALID; ++a) {
 
   680   for (Adaptor::ArcIt a(adaptor); a != INVALID; ++a) {
 
   467     flow[a] = 0;
 
   681     if (adaptor.backward(a))
 
   468   }
 
   682       adaptor.augment(a, adaptor.residualCapacity(a));
 
   469 
   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
 
   470   int flow_value = 0;
 
   700   int flow_value = 0;
 
       
   701   Adaptor::ResidualCapacity res_cap(adaptor);
 
   471   while (true) {
 
   702   while (true) {
 
   472 
   703 
   473     Bfs<Adaptor> bfs(adaptor);
 
   704     Bfs<Adaptor> bfs(adaptor);
 
   474     bfs.run(n1, n4);
 
   705     bfs.run(n1, n4);
 
   475 
   706 
   477 
   708 
   478     Path<Adaptor> p = bfs.path(n4);
 
   709     Path<Adaptor> p = bfs.path(n4);
 
   479 
   710 
   480     int min = std::numeric_limits<int>::max();
 
   711     int min = std::numeric_limits<int>::max();
 
   481     for (Path<Adaptor>::ArcIt a(p); a != INVALID; ++a) {
 
   712     for (Path<Adaptor>::ArcIt a(p); a != INVALID; ++a) {
 
   482       if (adaptor.residualCapacity(a) < min)
 
   713       if (res_cap[a] < min) min = res_cap[a];
 
   483         min = adaptor.residualCapacity(a);
 
       
   484     }
 
   714     }
 
   485 
   715 
   486     for (Path<Adaptor>::ArcIt a(p); a != INVALID; ++a) {
 
   716     for (Path<Adaptor>::ArcIt a(p); a != INVALID; ++a) {
 
   487       adaptor.augment(a, min);
 
   717       adaptor.augment(a, min);
 
   488     }
 
   718     }
 
   489     flow_value += min;
 
   719     flow_value += min;
 
   490   }
 
   720   }
 
   491 
   721 
   492   check(flow_value == 18, "Wrong flow with res graph adaptor");
 
   722   check(flow_value == 18, "Wrong flow with res graph adaptor");
 
   493 
   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);
 
   494 }
 
   740 }
 
   495 
   741 
   496 void checkSplitNodes() {
 
   742 void checkSplitNodes() {
 
       
   743   // Check concepts
 
   497   checkConcept<concepts::Digraph, SplitNodes<concepts::Digraph> >();
 
   744   checkConcept<concepts::Digraph, SplitNodes<concepts::Digraph> >();
 
   498 
   745   checkConcept<concepts::Digraph, SplitNodes<ListDigraph> >();
 
       
   746 
       
   747   // Create a digraph and an adaptor
 
   499   typedef ListDigraph Digraph;
 
   748   typedef ListDigraph Digraph;
 
   500   typedef SplitNodes<Digraph> Adaptor;
 
   749   typedef SplitNodes<Digraph> Adaptor;
 
   501 
   750 
   502   Digraph digraph;
 
   751   Digraph digraph;
 
   503   Adaptor adaptor(digraph);
 
   752   Adaptor adaptor(digraph);
 
   532   checkArcIds(adaptor);
 
   781   checkArcIds(adaptor);
 
   533 
   782 
   534   checkGraphNodeMap(adaptor);
 
   783   checkGraphNodeMap(adaptor);
 
   535   checkGraphArcMap(adaptor);
 
   784   checkGraphArcMap(adaptor);
 
   536 
   785 
       
   786   // Check split
 
   537   for (Adaptor::ArcIt a(adaptor); a != INVALID; ++a) {
 
   787   for (Adaptor::ArcIt a(adaptor); a != INVALID; ++a) {
 
   538     if (adaptor.origArc(a)) {
 
   788     if (adaptor.origArc(a)) {
 
   539       Digraph::Arc oa = a;
 
   789       Digraph::Arc oa = a;
 
   540       check(adaptor.source(a) == adaptor.outNode(digraph.source(oa)),
 
   790       check(adaptor.source(a) == adaptor.outNode(digraph.source(oa)),
 
   541             "Wrong split");
 
   791             "Wrong split");
 
   545       Digraph::Node on = a;
 
   795       Digraph::Node on = a;
 
   546       check(adaptor.source(a) == adaptor.inNode(on), "Wrong split");
 
   796       check(adaptor.source(a) == adaptor.inNode(on), "Wrong split");
 
   547       check(adaptor.target(a) == adaptor.outNode(on), "Wrong split");
 
   797       check(adaptor.target(a) == adaptor.outNode(on), "Wrong split");
 
   548     }
 
   798     }
 
   549   }
 
   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");
 
   550 }
 
   860 }
 
   551 
   861 
   552 void checkSubGraph() {
 
   862 void checkSubGraph() {
 
   553   checkConcept<concepts::Graph,
 
   863   // Check concepts
 
   554     SubGraph<concepts::Graph,
 
   864   checkConcept<concepts::Graph, SubGraph<concepts::Graph> >();
 
   555     concepts::Graph::NodeMap<bool>,
 
   865   checkConcept<concepts::Graph, SubGraph<ListGraph> >();
 
   556     concepts::Graph::EdgeMap<bool> > >();
 
   866   checkConcept<concepts::AlterableGraphComponent<>,
 
   557 
   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
 
   558   typedef ListGraph Graph;
 
   876   typedef ListGraph Graph;
 
   559   typedef Graph::NodeMap<bool> NodeFilter;
 
   877   typedef Graph::NodeMap<bool> NodeFilter;
 
   560   typedef Graph::EdgeMap<bool> EdgeFilter;
 
   878   typedef Graph::EdgeMap<bool> EdgeFilter;
 
   561   typedef SubGraph<Graph, NodeFilter, EdgeFilter> Adaptor;
 
   879   typedef SubGraph<Graph, NodeFilter, EdgeFilter> Adaptor;
 
   562 
   880 
   563   Graph graph;
 
   881   Graph graph;
 
   564   NodeFilter node_filter(graph);
 
   882   NodeFilter node_filter(graph);
 
   565   EdgeFilter edge_filter(graph);
 
   883   EdgeFilter edge_filter(graph);
 
   566   Adaptor adaptor(graph, node_filter, edge_filter);
 
   884   Adaptor adaptor(graph, node_filter, edge_filter);
 
   567 
   885 
       
   886   // Add nodes and edges to the original graph and the adaptor
 
   568   Graph::Node n1 = graph.addNode();
 
   887   Graph::Node n1 = graph.addNode();
 
   569   Graph::Node n2 = graph.addNode();
 
   888   Graph::Node n2 = graph.addNode();
 
   570   Graph::Node n3 = graph.addNode();
 
   889   Adaptor::Node n3 = adaptor.addNode();
 
   571   Graph::Node n4 = graph.addNode();
 
   890   Adaptor::Node n4 = adaptor.addNode();
 
       
   891 
       
   892   node_filter[n1] = node_filter[n2] = node_filter[n3] = node_filter[n4] = true;
 
   572 
   893 
   573   Graph::Edge e1 = graph.addEdge(n1, n2);
 
   894   Graph::Edge e1 = graph.addEdge(n1, n2);
 
   574   Graph::Edge e2 = graph.addEdge(n1, n3);
 
   895   Graph::Edge e2 = graph.addEdge(n1, n3);
 
   575   Graph::Edge e3 = graph.addEdge(n2, n3);
 
   896   Adaptor::Edge e3 = adaptor.addEdge(n2, n3);
 
   576   Graph::Edge e4 = graph.addEdge(n3, n4);
 
   897   Adaptor::Edge e4 = adaptor.addEdge(n3, n4);
 
   577 
   898 
   578   node_filter[n1] = node_filter[n2] = node_filter[n3] = node_filter[n4] = true;
 
       
   579   edge_filter[e1] = edge_filter[e2] = edge_filter[e3] = edge_filter[e4] = true;
 
   899   edge_filter[e1] = edge_filter[e2] = edge_filter[e3] = edge_filter[e4] = true;
 
   580 
   900 
   581   checkGraphNodeList(adaptor, 4);
 
   901   checkGraphNodeList(adaptor, 4);
 
   582   checkGraphArcList(adaptor, 8);
 
   902   checkGraphArcList(adaptor, 8);
 
   583   checkGraphEdgeList(adaptor, 4);
 
   903   checkGraphEdgeList(adaptor, 4);
 
   584   checkGraphConArcList(adaptor, 8);
 
   904   checkGraphConArcList(adaptor, 8);
 
   585   checkGraphConEdgeList(adaptor, 4);
 
   905   checkGraphConEdgeList(adaptor, 4);
 
   586 
   906 
   587   checkGraphOutArcList(adaptor, n1, 2);
 
   907   checkGraphIncEdgeArcLists(adaptor, n1, 2);
 
   588   checkGraphOutArcList(adaptor, n2, 2);
 
   908   checkGraphIncEdgeArcLists(adaptor, n2, 2);
 
   589   checkGraphOutArcList(adaptor, n3, 3);
 
   909   checkGraphIncEdgeArcLists(adaptor, n3, 3);
 
   590   checkGraphOutArcList(adaptor, n4, 1);
 
   910   checkGraphIncEdgeArcLists(adaptor, n4, 1);
 
   591 
       
   592   checkGraphInArcList(adaptor, n1, 2);
 
       
   593   checkGraphInArcList(adaptor, n2, 2);
 
       
   594   checkGraphInArcList(adaptor, n3, 3);
 
       
   595   checkGraphInArcList(adaptor, n4, 1);
 
       
   596 
       
   597   checkGraphIncEdgeList(adaptor, n1, 2);
 
       
   598   checkGraphIncEdgeList(adaptor, n2, 2);
 
       
   599   checkGraphIncEdgeList(adaptor, n3, 3);
 
       
   600   checkGraphIncEdgeList(adaptor, n4, 1);
 
       
   601 
   911 
   602   checkNodeIds(adaptor);
 
   912   checkNodeIds(adaptor);
 
   603   checkArcIds(adaptor);
 
   913   checkArcIds(adaptor);
 
   604   checkEdgeIds(adaptor);
 
   914   checkEdgeIds(adaptor);
 
   605 
   915 
   606   checkGraphNodeMap(adaptor);
 
   916   checkGraphNodeMap(adaptor);
 
   607   checkGraphArcMap(adaptor);
 
   917   checkGraphArcMap(adaptor);
 
   608   checkGraphEdgeMap(adaptor);
 
   918   checkGraphEdgeMap(adaptor);
 
   609 
   919 
   610   edge_filter[e2] = false;
 
   920   // Hide an edge
 
       
   921   adaptor.status(e2, false);
 
       
   922   adaptor.disable(e3);
 
       
   923   if (!adaptor.status(e3)) adaptor.enable(e3);
 
   611 
   924 
   612   checkGraphNodeList(adaptor, 4);
 
   925   checkGraphNodeList(adaptor, 4);
 
   613   checkGraphArcList(adaptor, 6);
 
   926   checkGraphArcList(adaptor, 6);
 
   614   checkGraphEdgeList(adaptor, 3);
 
   927   checkGraphEdgeList(adaptor, 3);
 
   615   checkGraphConArcList(adaptor, 6);
 
   928   checkGraphConArcList(adaptor, 6);
 
   616   checkGraphConEdgeList(adaptor, 3);
 
   929   checkGraphConEdgeList(adaptor, 3);
 
   617 
   930 
   618   checkGraphOutArcList(adaptor, n1, 1);
 
   931   checkGraphIncEdgeArcLists(adaptor, n1, 1);
 
   619   checkGraphOutArcList(adaptor, n2, 2);
 
   932   checkGraphIncEdgeArcLists(adaptor, n2, 2);
 
   620   checkGraphOutArcList(adaptor, n3, 2);
 
   933   checkGraphIncEdgeArcLists(adaptor, n3, 2);
 
   621   checkGraphOutArcList(adaptor, n4, 1);
 
   934   checkGraphIncEdgeArcLists(adaptor, n4, 1);
 
   622 
       
   623   checkGraphInArcList(adaptor, n1, 1);
 
       
   624   checkGraphInArcList(adaptor, n2, 2);
 
       
   625   checkGraphInArcList(adaptor, n3, 2);
 
       
   626   checkGraphInArcList(adaptor, n4, 1);
 
       
   627 
       
   628   checkGraphIncEdgeList(adaptor, n1, 1);
 
       
   629   checkGraphIncEdgeList(adaptor, n2, 2);
 
       
   630   checkGraphIncEdgeList(adaptor, n3, 2);
 
       
   631   checkGraphIncEdgeList(adaptor, n4, 1);
 
       
   632 
   935 
   633   checkNodeIds(adaptor);
 
   936   checkNodeIds(adaptor);
 
   634   checkArcIds(adaptor);
 
   937   checkArcIds(adaptor);
 
   635   checkEdgeIds(adaptor);
 
   938   checkEdgeIds(adaptor);
 
   636 
   939 
   637   checkGraphNodeMap(adaptor);
 
   940   checkGraphNodeMap(adaptor);
 
   638   checkGraphArcMap(adaptor);
 
   941   checkGraphArcMap(adaptor);
 
   639   checkGraphEdgeMap(adaptor);
 
   942   checkGraphEdgeMap(adaptor);
 
   640 
   943 
   641   node_filter[n1] = false;
 
   944   // Hide a node
 
       
   945   adaptor.status(n1, false);
 
       
   946   adaptor.disable(n3);
 
       
   947   if (!adaptor.status(n3)) adaptor.enable(n3);
 
   642 
   948 
   643   checkGraphNodeList(adaptor, 3);
 
   949   checkGraphNodeList(adaptor, 3);
 
   644   checkGraphArcList(adaptor, 4);
 
   950   checkGraphArcList(adaptor, 4);
 
   645   checkGraphEdgeList(adaptor, 2);
 
   951   checkGraphEdgeList(adaptor, 2);
 
   646   checkGraphConArcList(adaptor, 4);
 
   952   checkGraphConArcList(adaptor, 4);
 
   647   checkGraphConEdgeList(adaptor, 2);
 
   953   checkGraphConEdgeList(adaptor, 2);
 
   648 
   954 
   649   checkGraphOutArcList(adaptor, n2, 1);
 
   955   checkGraphIncEdgeArcLists(adaptor, n2, 1);
 
   650   checkGraphOutArcList(adaptor, n3, 2);
 
   956   checkGraphIncEdgeArcLists(adaptor, n3, 2);
 
   651   checkGraphOutArcList(adaptor, n4, 1);
 
   957   checkGraphIncEdgeArcLists(adaptor, n4, 1);
 
   652 
       
   653   checkGraphInArcList(adaptor, n2, 1);
 
       
   654   checkGraphInArcList(adaptor, n3, 2);
 
       
   655   checkGraphInArcList(adaptor, n4, 1);
 
       
   656 
       
   657   checkGraphIncEdgeList(adaptor, n2, 1);
 
       
   658   checkGraphIncEdgeList(adaptor, n3, 2);
 
       
   659   checkGraphIncEdgeList(adaptor, n4, 1);
 
       
   660 
   958 
   661   checkNodeIds(adaptor);
 
   959   checkNodeIds(adaptor);
 
   662   checkArcIds(adaptor);
 
   960   checkArcIds(adaptor);
 
   663   checkEdgeIds(adaptor);
 
   961   checkEdgeIds(adaptor);
 
   664 
   962 
   665   checkGraphNodeMap(adaptor);
 
   963   checkGraphNodeMap(adaptor);
 
   666   checkGraphArcMap(adaptor);
 
   964   checkGraphArcMap(adaptor);
 
   667   checkGraphEdgeMap(adaptor);
 
   965   checkGraphEdgeMap(adaptor);
 
   668 
   966 
       
   967   // Hide all nodes and edges
 
   669   node_filter[n1] = node_filter[n2] = node_filter[n3] = node_filter[n4] = false;
 
   968   node_filter[n1] = node_filter[n2] = node_filter[n3] = node_filter[n4] = false;
 
   670   edge_filter[e1] = edge_filter[e2] = edge_filter[e3] = edge_filter[e4] = false;
 
   969   edge_filter[e1] = edge_filter[e2] = edge_filter[e3] = edge_filter[e4] = false;
 
   671 
   970 
   672   checkGraphNodeList(adaptor, 0);
 
   971   checkGraphNodeList(adaptor, 0);
 
   673   checkGraphArcList(adaptor, 0);
 
   972   checkGraphArcList(adaptor, 0);
 
   680   checkEdgeIds(adaptor);
 
   979   checkEdgeIds(adaptor);
 
   681 
   980 
   682   checkGraphNodeMap(adaptor);
 
   981   checkGraphNodeMap(adaptor);
 
   683   checkGraphArcMap(adaptor);
 
   982   checkGraphArcMap(adaptor);
 
   684   checkGraphEdgeMap(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;
 
   685 }
 
   994 }
 
   686 
   995 
   687 void checkFilterNodes2() {
 
   996 void checkFilterNodes2() {
 
   688   checkConcept<concepts::Graph,
 
   997   // Check concepts
 
   689     FilterNodes<concepts::Graph,
 
   998   checkConcept<concepts::Graph, FilterNodes<concepts::Graph> >();
 
   690       concepts::Graph::NodeMap<bool> > >();
 
   999   checkConcept<concepts::Graph, FilterNodes<ListGraph> >();
 
   691 
  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
 
   692   typedef ListGraph Graph;
 
  1010   typedef ListGraph Graph;
 
   693   typedef Graph::NodeMap<bool> NodeFilter;
 
  1011   typedef Graph::NodeMap<bool> NodeFilter;
 
   694   typedef FilterNodes<Graph, NodeFilter> Adaptor;
 
  1012   typedef FilterNodes<Graph, NodeFilter> Adaptor;
 
   695 
  1013 
       
  1014   // Add nodes and edges to the original graph and the adaptor
 
   696   Graph graph;
 
  1015   Graph graph;
 
   697   NodeFilter node_filter(graph);
 
  1016   NodeFilter node_filter(graph);
 
   698   Adaptor adaptor(graph, node_filter);
 
  1017   Adaptor adaptor(graph, node_filter);
 
   699 
  1018 
   700   Graph::Node n1 = graph.addNode();
 
  1019   Graph::Node n1 = graph.addNode();
 
   701   Graph::Node n2 = graph.addNode();
 
  1020   Graph::Node n2 = graph.addNode();
 
   702   Graph::Node n3 = graph.addNode();
 
  1021   Adaptor::Node n3 = adaptor.addNode();
 
   703   Graph::Node n4 = graph.addNode();
 
  1022   Adaptor::Node n4 = adaptor.addNode();
 
       
  1023 
       
  1024   node_filter[n1] = node_filter[n2] = node_filter[n3] = node_filter[n4] = true;
 
   704 
  1025 
   705   Graph::Edge e1 = graph.addEdge(n1, n2);
 
  1026   Graph::Edge e1 = graph.addEdge(n1, n2);
 
   706   Graph::Edge e2 = graph.addEdge(n1, n3);
 
  1027   Graph::Edge e2 = graph.addEdge(n1, n3);
 
   707   Graph::Edge e3 = graph.addEdge(n2, n3);
 
  1028   Adaptor::Edge e3 = adaptor.addEdge(n2, n3);
 
   708   Graph::Edge e4 = graph.addEdge(n3, n4);
 
  1029   Adaptor::Edge e4 = adaptor.addEdge(n3, n4);
 
   709 
       
   710   node_filter[n1] = node_filter[n2] = node_filter[n3] = node_filter[n4] = true;
 
       
   711 
  1030 
   712   checkGraphNodeList(adaptor, 4);
 
  1031   checkGraphNodeList(adaptor, 4);
 
   713   checkGraphArcList(adaptor, 8);
 
  1032   checkGraphArcList(adaptor, 8);
 
   714   checkGraphEdgeList(adaptor, 4);
 
  1033   checkGraphEdgeList(adaptor, 4);
 
   715   checkGraphConArcList(adaptor, 8);
 
  1034   checkGraphConArcList(adaptor, 8);
 
   716   checkGraphConEdgeList(adaptor, 4);
 
  1035   checkGraphConEdgeList(adaptor, 4);
 
   717 
  1036 
   718   checkGraphOutArcList(adaptor, n1, 2);
 
  1037   checkGraphIncEdgeArcLists(adaptor, n1, 2);
 
   719   checkGraphOutArcList(adaptor, n2, 2);
 
  1038   checkGraphIncEdgeArcLists(adaptor, n2, 2);
 
   720   checkGraphOutArcList(adaptor, n3, 3);
 
  1039   checkGraphIncEdgeArcLists(adaptor, n3, 3);
 
   721   checkGraphOutArcList(adaptor, n4, 1);
 
  1040   checkGraphIncEdgeArcLists(adaptor, n4, 1);
 
   722 
       
   723   checkGraphInArcList(adaptor, n1, 2);
 
       
   724   checkGraphInArcList(adaptor, n2, 2);
 
       
   725   checkGraphInArcList(adaptor, n3, 3);
 
       
   726   checkGraphInArcList(adaptor, n4, 1);
 
       
   727 
       
   728   checkGraphIncEdgeList(adaptor, n1, 2);
 
       
   729   checkGraphIncEdgeList(adaptor, n2, 2);
 
       
   730   checkGraphIncEdgeList(adaptor, n3, 3);
 
       
   731   checkGraphIncEdgeList(adaptor, n4, 1);
 
       
   732 
  1041 
   733   checkNodeIds(adaptor);
 
  1042   checkNodeIds(adaptor);
 
   734   checkArcIds(adaptor);
 
  1043   checkArcIds(adaptor);
 
   735   checkEdgeIds(adaptor);
 
  1044   checkEdgeIds(adaptor);
 
   736 
  1045 
   737   checkGraphNodeMap(adaptor);
 
  1046   checkGraphNodeMap(adaptor);
 
   738   checkGraphArcMap(adaptor);
 
  1047   checkGraphArcMap(adaptor);
 
   739   checkGraphEdgeMap(adaptor);
 
  1048   checkGraphEdgeMap(adaptor);
 
   740 
  1049 
   741   node_filter[n1] = false;
 
  1050   // Hide a node
 
       
  1051   adaptor.status(n1, false);
 
       
  1052   adaptor.disable(n3);
 
       
  1053   if (!adaptor.status(n3)) adaptor.enable(n3);
 
   742 
  1054 
   743   checkGraphNodeList(adaptor, 3);
 
  1055   checkGraphNodeList(adaptor, 3);
 
   744   checkGraphArcList(adaptor, 4);
 
  1056   checkGraphArcList(adaptor, 4);
 
   745   checkGraphEdgeList(adaptor, 2);
 
  1057   checkGraphEdgeList(adaptor, 2);
 
   746   checkGraphConArcList(adaptor, 4);
 
  1058   checkGraphConArcList(adaptor, 4);
 
   747   checkGraphConEdgeList(adaptor, 2);
 
  1059   checkGraphConEdgeList(adaptor, 2);
 
   748 
  1060 
   749   checkGraphOutArcList(adaptor, n2, 1);
 
  1061   checkGraphIncEdgeArcLists(adaptor, n2, 1);
 
   750   checkGraphOutArcList(adaptor, n3, 2);
 
  1062   checkGraphIncEdgeArcLists(adaptor, n3, 2);
 
   751   checkGraphOutArcList(adaptor, n4, 1);
 
  1063   checkGraphIncEdgeArcLists(adaptor, n4, 1);
 
   752 
       
   753   checkGraphInArcList(adaptor, n2, 1);
 
       
   754   checkGraphInArcList(adaptor, n3, 2);
 
       
   755   checkGraphInArcList(adaptor, n4, 1);
 
       
   756 
       
   757   checkGraphIncEdgeList(adaptor, n2, 1);
 
       
   758   checkGraphIncEdgeList(adaptor, n3, 2);
 
       
   759   checkGraphIncEdgeList(adaptor, n4, 1);
 
       
   760 
  1064 
   761   checkNodeIds(adaptor);
 
  1065   checkNodeIds(adaptor);
 
   762   checkArcIds(adaptor);
 
  1066   checkArcIds(adaptor);
 
   763   checkEdgeIds(adaptor);
 
  1067   checkEdgeIds(adaptor);
 
   764 
  1068 
   765   checkGraphNodeMap(adaptor);
 
  1069   checkGraphNodeMap(adaptor);
 
   766   checkGraphArcMap(adaptor);
 
  1070   checkGraphArcMap(adaptor);
 
   767   checkGraphEdgeMap(adaptor);
 
  1071   checkGraphEdgeMap(adaptor);
 
   768 
  1072 
       
  1073   // Hide all nodes
 
   769   node_filter[n1] = node_filter[n2] = node_filter[n3] = node_filter[n4] = false;
 
  1074   node_filter[n1] = node_filter[n2] = node_filter[n3] = node_filter[n4] = false;
 
   770 
  1075 
   771   checkGraphNodeList(adaptor, 0);
 
  1076   checkGraphNodeList(adaptor, 0);
 
   772   checkGraphArcList(adaptor, 0);
 
  1077   checkGraphArcList(adaptor, 0);
 
   773   checkGraphEdgeList(adaptor, 0);
 
  1078   checkGraphEdgeList(adaptor, 0);
 
   779   checkEdgeIds(adaptor);
 
  1084   checkEdgeIds(adaptor);
 
   780 
  1085 
   781   checkGraphNodeMap(adaptor);
 
  1086   checkGraphNodeMap(adaptor);
 
   782   checkGraphArcMap(adaptor);
 
  1087   checkGraphArcMap(adaptor);
 
   783   checkGraphEdgeMap(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;
 
   784 }
 
  1099 }
 
   785 
  1100 
   786 void checkFilterEdges() {
 
  1101 void checkFilterEdges() {
 
   787   checkConcept<concepts::Graph,
 
  1102   // Check concepts
 
   788     FilterEdges<concepts::Graph,
 
  1103   checkConcept<concepts::Graph, FilterEdges<concepts::Graph> >();
 
   789     concepts::Graph::EdgeMap<bool> > >();
 
  1104   checkConcept<concepts::Graph, FilterEdges<ListGraph> >();
 
   790 
  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
 
   791   typedef ListGraph Graph;
 
  1115   typedef ListGraph Graph;
 
   792   typedef Graph::EdgeMap<bool> EdgeFilter;
 
  1116   typedef Graph::EdgeMap<bool> EdgeFilter;
 
   793   typedef FilterEdges<Graph, EdgeFilter> Adaptor;
 
  1117   typedef FilterEdges<Graph, EdgeFilter> Adaptor;
 
   794 
  1118 
   795   Graph graph;
 
  1119   Graph graph;
 
   796   EdgeFilter edge_filter(graph);
 
  1120   EdgeFilter edge_filter(graph);
 
   797   Adaptor adaptor(graph, edge_filter);
 
  1121   Adaptor adaptor(graph, edge_filter);
 
   798 
  1122 
       
  1123   // Add nodes and edges to the original graph and the adaptor
 
   799   Graph::Node n1 = graph.addNode();
 
  1124   Graph::Node n1 = graph.addNode();
 
   800   Graph::Node n2 = graph.addNode();
 
  1125   Graph::Node n2 = graph.addNode();
 
   801   Graph::Node n3 = graph.addNode();
 
  1126   Adaptor::Node n3 = adaptor.addNode();
 
   802   Graph::Node n4 = graph.addNode();
 
  1127   Adaptor::Node n4 = adaptor.addNode();
 
   803 
  1128 
   804   Graph::Edge e1 = graph.addEdge(n1, n2);
 
  1129   Graph::Edge e1 = graph.addEdge(n1, n2);
 
   805   Graph::Edge e2 = graph.addEdge(n1, n3);
 
  1130   Graph::Edge e2 = graph.addEdge(n1, n3);
 
   806   Graph::Edge e3 = graph.addEdge(n2, n3);
 
  1131   Adaptor::Edge e3 = adaptor.addEdge(n2, n3);
 
   807   Graph::Edge e4 = graph.addEdge(n3, n4);
 
  1132   Adaptor::Edge e4 = adaptor.addEdge(n3, n4);
 
   808 
  1133 
   809   edge_filter[e1] = edge_filter[e2] = edge_filter[e3] = edge_filter[e4] = true;
 
  1134   edge_filter[e1] = edge_filter[e2] = edge_filter[e3] = edge_filter[e4] = true;
 
   810 
  1135 
   811   checkGraphNodeList(adaptor, 4);
 
  1136   checkGraphNodeList(adaptor, 4);
 
   812   checkGraphArcList(adaptor, 8);
 
  1137   checkGraphArcList(adaptor, 8);
 
   813   checkGraphEdgeList(adaptor, 4);
 
  1138   checkGraphEdgeList(adaptor, 4);
 
   814   checkGraphConArcList(adaptor, 8);
 
  1139   checkGraphConArcList(adaptor, 8);
 
   815   checkGraphConEdgeList(adaptor, 4);
 
  1140   checkGraphConEdgeList(adaptor, 4);
 
   816 
  1141 
   817   checkGraphOutArcList(adaptor, n1, 2);
 
  1142   checkGraphIncEdgeArcLists(adaptor, n1, 2);
 
   818   checkGraphOutArcList(adaptor, n2, 2);
 
  1143   checkGraphIncEdgeArcLists(adaptor, n2, 2);
 
   819   checkGraphOutArcList(adaptor, n3, 3);
 
  1144   checkGraphIncEdgeArcLists(adaptor, n3, 3);
 
   820   checkGraphOutArcList(adaptor, n4, 1);
 
  1145   checkGraphIncEdgeArcLists(adaptor, n4, 1);
 
   821 
       
   822   checkGraphInArcList(adaptor, n1, 2);
 
       
   823   checkGraphInArcList(adaptor, n2, 2);
 
       
   824   checkGraphInArcList(adaptor, n3, 3);
 
       
   825   checkGraphInArcList(adaptor, n4, 1);
 
       
   826 
       
   827   checkGraphIncEdgeList(adaptor, n1, 2);
 
       
   828   checkGraphIncEdgeList(adaptor, n2, 2);
 
       
   829   checkGraphIncEdgeList(adaptor, n3, 3);
 
       
   830   checkGraphIncEdgeList(adaptor, n4, 1);
 
       
   831 
  1146 
   832   checkNodeIds(adaptor);
 
  1147   checkNodeIds(adaptor);
 
   833   checkArcIds(adaptor);
 
  1148   checkArcIds(adaptor);
 
   834   checkEdgeIds(adaptor);
 
  1149   checkEdgeIds(adaptor);
 
   835 
  1150 
   836   checkGraphNodeMap(adaptor);
 
  1151   checkGraphNodeMap(adaptor);
 
   837   checkGraphArcMap(adaptor);
 
  1152   checkGraphArcMap(adaptor);
 
   838   checkGraphEdgeMap(adaptor);
 
  1153   checkGraphEdgeMap(adaptor);
 
   839 
  1154 
   840   edge_filter[e2] = false;
 
  1155   // Hide an edge
 
       
  1156   adaptor.status(e2, false);
 
       
  1157   adaptor.disable(e3);
 
       
  1158   if (!adaptor.status(e3)) adaptor.enable(e3);
 
   841 
  1159 
   842   checkGraphNodeList(adaptor, 4);
 
  1160   checkGraphNodeList(adaptor, 4);
 
   843   checkGraphArcList(adaptor, 6);
 
  1161   checkGraphArcList(adaptor, 6);
 
   844   checkGraphEdgeList(adaptor, 3);
 
  1162   checkGraphEdgeList(adaptor, 3);
 
   845   checkGraphConArcList(adaptor, 6);
 
  1163   checkGraphConArcList(adaptor, 6);
 
   846   checkGraphConEdgeList(adaptor, 3);
 
  1164   checkGraphConEdgeList(adaptor, 3);
 
   847 
  1165 
   848   checkGraphOutArcList(adaptor, n1, 1);
 
  1166   checkGraphIncEdgeArcLists(adaptor, n1, 1);
 
   849   checkGraphOutArcList(adaptor, n2, 2);
 
  1167   checkGraphIncEdgeArcLists(adaptor, n2, 2);
 
   850   checkGraphOutArcList(adaptor, n3, 2);
 
  1168   checkGraphIncEdgeArcLists(adaptor, n3, 2);
 
   851   checkGraphOutArcList(adaptor, n4, 1);
 
  1169   checkGraphIncEdgeArcLists(adaptor, n4, 1);
 
   852 
       
   853   checkGraphInArcList(adaptor, n1, 1);
 
       
   854   checkGraphInArcList(adaptor, n2, 2);
 
       
   855   checkGraphInArcList(adaptor, n3, 2);
 
       
   856   checkGraphInArcList(adaptor, n4, 1);
 
       
   857 
       
   858   checkGraphIncEdgeList(adaptor, n1, 1);
 
       
   859   checkGraphIncEdgeList(adaptor, n2, 2);
 
       
   860   checkGraphIncEdgeList(adaptor, n3, 2);
 
       
   861   checkGraphIncEdgeList(adaptor, n4, 1);
 
       
   862 
  1170 
   863   checkNodeIds(adaptor);
 
  1171   checkNodeIds(adaptor);
 
   864   checkArcIds(adaptor);
 
  1172   checkArcIds(adaptor);
 
   865   checkEdgeIds(adaptor);
 
  1173   checkEdgeIds(adaptor);
 
   866 
  1174 
   867   checkGraphNodeMap(adaptor);
 
  1175   checkGraphNodeMap(adaptor);
 
   868   checkGraphArcMap(adaptor);
 
  1176   checkGraphArcMap(adaptor);
 
   869   checkGraphEdgeMap(adaptor);
 
  1177   checkGraphEdgeMap(adaptor);
 
   870 
  1178 
       
  1179   // Hide all edges
 
   871   edge_filter[e1] = edge_filter[e2] = edge_filter[e3] = edge_filter[e4] = false;
 
  1180   edge_filter[e1] = edge_filter[e2] = edge_filter[e3] = edge_filter[e4] = false;
 
   872 
  1181 
   873   checkGraphNodeList(adaptor, 4);
 
  1182   checkGraphNodeList(adaptor, 4);
 
   874   checkGraphArcList(adaptor, 0);
 
  1183   checkGraphArcList(adaptor, 0);
 
   875   checkGraphEdgeList(adaptor, 0);
 
  1184   checkGraphEdgeList(adaptor, 0);
 
   881   checkEdgeIds(adaptor);
 
  1190   checkEdgeIds(adaptor);
 
   882 
  1191 
   883   checkGraphNodeMap(adaptor);
 
  1192   checkGraphNodeMap(adaptor);
 
   884   checkGraphArcMap(adaptor);
 
  1193   checkGraphArcMap(adaptor);
 
   885   checkGraphEdgeMap(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;
 
   886 }
 
  1205 }
 
   887 
  1206 
   888 void checkOrienter() {
 
  1207 void checkOrienter() {
 
   889   checkConcept<concepts::Digraph,
 
  1208   // Check concepts
 
   890     Orienter<concepts::Graph, concepts::Graph::EdgeMap<bool> > >();
 
  1209   checkConcept<concepts::Digraph, Orienter<concepts::Graph> >();
 
   891 
  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
 
   892   typedef ListGraph Graph;
 
  1221   typedef ListGraph Graph;
 
   893   typedef ListGraph::EdgeMap<bool> DirMap;
 
  1222   typedef ListGraph::EdgeMap<bool> DirMap;
 
   894   typedef Orienter<Graph> Adaptor;
 
  1223   typedef Orienter<Graph> Adaptor;
 
   895 
  1224 
   896   Graph graph;
 
  1225   Graph graph;
 
   897   DirMap dir(graph, true);
 
  1226   DirMap dir(graph);
 
   898   Adaptor adaptor(graph, dir);
 
  1227   Adaptor adaptor(graph, dir);
 
   899 
  1228 
       
  1229   // Add nodes and edges to the original graph and the adaptor
 
   900   Graph::Node n1 = graph.addNode();
 
  1230   Graph::Node n1 = graph.addNode();
 
   901   Graph::Node n2 = graph.addNode();
 
  1231   Graph::Node n2 = graph.addNode();
 
   902   Graph::Node n3 = graph.addNode();
 
  1232   Adaptor::Node n3 = adaptor.addNode();
 
   903 
  1233 
   904   Graph::Edge e1 = graph.addEdge(n1, n2);
 
  1234   Graph::Edge e1 = graph.addEdge(n1, n2);
 
   905   Graph::Edge e2 = graph.addEdge(n1, n3);
 
  1235   Graph::Edge e2 = graph.addEdge(n1, n3);
 
   906   Graph::Edge e3 = graph.addEdge(n2, n3);
 
  1236   Adaptor::Arc e3 = adaptor.addArc(n2, n3);
 
   907 
  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
 
   908   checkGraphNodeList(adaptor, 3);
 
  1260   checkGraphNodeList(adaptor, 3);
 
   909   checkGraphArcList(adaptor, 3);
 
  1261   checkGraphArcList(adaptor, 3);
 
   910   checkGraphConArcList(adaptor, 3);
 
  1262   checkGraphConArcList(adaptor, 3);
 
   911 
  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
 
   912   {
 
  1279   {
 
   913     dir[e1] = true;
 
  1280     dir[e1] = true;
 
   914     Adaptor::Node u = adaptor.source(e1);
 
  1281     Adaptor::Node u = adaptor.source(e1);
 
   915     Adaptor::Node v = adaptor.target(e1);
 
  1282     Adaptor::Node v = adaptor.target(e1);
 
   916 
  1283 
   946 
  1313 
   947     check ((u == n2 && v == n3) || (u == n3 && v == n2), "Wrong dir");
 
  1314     check ((u == n2 && v == n3) || (u == n3 && v == n2), "Wrong dir");
 
   948     dir[e3] = n2 == u;
 
  1315     dir[e3] = n2 == u;
 
   949   }
 
  1316   }
 
   950 
  1317 
       
  1318   // Check the adaptor again
 
       
  1319   checkGraphNodeList(adaptor, 3);
 
       
  1320   checkGraphArcList(adaptor, 3);
 
       
  1321   checkGraphConArcList(adaptor, 3);
 
       
  1322 
   951   checkGraphOutArcList(adaptor, n1, 1);
 
  1323   checkGraphOutArcList(adaptor, n1, 1);
 
   952   checkGraphOutArcList(adaptor, n2, 1);
 
  1324   checkGraphOutArcList(adaptor, n2, 1);
 
   953   checkGraphOutArcList(adaptor, n3, 1);
 
  1325   checkGraphOutArcList(adaptor, n3, 1);
 
   954 
  1326 
   955   checkGraphInArcList(adaptor, n1, 1);
 
  1327   checkGraphInArcList(adaptor, n1, 1);
 
   960   checkArcIds(adaptor);
 
  1332   checkArcIds(adaptor);
 
   961 
  1333 
   962   checkGraphNodeMap(adaptor);
 
  1334   checkGraphNodeMap(adaptor);
 
   963   checkGraphArcMap(adaptor);
 
  1335   checkGraphArcMap(adaptor);
 
   964 
  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;
 
   965 }
 
  1363 }
 
   966 
  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 }
 
   967 
  1465 
   968 int main(int, const char **) {
 
  1466 int main(int, const char **) {
 
   969 
  1467   // Check the digraph adaptors (using ListDigraph)
 
   970   checkReverseDigraph();
 
  1468   checkReverseDigraph();
 
   971   checkSubDigraph();
 
  1469   checkSubDigraph();
 
   972   checkFilterNodes1();
 
  1470   checkFilterNodes1();
 
   973   checkFilterArcs();
 
  1471   checkFilterArcs();
 
   974   checkUndirector();
 
  1472   checkUndirector();
 
   975   checkResidual();
 
  1473   checkResidual();
 
   976   checkSplitNodes();
 
  1474   checkSplitNodes();
 
   977 
  1475 
       
  1476   // Check the graph adaptors (using ListGraph)
 
   978   checkSubGraph();
 
  1477   checkSubGraph();
 
   979   checkFilterNodes2();
 
  1478   checkFilterNodes2();
 
   980   checkFilterEdges();
 
  1479   checkFilterEdges();
 
   981   checkOrienter();
 
  1480   checkOrienter();
 
   982 
  1481 
       
  1482   // Combine adaptors (using GridGraph)
 
       
  1483   checkCombiningAdaptors();
 
       
  1484 
   983   return 0;
 
  1485   return 0;
 
   984 }
 
  1486 }
lemon-1.2