test/graph_adaptor_test.cc
changeset 434 5c69a36729cb
parent 415 4b6112235fad
child 440 88ed40ad0d4f
equal deleted inserted replaced
1:92c20458ee6d 2:4242f200ca55
     1 /* -*- C++ -*-
     1 /* -*- mode: C++; indent-tabs-mode: nil; -*-
     2  *
     2  *
     3  * This file is a part of LEMON, a generic C++ optimization library
     3  * This file is a part of LEMON, a generic C++ optimization library.
     4  *
     4  *
     5  * Copyright (C) 2003-2008
     5  * Copyright (C) 2003-2008
     6  * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
     6  * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
     7  * (Egervary Research Group on Combinatorial Optimization, EGRES).
     7  * (Egervary Research Group on Combinatorial Optimization, EGRES).
     8  *
     8  *
    23 #include<lemon/smart_graph.h>
    23 #include<lemon/smart_graph.h>
    24 
    24 
    25 #include<lemon/concepts/digraph.h>
    25 #include<lemon/concepts/digraph.h>
    26 #include<lemon/concepts/graph.h>
    26 #include<lemon/concepts/graph.h>
    27 
    27 
    28 #include<lemon/digraph_adaptor.h>
    28 #include<lemon/adaptors.h>
    29 #include<lemon/graph_adaptor.h>
       
    30 
    29 
    31 #include <limits>
    30 #include <limits>
    32 #include <lemon/bfs.h>
    31 #include <lemon/bfs.h>
    33 #include <lemon/path.h>
    32 #include <lemon/path.h>
    34 
    33 
    35 #include"test/test_tools.h"
    34 #include"test/test_tools.h"
    36 #include"test/graph_test.h"
    35 #include"test/graph_test.h"
    37 
    36 
    38 using namespace lemon;
    37 using namespace lemon;
    39 
    38 
    40 void checkRevDigraphAdaptor() {
    39 void checkReverseDigraph() {
    41   checkConcept<concepts::Digraph, RevDigraphAdaptor<concepts::Digraph> >();
    40   checkConcept<concepts::Digraph, ReverseDigraph<concepts::Digraph> >();
    42 
    41 
    43   typedef ListDigraph Digraph;
    42   typedef ListDigraph Digraph;
    44   typedef RevDigraphAdaptor<Digraph> Adaptor;
    43   typedef ReverseDigraph<Digraph> Adaptor;
    45 
    44 
    46   Digraph digraph;
    45   Digraph digraph;
    47   Adaptor adaptor(digraph);
    46   Adaptor adaptor(digraph);
    48 
    47 
    49   Digraph::Node n1 = digraph.addNode();
    48   Digraph::Node n1 = digraph.addNode();
    51   Digraph::Node n3 = digraph.addNode();
    50   Digraph::Node n3 = digraph.addNode();
    52 
    51 
    53   Digraph::Arc a1 = digraph.addArc(n1, n2);
    52   Digraph::Arc a1 = digraph.addArc(n1, n2);
    54   Digraph::Arc a2 = digraph.addArc(n1, n3);
    53   Digraph::Arc a2 = digraph.addArc(n1, n3);
    55   Digraph::Arc a3 = digraph.addArc(n2, n3);
    54   Digraph::Arc a3 = digraph.addArc(n2, n3);
    56   
    55 
    57   checkGraphNodeList(adaptor, 3);
    56   checkGraphNodeList(adaptor, 3);
    58   checkGraphArcList(adaptor, 3);
    57   checkGraphArcList(adaptor, 3);
    59   checkGraphConArcList(adaptor, 3);
    58   checkGraphConArcList(adaptor, 3);
    60 
    59 
    61   checkGraphOutArcList(adaptor, n1, 0);
    60   checkGraphOutArcList(adaptor, n1, 0);
    76     check(adaptor.source(a) == digraph.target(a), "Wrong reverse");
    75     check(adaptor.source(a) == digraph.target(a), "Wrong reverse");
    77     check(adaptor.target(a) == digraph.source(a), "Wrong reverse");
    76     check(adaptor.target(a) == digraph.source(a), "Wrong reverse");
    78   }
    77   }
    79 }
    78 }
    80 
    79 
    81 void checkSubDigraphAdaptor() {
    80 void checkSubDigraph() {
    82   checkConcept<concepts::Digraph, 
    81   checkConcept<concepts::Digraph,
    83     SubDigraphAdaptor<concepts::Digraph, 
    82     SubDigraph<concepts::Digraph,
    84     concepts::Digraph::NodeMap<bool>,
    83     concepts::Digraph::NodeMap<bool>,
    85     concepts::Digraph::ArcMap<bool> > >();
    84     concepts::Digraph::ArcMap<bool> > >();
    86 
    85 
    87   typedef ListDigraph Digraph;
    86   typedef ListDigraph Digraph;
    88   typedef Digraph::NodeMap<bool> NodeFilter;
    87   typedef Digraph::NodeMap<bool> NodeFilter;
    89   typedef Digraph::ArcMap<bool> ArcFilter;
    88   typedef Digraph::ArcMap<bool> ArcFilter;
    90   typedef SubDigraphAdaptor<Digraph, NodeFilter, ArcFilter> Adaptor;
    89   typedef SubDigraph<Digraph, NodeFilter, ArcFilter> Adaptor;
    91 
    90 
    92   Digraph digraph;
    91   Digraph digraph;
    93   NodeFilter node_filter(digraph);
    92   NodeFilter node_filter(digraph);
    94   ArcFilter arc_filter(digraph);
    93   ArcFilter arc_filter(digraph);
    95   Adaptor adaptor(digraph, node_filter, arc_filter);
    94   Adaptor adaptor(digraph, node_filter, arc_filter);
   121   checkArcIds(adaptor);
   120   checkArcIds(adaptor);
   122 
   121 
   123   checkGraphNodeMap(adaptor);
   122   checkGraphNodeMap(adaptor);
   124   checkGraphArcMap(adaptor);
   123   checkGraphArcMap(adaptor);
   125 
   124 
   126   arc_filter[a2] = false; 
   125   arc_filter[a2] = false;
   127 
   126 
   128   checkGraphNodeList(adaptor, 3);
   127   checkGraphNodeList(adaptor, 3);
   129   checkGraphArcList(adaptor, 2);
   128   checkGraphArcList(adaptor, 2);
   130   checkGraphConArcList(adaptor, 2);
   129   checkGraphConArcList(adaptor, 2);
   131 
   130 
   141   checkArcIds(adaptor);
   140   checkArcIds(adaptor);
   142 
   141 
   143   checkGraphNodeMap(adaptor);
   142   checkGraphNodeMap(adaptor);
   144   checkGraphArcMap(adaptor);
   143   checkGraphArcMap(adaptor);
   145 
   144 
   146   node_filter[n1] = false; 
   145   node_filter[n1] = false;
   147 
   146 
   148   checkGraphNodeList(adaptor, 2);
   147   checkGraphNodeList(adaptor, 2);
   149   checkGraphArcList(adaptor, 1);
   148   checkGraphArcList(adaptor, 1);
   150   checkGraphConArcList(adaptor, 1);
   149   checkGraphConArcList(adaptor, 1);
   151 
   150 
   173 
   172 
   174   checkGraphNodeMap(adaptor);
   173   checkGraphNodeMap(adaptor);
   175   checkGraphArcMap(adaptor);
   174   checkGraphArcMap(adaptor);
   176 }
   175 }
   177 
   176 
   178 void checkNodeSubDigraphAdaptor() {
   177 void checkFilterNodes1() {
   179   checkConcept<concepts::Digraph, 
   178   checkConcept<concepts::Digraph,
   180     NodeSubDigraphAdaptor<concepts::Digraph, 
   179     FilterNodes<concepts::Digraph,
   181       concepts::Digraph::NodeMap<bool> > >();
   180       concepts::Digraph::NodeMap<bool> > >();
   182 
   181 
   183   typedef ListDigraph Digraph;
   182   typedef ListDigraph Digraph;
   184   typedef Digraph::NodeMap<bool> NodeFilter;
   183   typedef Digraph::NodeMap<bool> NodeFilter;
   185   typedef NodeSubDigraphAdaptor<Digraph, NodeFilter> Adaptor;
   184   typedef FilterNodes<Digraph, NodeFilter> Adaptor;
   186 
   185 
   187   Digraph digraph;
   186   Digraph digraph;
   188   NodeFilter node_filter(digraph);
   187   NodeFilter node_filter(digraph);
   189   Adaptor adaptor(digraph, node_filter);
   188   Adaptor adaptor(digraph, node_filter);
   190 
   189 
   214   checkArcIds(adaptor);
   213   checkArcIds(adaptor);
   215 
   214 
   216   checkGraphNodeMap(adaptor);
   215   checkGraphNodeMap(adaptor);
   217   checkGraphArcMap(adaptor);
   216   checkGraphArcMap(adaptor);
   218 
   217 
   219   node_filter[n1] = false; 
   218   node_filter[n1] = false;
   220 
   219 
   221   checkGraphNodeList(adaptor, 2);
   220   checkGraphNodeList(adaptor, 2);
   222   checkGraphArcList(adaptor, 1);
   221   checkGraphArcList(adaptor, 1);
   223   checkGraphConArcList(adaptor, 1);
   222   checkGraphConArcList(adaptor, 1);
   224 
   223 
   245 
   244 
   246   checkGraphNodeMap(adaptor);
   245   checkGraphNodeMap(adaptor);
   247   checkGraphArcMap(adaptor);
   246   checkGraphArcMap(adaptor);
   248 }
   247 }
   249 
   248 
   250 void checkArcSubDigraphAdaptor() {
   249 void checkFilterArcs() {
   251   checkConcept<concepts::Digraph, 
   250   checkConcept<concepts::Digraph,
   252     ArcSubDigraphAdaptor<concepts::Digraph, 
   251     FilterArcs<concepts::Digraph,
   253     concepts::Digraph::ArcMap<bool> > >();
   252     concepts::Digraph::ArcMap<bool> > >();
   254 
   253 
   255   typedef ListDigraph Digraph;
   254   typedef ListDigraph Digraph;
   256   typedef Digraph::ArcMap<bool> ArcFilter;
   255   typedef Digraph::ArcMap<bool> ArcFilter;
   257   typedef ArcSubDigraphAdaptor<Digraph, ArcFilter> Adaptor;
   256   typedef FilterArcs<Digraph, ArcFilter> Adaptor;
   258 
   257 
   259   Digraph digraph;
   258   Digraph digraph;
   260   ArcFilter arc_filter(digraph);
   259   ArcFilter arc_filter(digraph);
   261   Adaptor adaptor(digraph, arc_filter);
   260   Adaptor adaptor(digraph, arc_filter);
   262 
   261 
   286   checkArcIds(adaptor);
   285   checkArcIds(adaptor);
   287 
   286 
   288   checkGraphNodeMap(adaptor);
   287   checkGraphNodeMap(adaptor);
   289   checkGraphArcMap(adaptor);
   288   checkGraphArcMap(adaptor);
   290 
   289 
   291   arc_filter[a2] = false; 
   290   arc_filter[a2] = false;
   292 
   291 
   293   checkGraphNodeList(adaptor, 3);
   292   checkGraphNodeList(adaptor, 3);
   294   checkGraphArcList(adaptor, 2);
   293   checkGraphArcList(adaptor, 2);
   295   checkGraphConArcList(adaptor, 2);
   294   checkGraphConArcList(adaptor, 2);
   296 
   295 
   319 
   318 
   320   checkGraphNodeMap(adaptor);
   319   checkGraphNodeMap(adaptor);
   321   checkGraphArcMap(adaptor);
   320   checkGraphArcMap(adaptor);
   322 }
   321 }
   323 
   322 
   324 void checkUndirDigraphAdaptor() {
   323 void checkUndirector() {
   325   checkConcept<concepts::Graph, UndirDigraphAdaptor<concepts::Digraph> >();
   324   checkConcept<concepts::Graph, Undirector<concepts::Digraph> >();
   326 
   325 
   327   typedef ListDigraph Digraph;
   326   typedef ListDigraph Digraph;
   328   typedef UndirDigraphAdaptor<Digraph> Adaptor;
   327   typedef Undirector<Digraph> Adaptor;
   329 
   328 
   330   Digraph digraph;
   329   Digraph digraph;
   331   Adaptor adaptor(digraph);
   330   Adaptor adaptor(digraph);
   332 
   331 
   333   Digraph::Node n1 = digraph.addNode();
   332   Digraph::Node n1 = digraph.addNode();
   335   Digraph::Node n3 = digraph.addNode();
   334   Digraph::Node n3 = digraph.addNode();
   336 
   335 
   337   Digraph::Arc a1 = digraph.addArc(n1, n2);
   336   Digraph::Arc a1 = digraph.addArc(n1, n2);
   338   Digraph::Arc a2 = digraph.addArc(n1, n3);
   337   Digraph::Arc a2 = digraph.addArc(n1, n3);
   339   Digraph::Arc a3 = digraph.addArc(n2, n3);
   338   Digraph::Arc a3 = digraph.addArc(n2, n3);
   340   
   339 
   341   checkGraphNodeList(adaptor, 3);
   340   checkGraphNodeList(adaptor, 3);
   342   checkGraphArcList(adaptor, 6);
   341   checkGraphArcList(adaptor, 6);
   343   checkGraphEdgeList(adaptor, 3);
   342   checkGraphEdgeList(adaptor, 3);
   344   checkGraphConArcList(adaptor, 6);
   343   checkGraphConArcList(adaptor, 6);
   345   checkGraphConEdgeList(adaptor, 3);
   344   checkGraphConEdgeList(adaptor, 3);
   369     check(adaptor.v(e) == digraph.target(e), "Wrong undir");
   368     check(adaptor.v(e) == digraph.target(e), "Wrong undir");
   370   }
   369   }
   371 
   370 
   372 }
   371 }
   373 
   372 
   374 void checkResDigraphAdaptor() {
   373 void checkResidual() {
   375   checkConcept<concepts::Digraph, 
   374   checkConcept<concepts::Digraph,
   376     ResDigraphAdaptor<concepts::Digraph, 
   375     Residual<concepts::Digraph,
   377     concepts::Digraph::ArcMap<int>, 
   376     concepts::Digraph::ArcMap<int>,
   378     concepts::Digraph::ArcMap<int> > >();
   377     concepts::Digraph::ArcMap<int> > >();
   379 
   378 
   380   typedef ListDigraph Digraph;
   379   typedef ListDigraph Digraph;
   381   typedef Digraph::ArcMap<int> IntArcMap;
   380   typedef Digraph::ArcMap<int> IntArcMap;
   382   typedef ResDigraphAdaptor<Digraph, IntArcMap> Adaptor;
   381   typedef Residual<Digraph, IntArcMap> Adaptor;
   383 
   382 
   384   Digraph digraph;
   383   Digraph digraph;
   385   IntArcMap capacity(digraph), flow(digraph);
   384   IntArcMap capacity(digraph), flow(digraph);
   386   Adaptor adaptor(digraph, capacity, flow);
   385   Adaptor adaptor(digraph, capacity, flow);
   387 
   386 
   405   capacity[a6] = 10;
   404   capacity[a6] = 10;
   406 
   405 
   407   for (Adaptor::ArcIt a(adaptor); a != INVALID; ++a) {
   406   for (Adaptor::ArcIt a(adaptor); a != INVALID; ++a) {
   408     flow[a] = 0;
   407     flow[a] = 0;
   409   }
   408   }
   410   
   409 
   411   checkGraphNodeList(adaptor, 4);
   410   checkGraphNodeList(adaptor, 4);
   412   checkGraphArcList(adaptor, 6);
   411   checkGraphArcList(adaptor, 6);
   413   checkGraphConArcList(adaptor, 6);
   412   checkGraphConArcList(adaptor, 6);
   414 
   413 
   415   checkGraphOutArcList(adaptor, n1, 3);
   414   checkGraphOutArcList(adaptor, n1, 3);
   423   checkGraphInArcList(adaptor, n4, 3);
   422   checkGraphInArcList(adaptor, n4, 3);
   424 
   423 
   425   for (Adaptor::ArcIt a(adaptor); a != INVALID; ++a) {
   424   for (Adaptor::ArcIt a(adaptor); a != INVALID; ++a) {
   426     flow[a] = capacity[a] / 2;
   425     flow[a] = capacity[a] / 2;
   427   }
   426   }
   428   
   427 
   429   checkGraphNodeList(adaptor, 4);
   428   checkGraphNodeList(adaptor, 4);
   430   checkGraphArcList(adaptor, 12);
   429   checkGraphArcList(adaptor, 12);
   431   checkGraphConArcList(adaptor, 12);
   430   checkGraphConArcList(adaptor, 12);
   432 
   431 
   433   checkGraphOutArcList(adaptor, n1, 3);
   432   checkGraphOutArcList(adaptor, n1, 3);
   447   checkGraphArcMap(adaptor);
   446   checkGraphArcMap(adaptor);
   448 
   447 
   449   for (Adaptor::ArcIt a(adaptor); a != INVALID; ++a) {
   448   for (Adaptor::ArcIt a(adaptor); a != INVALID; ++a) {
   450     flow[a] = capacity[a];
   449     flow[a] = capacity[a];
   451   }
   450   }
   452   
   451 
   453   checkGraphNodeList(adaptor, 4);
   452   checkGraphNodeList(adaptor, 4);
   454   checkGraphArcList(adaptor, 6);
   453   checkGraphArcList(adaptor, 6);
   455   checkGraphConArcList(adaptor, 6);
   454   checkGraphConArcList(adaptor, 6);
   456 
   455 
   457   checkGraphOutArcList(adaptor, n1, 0);
   456   checkGraphOutArcList(adaptor, n1, 0);
   468     flow[a] = 0;
   467     flow[a] = 0;
   469   }
   468   }
   470 
   469 
   471   int flow_value = 0;
   470   int flow_value = 0;
   472   while (true) {
   471   while (true) {
   473     
   472 
   474     Bfs<Adaptor> bfs(adaptor);
   473     Bfs<Adaptor> bfs(adaptor);
   475     bfs.run(n1, n4);
   474     bfs.run(n1, n4);
   476     
   475 
   477     if (!bfs.reached(n4)) break;
   476     if (!bfs.reached(n4)) break;
   478 
   477 
   479     Path<Adaptor> p = bfs.path(n4);
   478     Path<Adaptor> p = bfs.path(n4);
   480     
   479 
   481     int min = std::numeric_limits<int>::max();
   480     int min = std::numeric_limits<int>::max();
   482     for (Path<Adaptor>::ArcIt a(p); a != INVALID; ++a) {
   481     for (Path<Adaptor>::ArcIt a(p); a != INVALID; ++a) {
   483       if (adaptor.rescap(a) < min) min = adaptor.rescap(a);
   482       if (adaptor.residualCapacity(a) < min)
       
   483         min = adaptor.residualCapacity(a);
   484     }
   484     }
   485 
   485 
   486     for (Path<Adaptor>::ArcIt a(p); a != INVALID; ++a) {
   486     for (Path<Adaptor>::ArcIt a(p); a != INVALID; ++a) {
   487       adaptor.augment(a, min);
   487       adaptor.augment(a, min);
   488     }
   488     }
   491 
   491 
   492   check(flow_value == 18, "Wrong flow with res graph adaptor");
   492   check(flow_value == 18, "Wrong flow with res graph adaptor");
   493 
   493 
   494 }
   494 }
   495 
   495 
   496 void checkSplitDigraphAdaptor() {
   496 void checkSplitNodes() {
   497   checkConcept<concepts::Digraph, SplitDigraphAdaptor<concepts::Digraph> >();
   497   checkConcept<concepts::Digraph, SplitNodes<concepts::Digraph> >();
   498 
   498 
   499   typedef ListDigraph Digraph;
   499   typedef ListDigraph Digraph;
   500   typedef SplitDigraphAdaptor<Digraph> Adaptor;
   500   typedef SplitNodes<Digraph> Adaptor;
   501 
   501 
   502   Digraph digraph;
   502   Digraph digraph;
   503   Adaptor adaptor(digraph);
   503   Adaptor adaptor(digraph);
   504 
   504 
   505   Digraph::Node n1 = digraph.addNode();
   505   Digraph::Node n1 = digraph.addNode();
   507   Digraph::Node n3 = digraph.addNode();
   507   Digraph::Node n3 = digraph.addNode();
   508 
   508 
   509   Digraph::Arc a1 = digraph.addArc(n1, n2);
   509   Digraph::Arc a1 = digraph.addArc(n1, n2);
   510   Digraph::Arc a2 = digraph.addArc(n1, n3);
   510   Digraph::Arc a2 = digraph.addArc(n1, n3);
   511   Digraph::Arc a3 = digraph.addArc(n2, n3);
   511   Digraph::Arc a3 = digraph.addArc(n2, n3);
   512   
   512 
   513   checkGraphNodeList(adaptor, 6);
   513   checkGraphNodeList(adaptor, 6);
   514   checkGraphArcList(adaptor, 6);
   514   checkGraphArcList(adaptor, 6);
   515   checkGraphConArcList(adaptor, 6);
   515   checkGraphConArcList(adaptor, 6);
   516 
   516 
   517   checkGraphOutArcList(adaptor, adaptor.inNode(n1), 1);
   517   checkGraphOutArcList(adaptor, adaptor.inNode(n1), 1);
   528   checkGraphInArcList(adaptor, adaptor.inNode(n3), 2);
   528   checkGraphInArcList(adaptor, adaptor.inNode(n3), 2);
   529   checkGraphInArcList(adaptor, adaptor.outNode(n3), 1);
   529   checkGraphInArcList(adaptor, adaptor.outNode(n3), 1);
   530 
   530 
   531   checkNodeIds(adaptor);
   531   checkNodeIds(adaptor);
   532   checkArcIds(adaptor);
   532   checkArcIds(adaptor);
   533   
   533 
   534   checkGraphNodeMap(adaptor);
   534   checkGraphNodeMap(adaptor);
   535   checkGraphArcMap(adaptor);
   535   checkGraphArcMap(adaptor);
   536 
   536 
   537   for (Adaptor::ArcIt a(adaptor); a != INVALID; ++a) {
   537   for (Adaptor::ArcIt a(adaptor); a != INVALID; ++a) {
   538     if (adaptor.origArc(a)) {
   538     if (adaptor.origArc(a)) {
   539       Digraph::Arc oa = a;
   539       Digraph::Arc oa = a;
   540       check(adaptor.source(a) == adaptor.outNode(digraph.source(oa)), 
   540       check(adaptor.source(a) == adaptor.outNode(digraph.source(oa)),
   541 	    "Wrong split");
   541             "Wrong split");
   542       check(adaptor.target(a) == adaptor.inNode(digraph.target(oa)), 
   542       check(adaptor.target(a) == adaptor.inNode(digraph.target(oa)),
   543 	    "Wrong split"); 
   543             "Wrong split");
   544     } else {
   544     } else {
   545       Digraph::Node on = a;
   545       Digraph::Node on = a;
   546       check(adaptor.source(a) == adaptor.inNode(on), "Wrong split");
   546       check(adaptor.source(a) == adaptor.inNode(on), "Wrong split");
   547       check(adaptor.target(a) == adaptor.outNode(on), "Wrong split");
   547       check(adaptor.target(a) == adaptor.outNode(on), "Wrong split");
   548     }
   548     }
   549   }
   549   }
   550 }
   550 }
   551 
   551 
   552 void checkSubGraphAdaptor() {
   552 void checkSubGraph() {
   553   checkConcept<concepts::Graph, 
   553   checkConcept<concepts::Graph,
   554     SubGraphAdaptor<concepts::Graph, 
   554     SubGraph<concepts::Graph,
   555     concepts::Graph::NodeMap<bool>,
   555     concepts::Graph::NodeMap<bool>,
   556     concepts::Graph::EdgeMap<bool> > >();
   556     concepts::Graph::EdgeMap<bool> > >();
   557 
   557 
   558   typedef ListGraph Graph;
   558   typedef ListGraph Graph;
   559   typedef Graph::NodeMap<bool> NodeFilter;
   559   typedef Graph::NodeMap<bool> NodeFilter;
   560   typedef Graph::EdgeMap<bool> EdgeFilter;
   560   typedef Graph::EdgeMap<bool> EdgeFilter;
   561   typedef SubGraphAdaptor<Graph, NodeFilter, EdgeFilter> Adaptor;
   561   typedef SubGraph<Graph, NodeFilter, EdgeFilter> Adaptor;
   562 
   562 
   563   Graph graph;
   563   Graph graph;
   564   NodeFilter node_filter(graph);
   564   NodeFilter node_filter(graph);
   565   EdgeFilter edge_filter(graph);
   565   EdgeFilter edge_filter(graph);
   566   Adaptor adaptor(graph, node_filter, edge_filter);
   566   Adaptor adaptor(graph, node_filter, edge_filter);
   605 
   605 
   606   checkGraphNodeMap(adaptor);
   606   checkGraphNodeMap(adaptor);
   607   checkGraphArcMap(adaptor);
   607   checkGraphArcMap(adaptor);
   608   checkGraphEdgeMap(adaptor);
   608   checkGraphEdgeMap(adaptor);
   609 
   609 
   610   edge_filter[e2] = false; 
   610   edge_filter[e2] = false;
   611 
   611 
   612   checkGraphNodeList(adaptor, 4);
   612   checkGraphNodeList(adaptor, 4);
   613   checkGraphArcList(adaptor, 6);
   613   checkGraphArcList(adaptor, 6);
   614   checkGraphEdgeList(adaptor, 3);
   614   checkGraphEdgeList(adaptor, 3);
   615   checkGraphConArcList(adaptor, 6);
   615   checkGraphConArcList(adaptor, 6);
   636 
   636 
   637   checkGraphNodeMap(adaptor);
   637   checkGraphNodeMap(adaptor);
   638   checkGraphArcMap(adaptor);
   638   checkGraphArcMap(adaptor);
   639   checkGraphEdgeMap(adaptor);
   639   checkGraphEdgeMap(adaptor);
   640 
   640 
   641   node_filter[n1] = false; 
   641   node_filter[n1] = false;
   642 
   642 
   643   checkGraphNodeList(adaptor, 3);
   643   checkGraphNodeList(adaptor, 3);
   644   checkGraphArcList(adaptor, 4);
   644   checkGraphArcList(adaptor, 4);
   645   checkGraphEdgeList(adaptor, 2);
   645   checkGraphEdgeList(adaptor, 2);
   646   checkGraphConArcList(adaptor, 4);
   646   checkGraphConArcList(adaptor, 4);
   682   checkGraphNodeMap(adaptor);
   682   checkGraphNodeMap(adaptor);
   683   checkGraphArcMap(adaptor);
   683   checkGraphArcMap(adaptor);
   684   checkGraphEdgeMap(adaptor);
   684   checkGraphEdgeMap(adaptor);
   685 }
   685 }
   686 
   686 
   687 void checkNodeSubGraphAdaptor() {
   687 void checkFilterNodes2() {
   688   checkConcept<concepts::Graph, 
   688   checkConcept<concepts::Graph,
   689     NodeSubGraphAdaptor<concepts::Graph, 
   689     FilterNodes<concepts::Graph,
   690       concepts::Graph::NodeMap<bool> > >();
   690       concepts::Graph::NodeMap<bool> > >();
   691 
   691 
   692   typedef ListGraph Graph;
   692   typedef ListGraph Graph;
   693   typedef Graph::NodeMap<bool> NodeFilter;
   693   typedef Graph::NodeMap<bool> NodeFilter;
   694   typedef NodeSubGraphAdaptor<Graph, NodeFilter> Adaptor;
   694   typedef FilterNodes<Graph, NodeFilter> Adaptor;
   695 
   695 
   696   Graph graph;
   696   Graph graph;
   697   NodeFilter node_filter(graph);
   697   NodeFilter node_filter(graph);
   698   Adaptor adaptor(graph, node_filter);
   698   Adaptor adaptor(graph, node_filter);
   699 
   699 
   736 
   736 
   737   checkGraphNodeMap(adaptor);
   737   checkGraphNodeMap(adaptor);
   738   checkGraphArcMap(adaptor);
   738   checkGraphArcMap(adaptor);
   739   checkGraphEdgeMap(adaptor);
   739   checkGraphEdgeMap(adaptor);
   740 
   740 
   741   node_filter[n1] = false; 
   741   node_filter[n1] = false;
   742 
   742 
   743   checkGraphNodeList(adaptor, 3);
   743   checkGraphNodeList(adaptor, 3);
   744   checkGraphArcList(adaptor, 4);
   744   checkGraphArcList(adaptor, 4);
   745   checkGraphEdgeList(adaptor, 2);
   745   checkGraphEdgeList(adaptor, 2);
   746   checkGraphConArcList(adaptor, 4);
   746   checkGraphConArcList(adaptor, 4);
   781   checkGraphNodeMap(adaptor);
   781   checkGraphNodeMap(adaptor);
   782   checkGraphArcMap(adaptor);
   782   checkGraphArcMap(adaptor);
   783   checkGraphEdgeMap(adaptor);
   783   checkGraphEdgeMap(adaptor);
   784 }
   784 }
   785 
   785 
   786 void checkEdgeSubGraphAdaptor() {
   786 void checkFilterEdges() {
   787   checkConcept<concepts::Graph, 
   787   checkConcept<concepts::Graph,
   788     EdgeSubGraphAdaptor<concepts::Graph, 
   788     FilterEdges<concepts::Graph,
   789     concepts::Graph::EdgeMap<bool> > >();
   789     concepts::Graph::EdgeMap<bool> > >();
   790 
   790 
   791   typedef ListGraph Graph;
   791   typedef ListGraph Graph;
   792   typedef Graph::EdgeMap<bool> EdgeFilter;
   792   typedef Graph::EdgeMap<bool> EdgeFilter;
   793   typedef EdgeSubGraphAdaptor<Graph, EdgeFilter> Adaptor;
   793   typedef FilterEdges<Graph, EdgeFilter> Adaptor;
   794 
   794 
   795   Graph graph;
   795   Graph graph;
   796   EdgeFilter edge_filter(graph);
   796   EdgeFilter edge_filter(graph);
   797   Adaptor adaptor(graph, edge_filter);
   797   Adaptor adaptor(graph, edge_filter);
   798 
   798 
   835 
   835 
   836   checkGraphNodeMap(adaptor);
   836   checkGraphNodeMap(adaptor);
   837   checkGraphArcMap(adaptor);
   837   checkGraphArcMap(adaptor);
   838   checkGraphEdgeMap(adaptor);
   838   checkGraphEdgeMap(adaptor);
   839 
   839 
   840   edge_filter[e2] = false; 
   840   edge_filter[e2] = false;
   841 
   841 
   842   checkGraphNodeList(adaptor, 4);
   842   checkGraphNodeList(adaptor, 4);
   843   checkGraphArcList(adaptor, 6);
   843   checkGraphArcList(adaptor, 6);
   844   checkGraphEdgeList(adaptor, 3);
   844   checkGraphEdgeList(adaptor, 3);
   845   checkGraphConArcList(adaptor, 6);
   845   checkGraphConArcList(adaptor, 6);
   883   checkGraphNodeMap(adaptor);
   883   checkGraphNodeMap(adaptor);
   884   checkGraphArcMap(adaptor);
   884   checkGraphArcMap(adaptor);
   885   checkGraphEdgeMap(adaptor);
   885   checkGraphEdgeMap(adaptor);
   886 }
   886 }
   887 
   887 
   888 void checkDirGraphAdaptor() {
   888 void checkOrienter() {
   889   checkConcept<concepts::Digraph, 
   889   checkConcept<concepts::Digraph,
   890     DirGraphAdaptor<concepts::Graph, concepts::Graph::EdgeMap<bool> > >();
   890     Orienter<concepts::Graph, concepts::Graph::EdgeMap<bool> > >();
   891 
   891 
   892   typedef ListGraph Graph;
   892   typedef ListGraph Graph;
   893   typedef ListGraph::EdgeMap<bool> DirMap;
   893   typedef ListGraph::EdgeMap<bool> DirMap;
   894   typedef DirGraphAdaptor<Graph> Adaptor;
   894   typedef Orienter<Graph> Adaptor;
   895 
   895 
   896   Graph graph;
   896   Graph graph;
   897   DirMap dir(graph, true);
   897   DirMap dir(graph, true);
   898   Adaptor adaptor(graph, dir);
   898   Adaptor adaptor(graph, dir);
   899 
   899 
   902   Graph::Node n3 = graph.addNode();
   902   Graph::Node n3 = graph.addNode();
   903 
   903 
   904   Graph::Edge e1 = graph.addEdge(n1, n2);
   904   Graph::Edge e1 = graph.addEdge(n1, n2);
   905   Graph::Edge e2 = graph.addEdge(n1, n3);
   905   Graph::Edge e2 = graph.addEdge(n1, n3);
   906   Graph::Edge e3 = graph.addEdge(n2, n3);
   906   Graph::Edge e3 = graph.addEdge(n2, n3);
   907   
   907 
   908   checkGraphNodeList(adaptor, 3);
   908   checkGraphNodeList(adaptor, 3);
   909   checkGraphArcList(adaptor, 3);
   909   checkGraphArcList(adaptor, 3);
   910   checkGraphConArcList(adaptor, 3);
   910   checkGraphConArcList(adaptor, 3);
   911   
   911 
   912   {
   912   {
   913     dir[e1] = true;
   913     dir[e1] = true;
   914     Adaptor::Node u = adaptor.source(e1);
   914     Adaptor::Node u = adaptor.source(e1);
   915     Adaptor::Node v = adaptor.target(e1);
   915     Adaptor::Node v = adaptor.target(e1);
   916     
   916 
   917     dir[e1] = false;
   917     dir[e1] = false;
   918     check (u == adaptor.target(e1), "Wrong dir");
   918     check (u == adaptor.target(e1), "Wrong dir");
   919     check (v == adaptor.source(e1), "Wrong dir");
   919     check (v == adaptor.source(e1), "Wrong dir");
   920 
   920 
   921     check ((u == n1 && v == n2) || (u == n2 && v == n1), "Wrong dir");
   921     check ((u == n1 && v == n2) || (u == n2 && v == n1), "Wrong dir");
   924 
   924 
   925   {
   925   {
   926     dir[e2] = true;
   926     dir[e2] = true;
   927     Adaptor::Node u = adaptor.source(e2);
   927     Adaptor::Node u = adaptor.source(e2);
   928     Adaptor::Node v = adaptor.target(e2);
   928     Adaptor::Node v = adaptor.target(e2);
   929     
   929 
   930     dir[e2] = false;
   930     dir[e2] = false;
   931     check (u == adaptor.target(e2), "Wrong dir");
   931     check (u == adaptor.target(e2), "Wrong dir");
   932     check (v == adaptor.source(e2), "Wrong dir");
   932     check (v == adaptor.source(e2), "Wrong dir");
   933 
   933 
   934     check ((u == n1 && v == n3) || (u == n3 && v == n1), "Wrong dir");
   934     check ((u == n1 && v == n3) || (u == n3 && v == n1), "Wrong dir");
   937 
   937 
   938   {
   938   {
   939     dir[e3] = true;
   939     dir[e3] = true;
   940     Adaptor::Node u = adaptor.source(e3);
   940     Adaptor::Node u = adaptor.source(e3);
   941     Adaptor::Node v = adaptor.target(e3);
   941     Adaptor::Node v = adaptor.target(e3);
   942     
   942 
   943     dir[e3] = false;
   943     dir[e3] = false;
   944     check (u == adaptor.target(e3), "Wrong dir");
   944     check (u == adaptor.target(e3), "Wrong dir");
   945     check (v == adaptor.source(e3), "Wrong dir");
   945     check (v == adaptor.source(e3), "Wrong dir");
   946 
   946 
   947     check ((u == n2 && v == n3) || (u == n3 && v == n2), "Wrong dir");
   947     check ((u == n2 && v == n3) || (u == n3 && v == n2), "Wrong dir");
   965 }
   965 }
   966 
   966 
   967 
   967 
   968 int main(int, const char **) {
   968 int main(int, const char **) {
   969 
   969 
   970   checkRevDigraphAdaptor();
   970   checkReverseDigraph();
   971   checkSubDigraphAdaptor();
   971   checkSubDigraph();
   972   checkNodeSubDigraphAdaptor();
   972   checkFilterNodes1();
   973   checkArcSubDigraphAdaptor();
   973   checkFilterArcs();
   974   checkUndirDigraphAdaptor();
   974   checkUndirector();
   975   checkResDigraphAdaptor();
   975   checkResidual();
   976   checkSplitDigraphAdaptor();
   976   checkSplitNodes();
   977 
   977 
   978   checkSubGraphAdaptor();
   978   checkSubGraph();
   979   checkNodeSubGraphAdaptor();
   979   checkFilterNodes2();
   980   checkEdgeSubGraphAdaptor();
   980   checkFilterEdges();
   981   checkDirGraphAdaptor();
   981   checkOrienter();
   982 
   982 
   983   return 0;
   983   return 0;
   984 }
   984 }