test/graph_adaptor_test.cc
author Alpar Juttner <alpar@cs.elte.hu>
Mon, 08 Dec 2008 21:50:34 +0000
changeset 428 919878a41a60
parent 415 4b6112235fad
child 440 88ed40ad0d4f
permissions -rw-r--r--
Merge
     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-2008
     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<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>
    31 #include <lemon/bfs.h>
    32 #include <lemon/path.h>
    33 
    34 #include"test/test_tools.h"
    35 #include"test/graph_test.h"
    36 
    37 using namespace lemon;
    38 
    39 void checkReverseDigraph() {
    40   checkConcept<concepts::Digraph, ReverseDigraph<concepts::Digraph> >();
    41 
    42   typedef ListDigraph Digraph;
    43   typedef ReverseDigraph<Digraph> Adaptor;
    44 
    45   Digraph digraph;
    46   Adaptor adaptor(digraph);
    47 
    48   Digraph::Node n1 = digraph.addNode();
    49   Digraph::Node n2 = digraph.addNode();
    50   Digraph::Node n3 = digraph.addNode();
    51 
    52   Digraph::Arc a1 = digraph.addArc(n1, n2);
    53   Digraph::Arc a2 = digraph.addArc(n1, n3);
    54   Digraph::Arc a3 = digraph.addArc(n2, n3);
    55 
    56   checkGraphNodeList(adaptor, 3);
    57   checkGraphArcList(adaptor, 3);
    58   checkGraphConArcList(adaptor, 3);
    59 
    60   checkGraphOutArcList(adaptor, n1, 0);
    61   checkGraphOutArcList(adaptor, n2, 1);
    62   checkGraphOutArcList(adaptor, n3, 2);
    63 
    64   checkGraphInArcList(adaptor, n1, 2);
    65   checkGraphInArcList(adaptor, n2, 1);
    66   checkGraphInArcList(adaptor, n3, 0);
    67 
    68   checkNodeIds(adaptor);
    69   checkArcIds(adaptor);
    70 
    71   checkGraphNodeMap(adaptor);
    72   checkGraphArcMap(adaptor);
    73 
    74   for (Adaptor::ArcIt a(adaptor); a != INVALID; ++a) {
    75     check(adaptor.source(a) == digraph.target(a), "Wrong reverse");
    76     check(adaptor.target(a) == digraph.source(a), "Wrong reverse");
    77   }
    78 }
    79 
    80 void checkSubDigraph() {
    81   checkConcept<concepts::Digraph,
    82     SubDigraph<concepts::Digraph,
    83     concepts::Digraph::NodeMap<bool>,
    84     concepts::Digraph::ArcMap<bool> > >();
    85 
    86   typedef ListDigraph Digraph;
    87   typedef Digraph::NodeMap<bool> NodeFilter;
    88   typedef Digraph::ArcMap<bool> ArcFilter;
    89   typedef SubDigraph<Digraph, NodeFilter, ArcFilter> Adaptor;
    90 
    91   Digraph digraph;
    92   NodeFilter node_filter(digraph);
    93   ArcFilter arc_filter(digraph);
    94   Adaptor adaptor(digraph, node_filter, arc_filter);
    95 
    96   Digraph::Node n1 = digraph.addNode();
    97   Digraph::Node n2 = digraph.addNode();
    98   Digraph::Node n3 = digraph.addNode();
    99 
   100   Digraph::Arc a1 = digraph.addArc(n1, n2);
   101   Digraph::Arc a2 = digraph.addArc(n1, n3);
   102   Digraph::Arc a3 = digraph.addArc(n2, n3);
   103 
   104   node_filter[n1] = node_filter[n2] = node_filter[n3] = true;
   105   arc_filter[a1] = arc_filter[a2] = arc_filter[a3] = true;
   106   
   107   checkGraphNodeList(adaptor, 3);
   108   checkGraphArcList(adaptor, 3);
   109   checkGraphConArcList(adaptor, 3);
   110 
   111   checkGraphOutArcList(adaptor, n1, 2);
   112   checkGraphOutArcList(adaptor, n2, 1);
   113   checkGraphOutArcList(adaptor, n3, 0);
   114 
   115   checkGraphInArcList(adaptor, n1, 0);
   116   checkGraphInArcList(adaptor, n2, 1);
   117   checkGraphInArcList(adaptor, n3, 2);
   118 
   119   checkNodeIds(adaptor);
   120   checkArcIds(adaptor);
   121 
   122   checkGraphNodeMap(adaptor);
   123   checkGraphArcMap(adaptor);
   124 
   125   arc_filter[a2] = false;
   126 
   127   checkGraphNodeList(adaptor, 3);
   128   checkGraphArcList(adaptor, 2);
   129   checkGraphConArcList(adaptor, 2);
   130 
   131   checkGraphOutArcList(adaptor, n1, 1);
   132   checkGraphOutArcList(adaptor, n2, 1);
   133   checkGraphOutArcList(adaptor, n3, 0);
   134 
   135   checkGraphInArcList(adaptor, n1, 0);
   136   checkGraphInArcList(adaptor, n2, 1);
   137   checkGraphInArcList(adaptor, n3, 1);
   138 
   139   checkNodeIds(adaptor);
   140   checkArcIds(adaptor);
   141 
   142   checkGraphNodeMap(adaptor);
   143   checkGraphArcMap(adaptor);
   144 
   145   node_filter[n1] = false;
   146 
   147   checkGraphNodeList(adaptor, 2);
   148   checkGraphArcList(adaptor, 1);
   149   checkGraphConArcList(adaptor, 1);
   150 
   151   checkGraphOutArcList(adaptor, n2, 1);
   152   checkGraphOutArcList(adaptor, n3, 0);
   153 
   154   checkGraphInArcList(adaptor, n2, 0);
   155   checkGraphInArcList(adaptor, n3, 1);
   156 
   157   checkNodeIds(adaptor);
   158   checkArcIds(adaptor);
   159 
   160   checkGraphNodeMap(adaptor);
   161   checkGraphArcMap(adaptor);
   162 
   163   node_filter[n1] = node_filter[n2] = node_filter[n3] = false;
   164   arc_filter[a1] = arc_filter[a2] = arc_filter[a3] = false;
   165 
   166   checkGraphNodeList(adaptor, 0);
   167   checkGraphArcList(adaptor, 0);
   168   checkGraphConArcList(adaptor, 0);
   169 
   170   checkNodeIds(adaptor);
   171   checkArcIds(adaptor);
   172 
   173   checkGraphNodeMap(adaptor);
   174   checkGraphArcMap(adaptor);
   175 }
   176 
   177 void checkFilterNodes1() {
   178   checkConcept<concepts::Digraph,
   179     FilterNodes<concepts::Digraph,
   180       concepts::Digraph::NodeMap<bool> > >();
   181 
   182   typedef ListDigraph Digraph;
   183   typedef Digraph::NodeMap<bool> NodeFilter;
   184   typedef FilterNodes<Digraph, NodeFilter> Adaptor;
   185 
   186   Digraph digraph;
   187   NodeFilter node_filter(digraph);
   188   Adaptor adaptor(digraph, node_filter);
   189 
   190   Digraph::Node n1 = digraph.addNode();
   191   Digraph::Node n2 = digraph.addNode();
   192   Digraph::Node n3 = digraph.addNode();
   193 
   194   Digraph::Arc a1 = digraph.addArc(n1, n2);
   195   Digraph::Arc a2 = digraph.addArc(n1, n3);
   196   Digraph::Arc a3 = digraph.addArc(n2, n3);
   197 
   198   node_filter[n1] = node_filter[n2] = node_filter[n3] = true;
   199   
   200   checkGraphNodeList(adaptor, 3);
   201   checkGraphArcList(adaptor, 3);
   202   checkGraphConArcList(adaptor, 3);
   203 
   204   checkGraphOutArcList(adaptor, n1, 2);
   205   checkGraphOutArcList(adaptor, n2, 1);
   206   checkGraphOutArcList(adaptor, n3, 0);
   207 
   208   checkGraphInArcList(adaptor, n1, 0);
   209   checkGraphInArcList(adaptor, n2, 1);
   210   checkGraphInArcList(adaptor, n3, 2);
   211 
   212   checkNodeIds(adaptor);
   213   checkArcIds(adaptor);
   214 
   215   checkGraphNodeMap(adaptor);
   216   checkGraphArcMap(adaptor);
   217 
   218   node_filter[n1] = false;
   219 
   220   checkGraphNodeList(adaptor, 2);
   221   checkGraphArcList(adaptor, 1);
   222   checkGraphConArcList(adaptor, 1);
   223 
   224   checkGraphOutArcList(adaptor, n2, 1);
   225   checkGraphOutArcList(adaptor, n3, 0);
   226 
   227   checkGraphInArcList(adaptor, n2, 0);
   228   checkGraphInArcList(adaptor, n3, 1);
   229 
   230   checkNodeIds(adaptor);
   231   checkArcIds(adaptor);
   232 
   233   checkGraphNodeMap(adaptor);
   234   checkGraphArcMap(adaptor);
   235 
   236   node_filter[n1] = node_filter[n2] = node_filter[n3] = false;
   237 
   238   checkGraphNodeList(adaptor, 0);
   239   checkGraphArcList(adaptor, 0);
   240   checkGraphConArcList(adaptor, 0);
   241 
   242   checkNodeIds(adaptor);
   243   checkArcIds(adaptor);
   244 
   245   checkGraphNodeMap(adaptor);
   246   checkGraphArcMap(adaptor);
   247 }
   248 
   249 void checkFilterArcs() {
   250   checkConcept<concepts::Digraph,
   251     FilterArcs<concepts::Digraph,
   252     concepts::Digraph::ArcMap<bool> > >();
   253 
   254   typedef ListDigraph Digraph;
   255   typedef Digraph::ArcMap<bool> ArcFilter;
   256   typedef FilterArcs<Digraph, ArcFilter> Adaptor;
   257 
   258   Digraph digraph;
   259   ArcFilter arc_filter(digraph);
   260   Adaptor adaptor(digraph, arc_filter);
   261 
   262   Digraph::Node n1 = digraph.addNode();
   263   Digraph::Node n2 = digraph.addNode();
   264   Digraph::Node n3 = digraph.addNode();
   265 
   266   Digraph::Arc a1 = digraph.addArc(n1, n2);
   267   Digraph::Arc a2 = digraph.addArc(n1, n3);
   268   Digraph::Arc a3 = digraph.addArc(n2, n3);
   269 
   270   arc_filter[a1] = arc_filter[a2] = arc_filter[a3] = true;
   271   
   272   checkGraphNodeList(adaptor, 3);
   273   checkGraphArcList(adaptor, 3);
   274   checkGraphConArcList(adaptor, 3);
   275 
   276   checkGraphOutArcList(adaptor, n1, 2);
   277   checkGraphOutArcList(adaptor, n2, 1);
   278   checkGraphOutArcList(adaptor, n3, 0);
   279 
   280   checkGraphInArcList(adaptor, n1, 0);
   281   checkGraphInArcList(adaptor, n2, 1);
   282   checkGraphInArcList(adaptor, n3, 2);
   283 
   284   checkNodeIds(adaptor);
   285   checkArcIds(adaptor);
   286 
   287   checkGraphNodeMap(adaptor);
   288   checkGraphArcMap(adaptor);
   289 
   290   arc_filter[a2] = false;
   291 
   292   checkGraphNodeList(adaptor, 3);
   293   checkGraphArcList(adaptor, 2);
   294   checkGraphConArcList(adaptor, 2);
   295 
   296   checkGraphOutArcList(adaptor, n1, 1);
   297   checkGraphOutArcList(adaptor, n2, 1);
   298   checkGraphOutArcList(adaptor, n3, 0);
   299 
   300   checkGraphInArcList(adaptor, n1, 0);
   301   checkGraphInArcList(adaptor, n2, 1);
   302   checkGraphInArcList(adaptor, n3, 1);
   303 
   304   checkNodeIds(adaptor);
   305   checkArcIds(adaptor);
   306 
   307   checkGraphNodeMap(adaptor);
   308   checkGraphArcMap(adaptor);
   309 
   310   arc_filter[a1] = arc_filter[a2] = arc_filter[a3] = false;
   311 
   312   checkGraphNodeList(adaptor, 3);
   313   checkGraphArcList(adaptor, 0);
   314   checkGraphConArcList(adaptor, 0);
   315 
   316   checkNodeIds(adaptor);
   317   checkArcIds(adaptor);
   318 
   319   checkGraphNodeMap(adaptor);
   320   checkGraphArcMap(adaptor);
   321 }
   322 
   323 void checkUndirector() {
   324   checkConcept<concepts::Graph, Undirector<concepts::Digraph> >();
   325 
   326   typedef ListDigraph Digraph;
   327   typedef Undirector<Digraph> Adaptor;
   328 
   329   Digraph digraph;
   330   Adaptor adaptor(digraph);
   331 
   332   Digraph::Node n1 = digraph.addNode();
   333   Digraph::Node n2 = digraph.addNode();
   334   Digraph::Node n3 = digraph.addNode();
   335 
   336   Digraph::Arc a1 = digraph.addArc(n1, n2);
   337   Digraph::Arc a2 = digraph.addArc(n1, n3);
   338   Digraph::Arc a3 = digraph.addArc(n2, n3);
   339 
   340   checkGraphNodeList(adaptor, 3);
   341   checkGraphArcList(adaptor, 6);
   342   checkGraphEdgeList(adaptor, 3);
   343   checkGraphConArcList(adaptor, 6);
   344   checkGraphConEdgeList(adaptor, 3);
   345 
   346   checkGraphOutArcList(adaptor, n1, 2);
   347   checkGraphOutArcList(adaptor, n2, 2);
   348   checkGraphOutArcList(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 
   358   checkNodeIds(adaptor);
   359   checkArcIds(adaptor);
   360   checkEdgeIds(adaptor);
   361 
   362   checkGraphNodeMap(adaptor);
   363   checkGraphArcMap(adaptor);
   364   checkGraphEdgeMap(adaptor);
   365 
   366   for (Adaptor::EdgeIt e(adaptor); e != INVALID; ++e) {
   367     check(adaptor.u(e) == digraph.source(e), "Wrong undir");
   368     check(adaptor.v(e) == digraph.target(e), "Wrong undir");
   369   }
   370 
   371 }
   372 
   373 void checkResidual() {
   374   checkConcept<concepts::Digraph,
   375     Residual<concepts::Digraph,
   376     concepts::Digraph::ArcMap<int>,
   377     concepts::Digraph::ArcMap<int> > >();
   378 
   379   typedef ListDigraph Digraph;
   380   typedef Digraph::ArcMap<int> IntArcMap;
   381   typedef Residual<Digraph, IntArcMap> Adaptor;
   382 
   383   Digraph digraph;
   384   IntArcMap capacity(digraph), flow(digraph);
   385   Adaptor adaptor(digraph, capacity, flow);
   386 
   387   Digraph::Node n1 = digraph.addNode();
   388   Digraph::Node n2 = digraph.addNode();
   389   Digraph::Node n3 = digraph.addNode();
   390   Digraph::Node n4 = digraph.addNode();
   391 
   392   Digraph::Arc a1 = digraph.addArc(n1, n2);
   393   Digraph::Arc a2 = digraph.addArc(n1, n3);
   394   Digraph::Arc a3 = digraph.addArc(n1, n4);
   395   Digraph::Arc a4 = digraph.addArc(n2, n3);
   396   Digraph::Arc a5 = digraph.addArc(n2, n4);
   397   Digraph::Arc a6 = digraph.addArc(n3, n4);
   398 
   399   capacity[a1] = 8;
   400   capacity[a2] = 6;
   401   capacity[a3] = 4;
   402   capacity[a4] = 4;
   403   capacity[a5] = 6;
   404   capacity[a6] = 10;
   405 
   406   for (Adaptor::ArcIt a(adaptor); a != INVALID; ++a) {
   407     flow[a] = 0;
   408   }
   409 
   410   checkGraphNodeList(adaptor, 4);
   411   checkGraphArcList(adaptor, 6);
   412   checkGraphConArcList(adaptor, 6);
   413 
   414   checkGraphOutArcList(adaptor, n1, 3);
   415   checkGraphOutArcList(adaptor, n2, 2);
   416   checkGraphOutArcList(adaptor, n3, 1);
   417   checkGraphOutArcList(adaptor, n4, 0);
   418 
   419   checkGraphInArcList(adaptor, n1, 0);
   420   checkGraphInArcList(adaptor, n2, 1);
   421   checkGraphInArcList(adaptor, n3, 2);
   422   checkGraphInArcList(adaptor, n4, 3);
   423 
   424   for (Adaptor::ArcIt a(adaptor); a != INVALID; ++a) {
   425     flow[a] = capacity[a] / 2;
   426   }
   427 
   428   checkGraphNodeList(adaptor, 4);
   429   checkGraphArcList(adaptor, 12);
   430   checkGraphConArcList(adaptor, 12);
   431 
   432   checkGraphOutArcList(adaptor, n1, 3);
   433   checkGraphOutArcList(adaptor, n2, 3);
   434   checkGraphOutArcList(adaptor, n3, 3);
   435   checkGraphOutArcList(adaptor, n4, 3);
   436 
   437   checkGraphInArcList(adaptor, n1, 3);
   438   checkGraphInArcList(adaptor, n2, 3);
   439   checkGraphInArcList(adaptor, n3, 3);
   440   checkGraphInArcList(adaptor, n4, 3);
   441 
   442   checkNodeIds(adaptor);
   443   checkArcIds(adaptor);
   444 
   445   checkGraphNodeMap(adaptor);
   446   checkGraphArcMap(adaptor);
   447 
   448   for (Adaptor::ArcIt a(adaptor); a != INVALID; ++a) {
   449     flow[a] = capacity[a];
   450   }
   451 
   452   checkGraphNodeList(adaptor, 4);
   453   checkGraphArcList(adaptor, 6);
   454   checkGraphConArcList(adaptor, 6);
   455 
   456   checkGraphOutArcList(adaptor, n1, 0);
   457   checkGraphOutArcList(adaptor, n2, 1);
   458   checkGraphOutArcList(adaptor, n3, 2);
   459   checkGraphOutArcList(adaptor, n4, 3);
   460 
   461   checkGraphInArcList(adaptor, n1, 3);
   462   checkGraphInArcList(adaptor, n2, 2);
   463   checkGraphInArcList(adaptor, n3, 1);
   464   checkGraphInArcList(adaptor, n4, 0);
   465 
   466   for (Adaptor::ArcIt a(adaptor); a != INVALID; ++a) {
   467     flow[a] = 0;
   468   }
   469 
   470   int flow_value = 0;
   471   while (true) {
   472 
   473     Bfs<Adaptor> bfs(adaptor);
   474     bfs.run(n1, n4);
   475 
   476     if (!bfs.reached(n4)) break;
   477 
   478     Path<Adaptor> p = bfs.path(n4);
   479 
   480     int min = std::numeric_limits<int>::max();
   481     for (Path<Adaptor>::ArcIt a(p); a != INVALID; ++a) {
   482       if (adaptor.residualCapacity(a) < min)
   483         min = adaptor.residualCapacity(a);
   484     }
   485 
   486     for (Path<Adaptor>::ArcIt a(p); a != INVALID; ++a) {
   487       adaptor.augment(a, min);
   488     }
   489     flow_value += min;
   490   }
   491 
   492   check(flow_value == 18, "Wrong flow with res graph adaptor");
   493 
   494 }
   495 
   496 void checkSplitNodes() {
   497   checkConcept<concepts::Digraph, SplitNodes<concepts::Digraph> >();
   498 
   499   typedef ListDigraph Digraph;
   500   typedef SplitNodes<Digraph> Adaptor;
   501 
   502   Digraph digraph;
   503   Adaptor adaptor(digraph);
   504 
   505   Digraph::Node n1 = digraph.addNode();
   506   Digraph::Node n2 = digraph.addNode();
   507   Digraph::Node n3 = digraph.addNode();
   508 
   509   Digraph::Arc a1 = digraph.addArc(n1, n2);
   510   Digraph::Arc a2 = digraph.addArc(n1, n3);
   511   Digraph::Arc a3 = digraph.addArc(n2, n3);
   512 
   513   checkGraphNodeList(adaptor, 6);
   514   checkGraphArcList(adaptor, 6);
   515   checkGraphConArcList(adaptor, 6);
   516 
   517   checkGraphOutArcList(adaptor, adaptor.inNode(n1), 1);
   518   checkGraphOutArcList(adaptor, adaptor.outNode(n1), 2);
   519   checkGraphOutArcList(adaptor, adaptor.inNode(n2), 1);
   520   checkGraphOutArcList(adaptor, adaptor.outNode(n2), 1);
   521   checkGraphOutArcList(adaptor, adaptor.inNode(n3), 1);
   522   checkGraphOutArcList(adaptor, adaptor.outNode(n3), 0);
   523 
   524   checkGraphInArcList(adaptor, adaptor.inNode(n1), 0);
   525   checkGraphInArcList(adaptor, adaptor.outNode(n1), 1);
   526   checkGraphInArcList(adaptor, adaptor.inNode(n2), 1);
   527   checkGraphInArcList(adaptor, adaptor.outNode(n2), 1);
   528   checkGraphInArcList(adaptor, adaptor.inNode(n3), 2);
   529   checkGraphInArcList(adaptor, adaptor.outNode(n3), 1);
   530 
   531   checkNodeIds(adaptor);
   532   checkArcIds(adaptor);
   533 
   534   checkGraphNodeMap(adaptor);
   535   checkGraphArcMap(adaptor);
   536 
   537   for (Adaptor::ArcIt a(adaptor); a != INVALID; ++a) {
   538     if (adaptor.origArc(a)) {
   539       Digraph::Arc oa = a;
   540       check(adaptor.source(a) == adaptor.outNode(digraph.source(oa)),
   541             "Wrong split");
   542       check(adaptor.target(a) == adaptor.inNode(digraph.target(oa)),
   543             "Wrong split");
   544     } else {
   545       Digraph::Node on = a;
   546       check(adaptor.source(a) == adaptor.inNode(on), "Wrong split");
   547       check(adaptor.target(a) == adaptor.outNode(on), "Wrong split");
   548     }
   549   }
   550 }
   551 
   552 void checkSubGraph() {
   553   checkConcept<concepts::Graph,
   554     SubGraph<concepts::Graph,
   555     concepts::Graph::NodeMap<bool>,
   556     concepts::Graph::EdgeMap<bool> > >();
   557 
   558   typedef ListGraph Graph;
   559   typedef Graph::NodeMap<bool> NodeFilter;
   560   typedef Graph::EdgeMap<bool> EdgeFilter;
   561   typedef SubGraph<Graph, NodeFilter, EdgeFilter> Adaptor;
   562 
   563   Graph graph;
   564   NodeFilter node_filter(graph);
   565   EdgeFilter edge_filter(graph);
   566   Adaptor adaptor(graph, node_filter, edge_filter);
   567 
   568   Graph::Node n1 = graph.addNode();
   569   Graph::Node n2 = graph.addNode();
   570   Graph::Node n3 = graph.addNode();
   571   Graph::Node n4 = graph.addNode();
   572 
   573   Graph::Edge e1 = graph.addEdge(n1, n2);
   574   Graph::Edge e2 = graph.addEdge(n1, n3);
   575   Graph::Edge e3 = graph.addEdge(n2, n3);
   576   Graph::Edge e4 = graph.addEdge(n3, n4);
   577 
   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;
   580   
   581   checkGraphNodeList(adaptor, 4);
   582   checkGraphArcList(adaptor, 8);
   583   checkGraphEdgeList(adaptor, 4);
   584   checkGraphConArcList(adaptor, 8);
   585   checkGraphConEdgeList(adaptor, 4);
   586 
   587   checkGraphOutArcList(adaptor, n1, 2);
   588   checkGraphOutArcList(adaptor, n2, 2);
   589   checkGraphOutArcList(adaptor, n3, 3);
   590   checkGraphOutArcList(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 
   602   checkNodeIds(adaptor);
   603   checkArcIds(adaptor);
   604   checkEdgeIds(adaptor);
   605 
   606   checkGraphNodeMap(adaptor);
   607   checkGraphArcMap(adaptor);
   608   checkGraphEdgeMap(adaptor);
   609 
   610   edge_filter[e2] = false;
   611 
   612   checkGraphNodeList(adaptor, 4);
   613   checkGraphArcList(adaptor, 6);
   614   checkGraphEdgeList(adaptor, 3);
   615   checkGraphConArcList(adaptor, 6);
   616   checkGraphConEdgeList(adaptor, 3);
   617 
   618   checkGraphOutArcList(adaptor, n1, 1);
   619   checkGraphOutArcList(adaptor, n2, 2);
   620   checkGraphOutArcList(adaptor, n3, 2);
   621   checkGraphOutArcList(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 
   633   checkNodeIds(adaptor);
   634   checkArcIds(adaptor);
   635   checkEdgeIds(adaptor);
   636 
   637   checkGraphNodeMap(adaptor);
   638   checkGraphArcMap(adaptor);
   639   checkGraphEdgeMap(adaptor);
   640 
   641   node_filter[n1] = false;
   642 
   643   checkGraphNodeList(adaptor, 3);
   644   checkGraphArcList(adaptor, 4);
   645   checkGraphEdgeList(adaptor, 2);
   646   checkGraphConArcList(adaptor, 4);
   647   checkGraphConEdgeList(adaptor, 2);
   648 
   649   checkGraphOutArcList(adaptor, n2, 1);
   650   checkGraphOutArcList(adaptor, n3, 2);
   651   checkGraphOutArcList(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 
   661   checkNodeIds(adaptor);
   662   checkArcIds(adaptor);
   663   checkEdgeIds(adaptor);
   664 
   665   checkGraphNodeMap(adaptor);
   666   checkGraphArcMap(adaptor);
   667   checkGraphEdgeMap(adaptor);
   668 
   669   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;
   671 
   672   checkGraphNodeList(adaptor, 0);
   673   checkGraphArcList(adaptor, 0);
   674   checkGraphEdgeList(adaptor, 0);
   675   checkGraphConArcList(adaptor, 0);
   676   checkGraphConEdgeList(adaptor, 0);
   677 
   678   checkNodeIds(adaptor);
   679   checkArcIds(adaptor);
   680   checkEdgeIds(adaptor);
   681 
   682   checkGraphNodeMap(adaptor);
   683   checkGraphArcMap(adaptor);
   684   checkGraphEdgeMap(adaptor);
   685 }
   686 
   687 void checkFilterNodes2() {
   688   checkConcept<concepts::Graph,
   689     FilterNodes<concepts::Graph,
   690       concepts::Graph::NodeMap<bool> > >();
   691 
   692   typedef ListGraph Graph;
   693   typedef Graph::NodeMap<bool> NodeFilter;
   694   typedef FilterNodes<Graph, NodeFilter> Adaptor;
   695 
   696   Graph graph;
   697   NodeFilter node_filter(graph);
   698   Adaptor adaptor(graph, node_filter);
   699 
   700   Graph::Node n1 = graph.addNode();
   701   Graph::Node n2 = graph.addNode();
   702   Graph::Node n3 = graph.addNode();
   703   Graph::Node n4 = graph.addNode();
   704 
   705   Graph::Edge e1 = graph.addEdge(n1, n2);
   706   Graph::Edge e2 = graph.addEdge(n1, n3);
   707   Graph::Edge e3 = graph.addEdge(n2, n3);
   708   Graph::Edge e4 = graph.addEdge(n3, n4);
   709 
   710   node_filter[n1] = node_filter[n2] = node_filter[n3] = node_filter[n4] = true;
   711   
   712   checkGraphNodeList(adaptor, 4);
   713   checkGraphArcList(adaptor, 8);
   714   checkGraphEdgeList(adaptor, 4);
   715   checkGraphConArcList(adaptor, 8);
   716   checkGraphConEdgeList(adaptor, 4);
   717 
   718   checkGraphOutArcList(adaptor, n1, 2);
   719   checkGraphOutArcList(adaptor, n2, 2);
   720   checkGraphOutArcList(adaptor, n3, 3);
   721   checkGraphOutArcList(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 
   733   checkNodeIds(adaptor);
   734   checkArcIds(adaptor);
   735   checkEdgeIds(adaptor);
   736 
   737   checkGraphNodeMap(adaptor);
   738   checkGraphArcMap(adaptor);
   739   checkGraphEdgeMap(adaptor);
   740 
   741   node_filter[n1] = false;
   742 
   743   checkGraphNodeList(adaptor, 3);
   744   checkGraphArcList(adaptor, 4);
   745   checkGraphEdgeList(adaptor, 2);
   746   checkGraphConArcList(adaptor, 4);
   747   checkGraphConEdgeList(adaptor, 2);
   748 
   749   checkGraphOutArcList(adaptor, n2, 1);
   750   checkGraphOutArcList(adaptor, n3, 2);
   751   checkGraphOutArcList(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 
   761   checkNodeIds(adaptor);
   762   checkArcIds(adaptor);
   763   checkEdgeIds(adaptor);
   764 
   765   checkGraphNodeMap(adaptor);
   766   checkGraphArcMap(adaptor);
   767   checkGraphEdgeMap(adaptor);
   768 
   769   node_filter[n1] = node_filter[n2] = node_filter[n3] = node_filter[n4] = false;
   770 
   771   checkGraphNodeList(adaptor, 0);
   772   checkGraphArcList(adaptor, 0);
   773   checkGraphEdgeList(adaptor, 0);
   774   checkGraphConArcList(adaptor, 0);
   775   checkGraphConEdgeList(adaptor, 0);
   776 
   777   checkNodeIds(adaptor);
   778   checkArcIds(adaptor);
   779   checkEdgeIds(adaptor);
   780 
   781   checkGraphNodeMap(adaptor);
   782   checkGraphArcMap(adaptor);
   783   checkGraphEdgeMap(adaptor);
   784 }
   785 
   786 void checkFilterEdges() {
   787   checkConcept<concepts::Graph,
   788     FilterEdges<concepts::Graph,
   789     concepts::Graph::EdgeMap<bool> > >();
   790 
   791   typedef ListGraph Graph;
   792   typedef Graph::EdgeMap<bool> EdgeFilter;
   793   typedef FilterEdges<Graph, EdgeFilter> Adaptor;
   794 
   795   Graph graph;
   796   EdgeFilter edge_filter(graph);
   797   Adaptor adaptor(graph, edge_filter);
   798 
   799   Graph::Node n1 = graph.addNode();
   800   Graph::Node n2 = graph.addNode();
   801   Graph::Node n3 = graph.addNode();
   802   Graph::Node n4 = graph.addNode();
   803 
   804   Graph::Edge e1 = graph.addEdge(n1, n2);
   805   Graph::Edge e2 = graph.addEdge(n1, n3);
   806   Graph::Edge e3 = graph.addEdge(n2, n3);
   807   Graph::Edge e4 = graph.addEdge(n3, n4);
   808 
   809   edge_filter[e1] = edge_filter[e2] = edge_filter[e3] = edge_filter[e4] = true;
   810   
   811   checkGraphNodeList(adaptor, 4);
   812   checkGraphArcList(adaptor, 8);
   813   checkGraphEdgeList(adaptor, 4);
   814   checkGraphConArcList(adaptor, 8);
   815   checkGraphConEdgeList(adaptor, 4);
   816 
   817   checkGraphOutArcList(adaptor, n1, 2);
   818   checkGraphOutArcList(adaptor, n2, 2);
   819   checkGraphOutArcList(adaptor, n3, 3);
   820   checkGraphOutArcList(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 
   832   checkNodeIds(adaptor);
   833   checkArcIds(adaptor);
   834   checkEdgeIds(adaptor);
   835 
   836   checkGraphNodeMap(adaptor);
   837   checkGraphArcMap(adaptor);
   838   checkGraphEdgeMap(adaptor);
   839 
   840   edge_filter[e2] = false;
   841 
   842   checkGraphNodeList(adaptor, 4);
   843   checkGraphArcList(adaptor, 6);
   844   checkGraphEdgeList(adaptor, 3);
   845   checkGraphConArcList(adaptor, 6);
   846   checkGraphConEdgeList(adaptor, 3);
   847 
   848   checkGraphOutArcList(adaptor, n1, 1);
   849   checkGraphOutArcList(adaptor, n2, 2);
   850   checkGraphOutArcList(adaptor, n3, 2);
   851   checkGraphOutArcList(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 
   863   checkNodeIds(adaptor);
   864   checkArcIds(adaptor);
   865   checkEdgeIds(adaptor);
   866 
   867   checkGraphNodeMap(adaptor);
   868   checkGraphArcMap(adaptor);
   869   checkGraphEdgeMap(adaptor);
   870 
   871   edge_filter[e1] = edge_filter[e2] = edge_filter[e3] = edge_filter[e4] = false;
   872 
   873   checkGraphNodeList(adaptor, 4);
   874   checkGraphArcList(adaptor, 0);
   875   checkGraphEdgeList(adaptor, 0);
   876   checkGraphConArcList(adaptor, 0);
   877   checkGraphConEdgeList(adaptor, 0);
   878 
   879   checkNodeIds(adaptor);
   880   checkArcIds(adaptor);
   881   checkEdgeIds(adaptor);
   882 
   883   checkGraphNodeMap(adaptor);
   884   checkGraphArcMap(adaptor);
   885   checkGraphEdgeMap(adaptor);
   886 }
   887 
   888 void checkOrienter() {
   889   checkConcept<concepts::Digraph,
   890     Orienter<concepts::Graph, concepts::Graph::EdgeMap<bool> > >();
   891 
   892   typedef ListGraph Graph;
   893   typedef ListGraph::EdgeMap<bool> DirMap;
   894   typedef Orienter<Graph> Adaptor;
   895 
   896   Graph graph;
   897   DirMap dir(graph, true);
   898   Adaptor adaptor(graph, dir);
   899 
   900   Graph::Node n1 = graph.addNode();
   901   Graph::Node n2 = graph.addNode();
   902   Graph::Node n3 = graph.addNode();
   903 
   904   Graph::Edge e1 = graph.addEdge(n1, n2);
   905   Graph::Edge e2 = graph.addEdge(n1, n3);
   906   Graph::Edge e3 = graph.addEdge(n2, n3);
   907 
   908   checkGraphNodeList(adaptor, 3);
   909   checkGraphArcList(adaptor, 3);
   910   checkGraphConArcList(adaptor, 3);
   911 
   912   {
   913     dir[e1] = true;
   914     Adaptor::Node u = adaptor.source(e1);
   915     Adaptor::Node v = adaptor.target(e1);
   916 
   917     dir[e1] = false;
   918     check (u == adaptor.target(e1), "Wrong dir");
   919     check (v == adaptor.source(e1), "Wrong dir");
   920 
   921     check ((u == n1 && v == n2) || (u == n2 && v == n1), "Wrong dir");
   922     dir[e1] = n1 == u;
   923   }
   924 
   925   {
   926     dir[e2] = true;
   927     Adaptor::Node u = adaptor.source(e2);
   928     Adaptor::Node v = adaptor.target(e2);
   929 
   930     dir[e2] = false;
   931     check (u == adaptor.target(e2), "Wrong dir");
   932     check (v == adaptor.source(e2), "Wrong dir");
   933 
   934     check ((u == n1 && v == n3) || (u == n3 && v == n1), "Wrong dir");
   935     dir[e2] = n3 == u;
   936   }
   937 
   938   {
   939     dir[e3] = true;
   940     Adaptor::Node u = adaptor.source(e3);
   941     Adaptor::Node v = adaptor.target(e3);
   942 
   943     dir[e3] = false;
   944     check (u == adaptor.target(e3), "Wrong dir");
   945     check (v == adaptor.source(e3), "Wrong dir");
   946 
   947     check ((u == n2 && v == n3) || (u == n3 && v == n2), "Wrong dir");
   948     dir[e3] = n2 == u;
   949   }
   950 
   951   checkGraphOutArcList(adaptor, n1, 1);
   952   checkGraphOutArcList(adaptor, n2, 1);
   953   checkGraphOutArcList(adaptor, n3, 1);
   954 
   955   checkGraphInArcList(adaptor, n1, 1);
   956   checkGraphInArcList(adaptor, n2, 1);
   957   checkGraphInArcList(adaptor, n3, 1);
   958 
   959   checkNodeIds(adaptor);
   960   checkArcIds(adaptor);
   961 
   962   checkGraphNodeMap(adaptor);
   963   checkGraphArcMap(adaptor);
   964 
   965 }
   966 
   967 
   968 int main(int, const char **) {
   969 
   970   checkReverseDigraph();
   971   checkSubDigraph();
   972   checkFilterNodes1();
   973   checkFilterArcs();
   974   checkUndirector();
   975   checkResidual();
   976   checkSplitNodes();
   977 
   978   checkSubGraph();
   979   checkFilterNodes2();
   980   checkFilterEdges();
   981   checkOrienter();
   982 
   983   return 0;
   984 }