lemon: test/adaptors_test.cc@684964884a2e

     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);

    69   // Check the adaptor

    70   checkGraphNodeList(adaptor, 3);

    71   checkGraphArcList(adaptor, 3);

    72   checkGraphConArcList(adaptor, 3);

    74   checkGraphOutArcList(adaptor, n1, 0);

    75   checkGraphOutArcList(adaptor, n2, 1);

    76   checkGraphOutArcList(adaptor, n3, 2);

    78   checkGraphInArcList(adaptor, n1, 2);

    79   checkGraphInArcList(adaptor, n2, 1);

    80   checkGraphInArcList(adaptor, n3, 0);

    82   checkNodeIds(adaptor);

    83   checkArcIds(adaptor);

    85   checkGraphNodeMap(adaptor);

    86   checkGraphArcMap(adaptor);

    88   // Check the orientation of the arcs

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

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

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

    92   }

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

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

    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);

   103   adaptor.erase(a1);

   104   adaptor.erase(n3);

   106   // Check the adaptor

   107   checkGraphNodeList(adaptor, 3);

   108   checkGraphArcList(adaptor, 4);

   109   checkGraphConArcList(adaptor, 4);

   111   checkGraphOutArcList(adaptor, n1, 2);

   112   checkGraphOutArcList(adaptor, n2, 2);

   113   checkGraphOutArcList(adaptor, n4, 0);

   115   checkGraphInArcList(adaptor, n1, 0);

   116   checkGraphInArcList(adaptor, n2, 1);

   117   checkGraphInArcList(adaptor, n4, 3);

   119   checkNodeIds(adaptor);

   120   checkArcIds(adaptor);

   122   checkGraphNodeMap(adaptor);

   123   checkGraphArcMap(adaptor);

   125   // Check the digraph

   126   checkGraphNodeList(digraph, 3);

   127   checkGraphArcList(digraph, 4);

   128   checkGraphConArcList(digraph, 4);

   130   checkGraphOutArcList(digraph, n1, 0);

   131   checkGraphOutArcList(digraph, n2, 1);

   132   checkGraphOutArcList(digraph, n4, 3);

   134   checkGraphInArcList(digraph, n1, 2);

   135   checkGraphInArcList(digraph, n2, 2);

   136   checkGraphInArcList(digraph, n4, 0);

   138   checkNodeIds(digraph);

   139   checkArcIds(digraph);

   141   checkGraphNodeMap(digraph);

   142   checkGraphArcMap(digraph);

   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;

   153 }

   155 void checkSubDigraph() {

   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> >();

   168   // Create a digraph and an adaptor

   169   typedef ListDigraph Digraph;

   170   typedef Digraph::NodeMap<bool> NodeFilter;

   171   typedef Digraph::ArcMap<bool> ArcFilter;

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

   174   Digraph digraph;

   175   NodeFilter node_filter(digraph);

   176   ArcFilter arc_filter(digraph);

   177   Adaptor adaptor(digraph, node_filter, arc_filter);

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

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

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

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

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

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

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

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

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

   192   checkGraphNodeList(adaptor, 3);

   193   checkGraphArcList(adaptor, 3);

   194   checkGraphConArcList(adaptor, 3);

   196   checkGraphOutArcList(adaptor, n1, 2);

   197   checkGraphOutArcList(adaptor, n2, 1);

   198   checkGraphOutArcList(adaptor, n3, 0);

   200   checkGraphInArcList(adaptor, n1, 0);

   201   checkGraphInArcList(adaptor, n2, 1);

   202   checkGraphInArcList(adaptor, n3, 2);

   204   checkNodeIds(adaptor);

   205   checkArcIds(adaptor);

   207   checkGraphNodeMap(adaptor);

   208   checkGraphArcMap(adaptor);

   210   // Hide an arc

   211   adaptor.status(a2, false);

   212   adaptor.disable(a3);

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

   215   checkGraphNodeList(adaptor, 3);

   216   checkGraphArcList(adaptor, 2);

   217   checkGraphConArcList(adaptor, 2);

   219   checkGraphOutArcList(adaptor, n1, 1);

   220   checkGraphOutArcList(adaptor, n2, 1);

   221   checkGraphOutArcList(adaptor, n3, 0);

   223   checkGraphInArcList(adaptor, n1, 0);

   224   checkGraphInArcList(adaptor, n2, 1);

   225   checkGraphInArcList(adaptor, n3, 1);

   227   checkNodeIds(adaptor);

   228   checkArcIds(adaptor);

   230   checkGraphNodeMap(adaptor);

   231   checkGraphArcMap(adaptor);

   233   // Hide a node

   234   adaptor.status(n1, false);

   235   adaptor.disable(n3);

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

   238   checkGraphNodeList(adaptor, 2);

   239   checkGraphArcList(adaptor, 1);

   240   checkGraphConArcList(adaptor, 1);

   242   checkGraphOutArcList(adaptor, n2, 1);

   243   checkGraphOutArcList(adaptor, n3, 0);

   245   checkGraphInArcList(adaptor, n2, 0);

   246   checkGraphInArcList(adaptor, n3, 1);

   248   checkNodeIds(adaptor);

   249   checkArcIds(adaptor);

   251   checkGraphNodeMap(adaptor);

   252   checkGraphArcMap(adaptor);

   254   // Hide all nodes and arcs

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

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

   258   checkGraphNodeList(adaptor, 0);

   259   checkGraphArcList(adaptor, 0);

   260   checkGraphConArcList(adaptor, 0);

   262   checkNodeIds(adaptor);

   263   checkArcIds(adaptor);

   265   checkGraphNodeMap(adaptor);

   266   checkGraphArcMap(adaptor);

   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;

   277 }

   279 void checkFilterNodes1() {

   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> >();

   292   // Create a digraph and an adaptor

   293   typedef ListDigraph Digraph;

   294   typedef Digraph::NodeMap<bool> NodeFilter;

   295   typedef FilterNodes<Digraph, NodeFilter> Adaptor;

   297   Digraph digraph;

   298   NodeFilter node_filter(digraph);

   299   Adaptor adaptor(digraph, node_filter);

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

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

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

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

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

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

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

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

   312   checkGraphNodeList(adaptor, 3);

   313   checkGraphArcList(adaptor, 3);

   314   checkGraphConArcList(adaptor, 3);

   316   checkGraphOutArcList(adaptor, n1, 2);

   317   checkGraphOutArcList(adaptor, n2, 1);

   318   checkGraphOutArcList(adaptor, n3, 0);

   320   checkGraphInArcList(adaptor, n1, 0);

   321   checkGraphInArcList(adaptor, n2, 1);

   322   checkGraphInArcList(adaptor, n3, 2);

   324   checkNodeIds(adaptor);

   325   checkArcIds(adaptor);

   327   checkGraphNodeMap(adaptor);

   328   checkGraphArcMap(adaptor);

   330   // Hide a node

   331   adaptor.status(n1, false);

   332   adaptor.disable(n3);

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

   335   checkGraphNodeList(adaptor, 2);

   336   checkGraphArcList(adaptor, 1);

   337   checkGraphConArcList(adaptor, 1);

   339   checkGraphOutArcList(adaptor, n2, 1);

   340   checkGraphOutArcList(adaptor, n3, 0);

   342   checkGraphInArcList(adaptor, n2, 0);

   343   checkGraphInArcList(adaptor, n3, 1);

   345   checkNodeIds(adaptor);

   346   checkArcIds(adaptor);

   348   checkGraphNodeMap(adaptor);

   349   checkGraphArcMap(adaptor);

   351   // Hide all nodes

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

   354   checkGraphNodeList(adaptor, 0);

   355   checkGraphArcList(adaptor, 0);

   356   checkGraphConArcList(adaptor, 0);

   358   checkNodeIds(adaptor);

   359   checkArcIds(adaptor);

   361   checkGraphNodeMap(adaptor);

   362   checkGraphArcMap(adaptor);

   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;

   373 }

   375 void checkFilterArcs() {

   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> >();

   388   // Create a digraph and an adaptor

   389   typedef ListDigraph Digraph;

   390   typedef Digraph::ArcMap<bool> ArcFilter;

   391   typedef FilterArcs<Digraph, ArcFilter> Adaptor;

   393   Digraph digraph;

   394   ArcFilter arc_filter(digraph);

   395   Adaptor adaptor(digraph, arc_filter);

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

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

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

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

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

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

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

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

   408   checkGraphNodeList(adaptor, 3);

   409   checkGraphArcList(adaptor, 3);

   410   checkGraphConArcList(adaptor, 3);

   412   checkGraphOutArcList(adaptor, n1, 2);

   413   checkGraphOutArcList(adaptor, n2, 1);

   414   checkGraphOutArcList(adaptor, n3, 0);

   416   checkGraphInArcList(adaptor, n1, 0);

   417   checkGraphInArcList(adaptor, n2, 1);

   418   checkGraphInArcList(adaptor, n3, 2);

   420   checkNodeIds(adaptor);

   421   checkArcIds(adaptor);

   423   checkGraphNodeMap(adaptor);

   424   checkGraphArcMap(adaptor);

   426   // Hide an arc

   427   adaptor.status(a2, false);

   428   adaptor.disable(a3);

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

   431   checkGraphNodeList(adaptor, 3);

   432   checkGraphArcList(adaptor, 2);

   433   checkGraphConArcList(adaptor, 2);

   435   checkGraphOutArcList(adaptor, n1, 1);

   436   checkGraphOutArcList(adaptor, n2, 1);

   437   checkGraphOutArcList(adaptor, n3, 0);

   439   checkGraphInArcList(adaptor, n1, 0);

   440   checkGraphInArcList(adaptor, n2, 1);

   441   checkGraphInArcList(adaptor, n3, 1);

   443   checkNodeIds(adaptor);

   444   checkArcIds(adaptor);

   446   checkGraphNodeMap(adaptor);

   447   checkGraphArcMap(adaptor);

   449   // Hide all arcs

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

   452   checkGraphNodeList(adaptor, 3);

   453   checkGraphArcList(adaptor, 0);

   454   checkGraphConArcList(adaptor, 0);

   456   checkNodeIds(adaptor);

   457   checkArcIds(adaptor);

   459   checkGraphNodeMap(adaptor);

   460   checkGraphArcMap(adaptor);

   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;

   471 }

   473 void checkUndirector() {

   474   // Check concepts

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

   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> >();

   487   // Create a digraph and an adaptor

   488   typedef ListDigraph Digraph;

   489   typedef Undirector<Digraph> Adaptor;

   491   Digraph digraph;

   492   Adaptor adaptor(digraph);

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

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

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

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

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

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

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

   503   // Check the original digraph

   504   checkGraphNodeList(digraph, 3);

   505   checkGraphArcList(digraph, 3);

   506   checkGraphConArcList(digraph, 3);

   508   checkGraphOutArcList(digraph, n1, 2);

   509   checkGraphOutArcList(digraph, n2, 1);

   510   checkGraphOutArcList(digraph, n3, 0);

   512   checkGraphInArcList(digraph, n1, 0);

   513   checkGraphInArcList(digraph, n2, 1);

   514   checkGraphInArcList(digraph, n3, 2);

   516   checkNodeIds(digraph);

   517   checkArcIds(digraph);

   519   checkGraphNodeMap(digraph);

   520   checkGraphArcMap(digraph);

   522   // Check the adaptor

   523   checkGraphNodeList(adaptor, 3);

   524   checkGraphArcList(adaptor, 6);

   525   checkGraphEdgeList(adaptor, 3);

   526   checkGraphConArcList(adaptor, 6);

   527   checkGraphConEdgeList(adaptor, 3);

   529   checkGraphIncEdgeArcLists(adaptor, n1, 2);

   530   checkGraphIncEdgeArcLists(adaptor, n2, 2);

   531   checkGraphIncEdgeArcLists(adaptor, n3, 2);

   533   checkNodeIds(adaptor);

   534   checkArcIds(adaptor);

   535   checkEdgeIds(adaptor);

   537   checkGraphNodeMap(adaptor);

   538   checkGraphArcMap(adaptor);

   539   checkGraphEdgeMap(adaptor);

   541   // Check the edges of the adaptor

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

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

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

   545   }

   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>();

   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   }

   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   }

   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;

   582 }

   584 void checkResidualDigraph() {

   585   // Check concepts

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

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

   589   // Create a digraph and an adaptor

   590   typedef ListDigraph Digraph;

   591   typedef Digraph::ArcMap<int> IntArcMap;

   592   typedef ResidualDigraph<Digraph, IntArcMap> Adaptor;

   594   Digraph digraph;

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

   596   Adaptor adaptor(digraph, capacity, flow);

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

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

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

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

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

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

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

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

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

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

   610   capacity[a1] = 8;

   611   capacity[a2] = 6;

   612   capacity[a3] = 4;

   613   capacity[a4] = 4;

   614   capacity[a5] = 6;

   615   capacity[a6] = 10;

   617   // Check the adaptor with various flow values

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

   619     flow[a] = 0;

   620   }

   622   checkGraphNodeList(adaptor, 4);

   623   checkGraphArcList(adaptor, 6);

   624   checkGraphConArcList(adaptor, 6);

   626   checkGraphOutArcList(adaptor, n1, 3);

   627   checkGraphOutArcList(adaptor, n2, 2);

   628   checkGraphOutArcList(adaptor, n3, 1);

   629   checkGraphOutArcList(adaptor, n4, 0);

   631   checkGraphInArcList(adaptor, n1, 0);

   632   checkGraphInArcList(adaptor, n2, 1);

   633   checkGraphInArcList(adaptor, n3, 2);

   634   checkGraphInArcList(adaptor, n4, 3);

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

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

   638   }

   640   checkGraphNodeList(adaptor, 4);

   641   checkGraphArcList(adaptor, 12);

   642   checkGraphConArcList(adaptor, 12);

   644   checkGraphOutArcList(adaptor, n1, 3);

   645   checkGraphOutArcList(adaptor, n2, 3);

   646   checkGraphOutArcList(adaptor, n3, 3);

   647   checkGraphOutArcList(adaptor, n4, 3);

   649   checkGraphInArcList(adaptor, n1, 3);

   650   checkGraphInArcList(adaptor, n2, 3);

   651   checkGraphInArcList(adaptor, n3, 3);

   652   checkGraphInArcList(adaptor, n4, 3);

   654   checkNodeIds(adaptor);

   655   checkArcIds(adaptor);

   657   checkGraphNodeMap(adaptor);

   658   checkGraphArcMap(adaptor);

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

   661     flow[a] = capacity[a];

   662   }

   664   checkGraphNodeList(adaptor, 4);

   665   checkGraphArcList(adaptor, 6);

   666   checkGraphConArcList(adaptor, 6);

   668   checkGraphOutArcList(adaptor, n1, 0);

   669   checkGraphOutArcList(adaptor, n2, 1);

   670   checkGraphOutArcList(adaptor, n3, 2);

   671   checkGraphOutArcList(adaptor, n4, 3);

   673   checkGraphInArcList(adaptor, n1, 3);

   674   checkGraphInArcList(adaptor, n2, 2);

   675   checkGraphInArcList(adaptor, n3, 1);

   676   checkGraphInArcList(adaptor, n4, 0);

   678   // Saturate all backward arcs

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

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

   681     if (adaptor.backward(a))

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

   683   }

   685   checkGraphNodeList(adaptor, 4);

   686   checkGraphArcList(adaptor, 6);

   687   checkGraphConArcList(adaptor, 6);

   689   checkGraphOutArcList(adaptor, n1, 3);

   690   checkGraphOutArcList(adaptor, n2, 2);

   691   checkGraphOutArcList(adaptor, n3, 1);

   692   checkGraphOutArcList(adaptor, n4, 0);

   694   checkGraphInArcList(adaptor, n1, 0);

   695   checkGraphInArcList(adaptor, n2, 1);

   696   checkGraphInArcList(adaptor, n3, 2);

   697   checkGraphInArcList(adaptor, n4, 3);

   699   // Find maximum flow by augmenting along shortest paths

   700   int flow_value = 0;

   701   Adaptor::ResidualCapacity res_cap(adaptor);

   702   while (true) {

   704     Bfs<Adaptor> bfs(adaptor);

   705     bfs.run(n1, n4);

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

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

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

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

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

   714     }

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

   717       adaptor.augment(a, min);

   718     }

   719     flow_value += min;

   720   }

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

   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   }

   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);

   740 }

   742 void checkSplitNodes() {

   743   // Check concepts

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

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

   747   // Create a digraph and an adaptor

   748   typedef ListDigraph Digraph;

   749   typedef SplitNodes<Digraph> Adaptor;

   751   Digraph digraph;

   752   Adaptor adaptor(digraph);

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

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

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

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

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

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

   762   checkGraphNodeList(adaptor, 6);

   763   checkGraphArcList(adaptor, 6);

   764   checkGraphConArcList(adaptor, 6);

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

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

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

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

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

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

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

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

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

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

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

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

   780   checkNodeIds(adaptor);

   781   checkArcIds(adaptor);

   783   checkGraphNodeMap(adaptor);

   784   checkGraphArcMap(adaptor);

   786   // Check split

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

   788     if (adaptor.origArc(a)) {

   789       Digraph::Arc oa = a;

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

   791             "Wrong split");

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

   793             "Wrong split");

   794     } else {

   795       Digraph::Node on = a;

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

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

   798     }

   799   }

   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>();

   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   }

   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   }

   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>();

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

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

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

   844   }

   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   }

   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");

   860 }

   862 void checkSubGraph() {

   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> >();

   875   // Create a graph and an adaptor

   876   typedef ListGraph Graph;

   877   typedef Graph::NodeMap<bool> NodeFilter;

   878   typedef Graph::EdgeMap<bool> EdgeFilter;

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

   881   Graph graph;

   882   NodeFilter node_filter(graph);

   883   EdgeFilter edge_filter(graph);

   884   Adaptor adaptor(graph, node_filter, edge_filter);

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

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

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

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

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

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

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

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

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

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

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

   901   checkGraphNodeList(adaptor, 4);

   902   checkGraphArcList(adaptor, 8);

   903   checkGraphEdgeList(adaptor, 4);

   904   checkGraphConArcList(adaptor, 8);

   905   checkGraphConEdgeList(adaptor, 4);

   907   checkGraphIncEdgeArcLists(adaptor, n1, 2);

   908   checkGraphIncEdgeArcLists(adaptor, n2, 2);

   909   checkGraphIncEdgeArcLists(adaptor, n3, 3);

   910   checkGraphIncEdgeArcLists(adaptor, n4, 1);

   912   checkNodeIds(adaptor);

   913   checkArcIds(adaptor);

   914   checkEdgeIds(adaptor);

   916   checkGraphNodeMap(adaptor);

   917   checkGraphArcMap(adaptor);

   918   checkGraphEdgeMap(adaptor);

   920   // Hide an edge

   921   adaptor.status(e2, false);

   922   adaptor.disable(e3);

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

   925   checkGraphNodeList(adaptor, 4);

   926   checkGraphArcList(adaptor, 6);

   927   checkGraphEdgeList(adaptor, 3);

   928   checkGraphConArcList(adaptor, 6);

   929   checkGraphConEdgeList(adaptor, 3);

   931   checkGraphIncEdgeArcLists(adaptor, n1, 1);

   932   checkGraphIncEdgeArcLists(adaptor, n2, 2);

   933   checkGraphIncEdgeArcLists(adaptor, n3, 2);

   934   checkGraphIncEdgeArcLists(adaptor, n4, 1);

   936   checkNodeIds(adaptor);

   937   checkArcIds(adaptor);

   938   checkEdgeIds(adaptor);

   940   checkGraphNodeMap(adaptor);

   941   checkGraphArcMap(adaptor);

   942   checkGraphEdgeMap(adaptor);

   944   // Hide a node

   945   adaptor.status(n1, false);

   946   adaptor.disable(n3);

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

   949   checkGraphNodeList(adaptor, 3);

   950   checkGraphArcList(adaptor, 4);

   951   checkGraphEdgeList(adaptor, 2);

   952   checkGraphConArcList(adaptor, 4);

   953   checkGraphConEdgeList(adaptor, 2);

   955   checkGraphIncEdgeArcLists(adaptor, n2, 1);

   956   checkGraphIncEdgeArcLists(adaptor, n3, 2);

   957   checkGraphIncEdgeArcLists(adaptor, n4, 1);

   959   checkNodeIds(adaptor);

   960   checkArcIds(adaptor);

   961   checkEdgeIds(adaptor);

   963   checkGraphNodeMap(adaptor);

   964   checkGraphArcMap(adaptor);

   965   checkGraphEdgeMap(adaptor);

   967   // Hide all nodes and edges

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

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

   971   checkGraphNodeList(adaptor, 0);

   972   checkGraphArcList(adaptor, 0);

   973   checkGraphEdgeList(adaptor, 0);

   974   checkGraphConArcList(adaptor, 0);

   975   checkGraphConEdgeList(adaptor, 0);

   977   checkNodeIds(adaptor);

   978   checkArcIds(adaptor);

   979   checkEdgeIds(adaptor);

   981   checkGraphNodeMap(adaptor);

   982   checkGraphArcMap(adaptor);

   983   checkGraphEdgeMap(adaptor);

   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;

   994 }

   996 void checkFilterNodes2() {

   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> >();

  1009   // Create a graph and an adaptor

  1010   typedef ListGraph Graph;

  1011   typedef Graph::NodeMap<bool> NodeFilter;

  1012   typedef FilterNodes<Graph, NodeFilter> Adaptor;

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

  1015   Graph graph;

  1016   NodeFilter node_filter(graph);

  1017   Adaptor adaptor(graph, node_filter);

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

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

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

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

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

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

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

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

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

  1031   checkGraphNodeList(adaptor, 4);

  1032   checkGraphArcList(adaptor, 8);

  1033   checkGraphEdgeList(adaptor, 4);

  1034   checkGraphConArcList(adaptor, 8);

  1035   checkGraphConEdgeList(adaptor, 4);

  1037   checkGraphIncEdgeArcLists(adaptor, n1, 2);

  1038   checkGraphIncEdgeArcLists(adaptor, n2, 2);

  1039   checkGraphIncEdgeArcLists(adaptor, n3, 3);

  1040   checkGraphIncEdgeArcLists(adaptor, n4, 1);

  1042   checkNodeIds(adaptor);

  1043   checkArcIds(adaptor);

  1044   checkEdgeIds(adaptor);

  1046   checkGraphNodeMap(adaptor);

  1047   checkGraphArcMap(adaptor);

  1048   checkGraphEdgeMap(adaptor);

  1050   // Hide a node

  1051   adaptor.status(n1, false);

  1052   adaptor.disable(n3);

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

  1055   checkGraphNodeList(adaptor, 3);

  1056   checkGraphArcList(adaptor, 4);

  1057   checkGraphEdgeList(adaptor, 2);

  1058   checkGraphConArcList(adaptor, 4);

  1059   checkGraphConEdgeList(adaptor, 2);

  1061   checkGraphIncEdgeArcLists(adaptor, n2, 1);

  1062   checkGraphIncEdgeArcLists(adaptor, n3, 2);

  1063   checkGraphIncEdgeArcLists(adaptor, n4, 1);

  1065   checkNodeIds(adaptor);

  1066   checkArcIds(adaptor);

  1067   checkEdgeIds(adaptor);

  1069   checkGraphNodeMap(adaptor);

  1070   checkGraphArcMap(adaptor);

  1071   checkGraphEdgeMap(adaptor);

  1073   // Hide all nodes

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

  1076   checkGraphNodeList(adaptor, 0);

  1077   checkGraphArcList(adaptor, 0);

  1078   checkGraphEdgeList(adaptor, 0);

  1079   checkGraphConArcList(adaptor, 0);

  1080   checkGraphConEdgeList(adaptor, 0);

  1082   checkNodeIds(adaptor);

  1083   checkArcIds(adaptor);

  1084   checkEdgeIds(adaptor);

  1086   checkGraphNodeMap(adaptor);

  1087   checkGraphArcMap(adaptor);

  1088   checkGraphEdgeMap(adaptor);

  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;

  1099 }

  1101 void checkFilterEdges() {

  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> >();

  1114   // Create a graph and an adaptor

  1115   typedef ListGraph Graph;

  1116   typedef Graph::EdgeMap<bool> EdgeFilter;

  1117   typedef FilterEdges<Graph, EdgeFilter> Adaptor;

  1119   Graph graph;

  1120   EdgeFilter edge_filter(graph);

  1121   Adaptor adaptor(graph, edge_filter);

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

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

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

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

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

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

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

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

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

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

  1136   checkGraphNodeList(adaptor, 4);

  1137   checkGraphArcList(adaptor, 8);

  1138   checkGraphEdgeList(adaptor, 4);

  1139   checkGraphConArcList(adaptor, 8);

  1140   checkGraphConEdgeList(adaptor, 4);

  1142   checkGraphIncEdgeArcLists(adaptor, n1, 2);

  1143   checkGraphIncEdgeArcLists(adaptor, n2, 2);

  1144   checkGraphIncEdgeArcLists(adaptor, n3, 3);

  1145   checkGraphIncEdgeArcLists(adaptor, n4, 1);

  1147   checkNodeIds(adaptor);

  1148   checkArcIds(adaptor);

  1149   checkEdgeIds(adaptor);

  1151   checkGraphNodeMap(adaptor);

  1152   checkGraphArcMap(adaptor);

  1153   checkGraphEdgeMap(adaptor);

  1155   // Hide an edge

  1156   adaptor.status(e2, false);

  1157   adaptor.disable(e3);

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

  1160   checkGraphNodeList(adaptor, 4);

  1161   checkGraphArcList(adaptor, 6);

  1162   checkGraphEdgeList(adaptor, 3);

  1163   checkGraphConArcList(adaptor, 6);

  1164   checkGraphConEdgeList(adaptor, 3);

  1166   checkGraphIncEdgeArcLists(adaptor, n1, 1);

  1167   checkGraphIncEdgeArcLists(adaptor, n2, 2);

  1168   checkGraphIncEdgeArcLists(adaptor, n3, 2);

  1169   checkGraphIncEdgeArcLists(adaptor, n4, 1);

  1171   checkNodeIds(adaptor);

  1172   checkArcIds(adaptor);

  1173   checkEdgeIds(adaptor);

  1175   checkGraphNodeMap(adaptor);

  1176   checkGraphArcMap(adaptor);

  1177   checkGraphEdgeMap(adaptor);

  1179   // Hide all edges

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

  1182   checkGraphNodeList(adaptor, 4);

  1183   checkGraphArcList(adaptor, 0);

  1184   checkGraphEdgeList(adaptor, 0);

  1185   checkGraphConArcList(adaptor, 0);

  1186   checkGraphConEdgeList(adaptor, 0);

  1188   checkNodeIds(adaptor);

  1189   checkArcIds(adaptor);

  1190   checkEdgeIds(adaptor);

  1192   checkGraphNodeMap(adaptor);

  1193   checkGraphArcMap(adaptor);

  1194   checkGraphEdgeMap(adaptor);

  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;

  1205 }

  1207 void checkOrienter() {

  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> >();

  1220   // Create a graph and an adaptor

  1221   typedef ListGraph Graph;

  1222   typedef ListGraph::EdgeMap<bool> DirMap;

  1223   typedef Orienter<Graph> Adaptor;

  1225   Graph graph;

  1226   DirMap dir(graph);

  1227   Adaptor adaptor(graph, dir);

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

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

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

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

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

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

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

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

  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);

  1247   checkGraphIncEdgeArcLists(graph, n1, 2);

  1248   checkGraphIncEdgeArcLists(graph, n2, 2);

  1249   checkGraphIncEdgeArcLists(graph, n3, 2);

  1251   checkNodeIds(graph);

  1252   checkArcIds(graph);

  1253   checkEdgeIds(graph);

  1255   checkGraphNodeMap(graph);

  1256   checkGraphArcMap(graph);

  1257   checkGraphEdgeMap(graph);

  1259   // Check the adaptor

  1260   checkGraphNodeList(adaptor, 3);

  1261   checkGraphArcList(adaptor, 3);

  1262   checkGraphConArcList(adaptor, 3);

  1264   checkGraphOutArcList(adaptor, n1, 2);

  1265   checkGraphOutArcList(adaptor, n2, 1);

  1266   checkGraphOutArcList(adaptor, n3, 0);

  1268   checkGraphInArcList(adaptor, n1, 0);

  1269   checkGraphInArcList(adaptor, n2, 1);

  1270   checkGraphInArcList(adaptor, n3, 2);

  1272   checkNodeIds(adaptor);

  1273   checkArcIds(adaptor);

  1275   checkGraphNodeMap(adaptor);

  1276   checkGraphArcMap(adaptor);

  1278   // Check direction changing

  1279   {

  1280     dir[e1] = true;

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

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

  1284     dir[e1] = false;

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

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

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

  1289     dir[e1] = n1 == u;

  1290   }

  1292   {

  1293     dir[e2] = true;

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

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

  1297     dir[e2] = false;

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

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

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

  1302     dir[e2] = n3 == u;

  1303   }

  1305   {

  1306     dir[e3] = true;

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

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

  1310     dir[e3] = false;

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

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

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

  1315     dir[e3] = n2 == u;

  1316   }

  1318   // Check the adaptor again

  1319   checkGraphNodeList(adaptor, 3);

  1320   checkGraphArcList(adaptor, 3);

  1321   checkGraphConArcList(adaptor, 3);

  1323   checkGraphOutArcList(adaptor, n1, 1);

  1324   checkGraphOutArcList(adaptor, n2, 1);

  1325   checkGraphOutArcList(adaptor, n3, 1);

  1327   checkGraphInArcList(adaptor, n1, 1);

  1328   checkGraphInArcList(adaptor, n2, 1);

  1329   checkGraphInArcList(adaptor, n3, 1);

  1331   checkNodeIds(adaptor);

  1332   checkArcIds(adaptor);

  1334   checkGraphNodeMap(adaptor);

  1335   checkGraphArcMap(adaptor);

  1337   // Check reverseArc()

  1338   adaptor.reverseArc(e2);

  1339   adaptor.reverseArc(e3);

  1340   adaptor.reverseArc(e2);

  1342   checkGraphNodeList(adaptor, 3);

  1343   checkGraphArcList(adaptor, 3);

  1344   checkGraphConArcList(adaptor, 3);

  1346   checkGraphOutArcList(adaptor, n1, 1);

  1347   checkGraphOutArcList(adaptor, n2, 0);

  1348   checkGraphOutArcList(adaptor, n3, 2);

  1350   checkGraphInArcList(adaptor, n1, 1);

  1351   checkGraphInArcList(adaptor, n2, 2);

  1352   checkGraphInArcList(adaptor, n3, 0);

  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;

  1363 }

  1365 void checkCombiningAdaptors() {

  1366   // Create a grid graph

  1367   GridGraph graph(2,2);

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

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

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

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

  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;

  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>();

  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);

  1397   // Check adaptor

  1398   checkGraphNodeList(adaptor, 8);

  1399   checkGraphArcList(adaptor, 8);

  1400   checkGraphConArcList(adaptor, 8);

  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);

  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);

  1420   checkNodeIds(adaptor);

  1421   checkArcIds(adaptor);

  1423   checkGraphNodeMap(adaptor);

  1424   checkGraphArcMap(adaptor);

  1426   // Check uadaptor

  1427   checkGraphNodeList(uadaptor, 8);

  1428   checkGraphEdgeList(uadaptor, 8);

  1429   checkGraphArcList(uadaptor, 16);

  1430   checkGraphConEdgeList(uadaptor, 8);

  1431   checkGraphConArcList(uadaptor, 16);

  1433   checkNodeIds(uadaptor);

  1434   checkEdgeIds(uadaptor);

  1435   checkArcIds(uadaptor);

  1437   checkGraphNodeMap(uadaptor);

  1438   checkGraphEdgeMap(uadaptor);

  1439   checkGraphArcMap(uadaptor);

  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);

  1450   // Check uuadaptor

  1451   checkGraphNodeList(uuadaptor, 8);

  1452   checkGraphEdgeList(uuadaptor, 16);

  1453   checkGraphArcList(uuadaptor, 32);

  1454   checkGraphConEdgeList(uuadaptor, 16);

  1455   checkGraphConArcList(uuadaptor, 32);

  1457   checkNodeIds(uuadaptor);

  1458   checkEdgeIds(uuadaptor);

  1459   checkArcIds(uuadaptor);

  1461   checkGraphNodeMap(uuadaptor);

  1462   checkGraphEdgeMap(uuadaptor);

  1463   checkGraphArcMap(uuadaptor);

  1464 }

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

  1467   // Check the digraph adaptors (using ListDigraph)

  1468   checkReverseDigraph();

  1469   checkSubDigraph();

  1470   checkFilterNodes1();

  1471   checkFilterArcs();

  1472   checkUndirector();

  1473   checkResidualDigraph();

  1474   checkSplitNodes();

  1476   // Check the graph adaptors (using ListGraph)

  1477   checkSubGraph();

  1478   checkFilterNodes2();

  1479   checkFilterEdges();

  1480   checkOrienter();

  1482   // Combine adaptors (using GridGraph)

  1483   checkCombiningAdaptors();

  1485   return 0;

  1486 }

author	Alpar Juttner <alpar@cs.elte.hu>
	Fri, 25 Sep 2009 09:13:03 +0200
changeset 764	684964884a2e
parent 487	acfb0f24d178
child 550	c35afa9e89e7
child 1156	939d747055cd
child 1157	761fe0846f49
permissions	-rw-r--r--