COIN-OR::LEMON - Graph Library

Changeset 463:a2fd8b8d0b30 in lemon-main


Ignore:
Timestamp:
01/12/09 07:52:48 (16 years ago)
Author:
Peter Kovacs <kpeter@…>
Branch:
default
Phase:
public
Message:

Greatly extend and improve the test file for adaptors (#67)

  • Add concept checks for the alterable, extendable, erasable and clearable adaptors.
  • Add test cases for modifying the underlying graphs through adaptors whenever it is possible.
  • Check the conversions between Node, Arc and Edge types.
  • Add more test cases for the adaptor-specific functions and maps: enable(), disable(), status(), forward(), backward(), CombinedArcMap?, CombinedNodeMap?, ResidualCapacity? etc.
  • Use checkGraphIncEdgeArcLists() to simplify the test cases for undirected graphs.
  • Add test cases that use static graph structure (GridGraph?) with several adaptors combined.
  • Add comments for the test cases.
File:
1 edited

Legend:

Unmodified
Added
Removed
  • test/graph_adaptor_test.cc

    r440 r463  
    1717 */
    1818
    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 
     19#include <iostream>
    3020#include <limits>
     21
     22#include <lemon/list_graph.h>
     23#include <lemon/grid_graph.h>
    3124#include <lemon/bfs.h>
    3225#include <lemon/path.h>
    3326
    34 #include"test/test_tools.h"
    35 #include"test/graph_test.h"
     27#include <lemon/concepts/digraph.h>
     28#include <lemon/concepts/graph.h>
     29#include <lemon/concepts/graph_components.h>
     30#include <lemon/concepts/maps.h>
     31#include <lemon/concept_check.h>
     32
     33#include <lemon/adaptors.h>
     34
     35#include "test/test_tools.h"
     36#include "test/graph_test.h"
    3637
    3738using namespace lemon;
    3839
    3940void checkReverseDigraph() {
     41  // Check concepts
    4042  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
    4254  typedef ListDigraph Digraph;
    4355  typedef ReverseDigraph<Digraph> Adaptor;
     
    4658  Adaptor adaptor(digraph);
    4759
     60  // Add nodes and arcs to the original digraph
    4861  Digraph::Node n1 = digraph.addNode();
    4962  Digraph::Node n2 = digraph.addNode();
     
    5467  Digraph::Arc a3 = digraph.addArc(n2, n3);
    5568
     69  // Check the adaptor
    5670  checkGraphNodeList(adaptor, 3);
    5771  checkGraphArcList(adaptor, 3);
     
    7286  checkGraphArcMap(adaptor);
    7387
     88  // Check the orientation of the arcs
    7489  for (Adaptor::ArcIt a(adaptor); a != INVALID; ++a) {
    7590    check(adaptor.source(a) == digraph.target(a), "Wrong reverse");
    7691    check(adaptor.target(a) == digraph.source(a), "Wrong reverse");
    7792  }
     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;
    78153}
    79154
    80155void checkSubDigraph() {
    81   checkConcept<concepts::Digraph,
    82     SubDigraph<concepts::Digraph,
    83     concepts::Digraph::NodeMap<bool>,
    84     concepts::Digraph::ArcMap<bool> > >();
    85 
     156  // Check concepts
     157  checkConcept<concepts::Digraph, SubDigraph<concepts::Digraph> >();
     158  checkConcept<concepts::Digraph, SubDigraph<ListDigraph> >();
     159  checkConcept<concepts::AlterableDigraphComponent<>,
     160               SubDigraph<ListDigraph> >();
     161  checkConcept<concepts::ExtendableDigraphComponent<>,
     162               SubDigraph<ListDigraph> >();
     163  checkConcept<concepts::ErasableDigraphComponent<>,
     164               SubDigraph<ListDigraph> >();
     165  checkConcept<concepts::ClearableDigraphComponent<>,
     166               SubDigraph<ListDigraph> >();
     167
     168  // Create a digraph and an adaptor
    86169  typedef ListDigraph Digraph;
    87170  typedef Digraph::NodeMap<bool> NodeFilter;
     
    94177  Adaptor adaptor(digraph, node_filter, arc_filter);
    95178
     179  // Add nodes and arcs to the original digraph and the adaptor
    96180  Digraph::Node n1 = digraph.addNode();
    97181  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;
    99185
    100186  Digraph::Arc a1 = digraph.addArc(n1, n2);
    101187  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;
     188  Adaptor::Arc a3 = adaptor.addArc(n2, n3);
     189
    105190  arc_filter[a1] = arc_filter[a2] = arc_filter[a3] = true;
    106191
     
    123208  checkGraphArcMap(adaptor);
    124209
    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);
    126214
    127215  checkGraphNodeList(adaptor, 3);
     
    143231  checkGraphArcMap(adaptor);
    144232
    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);
    146237
    147238  checkGraphNodeList(adaptor, 2);
     
    161252  checkGraphArcMap(adaptor);
    162253
     254  // Hide all nodes and arcs
    163255  node_filter[n1] = node_filter[n2] = node_filter[n3] = false;
    164256  arc_filter[a1] = arc_filter[a2] = arc_filter[a3] = false;
     
    173265  checkGraphNodeMap(adaptor);
    174266  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;
    175277}
    176278
    177279void checkFilterNodes1() {
    178   checkConcept<concepts::Digraph,
    179     FilterNodes<concepts::Digraph,
    180       concepts::Digraph::NodeMap<bool> > >();
    181 
     280  // Check concepts
     281  checkConcept<concepts::Digraph, FilterNodes<concepts::Digraph> >();
     282  checkConcept<concepts::Digraph, FilterNodes<ListDigraph> >();
     283  checkConcept<concepts::AlterableDigraphComponent<>,
     284               FilterNodes<ListDigraph> >();
     285  checkConcept<concepts::ExtendableDigraphComponent<>,
     286               FilterNodes<ListDigraph> >();
     287  checkConcept<concepts::ErasableDigraphComponent<>,
     288               FilterNodes<ListDigraph> >();
     289  checkConcept<concepts::ClearableDigraphComponent<>,
     290               FilterNodes<ListDigraph> >();
     291
     292  // Create a digraph and an adaptor
    182293  typedef ListDigraph Digraph;
    183294  typedef Digraph::NodeMap<bool> NodeFilter;
     
    188299  Adaptor adaptor(digraph, node_filter);
    189300
     301  // Add nodes and arcs to the original digraph and the adaptor
    190302  Digraph::Node n1 = digraph.addNode();
    191303  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;
    193307
    194308  Digraph::Arc a1 = digraph.addArc(n1, n2);
    195309  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;
     310  Adaptor::Arc a3 = adaptor.addArc(n2, n3);
    199311
    200312  checkGraphNodeList(adaptor, 3);
     
    216328  checkGraphArcMap(adaptor);
    217329
    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);
    219334
    220335  checkGraphNodeList(adaptor, 2);
     
    234349  checkGraphArcMap(adaptor);
    235350
     351  // Hide all nodes
    236352  node_filter[n1] = node_filter[n2] = node_filter[n3] = false;
    237353
     
    245361  checkGraphNodeMap(adaptor);
    246362  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;
    247373}
    248374
    249375void checkFilterArcs() {
    250   checkConcept<concepts::Digraph,
    251     FilterArcs<concepts::Digraph,
    252     concepts::Digraph::ArcMap<bool> > >();
    253 
     376  // Check concepts
     377  checkConcept<concepts::Digraph, FilterArcs<concepts::Digraph> >();
     378  checkConcept<concepts::Digraph, FilterArcs<ListDigraph> >();
     379  checkConcept<concepts::AlterableDigraphComponent<>,
     380               FilterArcs<ListDigraph> >();
     381  checkConcept<concepts::ExtendableDigraphComponent<>,
     382               FilterArcs<ListDigraph> >();
     383  checkConcept<concepts::ErasableDigraphComponent<>,
     384               FilterArcs<ListDigraph> >();
     385  checkConcept<concepts::ClearableDigraphComponent<>,
     386               FilterArcs<ListDigraph> >();
     387
     388  // Create a digraph and an adaptor
    254389  typedef ListDigraph Digraph;
    255390  typedef Digraph::ArcMap<bool> ArcFilter;
     
    260395  Adaptor adaptor(digraph, arc_filter);
    261396
     397  // Add nodes and arcs to the original digraph and the adaptor
    262398  Digraph::Node n1 = digraph.addNode();
    263399  Digraph::Node n2 = digraph.addNode();
    264   Digraph::Node n3 = digraph.addNode();
     400  Adaptor::Node n3 = adaptor.addNode();
    265401
    266402  Digraph::Arc a1 = digraph.addArc(n1, n2);
    267403  Digraph::Arc a2 = digraph.addArc(n1, n3);
    268   Digraph::Arc a3 = digraph.addArc(n2, n3);
     404  Adaptor::Arc a3 = adaptor.addArc(n2, n3);
    269405
    270406  arc_filter[a1] = arc_filter[a2] = arc_filter[a3] = true;
     
    288424  checkGraphArcMap(adaptor);
    289425
    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);
    291430
    292431  checkGraphNodeList(adaptor, 3);
     
    308447  checkGraphArcMap(adaptor);
    309448
     449  // Hide all arcs
    310450  arc_filter[a1] = arc_filter[a2] = arc_filter[a3] = false;
    311451
     
    319459  checkGraphNodeMap(adaptor);
    320460  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;
    321471}
    322472
    323473void checkUndirector() {
     474  // Check concepts
    324475  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
    326488  typedef ListDigraph Digraph;
    327489  typedef Undirector<Digraph> Adaptor;
     
    330492  Adaptor adaptor(digraph);
    331493
     494  // Add nodes and arcs/edges to the original digraph and the adaptor
    332495  Digraph::Node n1 = digraph.addNode();
    333496  Digraph::Node n2 = digraph.addNode();
    334   Digraph::Node n3 = digraph.addNode();
     497  Adaptor::Node n3 = adaptor.addNode();
    335498
    336499  Digraph::Arc a1 = digraph.addArc(n1, n2);
    337500  Digraph::Arc a2 = digraph.addArc(n1, n3);
    338   Digraph::Arc a3 = digraph.addArc(n2, n3);
    339 
     501  Adaptor::Edge e3 = adaptor.addEdge(n2, n3);
     502
     503  // Check the original digraph
     504  checkGraphNodeList(digraph, 3);
     505  checkGraphArcList(digraph, 3);
     506  checkGraphConArcList(digraph, 3);
     507
     508  checkGraphOutArcList(digraph, n1, 2);
     509  checkGraphOutArcList(digraph, n2, 1);
     510  checkGraphOutArcList(digraph, n3, 0);
     511
     512  checkGraphInArcList(digraph, n1, 0);
     513  checkGraphInArcList(digraph, n2, 1);
     514  checkGraphInArcList(digraph, n3, 2);
     515
     516  checkNodeIds(digraph);
     517  checkArcIds(digraph);
     518
     519  checkGraphNodeMap(digraph);
     520  checkGraphArcMap(digraph);
     521
     522  // Check the adaptor
    340523  checkGraphNodeList(adaptor, 3);
    341524  checkGraphArcList(adaptor, 6);
     
    344527  checkGraphConEdgeList(adaptor, 3);
    345528
    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);
     529  checkGraphIncEdgeArcLists(adaptor, n1, 2);
     530  checkGraphIncEdgeArcLists(adaptor, n2, 2);
     531  checkGraphIncEdgeArcLists(adaptor, n3, 2);
    357532
    358533  checkNodeIds(adaptor);
     
    364539  checkGraphEdgeMap(adaptor);
    365540
     541  // Check the edges of the adaptor
    366542  for (Adaptor::EdgeIt e(adaptor); e != INVALID; ++e) {
    367543    check(adaptor.u(e) == digraph.source(e), "Wrong undir");
     
    369545  }
    370546
     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;
    371582}
    372583
    373584void checkResidual() {
    374   checkConcept<concepts::Digraph,
    375     Residual<concepts::Digraph,
    376     concepts::Digraph::ArcMap<int>,
    377     concepts::Digraph::ArcMap<int> > >();
    378 
     585  // Check concepts
     586  checkConcept<concepts::Digraph, Residual<concepts::Digraph> >();
     587  checkConcept<concepts::Digraph, Residual<ListDigraph> >();
     588
     589  // Create a digraph and an adaptor
    379590  typedef ListDigraph Digraph;
    380591  typedef Digraph::ArcMap<int> IntArcMap;
     
    404615  capacity[a6] = 10;
    405616
    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) {
    407619    flow[a] = 0;
    408620  }
     
    422634  checkGraphInArcList(adaptor, n4, 3);
    423635
    424   for (Adaptor::ArcIt a(adaptor); a != INVALID; ++a) {
     636  for (Digraph::ArcIt a(digraph); a != INVALID; ++a) {
    425637    flow[a] = capacity[a] / 2;
    426638  }
     
    446658  checkGraphArcMap(adaptor);
    447659
    448   for (Adaptor::ArcIt a(adaptor); a != INVALID; ++a) {
     660  for (Digraph::ArcIt a(digraph); a != INVALID; ++a) {
    449661    flow[a] = capacity[a];
    450662  }
     
    464676  checkGraphInArcList(adaptor, n4, 0);
    465677
     678  // Saturate all backward arcs
     679  // (set the flow to zero on all forward arcs)
    466680  for (Adaptor::ArcIt a(adaptor); a != INVALID; ++a) {
    467     flow[a] = 0;
    468   }
    469 
     681    if (adaptor.backward(a))
     682      adaptor.augment(a, adaptor.residualCapacity(a));
     683  }
     684
     685  checkGraphNodeList(adaptor, 4);
     686  checkGraphArcList(adaptor, 6);
     687  checkGraphConArcList(adaptor, 6);
     688
     689  checkGraphOutArcList(adaptor, n1, 3);
     690  checkGraphOutArcList(adaptor, n2, 2);
     691  checkGraphOutArcList(adaptor, n3, 1);
     692  checkGraphOutArcList(adaptor, n4, 0);
     693
     694  checkGraphInArcList(adaptor, n1, 0);
     695  checkGraphInArcList(adaptor, n2, 1);
     696  checkGraphInArcList(adaptor, n3, 2);
     697  checkGraphInArcList(adaptor, n4, 3);
     698
     699  // Find maximum flow by augmenting along shortest paths
    470700  int flow_value = 0;
     701  Adaptor::ResidualCapacity res_cap(adaptor);
    471702  while (true) {
    472703
     
    480711    int min = std::numeric_limits<int>::max();
    481712    for (Path<Adaptor>::ArcIt a(p); a != INVALID; ++a) {
    482       if (adaptor.residualCapacity(a) < min)
    483         min = adaptor.residualCapacity(a);
     713      if (res_cap[a] < min) min = res_cap[a];
    484714    }
    485715
     
    492722  check(flow_value == 18, "Wrong flow with res graph adaptor");
    493723
     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);
    494740}
    495741
    496742void checkSplitNodes() {
     743  // Check concepts
    497744  checkConcept<concepts::Digraph, SplitNodes<concepts::Digraph> >();
    498 
     745  checkConcept<concepts::Digraph, SplitNodes<ListDigraph> >();
     746
     747  // Create a digraph and an adaptor
    499748  typedef ListDigraph Digraph;
    500749  typedef SplitNodes<Digraph> Adaptor;
     
    535784  checkGraphArcMap(adaptor);
    536785
     786  // Check split
    537787  for (Adaptor::ArcIt a(adaptor); a != INVALID; ++a) {
    538788    if (adaptor.origArc(a)) {
     
    548798    }
    549799  }
     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");
    550860}
    551861
    552862void checkSubGraph() {
    553   checkConcept<concepts::Graph,
    554     SubGraph<concepts::Graph,
    555     concepts::Graph::NodeMap<bool>,
    556     concepts::Graph::EdgeMap<bool> > >();
    557 
     863  // Check concepts
     864  checkConcept<concepts::Graph, SubGraph<concepts::Graph> >();
     865  checkConcept<concepts::Graph, SubGraph<ListGraph> >();
     866  checkConcept<concepts::AlterableGraphComponent<>,
     867               SubGraph<ListGraph> >();
     868  checkConcept<concepts::ExtendableGraphComponent<>,
     869               SubGraph<ListGraph> >();
     870  checkConcept<concepts::ErasableGraphComponent<>,
     871               SubGraph<ListGraph> >();
     872  checkConcept<concepts::ClearableGraphComponent<>,
     873               SubGraph<ListGraph> >();
     874
     875  // Create a graph and an adaptor
    558876  typedef ListGraph Graph;
    559877  typedef Graph::NodeMap<bool> NodeFilter;
     
    566884  Adaptor adaptor(graph, node_filter, edge_filter);
    567885
     886  // Add nodes and edges to the original graph and the adaptor
    568887  Graph::Node n1 = graph.addNode();
    569888  Graph::Node n2 = graph.addNode();
    570   Graph::Node n3 = graph.addNode();
    571   Graph::Node n4 = graph.addNode();
     889  Adaptor::Node n3 = adaptor.addNode();
     890  Adaptor::Node n4 = adaptor.addNode();
     891
     892  node_filter[n1] = node_filter[n2] = node_filter[n3] = node_filter[n4] = true;
    572893
    573894  Graph::Edge e1 = graph.addEdge(n1, n2);
    574895  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;
     896  Adaptor::Edge e3 = adaptor.addEdge(n2, n3);
     897  Adaptor::Edge e4 = adaptor.addEdge(n3, n4);
     898
    579899  edge_filter[e1] = edge_filter[e2] = edge_filter[e3] = edge_filter[e4] = true;
    580900
     
    585905  checkGraphConEdgeList(adaptor, 4);
    586906
    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);
     907  checkGraphIncEdgeArcLists(adaptor, n1, 2);
     908  checkGraphIncEdgeArcLists(adaptor, n2, 2);
     909  checkGraphIncEdgeArcLists(adaptor, n3, 3);
     910  checkGraphIncEdgeArcLists(adaptor, n4, 1);
    601911
    602912  checkNodeIds(adaptor);
     
    608918  checkGraphEdgeMap(adaptor);
    609919
    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);
    611924
    612925  checkGraphNodeList(adaptor, 4);
     
    616929  checkGraphConEdgeList(adaptor, 3);
    617930
    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);
     931  checkGraphIncEdgeArcLists(adaptor, n1, 1);
     932  checkGraphIncEdgeArcLists(adaptor, n2, 2);
     933  checkGraphIncEdgeArcLists(adaptor, n3, 2);
     934  checkGraphIncEdgeArcLists(adaptor, n4, 1);
    632935
    633936  checkNodeIds(adaptor);
     
    639942  checkGraphEdgeMap(adaptor);
    640943
    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);
    642948
    643949  checkGraphNodeList(adaptor, 3);
     
    647953  checkGraphConEdgeList(adaptor, 2);
    648954
    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);
     955  checkGraphIncEdgeArcLists(adaptor, n2, 1);
     956  checkGraphIncEdgeArcLists(adaptor, n3, 2);
     957  checkGraphIncEdgeArcLists(adaptor, n4, 1);
    660958
    661959  checkNodeIds(adaptor);
     
    667965  checkGraphEdgeMap(adaptor);
    668966
     967  // Hide all nodes and edges
    669968  node_filter[n1] = node_filter[n2] = node_filter[n3] = node_filter[n4] = false;
    670969  edge_filter[e1] = edge_filter[e2] = edge_filter[e3] = edge_filter[e4] = false;
     
    683982  checkGraphArcMap(adaptor);
    684983  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;
    685994}
    686995
    687996void checkFilterNodes2() {
    688   checkConcept<concepts::Graph,
    689     FilterNodes<concepts::Graph,
    690       concepts::Graph::NodeMap<bool> > >();
    691 
     997  // Check concepts
     998  checkConcept<concepts::Graph, FilterNodes<concepts::Graph> >();
     999  checkConcept<concepts::Graph, FilterNodes<ListGraph> >();
     1000  checkConcept<concepts::AlterableGraphComponent<>,
     1001               FilterNodes<ListGraph> >();
     1002  checkConcept<concepts::ExtendableGraphComponent<>,
     1003               FilterNodes<ListGraph> >();
     1004  checkConcept<concepts::ErasableGraphComponent<>,
     1005               FilterNodes<ListGraph> >();
     1006  checkConcept<concepts::ClearableGraphComponent<>,
     1007               FilterNodes<ListGraph> >();
     1008
     1009  // Create a graph and an adaptor
    6921010  typedef ListGraph Graph;
    6931011  typedef Graph::NodeMap<bool> NodeFilter;
    6941012  typedef FilterNodes<Graph, NodeFilter> Adaptor;
    6951013
     1014  // Add nodes and edges to the original graph and the adaptor
    6961015  Graph graph;
    6971016  NodeFilter node_filter(graph);
     
    7001019  Graph::Node n1 = graph.addNode();
    7011020  Graph::Node n2 = graph.addNode();
    702   Graph::Node n3 = graph.addNode();
    703   Graph::Node n4 = graph.addNode();
     1021  Adaptor::Node n3 = adaptor.addNode();
     1022  Adaptor::Node n4 = adaptor.addNode();
     1023
     1024  node_filter[n1] = node_filter[n2] = node_filter[n3] = node_filter[n4] = true;
    7041025
    7051026  Graph::Edge e1 = graph.addEdge(n1, n2);
    7061027  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;
     1028  Adaptor::Edge e3 = adaptor.addEdge(n2, n3);
     1029  Adaptor::Edge e4 = adaptor.addEdge(n3, n4);
    7111030
    7121031  checkGraphNodeList(adaptor, 4);
     
    7161035  checkGraphConEdgeList(adaptor, 4);
    7171036
    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);
     1037  checkGraphIncEdgeArcLists(adaptor, n1, 2);
     1038  checkGraphIncEdgeArcLists(adaptor, n2, 2);
     1039  checkGraphIncEdgeArcLists(adaptor, n3, 3);
     1040  checkGraphIncEdgeArcLists(adaptor, n4, 1);
    7321041
    7331042  checkNodeIds(adaptor);
     
    7391048  checkGraphEdgeMap(adaptor);
    7401049
    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);
    7421054
    7431055  checkGraphNodeList(adaptor, 3);
     
    7471059  checkGraphConEdgeList(adaptor, 2);
    7481060
    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);
     1061  checkGraphIncEdgeArcLists(adaptor, n2, 1);
     1062  checkGraphIncEdgeArcLists(adaptor, n3, 2);
     1063  checkGraphIncEdgeArcLists(adaptor, n4, 1);
    7601064
    7611065  checkNodeIds(adaptor);
     
    7671071  checkGraphEdgeMap(adaptor);
    7681072
     1073  // Hide all nodes
    7691074  node_filter[n1] = node_filter[n2] = node_filter[n3] = node_filter[n4] = false;
    7701075
     
    7821087  checkGraphArcMap(adaptor);
    7831088  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;
    7841099}
    7851100
    7861101void checkFilterEdges() {
    787   checkConcept<concepts::Graph,
    788     FilterEdges<concepts::Graph,
    789     concepts::Graph::EdgeMap<bool> > >();
    790 
     1102  // Check concepts
     1103  checkConcept<concepts::Graph, FilterEdges<concepts::Graph> >();
     1104  checkConcept<concepts::Graph, FilterEdges<ListGraph> >();
     1105  checkConcept<concepts::AlterableGraphComponent<>,
     1106               FilterEdges<ListGraph> >();
     1107  checkConcept<concepts::ExtendableGraphComponent<>,
     1108               FilterEdges<ListGraph> >();
     1109  checkConcept<concepts::ErasableGraphComponent<>,
     1110               FilterEdges<ListGraph> >();
     1111  checkConcept<concepts::ClearableGraphComponent<>,
     1112               FilterEdges<ListGraph> >();
     1113
     1114  // Create a graph and an adaptor
    7911115  typedef ListGraph Graph;
    7921116  typedef Graph::EdgeMap<bool> EdgeFilter;
     
    7971121  Adaptor adaptor(graph, edge_filter);
    7981122
     1123  // Add nodes and edges to the original graph and the adaptor
    7991124  Graph::Node n1 = graph.addNode();
    8001125  Graph::Node n2 = graph.addNode();
    801   Graph::Node n3 = graph.addNode();
    802   Graph::Node n4 = graph.addNode();
     1126  Adaptor::Node n3 = adaptor.addNode();
     1127  Adaptor::Node n4 = adaptor.addNode();
    8031128
    8041129  Graph::Edge e1 = graph.addEdge(n1, n2);
    8051130  Graph::Edge e2 = graph.addEdge(n1, n3);
    806   Graph::Edge e3 = graph.addEdge(n2, n3);
    807   Graph::Edge e4 = graph.addEdge(n3, n4);
     1131  Adaptor::Edge e3 = adaptor.addEdge(n2, n3);
     1132  Adaptor::Edge e4 = adaptor.addEdge(n3, n4);
    8081133
    8091134  edge_filter[e1] = edge_filter[e2] = edge_filter[e3] = edge_filter[e4] = true;
     
    8151140  checkGraphConEdgeList(adaptor, 4);
    8161141
    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);
     1142  checkGraphIncEdgeArcLists(adaptor, n1, 2);
     1143  checkGraphIncEdgeArcLists(adaptor, n2, 2);
     1144  checkGraphIncEdgeArcLists(adaptor, n3, 3);
     1145  checkGraphIncEdgeArcLists(adaptor, n4, 1);
    8311146
    8321147  checkNodeIds(adaptor);
     
    8381153  checkGraphEdgeMap(adaptor);
    8391154
    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);
    8411159
    8421160  checkGraphNodeList(adaptor, 4);
     
    8461164  checkGraphConEdgeList(adaptor, 3);
    8471165
    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);
     1166  checkGraphIncEdgeArcLists(adaptor, n1, 1);
     1167  checkGraphIncEdgeArcLists(adaptor, n2, 2);
     1168  checkGraphIncEdgeArcLists(adaptor, n3, 2);
     1169  checkGraphIncEdgeArcLists(adaptor, n4, 1);
    8621170
    8631171  checkNodeIds(adaptor);
     
    8691177  checkGraphEdgeMap(adaptor);
    8701178
     1179  // Hide all edges
    8711180  edge_filter[e1] = edge_filter[e2] = edge_filter[e3] = edge_filter[e4] = false;
    8721181
     
    8841193  checkGraphArcMap(adaptor);
    8851194  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;
    8861205}
    8871206
    8881207void checkOrienter() {
    889   checkConcept<concepts::Digraph,
    890     Orienter<concepts::Graph, concepts::Graph::EdgeMap<bool> > >();
    891 
     1208  // Check concepts
     1209  checkConcept<concepts::Digraph, Orienter<concepts::Graph> >();
     1210  checkConcept<concepts::Digraph, Orienter<ListGraph> >();
     1211  checkConcept<concepts::AlterableDigraphComponent<>,
     1212               Orienter<ListGraph> >();
     1213  checkConcept<concepts::ExtendableDigraphComponent<>,
     1214               Orienter<ListGraph> >();
     1215  checkConcept<concepts::ErasableDigraphComponent<>,
     1216               Orienter<ListGraph> >();
     1217  checkConcept<concepts::ClearableDigraphComponent<>,
     1218               Orienter<ListGraph> >();
     1219
     1220  // Create a graph and an adaptor
    8921221  typedef ListGraph Graph;
    8931222  typedef ListGraph::EdgeMap<bool> DirMap;
     
    8951224
    8961225  Graph graph;
    897   DirMap dir(graph, true);
     1226  DirMap dir(graph);
    8981227  Adaptor adaptor(graph, dir);
    8991228
     1229  // Add nodes and edges to the original graph and the adaptor
    9001230  Graph::Node n1 = graph.addNode();
    9011231  Graph::Node n2 = graph.addNode();
    902   Graph::Node n3 = graph.addNode();
     1232  Adaptor::Node n3 = adaptor.addNode();
    9031233
    9041234  Graph::Edge e1 = graph.addEdge(n1, n2);
    9051235  Graph::Edge e2 = graph.addEdge(n1, n3);
    906   Graph::Edge e3 = graph.addEdge(n2, n3);
    907 
     1236  Adaptor::Arc e3 = adaptor.addArc(n2, n3);
     1237
     1238  dir[e1] = dir[e2] = dir[e3] = true;
     1239
     1240  // Check the original graph
     1241  checkGraphNodeList(graph, 3);
     1242  checkGraphArcList(graph, 6);
     1243  checkGraphConArcList(graph, 6);
     1244  checkGraphEdgeList(graph, 3);
     1245  checkGraphConEdgeList(graph, 3);
     1246
     1247  checkGraphIncEdgeArcLists(graph, n1, 2);
     1248  checkGraphIncEdgeArcLists(graph, n2, 2);
     1249  checkGraphIncEdgeArcLists(graph, n3, 2);
     1250
     1251  checkNodeIds(graph);
     1252  checkArcIds(graph);
     1253  checkEdgeIds(graph);
     1254
     1255  checkGraphNodeMap(graph);
     1256  checkGraphArcMap(graph);
     1257  checkGraphEdgeMap(graph);
     1258
     1259  // Check the adaptor
    9081260  checkGraphNodeList(adaptor, 3);
    9091261  checkGraphArcList(adaptor, 3);
    9101262  checkGraphConArcList(adaptor, 3);
    9111263
     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
    9121279  {
    9131280    dir[e1] = true;
     
    9491316  }
    9501317
     1318  // Check the adaptor again
     1319  checkGraphNodeList(adaptor, 3);
     1320  checkGraphArcList(adaptor, 3);
     1321  checkGraphConArcList(adaptor, 3);
     1322
    9511323  checkGraphOutArcList(adaptor, n1, 1);
    9521324  checkGraphOutArcList(adaptor, n2, 1);
     
    9631335  checkGraphArcMap(adaptor);
    9641336
     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;
    9651363}
    9661364
     1365void 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}
    9671465
    9681466int main(int, const char **) {
    969 
     1467  // Check the digraph adaptors (using ListDigraph)
    9701468  checkReverseDigraph();
    9711469  checkSubDigraph();
     
    9761474  checkSplitNodes();
    9771475
     1476  // Check the graph adaptors (using ListGraph)
    9781477  checkSubGraph();
    9791478  checkFilterNodes2();
     
    9811480  checkOrienter();
    9821481
     1482  // Combine adaptors (using GridGraph)
     1483  checkCombiningAdaptors();
     1484
    9831485  return 0;
    9841486}
Note: See TracChangeset for help on using the changeset viewer.