lemon-1.3: test/adaptors_test.cc@f7247b5c04bf

     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-2009

     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  */

    19 #include <iostream>

    20 #include <limits>

    22 #include <lemon/list_graph.h>

    23 #include <lemon/grid_graph.h>

    24 #include <lemon/bfs.h>

    25 #include <lemon/path.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>

    33 #include <lemon/adaptors.h>

    35 #include "test/test_tools.h"

    36 #include "test/graph_test.h"

    38 using namespace lemon;

    40 void checkReverseDigraph() {

    41   // Check concepts

    42   checkConcept<concepts::Digraph, ReverseDigraph<concepts::Digraph> >();

    43   checkConcept<concepts::Digraph, ReverseDigraph<ListDigraph> >();

    44   checkConcept<concepts::AlterableDigraphComponent<>,

    45                ReverseDigraph<ListDigraph> >();

    46   checkConcept<concepts::ExtendableDigraphComponent<>,

    47                ReverseDigraph<ListDigraph> >();

    48   checkConcept<concepts::ErasableDigraphComponent<>,

    49                ReverseDigraph<ListDigraph> >();

    50   checkConcept<concepts::ClearableDigraphComponent<>,

    51                ReverseDigraph<ListDigraph> >();

    53   // Create a digraph and an adaptor

    54   typedef ListDigraph Digraph;

    55   typedef ReverseDigraph<Digraph> Adaptor;

    57   Digraph digraph;

    58   Adaptor adaptor(digraph);

    60   // Add nodes and arcs to the original digraph

    61   Digraph::Node n1 = digraph.addNode();

    62   Digraph::Node n2 = digraph.addNode();

    63   Digraph::Node n3 = digraph.addNode();

    65   Digraph::Arc a1 = digraph.addArc(n1, n2);

    66   Digraph::Arc a2 = digraph.addArc(n1, n3);

    67   Digraph::Arc a3 = digraph.addArc(n2, n3);

    68   ignore_unused_variable_warning(a3);

    70   // Check the adaptor

    71   checkGraphNodeList(adaptor, 3);

    72   checkGraphArcList(adaptor, 3);

    73   checkGraphConArcList(adaptor, 3);

    75   checkGraphOutArcList(adaptor, n1, 0);

    76   checkGraphOutArcList(adaptor, n2, 1);

    77   checkGraphOutArcList(adaptor, n3, 2);

    79   checkGraphInArcList(adaptor, n1, 2);

    80   checkGraphInArcList(adaptor, n2, 1);

    81   checkGraphInArcList(adaptor, n3, 0);

    83   checkNodeIds(adaptor);

    84   checkArcIds(adaptor);

    86   checkGraphNodeMap(adaptor);

    87   checkGraphArcMap(adaptor);

    89   // Check the orientation of the arcs

    90   for (Adaptor::ArcIt a(adaptor); a != INVALID; ++a) {

    91     check(adaptor.source(a) == digraph.target(a), "Wrong reverse");

    92     check(adaptor.target(a) == digraph.source(a), "Wrong reverse");

    93   }

    95   // Add and erase nodes and arcs in the digraph through the adaptor

    96   Adaptor::Node n4 = adaptor.addNode();

    98   Adaptor::Arc a4 = adaptor.addArc(n4, n3);

    99   Adaptor::Arc a5 = adaptor.addArc(n2, n4);

   100   Adaptor::Arc a6 = adaptor.addArc(n2, n4);

   101   Adaptor::Arc a7 = adaptor.addArc(n1, n4);

   102   Adaptor::Arc a8 = adaptor.addArc(n1, n2);

   103   ignore_unused_variable_warning(a6,a7,a8);

   105   adaptor.erase(a1);

   106   adaptor.erase(n3);

   108   // Check the adaptor

   109   checkGraphNodeList(adaptor, 3);

   110   checkGraphArcList(adaptor, 4);

   111   checkGraphConArcList(adaptor, 4);

   113   checkGraphOutArcList(adaptor, n1, 2);

   114   checkGraphOutArcList(adaptor, n2, 2);

   115   checkGraphOutArcList(adaptor, n4, 0);

   117   checkGraphInArcList(adaptor, n1, 0);

   118   checkGraphInArcList(adaptor, n2, 1);

   119   checkGraphInArcList(adaptor, n4, 3);

   121   checkNodeIds(adaptor);

   122   checkArcIds(adaptor);

   124   checkGraphNodeMap(adaptor);

   125   checkGraphArcMap(adaptor);

   127   // Check the digraph

   128   checkGraphNodeList(digraph, 3);

   129   checkGraphArcList(digraph, 4);

   130   checkGraphConArcList(digraph, 4);

   132   checkGraphOutArcList(digraph, n1, 0);

   133   checkGraphOutArcList(digraph, n2, 1);

   134   checkGraphOutArcList(digraph, n4, 3);

   136   checkGraphInArcList(digraph, n1, 2);

   137   checkGraphInArcList(digraph, n2, 2);

   138   checkGraphInArcList(digraph, n4, 0);

   140   checkNodeIds(digraph);

   141   checkArcIds(digraph);

   143   checkGraphNodeMap(digraph);

   144   checkGraphArcMap(digraph);

   146   // Check the conversion of nodes and arcs

   147   Digraph::Node nd = n4;

   148   nd = n4;

   149   Adaptor::Node na = n1;

   150   na = n2;

   151   Digraph::Arc ad = a4;

   152   ad = a5;

   153   Adaptor::Arc aa = a1;

   154   aa = a2;

   155 }

   157 void checkSubDigraph() {

   158   // Check concepts

   159   checkConcept<concepts::Digraph, SubDigraph<concepts::Digraph> >();

   160   checkConcept<concepts::Digraph, SubDigraph<ListDigraph> >();

   161   checkConcept<concepts::AlterableDigraphComponent<>,

   162                SubDigraph<ListDigraph> >();

   163   checkConcept<concepts::ExtendableDigraphComponent<>,

   164                SubDigraph<ListDigraph> >();

   165   checkConcept<concepts::ErasableDigraphComponent<>,

   166                SubDigraph<ListDigraph> >();

   167   checkConcept<concepts::ClearableDigraphComponent<>,

   168                SubDigraph<ListDigraph> >();

   170   // Create a digraph and an adaptor

   171   typedef ListDigraph Digraph;

   172   typedef Digraph::NodeMap<bool> NodeFilter;

   173   typedef Digraph::ArcMap<bool> ArcFilter;

   174   typedef SubDigraph<Digraph, NodeFilter, ArcFilter> Adaptor;

   176   Digraph digraph;

   177   NodeFilter node_filter(digraph);

   178   ArcFilter arc_filter(digraph);

   179   Adaptor adaptor(digraph, node_filter, arc_filter);

   181   // Add nodes and arcs to the original digraph and the adaptor

   182   Digraph::Node n1 = digraph.addNode();

   183   Digraph::Node n2 = digraph.addNode();

   184   Adaptor::Node n3 = adaptor.addNode();

   186   node_filter[n1] = node_filter[n2] = node_filter[n3] = true;

   188   Digraph::Arc a1 = digraph.addArc(n1, n2);

   189   Digraph::Arc a2 = digraph.addArc(n1, n3);

   190   Adaptor::Arc a3 = adaptor.addArc(n2, n3);

   192   arc_filter[a1] = arc_filter[a2] = arc_filter[a3] = true;

   194   checkGraphNodeList(adaptor, 3);

   195   checkGraphArcList(adaptor, 3);

   196   checkGraphConArcList(adaptor, 3);

   198   checkGraphOutArcList(adaptor, n1, 2);

   199   checkGraphOutArcList(adaptor, n2, 1);

   200   checkGraphOutArcList(adaptor, n3, 0);

   202   checkGraphInArcList(adaptor, n1, 0);

   203   checkGraphInArcList(adaptor, n2, 1);

   204   checkGraphInArcList(adaptor, n3, 2);

   206   checkNodeIds(adaptor);

   207   checkArcIds(adaptor);

   209   checkGraphNodeMap(adaptor);

   210   checkGraphArcMap(adaptor);

   212   // Hide an arc

   213   adaptor.status(a2, false);

   214   adaptor.disable(a3);

   215   if (!adaptor.status(a3)) adaptor.enable(a3);

   217   checkGraphNodeList(adaptor, 3);

   218   checkGraphArcList(adaptor, 2);

   219   checkGraphConArcList(adaptor, 2);

   221   checkGraphOutArcList(adaptor, n1, 1);

   222   checkGraphOutArcList(adaptor, n2, 1);

   223   checkGraphOutArcList(adaptor, n3, 0);

   225   checkGraphInArcList(adaptor, n1, 0);

   226   checkGraphInArcList(adaptor, n2, 1);

   227   checkGraphInArcList(adaptor, n3, 1);

   229   checkNodeIds(adaptor);

   230   checkArcIds(adaptor);

   232   checkGraphNodeMap(adaptor);

   233   checkGraphArcMap(adaptor);

   235   // Hide a node

   236   adaptor.status(n1, false);

   237   adaptor.disable(n3);

   238   if (!adaptor.status(n3)) adaptor.enable(n3);

   240   checkGraphNodeList(adaptor, 2);

   241   checkGraphArcList(adaptor, 1);

   242   checkGraphConArcList(adaptor, 1);

   244   checkGraphOutArcList(adaptor, n2, 1);

   245   checkGraphOutArcList(adaptor, n3, 0);

   247   checkGraphInArcList(adaptor, n2, 0);

   248   checkGraphInArcList(adaptor, n3, 1);

   250   checkNodeIds(adaptor);

   251   checkArcIds(adaptor);

   253   checkGraphNodeMap(adaptor);

   254   checkGraphArcMap(adaptor);

   256   // Hide all nodes and arcs

   257   node_filter[n1] = node_filter[n2] = node_filter[n3] = false;

   258   arc_filter[a1] = arc_filter[a2] = arc_filter[a3] = false;

   260   checkGraphNodeList(adaptor, 0);

   261   checkGraphArcList(adaptor, 0);

   262   checkGraphConArcList(adaptor, 0);

   264   checkNodeIds(adaptor);

   265   checkArcIds(adaptor);

   267   checkGraphNodeMap(adaptor);

   268   checkGraphArcMap(adaptor);

   270   // Check the conversion of nodes and arcs

   271   Digraph::Node nd = n3;

   272   nd = n3;

   273   Adaptor::Node na = n1;

   274   na = n2;

   275   Digraph::Arc ad = a3;

   276   ad = a3;

   277   Adaptor::Arc aa = a1;

   278   aa = a2;

   279 }

   281 void checkFilterNodes1() {

   282   // Check concepts

   283   checkConcept<concepts::Digraph, FilterNodes<concepts::Digraph> >();

   284   checkConcept<concepts::Digraph, FilterNodes<ListDigraph> >();

   285   checkConcept<concepts::AlterableDigraphComponent<>,

   286                FilterNodes<ListDigraph> >();

   287   checkConcept<concepts::ExtendableDigraphComponent<>,

   288                FilterNodes<ListDigraph> >();

   289   checkConcept<concepts::ErasableDigraphComponent<>,

   290                FilterNodes<ListDigraph> >();

   291   checkConcept<concepts::ClearableDigraphComponent<>,

   292                FilterNodes<ListDigraph> >();

   294   // Create a digraph and an adaptor

   295   typedef ListDigraph Digraph;

   296   typedef Digraph::NodeMap<bool> NodeFilter;

   297   typedef FilterNodes<Digraph, NodeFilter> Adaptor;

   299   Digraph digraph;

   300   NodeFilter node_filter(digraph);

   301   Adaptor adaptor(digraph, node_filter);

   303   // Add nodes and arcs to the original digraph and the adaptor

   304   Digraph::Node n1 = digraph.addNode();

   305   Digraph::Node n2 = digraph.addNode();

   306   Adaptor::Node n3 = adaptor.addNode();

   308   node_filter[n1] = node_filter[n2] = node_filter[n3] = true;

   310   Digraph::Arc a1 = digraph.addArc(n1, n2);

   311   Digraph::Arc a2 = digraph.addArc(n1, n3);

   312   Adaptor::Arc a3 = adaptor.addArc(n2, n3);

   314   checkGraphNodeList(adaptor, 3);

   315   checkGraphArcList(adaptor, 3);

   316   checkGraphConArcList(adaptor, 3);

   318   checkGraphOutArcList(adaptor, n1, 2);

   319   checkGraphOutArcList(adaptor, n2, 1);

   320   checkGraphOutArcList(adaptor, n3, 0);

   322   checkGraphInArcList(adaptor, n1, 0);

   323   checkGraphInArcList(adaptor, n2, 1);

   324   checkGraphInArcList(adaptor, n3, 2);

   326   checkNodeIds(adaptor);

   327   checkArcIds(adaptor);

   329   checkGraphNodeMap(adaptor);

   330   checkGraphArcMap(adaptor);

   332   // Hide a node

   333   adaptor.status(n1, false);

   334   adaptor.disable(n3);

   335   if (!adaptor.status(n3)) adaptor.enable(n3);

   337   checkGraphNodeList(adaptor, 2);

   338   checkGraphArcList(adaptor, 1);

   339   checkGraphConArcList(adaptor, 1);

   341   checkGraphOutArcList(adaptor, n2, 1);

   342   checkGraphOutArcList(adaptor, n3, 0);

   344   checkGraphInArcList(adaptor, n2, 0);

   345   checkGraphInArcList(adaptor, n3, 1);

   347   checkNodeIds(adaptor);

   348   checkArcIds(adaptor);

   350   checkGraphNodeMap(adaptor);

   351   checkGraphArcMap(adaptor);

   353   // Hide all nodes

   354   node_filter[n1] = node_filter[n2] = node_filter[n3] = false;

   356   checkGraphNodeList(adaptor, 0);

   357   checkGraphArcList(adaptor, 0);

   358   checkGraphConArcList(adaptor, 0);

   360   checkNodeIds(adaptor);

   361   checkArcIds(adaptor);

   363   checkGraphNodeMap(adaptor);

   364   checkGraphArcMap(adaptor);

   366   // Check the conversion of nodes and arcs

   367   Digraph::Node nd = n3;

   368   nd = n3;

   369   Adaptor::Node na = n1;

   370   na = n2;

   371   Digraph::Arc ad = a3;

   372   ad = a3;

   373   Adaptor::Arc aa = a1;

   374   aa = a2;

   375 }

   377 void checkFilterArcs() {

   378   // Check concepts

   379   checkConcept<concepts::Digraph, FilterArcs<concepts::Digraph> >();

   380   checkConcept<concepts::Digraph, FilterArcs<ListDigraph> >();

   381   checkConcept<concepts::AlterableDigraphComponent<>,

   382                FilterArcs<ListDigraph> >();

   383   checkConcept<concepts::ExtendableDigraphComponent<>,

   384                FilterArcs<ListDigraph> >();

   385   checkConcept<concepts::ErasableDigraphComponent<>,

   386                FilterArcs<ListDigraph> >();

   387   checkConcept<concepts::ClearableDigraphComponent<>,

   388                FilterArcs<ListDigraph> >();

   390   // Create a digraph and an adaptor

   391   typedef ListDigraph Digraph;

   392   typedef Digraph::ArcMap<bool> ArcFilter;

   393   typedef FilterArcs<Digraph, ArcFilter> Adaptor;

   395   Digraph digraph;

   396   ArcFilter arc_filter(digraph);

   397   Adaptor adaptor(digraph, arc_filter);

   399   // Add nodes and arcs to the original digraph and the adaptor

   400   Digraph::Node n1 = digraph.addNode();

   401   Digraph::Node n2 = digraph.addNode();

   402   Adaptor::Node n3 = adaptor.addNode();

   404   Digraph::Arc a1 = digraph.addArc(n1, n2);

   405   Digraph::Arc a2 = digraph.addArc(n1, n3);

   406   Adaptor::Arc a3 = adaptor.addArc(n2, n3);

   408   arc_filter[a1] = arc_filter[a2] = arc_filter[a3] = true;

   410   checkGraphNodeList(adaptor, 3);

   411   checkGraphArcList(adaptor, 3);

   412   checkGraphConArcList(adaptor, 3);

   414   checkGraphOutArcList(adaptor, n1, 2);

   415   checkGraphOutArcList(adaptor, n2, 1);

   416   checkGraphOutArcList(adaptor, n3, 0);

   418   checkGraphInArcList(adaptor, n1, 0);

   419   checkGraphInArcList(adaptor, n2, 1);

   420   checkGraphInArcList(adaptor, n3, 2);

   422   checkNodeIds(adaptor);

   423   checkArcIds(adaptor);

   425   checkGraphNodeMap(adaptor);

   426   checkGraphArcMap(adaptor);

   428   // Hide an arc

   429   adaptor.status(a2, false);

   430   adaptor.disable(a3);

   431   if (!adaptor.status(a3)) adaptor.enable(a3);

   433   checkGraphNodeList(adaptor, 3);

   434   checkGraphArcList(adaptor, 2);

   435   checkGraphConArcList(adaptor, 2);

   437   checkGraphOutArcList(adaptor, n1, 1);

   438   checkGraphOutArcList(adaptor, n2, 1);

   439   checkGraphOutArcList(adaptor, n3, 0);

   441   checkGraphInArcList(adaptor, n1, 0);

   442   checkGraphInArcList(adaptor, n2, 1);

   443   checkGraphInArcList(adaptor, n3, 1);

   445   checkNodeIds(adaptor);

   446   checkArcIds(adaptor);

   448   checkGraphNodeMap(adaptor);

   449   checkGraphArcMap(adaptor);

   451   // Hide all arcs

   452   arc_filter[a1] = arc_filter[a2] = arc_filter[a3] = false;

   454   checkGraphNodeList(adaptor, 3);

   455   checkGraphArcList(adaptor, 0);

   456   checkGraphConArcList(adaptor, 0);

   458   checkNodeIds(adaptor);

   459   checkArcIds(adaptor);

   461   checkGraphNodeMap(adaptor);

   462   checkGraphArcMap(adaptor);

   464   // Check the conversion of nodes and arcs

   465   Digraph::Node nd = n3;

   466   nd = n3;

   467   Adaptor::Node na = n1;

   468   na = n2;

   469   Digraph::Arc ad = a3;

   470   ad = a3;

   471   Adaptor::Arc aa = a1;

   472   aa = a2;

   473 }

   475 void checkUndirector() {

   476   // Check concepts

   477   checkConcept<concepts::Graph, Undirector<concepts::Digraph> >();

   478   checkConcept<concepts::Graph, Undirector<ListDigraph> >();

   479   checkConcept<concepts::AlterableGraphComponent<>,

   480                Undirector<ListDigraph> >();

   481   checkConcept<concepts::ExtendableGraphComponent<>,

   482                Undirector<ListDigraph> >();

   483   checkConcept<concepts::ErasableGraphComponent<>,

   484                Undirector<ListDigraph> >();

   485   checkConcept<concepts::ClearableGraphComponent<>,

   486                Undirector<ListDigraph> >();

   489   // Create a digraph and an adaptor

   490   typedef ListDigraph Digraph;

   491   typedef Undirector<Digraph> Adaptor;

   493   Digraph digraph;

   494   Adaptor adaptor(digraph);

   496   // Add nodes and arcs/edges to the original digraph and the adaptor

   497   Digraph::Node n1 = digraph.addNode();

   498   Digraph::Node n2 = digraph.addNode();

   499   Adaptor::Node n3 = adaptor.addNode();

   501   Digraph::Arc a1 = digraph.addArc(n1, n2);

   502   Digraph::Arc a2 = digraph.addArc(n1, n3);

   503   Adaptor::Edge e3 = adaptor.addEdge(n2, n3);

   505   // Check the original digraph

   506   checkGraphNodeList(digraph, 3);

   507   checkGraphArcList(digraph, 3);

   508   checkGraphConArcList(digraph, 3);

   510   checkGraphOutArcList(digraph, n1, 2);

   511   checkGraphOutArcList(digraph, n2, 1);

   512   checkGraphOutArcList(digraph, n3, 0);

   514   checkGraphInArcList(digraph, n1, 0);

   515   checkGraphInArcList(digraph, n2, 1);

   516   checkGraphInArcList(digraph, n3, 2);

   518   checkNodeIds(digraph);

   519   checkArcIds(digraph);

   521   checkGraphNodeMap(digraph);

   522   checkGraphArcMap(digraph);

   524   // Check the adaptor

   525   checkGraphNodeList(adaptor, 3);

   526   checkGraphArcList(adaptor, 6);

   527   checkGraphEdgeList(adaptor, 3);

   528   checkGraphConArcList(adaptor, 6);

   529   checkGraphConEdgeList(adaptor, 3);

   531   checkGraphIncEdgeArcLists(adaptor, n1, 2);

   532   checkGraphIncEdgeArcLists(adaptor, n2, 2);

   533   checkGraphIncEdgeArcLists(adaptor, n3, 2);

   535   checkNodeIds(adaptor);

   536   checkArcIds(adaptor);

   537   checkEdgeIds(adaptor);

   539   checkGraphNodeMap(adaptor);

   540   checkGraphArcMap(adaptor);

   541   checkGraphEdgeMap(adaptor);

   543   // Check the edges of the adaptor

   544   for (Adaptor::EdgeIt e(adaptor); e != INVALID; ++e) {

   545     check(adaptor.u(e) == digraph.source(e), "Wrong undir");

   546     check(adaptor.v(e) == digraph.target(e), "Wrong undir");

   547   }

   549   // Check CombinedArcMap

   550   typedef Adaptor::CombinedArcMap

   551     <Digraph::ArcMap<int>, Digraph::ArcMap<int> > IntCombinedMap;

   552   typedef Adaptor::CombinedArcMap

   553     <Digraph::ArcMap<bool>, Digraph::ArcMap<bool> > BoolCombinedMap;

   554   checkConcept<concepts::ReferenceMap<Adaptor::Arc, int, int&, const int&>,

   555     IntCombinedMap>();

   556   checkConcept<concepts::ReferenceMap<Adaptor::Arc, bool, bool&, const bool&>,

   557     BoolCombinedMap>();

   559   Digraph::ArcMap<int> fw_map(digraph), bk_map(digraph);

   560   for (Digraph::ArcIt a(digraph); a != INVALID; ++a) {

   561     fw_map[a] = digraph.id(a);

   562     bk_map[a] = -digraph.id(a);

   563   }

   565   Adaptor::CombinedArcMap<Digraph::ArcMap<int>, Digraph::ArcMap<int> >

   566     comb_map(fw_map, bk_map);

   567   for (Adaptor::ArcIt a(adaptor); a != INVALID; ++a) {

   568     if (adaptor.source(a) == digraph.source(a)) {

   569       check(comb_map[a] == fw_map[a], "Wrong combined map");

   570     } else {

   571       check(comb_map[a] == bk_map[a], "Wrong combined map");

   572     }

   573   }

   575   // Check the conversion of nodes and arcs/edges

   576   Digraph::Node nd = n3;

   577   nd = n3;

   578   Adaptor::Node na = n1;

   579   na = n2;

   580   Digraph::Arc ad = e3;

   581   ad = e3;

   582   Adaptor::Edge ea = a1;

   583   ea = a2;

   584 }

   586 void checkResidualDigraph() {

   587   // Check concepts

   588   checkConcept<concepts::Digraph, ResidualDigraph<concepts::Digraph> >();

   589   checkConcept<concepts::Digraph, ResidualDigraph<ListDigraph> >();

   591   // Create a digraph and an adaptor

   592   typedef ListDigraph Digraph;

   593   typedef Digraph::ArcMap<int> IntArcMap;

   594   typedef ResidualDigraph<Digraph, IntArcMap> Adaptor;

   596   Digraph digraph;

   597   IntArcMap capacity(digraph), flow(digraph);

   598   Adaptor adaptor(digraph, capacity, flow);

   600   Digraph::Node n1 = digraph.addNode();

   601   Digraph::Node n2 = digraph.addNode();

   602   Digraph::Node n3 = digraph.addNode();

   603   Digraph::Node n4 = digraph.addNode();

   605   Digraph::Arc a1 = digraph.addArc(n1, n2);

   606   Digraph::Arc a2 = digraph.addArc(n1, n3);

   607   Digraph::Arc a3 = digraph.addArc(n1, n4);

   608   Digraph::Arc a4 = digraph.addArc(n2, n3);

   609   Digraph::Arc a5 = digraph.addArc(n2, n4);

   610   Digraph::Arc a6 = digraph.addArc(n3, n4);

   612   capacity[a1] = 8;

   613   capacity[a2] = 6;

   614   capacity[a3] = 4;

   615   capacity[a4] = 4;

   616   capacity[a5] = 6;

   617   capacity[a6] = 10;

   619   // Check the adaptor with various flow values

   620   for (Digraph::ArcIt a(digraph); a != INVALID; ++a) {

   621     flow[a] = 0;

   622   }

   624   checkGraphNodeList(adaptor, 4);

   625   checkGraphArcList(adaptor, 6);

   626   checkGraphConArcList(adaptor, 6);

   628   checkGraphOutArcList(adaptor, n1, 3);

   629   checkGraphOutArcList(adaptor, n2, 2);

   630   checkGraphOutArcList(adaptor, n3, 1);

   631   checkGraphOutArcList(adaptor, n4, 0);

   633   checkGraphInArcList(adaptor, n1, 0);

   634   checkGraphInArcList(adaptor, n2, 1);

   635   checkGraphInArcList(adaptor, n3, 2);

   636   checkGraphInArcList(adaptor, n4, 3);

   638   for (Digraph::ArcIt a(digraph); a != INVALID; ++a) {

   639     flow[a] = capacity[a] / 2;

   640   }

   642   checkGraphNodeList(adaptor, 4);

   643   checkGraphArcList(adaptor, 12);

   644   checkGraphConArcList(adaptor, 12);

   646   checkGraphOutArcList(adaptor, n1, 3);

   647   checkGraphOutArcList(adaptor, n2, 3);

   648   checkGraphOutArcList(adaptor, n3, 3);

   649   checkGraphOutArcList(adaptor, n4, 3);

   651   checkGraphInArcList(adaptor, n1, 3);

   652   checkGraphInArcList(adaptor, n2, 3);

   653   checkGraphInArcList(adaptor, n3, 3);

   654   checkGraphInArcList(adaptor, n4, 3);

   656   checkNodeIds(adaptor);

   657   checkArcIds(adaptor);

   659   checkGraphNodeMap(adaptor);

   660   checkGraphArcMap(adaptor);

   662   for (Digraph::ArcIt a(digraph); a != INVALID; ++a) {

   663     flow[a] = capacity[a];

   664   }

   666   checkGraphNodeList(adaptor, 4);

   667   checkGraphArcList(adaptor, 6);

   668   checkGraphConArcList(adaptor, 6);

   670   checkGraphOutArcList(adaptor, n1, 0);

   671   checkGraphOutArcList(adaptor, n2, 1);

   672   checkGraphOutArcList(adaptor, n3, 2);

   673   checkGraphOutArcList(adaptor, n4, 3);

   675   checkGraphInArcList(adaptor, n1, 3);

   676   checkGraphInArcList(adaptor, n2, 2);

   677   checkGraphInArcList(adaptor, n3, 1);

   678   checkGraphInArcList(adaptor, n4, 0);

   680   // Saturate all backward arcs

   681   // (set the flow to zero on all forward arcs)

   682   for (Adaptor::ArcIt a(adaptor); a != INVALID; ++a) {

   683     if (adaptor.backward(a))

   684       adaptor.augment(a, adaptor.residualCapacity(a));

   685   }

   687   checkGraphNodeList(adaptor, 4);

   688   checkGraphArcList(adaptor, 6);

   689   checkGraphConArcList(adaptor, 6);

   691   checkGraphOutArcList(adaptor, n1, 3);

   692   checkGraphOutArcList(adaptor, n2, 2);

   693   checkGraphOutArcList(adaptor, n3, 1);

   694   checkGraphOutArcList(adaptor, n4, 0);

   696   checkGraphInArcList(adaptor, n1, 0);

   697   checkGraphInArcList(adaptor, n2, 1);

   698   checkGraphInArcList(adaptor, n3, 2);

   699   checkGraphInArcList(adaptor, n4, 3);

   701   // Find maximum flow by augmenting along shortest paths

   702   int flow_value = 0;

   703   Adaptor::ResidualCapacity res_cap(adaptor);

   704   while (true) {

   706     Bfs<Adaptor> bfs(adaptor);

   707     bfs.run(n1, n4);

   709     if (!bfs.reached(n4)) break;

   711     Path<Adaptor> p = bfs.path(n4);

   713     int min = std::numeric_limits<int>::max();

   714     for (Path<Adaptor>::ArcIt a(p); a != INVALID; ++a) {

   715       if (res_cap[a] < min) min = res_cap[a];

   716     }

   718     for (Path<Adaptor>::ArcIt a(p); a != INVALID; ++a) {

   719       adaptor.augment(a, min);

   720     }

   721     flow_value += min;

   722   }

   724   check(flow_value == 18, "Wrong flow with res graph adaptor");

   726   // Check forward() and backward()

   727   for (Adaptor::ArcIt a(adaptor); a != INVALID; ++a) {

   728     check(adaptor.forward(a) != adaptor.backward(a),

   729           "Wrong forward() or backward()");

   730     check((adaptor.forward(a) && adaptor.forward(Digraph::Arc(a)) == a) ||

   731           (adaptor.backward(a) && adaptor.backward(Digraph::Arc(a)) == a),

   732           "Wrong forward() or backward()");

   733   }

   735   // Check the conversion of nodes and arcs

   736   Digraph::Node nd = Adaptor::NodeIt(adaptor);

   737   nd = ++Adaptor::NodeIt(adaptor);

   738   Adaptor::Node na = n1;

   739   na = n2;

   740   Digraph::Arc ad = Adaptor::ArcIt(adaptor);

   741   ad = ++Adaptor::ArcIt(adaptor);

   742 }

   744 void checkSplitNodes() {

   745   // Check concepts

   746   checkConcept<concepts::Digraph, SplitNodes<concepts::Digraph> >();

   747   checkConcept<concepts::Digraph, SplitNodes<ListDigraph> >();

   749   // Create a digraph and an adaptor

   750   typedef ListDigraph Digraph;

   751   typedef SplitNodes<Digraph> Adaptor;

   753   Digraph digraph;

   754   Adaptor adaptor(digraph);

   756   Digraph::Node n1 = digraph.addNode();

   757   Digraph::Node n2 = digraph.addNode();

   758   Digraph::Node n3 = digraph.addNode();

   760   Digraph::Arc a1 = digraph.addArc(n1, n2);

   761   Digraph::Arc a2 = digraph.addArc(n1, n3);

   762   Digraph::Arc a3 = digraph.addArc(n2, n3);

   763   ignore_unused_variable_warning(a1,a2,a3);

   765   checkGraphNodeList(adaptor, 6);

   766   checkGraphArcList(adaptor, 6);

   767   checkGraphConArcList(adaptor, 6);

   769   checkGraphOutArcList(adaptor, adaptor.inNode(n1), 1);

   770   checkGraphOutArcList(adaptor, adaptor.outNode(n1), 2);

   771   checkGraphOutArcList(adaptor, adaptor.inNode(n2), 1);

   772   checkGraphOutArcList(adaptor, adaptor.outNode(n2), 1);

   773   checkGraphOutArcList(adaptor, adaptor.inNode(n3), 1);

   774   checkGraphOutArcList(adaptor, adaptor.outNode(n3), 0);

   776   checkGraphInArcList(adaptor, adaptor.inNode(n1), 0);

   777   checkGraphInArcList(adaptor, adaptor.outNode(n1), 1);

   778   checkGraphInArcList(adaptor, adaptor.inNode(n2), 1);

   779   checkGraphInArcList(adaptor, adaptor.outNode(n2), 1);

   780   checkGraphInArcList(adaptor, adaptor.inNode(n3), 2);

   781   checkGraphInArcList(adaptor, adaptor.outNode(n3), 1);

   783   checkNodeIds(adaptor);

   784   checkArcIds(adaptor);

   786   checkGraphNodeMap(adaptor);

   787   checkGraphArcMap(adaptor);

   789   // Check split

   790   for (Adaptor::ArcIt a(adaptor); a != INVALID; ++a) {

   791     if (adaptor.origArc(a)) {

   792       Digraph::Arc oa = a;

   793       check(adaptor.source(a) == adaptor.outNode(digraph.source(oa)),

   794             "Wrong split");

   795       check(adaptor.target(a) == adaptor.inNode(digraph.target(oa)),

   796             "Wrong split");

   797     } else {

   798       Digraph::Node on = a;

   799       check(adaptor.source(a) == adaptor.inNode(on), "Wrong split");

   800       check(adaptor.target(a) == adaptor.outNode(on), "Wrong split");

   801     }

   802   }

   804   // Check combined node map

   805   typedef Adaptor::CombinedNodeMap

   806     <Digraph::NodeMap<int>, Digraph::NodeMap<int> > IntCombinedNodeMap;

   807   typedef Adaptor::CombinedNodeMap

   808     <Digraph::NodeMap<bool>, Digraph::NodeMap<bool> > BoolCombinedNodeMap;

   809   checkConcept<concepts::ReferenceMap<Adaptor::Node, int, int&, const int&>,

   810     IntCombinedNodeMap>();

   811 //checkConcept<concepts::ReferenceMap<Adaptor::Node, bool, bool&, const bool&>,

   812 //  BoolCombinedNodeMap>();

   813   checkConcept<concepts::ReadWriteMap<Adaptor::Node, bool>,

   814     BoolCombinedNodeMap>();

   816   Digraph::NodeMap<int> in_map(digraph), out_map(digraph);

   817   for (Digraph::NodeIt n(digraph); n != INVALID; ++n) {

   818     in_map[n] = digraph.id(n);

   819     out_map[n] = -digraph.id(n);

   820   }

   822   Adaptor::CombinedNodeMap<Digraph::NodeMap<int>, Digraph::NodeMap<int> >

   823     node_map(in_map, out_map);

   824   for (Adaptor::NodeIt n(adaptor); n != INVALID; ++n) {

   825     if (adaptor.inNode(n)) {

   826       check(node_map[n] == in_map[n], "Wrong combined node map");

   827     } else {

   828       check(node_map[n] == out_map[n], "Wrong combined node map");

   829     }

   830   }

   832   // Check combined arc map

   833   typedef Adaptor::CombinedArcMap

   834     <Digraph::ArcMap<int>, Digraph::NodeMap<int> > IntCombinedArcMap;

   835   typedef Adaptor::CombinedArcMap

   836     <Digraph::ArcMap<bool>, Digraph::NodeMap<bool> > BoolCombinedArcMap;

   837   checkConcept<concepts::ReferenceMap<Adaptor::Arc, int, int&, const int&>,

   838     IntCombinedArcMap>();

   839 //checkConcept<concepts::ReferenceMap<Adaptor::Arc, bool, bool&, const bool&>,

   840 //  BoolCombinedArcMap>();

   841   checkConcept<concepts::ReadWriteMap<Adaptor::Arc, bool>,

   842     BoolCombinedArcMap>();

   844   Digraph::ArcMap<int> a_map(digraph);

   845   for (Digraph::ArcIt a(digraph); a != INVALID; ++a) {

   846     a_map[a] = digraph.id(a);

   847   }

   849   Adaptor::CombinedArcMap<Digraph::ArcMap<int>, Digraph::NodeMap<int> >

   850     arc_map(a_map, out_map);

   851   for (Digraph::ArcIt a(digraph); a != INVALID; ++a) {

   852     check(arc_map[adaptor.arc(a)] == a_map[a],  "Wrong combined arc map");

   853   }

   854   for (Digraph::NodeIt n(digraph); n != INVALID; ++n) {

   855     check(arc_map[adaptor.arc(n)] == out_map[n],  "Wrong combined arc map");

   856   }

   858   // Check the conversion of nodes

   859   Digraph::Node nd = adaptor.inNode(n1);

   860   check (nd == n1, "Wrong node conversion");

   861   nd = adaptor.outNode(n2);

   862   check (nd == n2, "Wrong node conversion");

   863 }

   865 void checkSubGraph() {

   866   // Check concepts

   867   checkConcept<concepts::Graph, SubGraph<concepts::Graph> >();

   868   checkConcept<concepts::Graph, SubGraph<ListGraph> >();

   869   checkConcept<concepts::AlterableGraphComponent<>,

   870                SubGraph<ListGraph> >();

   871   checkConcept<concepts::ExtendableGraphComponent<>,

   872                SubGraph<ListGraph> >();

   873   checkConcept<concepts::ErasableGraphComponent<>,

   874                SubGraph<ListGraph> >();

   875   checkConcept<concepts::ClearableGraphComponent<>,

   876                SubGraph<ListGraph> >();

   878   // Create a graph and an adaptor

   879   typedef ListGraph Graph;

   880   typedef Graph::NodeMap<bool> NodeFilter;

   881   typedef Graph::EdgeMap<bool> EdgeFilter;

   882   typedef SubGraph<Graph, NodeFilter, EdgeFilter> Adaptor;

   884   Graph graph;

   885   NodeFilter node_filter(graph);

   886   EdgeFilter edge_filter(graph);

   887   Adaptor adaptor(graph, node_filter, edge_filter);

   889   // Add nodes and edges to the original graph and the adaptor

   890   Graph::Node n1 = graph.addNode();

   891   Graph::Node n2 = graph.addNode();

   892   Adaptor::Node n3 = adaptor.addNode();

   893   Adaptor::Node n4 = adaptor.addNode();

   895   node_filter[n1] = node_filter[n2] = node_filter[n3] = node_filter[n4] = true;

   897   Graph::Edge e1 = graph.addEdge(n1, n2);

   898   Graph::Edge e2 = graph.addEdge(n1, n3);

   899   Adaptor::Edge e3 = adaptor.addEdge(n2, n3);

   900   Adaptor::Edge e4 = adaptor.addEdge(n3, n4);

   902   edge_filter[e1] = edge_filter[e2] = edge_filter[e3] = edge_filter[e4] = true;

   904   checkGraphNodeList(adaptor, 4);

   905   checkGraphArcList(adaptor, 8);

   906   checkGraphEdgeList(adaptor, 4);

   907   checkGraphConArcList(adaptor, 8);

   908   checkGraphConEdgeList(adaptor, 4);

   910   checkGraphIncEdgeArcLists(adaptor, n1, 2);

   911   checkGraphIncEdgeArcLists(adaptor, n2, 2);

   912   checkGraphIncEdgeArcLists(adaptor, n3, 3);

   913   checkGraphIncEdgeArcLists(adaptor, n4, 1);

   915   checkNodeIds(adaptor);

   916   checkArcIds(adaptor);

   917   checkEdgeIds(adaptor);

   919   checkGraphNodeMap(adaptor);

   920   checkGraphArcMap(adaptor);

   921   checkGraphEdgeMap(adaptor);

   923   // Hide an edge

   924   adaptor.status(e2, false);

   925   adaptor.disable(e3);

   926   if (!adaptor.status(e3)) adaptor.enable(e3);

   928   checkGraphNodeList(adaptor, 4);

   929   checkGraphArcList(adaptor, 6);

   930   checkGraphEdgeList(adaptor, 3);

   931   checkGraphConArcList(adaptor, 6);

   932   checkGraphConEdgeList(adaptor, 3);

   934   checkGraphIncEdgeArcLists(adaptor, n1, 1);

   935   checkGraphIncEdgeArcLists(adaptor, n2, 2);

   936   checkGraphIncEdgeArcLists(adaptor, n3, 2);

   937   checkGraphIncEdgeArcLists(adaptor, n4, 1);

   939   checkNodeIds(adaptor);

   940   checkArcIds(adaptor);

   941   checkEdgeIds(adaptor);

   943   checkGraphNodeMap(adaptor);

   944   checkGraphArcMap(adaptor);

   945   checkGraphEdgeMap(adaptor);

   947   // Hide a node

   948   adaptor.status(n1, false);

   949   adaptor.disable(n3);

   950   if (!adaptor.status(n3)) adaptor.enable(n3);

   952   checkGraphNodeList(adaptor, 3);

   953   checkGraphArcList(adaptor, 4);

   954   checkGraphEdgeList(adaptor, 2);

   955   checkGraphConArcList(adaptor, 4);

   956   checkGraphConEdgeList(adaptor, 2);

   958   checkGraphIncEdgeArcLists(adaptor, n2, 1);

   959   checkGraphIncEdgeArcLists(adaptor, n3, 2);

   960   checkGraphIncEdgeArcLists(adaptor, n4, 1);

   962   checkNodeIds(adaptor);

   963   checkArcIds(adaptor);

   964   checkEdgeIds(adaptor);

   966   checkGraphNodeMap(adaptor);

   967   checkGraphArcMap(adaptor);

   968   checkGraphEdgeMap(adaptor);

   970   // Hide all nodes and edges

   971   node_filter[n1] = node_filter[n2] = node_filter[n3] = node_filter[n4] = false;

   972   edge_filter[e1] = edge_filter[e2] = edge_filter[e3] = edge_filter[e4] = false;

   974   checkGraphNodeList(adaptor, 0);

   975   checkGraphArcList(adaptor, 0);

   976   checkGraphEdgeList(adaptor, 0);

   977   checkGraphConArcList(adaptor, 0);

   978   checkGraphConEdgeList(adaptor, 0);

   980   checkNodeIds(adaptor);

   981   checkArcIds(adaptor);

   982   checkEdgeIds(adaptor);

   984   checkGraphNodeMap(adaptor);

   985   checkGraphArcMap(adaptor);

   986   checkGraphEdgeMap(adaptor);

   988   // Check the conversion of nodes and edges

   989   Graph::Node ng = n3;

   990   ng = n4;

   991   Adaptor::Node na = n1;

   992   na = n2;

   993   Graph::Edge eg = e3;

   994   eg = e4;

   995   Adaptor::Edge ea = e1;

   996   ea = e2;

   997 }

   999 void checkFilterNodes2() {

  1000   // Check concepts

  1001   checkConcept<concepts::Graph, FilterNodes<concepts::Graph> >();

  1002   checkConcept<concepts::Graph, FilterNodes<ListGraph> >();

  1003   checkConcept<concepts::AlterableGraphComponent<>,

  1004                FilterNodes<ListGraph> >();

  1005   checkConcept<concepts::ExtendableGraphComponent<>,

  1006                FilterNodes<ListGraph> >();

  1007   checkConcept<concepts::ErasableGraphComponent<>,

  1008                FilterNodes<ListGraph> >();

  1009   checkConcept<concepts::ClearableGraphComponent<>,

  1010                FilterNodes<ListGraph> >();

  1012   // Create a graph and an adaptor

  1013   typedef ListGraph Graph;

  1014   typedef Graph::NodeMap<bool> NodeFilter;

  1015   typedef FilterNodes<Graph, NodeFilter> Adaptor;

  1017   // Add nodes and edges to the original graph and the adaptor

  1018   Graph graph;

  1019   NodeFilter node_filter(graph);

  1020   Adaptor adaptor(graph, node_filter);

  1022   Graph::Node n1 = graph.addNode();

  1023   Graph::Node n2 = graph.addNode();

  1024   Adaptor::Node n3 = adaptor.addNode();

  1025   Adaptor::Node n4 = adaptor.addNode();

  1027   node_filter[n1] = node_filter[n2] = node_filter[n3] = node_filter[n4] = true;

  1029   Graph::Edge e1 = graph.addEdge(n1, n2);

  1030   Graph::Edge e2 = graph.addEdge(n1, n3);

  1031   Adaptor::Edge e3 = adaptor.addEdge(n2, n3);

  1032   Adaptor::Edge e4 = adaptor.addEdge(n3, n4);

  1034   checkGraphNodeList(adaptor, 4);

  1035   checkGraphArcList(adaptor, 8);

  1036   checkGraphEdgeList(adaptor, 4);

  1037   checkGraphConArcList(adaptor, 8);

  1038   checkGraphConEdgeList(adaptor, 4);

  1040   checkGraphIncEdgeArcLists(adaptor, n1, 2);

  1041   checkGraphIncEdgeArcLists(adaptor, n2, 2);

  1042   checkGraphIncEdgeArcLists(adaptor, n3, 3);

  1043   checkGraphIncEdgeArcLists(adaptor, n4, 1);

  1045   checkNodeIds(adaptor);

  1046   checkArcIds(adaptor);

  1047   checkEdgeIds(adaptor);

  1049   checkGraphNodeMap(adaptor);

  1050   checkGraphArcMap(adaptor);

  1051   checkGraphEdgeMap(adaptor);

  1053   // Hide a node

  1054   adaptor.status(n1, false);

  1055   adaptor.disable(n3);

  1056   if (!adaptor.status(n3)) adaptor.enable(n3);

  1058   checkGraphNodeList(adaptor, 3);

  1059   checkGraphArcList(adaptor, 4);

  1060   checkGraphEdgeList(adaptor, 2);

  1061   checkGraphConArcList(adaptor, 4);

  1062   checkGraphConEdgeList(adaptor, 2);

  1064   checkGraphIncEdgeArcLists(adaptor, n2, 1);

  1065   checkGraphIncEdgeArcLists(adaptor, n3, 2);

  1066   checkGraphIncEdgeArcLists(adaptor, n4, 1);

  1068   checkNodeIds(adaptor);

  1069   checkArcIds(adaptor);

  1070   checkEdgeIds(adaptor);

  1072   checkGraphNodeMap(adaptor);

  1073   checkGraphArcMap(adaptor);

  1074   checkGraphEdgeMap(adaptor);

  1076   // Hide all nodes

  1077   node_filter[n1] = node_filter[n2] = node_filter[n3] = node_filter[n4] = false;

  1079   checkGraphNodeList(adaptor, 0);

  1080   checkGraphArcList(adaptor, 0);

  1081   checkGraphEdgeList(adaptor, 0);

  1082   checkGraphConArcList(adaptor, 0);

  1083   checkGraphConEdgeList(adaptor, 0);

  1085   checkNodeIds(adaptor);

  1086   checkArcIds(adaptor);

  1087   checkEdgeIds(adaptor);

  1089   checkGraphNodeMap(adaptor);

  1090   checkGraphArcMap(adaptor);

  1091   checkGraphEdgeMap(adaptor);

  1093   // Check the conversion of nodes and edges

  1094   Graph::Node ng = n3;

  1095   ng = n4;

  1096   Adaptor::Node na = n1;

  1097   na = n2;

  1098   Graph::Edge eg = e3;

  1099   eg = e4;

  1100   Adaptor::Edge ea = e1;

  1101   ea = e2;

  1102 }

  1104 void checkFilterEdges() {

  1105   // Check concepts

  1106   checkConcept<concepts::Graph, FilterEdges<concepts::Graph> >();

  1107   checkConcept<concepts::Graph, FilterEdges<ListGraph> >();

  1108   checkConcept<concepts::AlterableGraphComponent<>,

  1109                FilterEdges<ListGraph> >();

  1110   checkConcept<concepts::ExtendableGraphComponent<>,

  1111                FilterEdges<ListGraph> >();

  1112   checkConcept<concepts::ErasableGraphComponent<>,

  1113                FilterEdges<ListGraph> >();

  1114   checkConcept<concepts::ClearableGraphComponent<>,

  1115                FilterEdges<ListGraph> >();

  1117   // Create a graph and an adaptor

  1118   typedef ListGraph Graph;

  1119   typedef Graph::EdgeMap<bool> EdgeFilter;

  1120   typedef FilterEdges<Graph, EdgeFilter> Adaptor;

  1122   Graph graph;

  1123   EdgeFilter edge_filter(graph);

  1124   Adaptor adaptor(graph, edge_filter);

  1126   // Add nodes and edges to the original graph and the adaptor

  1127   Graph::Node n1 = graph.addNode();

  1128   Graph::Node n2 = graph.addNode();

  1129   Adaptor::Node n3 = adaptor.addNode();

  1130   Adaptor::Node n4 = adaptor.addNode();

  1132   Graph::Edge e1 = graph.addEdge(n1, n2);

  1133   Graph::Edge e2 = graph.addEdge(n1, n3);

  1134   Adaptor::Edge e3 = adaptor.addEdge(n2, n3);

  1135   Adaptor::Edge e4 = adaptor.addEdge(n3, n4);

  1137   edge_filter[e1] = edge_filter[e2] = edge_filter[e3] = edge_filter[e4] = true;

  1139   checkGraphNodeList(adaptor, 4);

  1140   checkGraphArcList(adaptor, 8);

  1141   checkGraphEdgeList(adaptor, 4);

  1142   checkGraphConArcList(adaptor, 8);

  1143   checkGraphConEdgeList(adaptor, 4);

  1145   checkGraphIncEdgeArcLists(adaptor, n1, 2);

  1146   checkGraphIncEdgeArcLists(adaptor, n2, 2);

  1147   checkGraphIncEdgeArcLists(adaptor, n3, 3);

  1148   checkGraphIncEdgeArcLists(adaptor, n4, 1);

  1150   checkNodeIds(adaptor);

  1151   checkArcIds(adaptor);

  1152   checkEdgeIds(adaptor);

  1154   checkGraphNodeMap(adaptor);

  1155   checkGraphArcMap(adaptor);

  1156   checkGraphEdgeMap(adaptor);

  1158   // Hide an edge

  1159   adaptor.status(e2, false);

  1160   adaptor.disable(e3);

  1161   if (!adaptor.status(e3)) adaptor.enable(e3);

  1163   checkGraphNodeList(adaptor, 4);

  1164   checkGraphArcList(adaptor, 6);

  1165   checkGraphEdgeList(adaptor, 3);

  1166   checkGraphConArcList(adaptor, 6);

  1167   checkGraphConEdgeList(adaptor, 3);

  1169   checkGraphIncEdgeArcLists(adaptor, n1, 1);

  1170   checkGraphIncEdgeArcLists(adaptor, n2, 2);

  1171   checkGraphIncEdgeArcLists(adaptor, n3, 2);

  1172   checkGraphIncEdgeArcLists(adaptor, n4, 1);

  1174   checkNodeIds(adaptor);

  1175   checkArcIds(adaptor);

  1176   checkEdgeIds(adaptor);

  1178   checkGraphNodeMap(adaptor);

  1179   checkGraphArcMap(adaptor);

  1180   checkGraphEdgeMap(adaptor);

  1182   // Hide all edges

  1183   edge_filter[e1] = edge_filter[e2] = edge_filter[e3] = edge_filter[e4] = false;

  1185   checkGraphNodeList(adaptor, 4);

  1186   checkGraphArcList(adaptor, 0);

  1187   checkGraphEdgeList(adaptor, 0);

  1188   checkGraphConArcList(adaptor, 0);

  1189   checkGraphConEdgeList(adaptor, 0);

  1191   checkNodeIds(adaptor);

  1192   checkArcIds(adaptor);

  1193   checkEdgeIds(adaptor);

  1195   checkGraphNodeMap(adaptor);

  1196   checkGraphArcMap(adaptor);

  1197   checkGraphEdgeMap(adaptor);

  1199   // Check the conversion of nodes and edges

  1200   Graph::Node ng = n3;

  1201   ng = n4;

  1202   Adaptor::Node na = n1;

  1203   na = n2;

  1204   Graph::Edge eg = e3;

  1205   eg = e4;

  1206   Adaptor::Edge ea = e1;

  1207   ea = e2;

  1208 }

  1210 void checkOrienter() {

  1211   // Check concepts

  1212   checkConcept<concepts::Digraph, Orienter<concepts::Graph> >();

  1213   checkConcept<concepts::Digraph, Orienter<ListGraph> >();

  1214   checkConcept<concepts::AlterableDigraphComponent<>,

  1215                Orienter<ListGraph> >();

  1216   checkConcept<concepts::ExtendableDigraphComponent<>,

  1217                Orienter<ListGraph> >();

  1218   checkConcept<concepts::ErasableDigraphComponent<>,

  1219                Orienter<ListGraph> >();

  1220   checkConcept<concepts::ClearableDigraphComponent<>,

  1221                Orienter<ListGraph> >();

  1223   // Create a graph and an adaptor

  1224   typedef ListGraph Graph;

  1225   typedef ListGraph::EdgeMap<bool> DirMap;

  1226   typedef Orienter<Graph> Adaptor;

  1228   Graph graph;

  1229   DirMap dir(graph);

  1230   Adaptor adaptor(graph, dir);

  1232   // Add nodes and edges to the original graph and the adaptor

  1233   Graph::Node n1 = graph.addNode();

  1234   Graph::Node n2 = graph.addNode();

  1235   Adaptor::Node n3 = adaptor.addNode();

  1237   Graph::Edge e1 = graph.addEdge(n1, n2);

  1238   Graph::Edge e2 = graph.addEdge(n1, n3);

  1239   Adaptor::Arc e3 = adaptor.addArc(n2, n3);

  1241   dir[e1] = dir[e2] = dir[e3] = true;

  1243   // Check the original graph

  1244   checkGraphNodeList(graph, 3);

  1245   checkGraphArcList(graph, 6);

  1246   checkGraphConArcList(graph, 6);

  1247   checkGraphEdgeList(graph, 3);

  1248   checkGraphConEdgeList(graph, 3);

  1250   checkGraphIncEdgeArcLists(graph, n1, 2);

  1251   checkGraphIncEdgeArcLists(graph, n2, 2);

  1252   checkGraphIncEdgeArcLists(graph, n3, 2);

  1254   checkNodeIds(graph);

  1255   checkArcIds(graph);

  1256   checkEdgeIds(graph);

  1258   checkGraphNodeMap(graph);

  1259   checkGraphArcMap(graph);

  1260   checkGraphEdgeMap(graph);

  1262   // Check the adaptor

  1263   checkGraphNodeList(adaptor, 3);

  1264   checkGraphArcList(adaptor, 3);

  1265   checkGraphConArcList(adaptor, 3);

  1267   checkGraphOutArcList(adaptor, n1, 2);

  1268   checkGraphOutArcList(adaptor, n2, 1);

  1269   checkGraphOutArcList(adaptor, n3, 0);

  1271   checkGraphInArcList(adaptor, n1, 0);

  1272   checkGraphInArcList(adaptor, n2, 1);

  1273   checkGraphInArcList(adaptor, n3, 2);

  1275   checkNodeIds(adaptor);

  1276   checkArcIds(adaptor);

  1278   checkGraphNodeMap(adaptor);

  1279   checkGraphArcMap(adaptor);

  1281   // Check direction changing

  1282   {

  1283     dir[e1] = true;

  1284     Adaptor::Node u = adaptor.source(e1);

  1285     Adaptor::Node v = adaptor.target(e1);

  1287     dir[e1] = false;

  1288     check (u == adaptor.target(e1), "Wrong dir");

  1289     check (v == adaptor.source(e1), "Wrong dir");

  1291     check ((u == n1 && v == n2) || (u == n2 && v == n1), "Wrong dir");

  1292     dir[e1] = n1 == u;

  1293   }

  1295   {

  1296     dir[e2] = true;

  1297     Adaptor::Node u = adaptor.source(e2);

  1298     Adaptor::Node v = adaptor.target(e2);

  1300     dir[e2] = false;

  1301     check (u == adaptor.target(e2), "Wrong dir");

  1302     check (v == adaptor.source(e2), "Wrong dir");

  1304     check ((u == n1 && v == n3) || (u == n3 && v == n1), "Wrong dir");

  1305     dir[e2] = n3 == u;

  1306   }

  1308   {

  1309     dir[e3] = true;

  1310     Adaptor::Node u = adaptor.source(e3);

  1311     Adaptor::Node v = adaptor.target(e3);

  1313     dir[e3] = false;

  1314     check (u == adaptor.target(e3), "Wrong dir");

  1315     check (v == adaptor.source(e3), "Wrong dir");

  1317     check ((u == n2 && v == n3) || (u == n3 && v == n2), "Wrong dir");

  1318     dir[e3] = n2 == u;

  1319   }

  1321   // Check the adaptor again

  1322   checkGraphNodeList(adaptor, 3);

  1323   checkGraphArcList(adaptor, 3);

  1324   checkGraphConArcList(adaptor, 3);

  1326   checkGraphOutArcList(adaptor, n1, 1);

  1327   checkGraphOutArcList(adaptor, n2, 1);

  1328   checkGraphOutArcList(adaptor, n3, 1);

  1330   checkGraphInArcList(adaptor, n1, 1);

  1331   checkGraphInArcList(adaptor, n2, 1);

  1332   checkGraphInArcList(adaptor, n3, 1);

  1334   checkNodeIds(adaptor);

  1335   checkArcIds(adaptor);

  1337   checkGraphNodeMap(adaptor);

  1338   checkGraphArcMap(adaptor);

  1340   // Check reverseArc()

  1341   adaptor.reverseArc(e2);

  1342   adaptor.reverseArc(e3);

  1343   adaptor.reverseArc(e2);

  1345   checkGraphNodeList(adaptor, 3);

  1346   checkGraphArcList(adaptor, 3);

  1347   checkGraphConArcList(adaptor, 3);

  1349   checkGraphOutArcList(adaptor, n1, 1);

  1350   checkGraphOutArcList(adaptor, n2, 0);

  1351   checkGraphOutArcList(adaptor, n3, 2);

  1353   checkGraphInArcList(adaptor, n1, 1);

  1354   checkGraphInArcList(adaptor, n2, 2);

  1355   checkGraphInArcList(adaptor, n3, 0);

  1357   // Check the conversion of nodes and arcs/edges

  1358   Graph::Node ng = n3;

  1359   ng = n3;

  1360   Adaptor::Node na = n1;

  1361   na = n2;

  1362   Graph::Edge eg = e3;

  1363   eg = e3;

  1364   Adaptor::Arc aa = e1;

  1365   aa = e2;

  1366 }

  1368 void checkCombiningAdaptors() {

  1369   // Create a grid graph

  1370   GridGraph graph(2,2);

  1371   GridGraph::Node n1 = graph(0,0);

  1372   GridGraph::Node n2 = graph(0,1);

  1373   GridGraph::Node n3 = graph(1,0);

  1374   GridGraph::Node n4 = graph(1,1);

  1376   GridGraph::EdgeMap<bool> dir_map(graph);

  1377   dir_map[graph.right(n1)] = graph.u(graph.right(n1)) != n1;

  1378   dir_map[graph.up(n1)] = graph.u(graph.up(n1)) == n1;

  1379   dir_map[graph.left(n4)] = graph.u(graph.left(n4)) == n4;

  1380   dir_map[graph.down(n4)] = graph.u(graph.down(n4)) == n4;

  1382   // Apply several adaptors on the grid graph

  1383   typedef Orienter< const GridGraph, GridGraph::EdgeMap<bool> >

  1384     OrientedGridGraph;

  1385   typedef SplitNodes<OrientedGridGraph> SplitGridGraph;

  1386   typedef Undirector<const SplitGridGraph> USplitGridGraph;

  1387   checkConcept<concepts::Digraph, SplitGridGraph>();

  1388   checkConcept<concepts::Graph, USplitGridGraph>();

  1390   OrientedGridGraph oadaptor = orienter(graph, dir_map);

  1391   SplitGridGraph adaptor = splitNodes(oadaptor);

  1392   USplitGridGraph uadaptor = undirector(adaptor);

  1394   // Check adaptor

  1395   checkGraphNodeList(adaptor, 8);

  1396   checkGraphArcList(adaptor, 8);

  1397   checkGraphConArcList(adaptor, 8);

  1399   checkGraphOutArcList(adaptor, adaptor.inNode(n1), 1);

  1400   checkGraphOutArcList(adaptor, adaptor.outNode(n1), 1);

  1401   checkGraphOutArcList(adaptor, adaptor.inNode(n2), 1);

  1402   checkGraphOutArcList(adaptor, adaptor.outNode(n2), 0);

  1403   checkGraphOutArcList(adaptor, adaptor.inNode(n3), 1);

  1404   checkGraphOutArcList(adaptor, adaptor.outNode(n3), 1);

  1405   checkGraphOutArcList(adaptor, adaptor.inNode(n4), 1);

  1406   checkGraphOutArcList(adaptor, adaptor.outNode(n4), 2);

  1408   checkGraphInArcList(adaptor, adaptor.inNode(n1), 1);

  1409   checkGraphInArcList(adaptor, adaptor.outNode(n1), 1);

  1410   checkGraphInArcList(adaptor, adaptor.inNode(n2), 2);

  1411   checkGraphInArcList(adaptor, adaptor.outNode(n2), 1);

  1412   checkGraphInArcList(adaptor, adaptor.inNode(n3), 1);

  1413   checkGraphInArcList(adaptor, adaptor.outNode(n3), 1);

  1414   checkGraphInArcList(adaptor, adaptor.inNode(n4), 0);

  1415   checkGraphInArcList(adaptor, adaptor.outNode(n4), 1);

  1417   checkNodeIds(adaptor);

  1418   checkArcIds(adaptor);

  1420   checkGraphNodeMap(adaptor);

  1421   checkGraphArcMap(adaptor);

  1423   // Check uadaptor

  1424   checkGraphNodeList(uadaptor, 8);

  1425   checkGraphEdgeList(uadaptor, 8);

  1426   checkGraphArcList(uadaptor, 16);

  1427   checkGraphConEdgeList(uadaptor, 8);

  1428   checkGraphConArcList(uadaptor, 16);

  1430   checkNodeIds(uadaptor);

  1431   checkEdgeIds(uadaptor);

  1432   checkArcIds(uadaptor);

  1434   checkGraphNodeMap(uadaptor);

  1435   checkGraphEdgeMap(uadaptor);

  1436   checkGraphArcMap(uadaptor);

  1438   checkGraphIncEdgeArcLists(uadaptor, adaptor.inNode(n1), 2);

  1439   checkGraphIncEdgeArcLists(uadaptor, adaptor.outNode(n1), 2);

  1440   checkGraphIncEdgeArcLists(uadaptor, adaptor.inNode(n2), 3);

  1441   checkGraphIncEdgeArcLists(uadaptor, adaptor.outNode(n2), 1);

  1442   checkGraphIncEdgeArcLists(uadaptor, adaptor.inNode(n3), 2);

  1443   checkGraphIncEdgeArcLists(uadaptor, adaptor.outNode(n3), 2);

  1444   checkGraphIncEdgeArcLists(uadaptor, adaptor.inNode(n4), 1);

  1445   checkGraphIncEdgeArcLists(uadaptor, adaptor.outNode(n4), 3);

  1446 }

  1448 int main(int, const char **) {

  1449   // Check the digraph adaptors (using ListDigraph)

  1450   checkReverseDigraph();

  1451   checkSubDigraph();

  1452   checkFilterNodes1();

  1453   checkFilterArcs();

  1454   checkUndirector();

  1455   checkResidualDigraph();

  1456   checkSplitNodes();

  1458   // Check the graph adaptors (using ListGraph)

  1459   checkSubGraph();

  1460   checkFilterNodes2();

  1461   checkFilterEdges();

  1462   checkOrienter();

  1464   // Combine adaptors (using GridGraph)

  1465   checkCombiningAdaptors();

  1467   return 0;

  1468 }

author	Alpar Juttner <alpar@cs.elte.hu>
	Fri, 15 Mar 2013 17:15:46 +0100
changeset 1047	f7247b5c04bf
parent 995	4bb9e72e1a41
parent 997	761fe0846f49
child 1084	8b2d4e5d96e4
permissions	-rw-r--r--