Mercuriallemon-main / file revision
summary | shortlog | changelog | graph | tags | bookmarks | branches | files | changeset | file | latest | revisions | annotate | diff | comparison | raw | help
test/maps_test.cc
author Peter Kovacs <kpeter@inf.elte.hu>
Tue, 15 Mar 2011 19:32:21 +0100
changeset 936 ddd3c0d3d9bf
parent 789 8ddb7deabab9
child 942 633956ca9421
permissions -rw-r--r--
Implement the scaling Price Refinement heuristic in CostScaling (#417)
instead of Early Termination.

These two heuristics are similar, but the newer one is faster
and not only makes it possible to skip some epsilon phases, but
it can improve the performance of the other phases, as well. 
     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-2010

     6  * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport

     7  * (Egervary Research Group on Combinatorial Optimization, EGRES).

     8  *

     9  * Permission to use, modify and distribute this software is granted

    10  * provided that this copyright notice appears in all copies. For

    11  * precise terms see the accompanying LICENSE file.

    12  *

    13  * This software is provided "AS IS" with no warranty of any kind,

    14  * express or implied, and with no claim as to its suitability for any

    15  * purpose.

    16  *

    17  */

    18 

    19 #include <deque>

    20 #include <set>

    21 

    22 #include <lemon/concept_check.h>

    23 #include <lemon/concepts/maps.h>

    24 #include <lemon/maps.h>

    25 #include <lemon/list_graph.h>

    26 #include <lemon/smart_graph.h>

    27 #include <lemon/adaptors.h>

    28 #include <lemon/dfs.h>

    29 #include <algorithm>

    30 

    31 #include "test_tools.h"

    32 

    33 using namespace lemon;

    34 using namespace lemon::concepts;

    35 

    36 struct A {};

    37 inline bool operator<(A, A) { return true; }

    38 struct B {};

    39 

    40 class C {

    41   int _x;

    42 public:

    43   C(int x) : _x(x) {}

    44   int get() const { return _x; }

    45 };

    46 inline bool operator<(C c1, C c2) { return c1.get() < c2.get(); }

    47 inline bool operator==(C c1, C c2) { return c1.get() == c2.get(); }

    48 

    49 C createC(int x) { return C(x); }

    50 

    51 template <typename T>

    52 class Less {

    53   T _t;

    54 public:

    55   Less(T t): _t(t) {}

    56   bool operator()(const T& t) const { return t < _t; }

    57 };

    58 

    59 class F {

    60 public:

    61   typedef A argument_type;

    62   typedef B result_type;

    63 

    64   B operator()(const A&) const { return B(); }

    65 private:

    66   F& operator=(const F&);

    67 };

    68 

    69 int func(A) { return 3; }

    70 

    71 int binc(int a, B) { return a+1; }

    72 

    73 template <typename T>

    74 class Sum {

    75   T& _sum;

    76 public:

    77   Sum(T& sum) : _sum(sum) {}

    78   void operator()(const T& t) { _sum += t; }

    79 };

    80 

    81 typedef ReadMap<A, double> DoubleMap;

    82 typedef ReadWriteMap<A, double> DoubleWriteMap;

    83 typedef ReferenceMap<A, double, double&, const double&> DoubleRefMap;

    84 

    85 typedef ReadMap<A, bool> BoolMap;

    86 typedef ReadWriteMap<A, bool> BoolWriteMap;

    87 typedef ReferenceMap<A, bool, bool&, const bool&> BoolRefMap;

    88 

    89 int main()

    90 {

    91   // Map concepts

    92   checkConcept<ReadMap<A,B>, ReadMap<A,B> >();

    93   checkConcept<ReadMap<A,C>, ReadMap<A,C> >();

    94   checkConcept<WriteMap<A,B>, WriteMap<A,B> >();

    95   checkConcept<WriteMap<A,C>, WriteMap<A,C> >();

    96   checkConcept<ReadWriteMap<A,B>, ReadWriteMap<A,B> >();

    97   checkConcept<ReadWriteMap<A,C>, ReadWriteMap<A,C> >();

    98   checkConcept<ReferenceMap<A,B,B&,const B&>, ReferenceMap<A,B,B&,const B&> >();

    99   checkConcept<ReferenceMap<A,C,C&,const C&>, ReferenceMap<A,C,C&,const C&> >();

   100 

   101   // NullMap

   102   {

   103     checkConcept<ReadWriteMap<A,B>, NullMap<A,B> >();

   104     NullMap<A,B> map1;

   105     NullMap<A,B> map2 = map1;

   106     map1 = nullMap<A,B>();

   107   }

   108 

   109   // ConstMap

   110   {

   111     checkConcept<ReadWriteMap<A,B>, ConstMap<A,B> >();

   112     checkConcept<ReadWriteMap<A,C>, ConstMap<A,C> >();

   113     ConstMap<A,B> map1;

   114     ConstMap<A,B> map2 = B();

   115     ConstMap<A,B> map3 = map1;

   116     map1 = constMap<A>(B());

   117     map1 = constMap<A,B>();

   118     map1.setAll(B());

   119     ConstMap<A,C> map4(C(1));

   120     ConstMap<A,C> map5 = map4;

   121     map4 = constMap<A>(C(2));

   122     map4.setAll(C(3));

   123 

   124     checkConcept<ReadWriteMap<A,int>, ConstMap<A,int> >();

   125     check(constMap<A>(10)[A()] == 10, "Something is wrong with ConstMap");

   126 

   127     checkConcept<ReadWriteMap<A,int>, ConstMap<A,Const<int,10> > >();

   128     ConstMap<A,Const<int,10> > map6;

   129     ConstMap<A,Const<int,10> > map7 = map6;

   130     map6 = constMap<A,int,10>();

   131     map7 = constMap<A,Const<int,10> >();

   132     check(map6[A()] == 10 && map7[A()] == 10,

   133           "Something is wrong with ConstMap");

   134   }

   135 

   136   // IdentityMap

   137   {

   138     checkConcept<ReadMap<A,A>, IdentityMap<A> >();

   139     IdentityMap<A> map1;

   140     IdentityMap<A> map2 = map1;

   141     map1 = identityMap<A>();

   142 

   143     checkConcept<ReadMap<double,double>, IdentityMap<double> >();

   144     check(identityMap<double>()[1.0] == 1.0 &&

   145           identityMap<double>()[3.14] == 3.14,

   146           "Something is wrong with IdentityMap");

   147   }

   148 

   149   // RangeMap

   150   {

   151     checkConcept<ReferenceMap<int,B,B&,const B&>, RangeMap<B> >();

   152     RangeMap<B> map1;

   153     RangeMap<B> map2(10);

   154     RangeMap<B> map3(10,B());

   155     RangeMap<B> map4 = map1;

   156     RangeMap<B> map5 = rangeMap<B>();

   157     RangeMap<B> map6 = rangeMap<B>(10);

   158     RangeMap<B> map7 = rangeMap(10,B());

   159 

   160     checkConcept< ReferenceMap<int, double, double&, const double&>,

   161                   RangeMap<double> >();

   162     std::vector<double> v(10, 0);

   163     v[5] = 100;

   164     RangeMap<double> map8(v);

   165     RangeMap<double> map9 = rangeMap(v);

   166     check(map9.size() == 10 && map9[2] == 0 && map9[5] == 100,

   167           "Something is wrong with RangeMap");

   168   }

   169 

   170   // SparseMap

   171   {

   172     checkConcept<ReferenceMap<A,B,B&,const B&>, SparseMap<A,B> >();

   173     SparseMap<A,B> map1;

   174     SparseMap<A,B> map2 = B();

   175     SparseMap<A,B> map3 = sparseMap<A,B>();

   176     SparseMap<A,B> map4 = sparseMap<A>(B());

   177 

   178     checkConcept< ReferenceMap<double, int, int&, const int&>,

   179                   SparseMap<double, int> >();

   180     std::map<double, int> m;

   181     SparseMap<double, int> map5(m);

   182     SparseMap<double, int> map6(m,10);

   183     SparseMap<double, int> map7 = sparseMap(m);

   184     SparseMap<double, int> map8 = sparseMap(m,10);

   185 

   186     check(map5[1.0] == 0 && map5[3.14] == 0 &&

   187           map6[1.0] == 10 && map6[3.14] == 10,

   188           "Something is wrong with SparseMap");

   189     map5[1.0] = map6[3.14] = 100;

   190     check(map5[1.0] == 100 && map5[3.14] == 0 &&

   191           map6[1.0] == 10 && map6[3.14] == 100,

   192           "Something is wrong with SparseMap");

   193   }

   194 

   195   // ComposeMap

   196   {

   197     typedef ComposeMap<DoubleMap, ReadMap<B,A> > CompMap;

   198     checkConcept<ReadMap<B,double>, CompMap>();

   199     CompMap map1 = CompMap(DoubleMap(),ReadMap<B,A>());

   200     CompMap map2 = composeMap(DoubleMap(), ReadMap<B,A>());

   201 

   202     SparseMap<double, bool> m1(false); m1[3.14] = true;

   203     RangeMap<double> m2(2); m2[0] = 3.0; m2[1] = 3.14;

   204     check(!composeMap(m1,m2)[0] && composeMap(m1,m2)[1],

   205           "Something is wrong with ComposeMap")

   206   }

   207 

   208   // CombineMap

   209   {

   210     typedef CombineMap<DoubleMap, DoubleMap, std::plus<double> > CombMap;

   211     checkConcept<ReadMap<A,double>, CombMap>();

   212     CombMap map1 = CombMap(DoubleMap(), DoubleMap());

   213     CombMap map2 = combineMap(DoubleMap(), DoubleMap(), std::plus<double>());

   214 

   215     check(combineMap(constMap<B,int,2>(), identityMap<B>(), &binc)[B()] == 3,

   216           "Something is wrong with CombineMap");

   217   }

   218 

   219   // FunctorToMap, MapToFunctor

   220   {

   221     checkConcept<ReadMap<A,B>, FunctorToMap<F,A,B> >();

   222     checkConcept<ReadMap<A,B>, FunctorToMap<F> >();

   223     FunctorToMap<F> map1;

   224     FunctorToMap<F> map2 = FunctorToMap<F>(F());

   225     B b = functorToMap(F())[A()];

   226 

   227     checkConcept<ReadMap<A,B>, MapToFunctor<ReadMap<A,B> > >();

   228     MapToFunctor<ReadMap<A,B> > map =

   229       MapToFunctor<ReadMap<A,B> >(ReadMap<A,B>());

   230 

   231     check(functorToMap(&func)[A()] == 3,

   232           "Something is wrong with FunctorToMap");

   233     check(mapToFunctor(constMap<A,int>(2))(A()) == 2,

   234           "Something is wrong with MapToFunctor");

   235     check(mapToFunctor(functorToMap(&func))(A()) == 3 &&

   236           mapToFunctor(functorToMap(&func))[A()] == 3,

   237           "Something is wrong with FunctorToMap or MapToFunctor");

   238     check(functorToMap(mapToFunctor(constMap<A,int>(2)))[A()] == 2,

   239           "Something is wrong with FunctorToMap or MapToFunctor");

   240   }

   241 

   242   // ConvertMap

   243   {

   244     checkConcept<ReadMap<double,double>,

   245       ConvertMap<ReadMap<double, int>, double> >();

   246     ConvertMap<RangeMap<bool>, int> map1(rangeMap(1, true));

   247     ConvertMap<RangeMap<bool>, int> map2 = convertMap<int>(rangeMap(2, false));

   248   }

   249 

   250   // ForkMap

   251   {

   252     checkConcept<DoubleWriteMap, ForkMap<DoubleWriteMap, DoubleWriteMap> >();

   253 

   254     typedef RangeMap<double> RM;

   255     typedef SparseMap<int, double> SM;

   256     RM m1(10, -1);

   257     SM m2(-1);

   258     checkConcept<ReadWriteMap<int, double>, ForkMap<RM, SM> >();

   259     checkConcept<ReadWriteMap<int, double>, ForkMap<SM, RM> >();

   260     ForkMap<RM, SM> map1(m1,m2);

   261     ForkMap<SM, RM> map2 = forkMap(m2,m1);

   262     map2.set(5, 10);

   263     check(m1[1] == -1 && m1[5] == 10 && m2[1] == -1 &&

   264           m2[5] == 10 && map2[1] == -1 && map2[5] == 10,

   265           "Something is wrong with ForkMap");

   266   }

   267 

   268   // Arithmetic maps:

   269   // - AddMap, SubMap, MulMap, DivMap

   270   // - ShiftMap, ShiftWriteMap, ScaleMap, ScaleWriteMap

   271   // - NegMap, NegWriteMap, AbsMap

   272   {

   273     checkConcept<DoubleMap, AddMap<DoubleMap,DoubleMap> >();

   274     checkConcept<DoubleMap, SubMap<DoubleMap,DoubleMap> >();

   275     checkConcept<DoubleMap, MulMap<DoubleMap,DoubleMap> >();

   276     checkConcept<DoubleMap, DivMap<DoubleMap,DoubleMap> >();

   277 

   278     ConstMap<int, double> c1(1.0), c2(3.14);

   279     IdentityMap<int> im;

   280     ConvertMap<IdentityMap<int>, double> id(im);

   281     check(addMap(c1,id)[0] == 1.0  && addMap(c1,id)[10] == 11.0,

   282           "Something is wrong with AddMap");

   283     check(subMap(id,c1)[0] == -1.0 && subMap(id,c1)[10] == 9.0,

   284           "Something is wrong with SubMap");

   285     check(mulMap(id,c2)[0] == 0    && mulMap(id,c2)[2]  == 6.28,

   286           "Something is wrong with MulMap");

   287     check(divMap(c2,id)[1] == 3.14 && divMap(c2,id)[2]  == 1.57,

   288           "Something is wrong with DivMap");

   289 

   290     checkConcept<DoubleMap, ShiftMap<DoubleMap> >();

   291     checkConcept<DoubleWriteMap, ShiftWriteMap<DoubleWriteMap> >();

   292     checkConcept<DoubleMap, ScaleMap<DoubleMap> >();

   293     checkConcept<DoubleWriteMap, ScaleWriteMap<DoubleWriteMap> >();

   294     checkConcept<DoubleMap, NegMap<DoubleMap> >();

   295     checkConcept<DoubleWriteMap, NegWriteMap<DoubleWriteMap> >();

   296     checkConcept<DoubleMap, AbsMap<DoubleMap> >();

   297 

   298     check(shiftMap(id, 2.0)[1] == 3.0 && shiftMap(id, 2.0)[10] == 12.0,

   299           "Something is wrong with ShiftMap");

   300     check(shiftWriteMap(id, 2.0)[1] == 3.0 &&

   301           shiftWriteMap(id, 2.0)[10] == 12.0,

   302           "Something is wrong with ShiftWriteMap");

   303     check(scaleMap(id, 2.0)[1] == 2.0 && scaleMap(id, 2.0)[10] == 20.0,

   304           "Something is wrong with ScaleMap");

   305     check(scaleWriteMap(id, 2.0)[1] == 2.0 &&

   306           scaleWriteMap(id, 2.0)[10] == 20.0,

   307           "Something is wrong with ScaleWriteMap");

   308     check(negMap(id)[1] == -1.0 && negMap(id)[-10] == 10.0,

   309           "Something is wrong with NegMap");

   310     check(negWriteMap(id)[1] == -1.0 && negWriteMap(id)[-10] == 10.0,

   311           "Something is wrong with NegWriteMap");

   312     check(absMap(id)[1] == 1.0 && absMap(id)[-10] == 10.0,

   313           "Something is wrong with AbsMap");

   314   }

   315 

   316   // Logical maps:

   317   // - TrueMap, FalseMap

   318   // - AndMap, OrMap

   319   // - NotMap, NotWriteMap

   320   // - EqualMap, LessMap

   321   {

   322     checkConcept<BoolMap, TrueMap<A> >();

   323     checkConcept<BoolMap, FalseMap<A> >();

   324     checkConcept<BoolMap, AndMap<BoolMap,BoolMap> >();

   325     checkConcept<BoolMap, OrMap<BoolMap,BoolMap> >();

   326     checkConcept<BoolMap, NotMap<BoolMap> >();

   327     checkConcept<BoolWriteMap, NotWriteMap<BoolWriteMap> >();

   328     checkConcept<BoolMap, EqualMap<DoubleMap,DoubleMap> >();

   329     checkConcept<BoolMap, LessMap<DoubleMap,DoubleMap> >();

   330 

   331     TrueMap<int> tm;

   332     FalseMap<int> fm;

   333     RangeMap<bool> rm(2);

   334     rm[0] = true; rm[1] = false;

   335     check(andMap(tm,rm)[0] && !andMap(tm,rm)[1] &&

   336           !andMap(fm,rm)[0] && !andMap(fm,rm)[1],

   337           "Something is wrong with AndMap");

   338     check(orMap(tm,rm)[0] && orMap(tm,rm)[1] &&

   339           orMap(fm,rm)[0] && !orMap(fm,rm)[1],

   340           "Something is wrong with OrMap");

   341     check(!notMap(rm)[0] && notMap(rm)[1],

   342           "Something is wrong with NotMap");

   343     check(!notWriteMap(rm)[0] && notWriteMap(rm)[1],

   344           "Something is wrong with NotWriteMap");

   345 

   346     ConstMap<int, double> cm(2.0);

   347     IdentityMap<int> im;

   348     ConvertMap<IdentityMap<int>, double> id(im);

   349     check(lessMap(id,cm)[1] && !lessMap(id,cm)[2] && !lessMap(id,cm)[3],

   350           "Something is wrong with LessMap");

   351     check(!equalMap(id,cm)[1] && equalMap(id,cm)[2] && !equalMap(id,cm)[3],

   352           "Something is wrong with EqualMap");

   353   }

   354 

   355   // LoggerBoolMap

   356   {

   357     typedef std::vector<int> vec;

   358     checkConcept<WriteMap<int, bool>, LoggerBoolMap<vec::iterator> >();

   359     checkConcept<WriteMap<int, bool>,

   360                  LoggerBoolMap<std::back_insert_iterator<vec> > >();

   361 

   362     vec v1;

   363     vec v2(10);

   364     LoggerBoolMap<std::back_insert_iterator<vec> >

   365       map1(std::back_inserter(v1));

   366     LoggerBoolMap<vec::iterator> map2(v2.begin());

   367     map1.set(10, false);

   368     map1.set(20, true);   map2.set(20, true);

   369     map1.set(30, false);  map2.set(40, false);

   370     map1.set(50, true);   map2.set(50, true);

   371     map1.set(60, true);   map2.set(60, true);

   372     check(v1.size() == 3 && v2.size() == 10 &&

   373           v1[0]==20 && v1[1]==50 && v1[2]==60 &&

   374           v2[0]==20 && v2[1]==50 && v2[2]==60,

   375           "Something is wrong with LoggerBoolMap");

   376 

   377     int i = 0;

   378     for ( LoggerBoolMap<vec::iterator>::Iterator it = map2.begin();

   379           it != map2.end(); ++it )

   380       check(v1[i++] == *it, "Something is wrong with LoggerBoolMap");

   381 

   382     typedef ListDigraph Graph;

   383     DIGRAPH_TYPEDEFS(Graph);

   384     Graph gr;

   385 

   386     Node n0 = gr.addNode();

   387     Node n1 = gr.addNode();

   388     Node n2 = gr.addNode();

   389     Node n3 = gr.addNode();

   390 

   391     gr.addArc(n3, n0);

   392     gr.addArc(n3, n2);

   393     gr.addArc(n0, n2);

   394     gr.addArc(n2, n1);

   395     gr.addArc(n0, n1);

   396 

   397     {

   398       std::vector<Node> v;

   399       dfs(gr).processedMap(loggerBoolMap(std::back_inserter(v))).run();

   400 

   401       check(v.size()==4 && v[0]==n1 && v[1]==n2 && v[2]==n0 && v[3]==n3,

   402             "Something is wrong with LoggerBoolMap");

   403     }

   404     {

   405       std::vector<Node> v(countNodes(gr));

   406       dfs(gr).processedMap(loggerBoolMap(v.begin())).run();

   407 

   408       check(v.size()==4 && v[0]==n1 && v[1]==n2 && v[2]==n0 && v[3]==n3,

   409             "Something is wrong with LoggerBoolMap");

   410     }

   411   }

   412 

   413   // IdMap, RangeIdMap

   414   {

   415     typedef ListDigraph Graph;

   416     DIGRAPH_TYPEDEFS(Graph);

   417 

   418     checkConcept<ReadMap<Node, int>, IdMap<Graph, Node> >();

   419     checkConcept<ReadMap<Arc, int>, IdMap<Graph, Arc> >();

   420     checkConcept<ReadMap<Node, int>, RangeIdMap<Graph, Node> >();

   421     checkConcept<ReadMap<Arc, int>, RangeIdMap<Graph, Arc> >();

   422 

   423     Graph gr;

   424     IdMap<Graph, Node> nmap(gr);

   425     IdMap<Graph, Arc> amap(gr);

   426     RangeIdMap<Graph, Node> nrmap(gr);

   427     RangeIdMap<Graph, Arc> armap(gr);

   428 

   429     Node n0 = gr.addNode();

   430     Node n1 = gr.addNode();

   431     Node n2 = gr.addNode();

   432 

   433     Arc a0 = gr.addArc(n0, n1);

   434     Arc a1 = gr.addArc(n0, n2);

   435     Arc a2 = gr.addArc(n2, n1);

   436     Arc a3 = gr.addArc(n2, n0);

   437 

   438     check(nmap[n0] == gr.id(n0) && nmap(gr.id(n0)) == n0, "Wrong IdMap");

   439     check(nmap[n1] == gr.id(n1) && nmap(gr.id(n1)) == n1, "Wrong IdMap");

   440     check(nmap[n2] == gr.id(n2) && nmap(gr.id(n2)) == n2, "Wrong IdMap");

   441 

   442     check(amap[a0] == gr.id(a0) && amap(gr.id(a0)) == a0, "Wrong IdMap");

   443     check(amap[a1] == gr.id(a1) && amap(gr.id(a1)) == a1, "Wrong IdMap");

   444     check(amap[a2] == gr.id(a2) && amap(gr.id(a2)) == a2, "Wrong IdMap");

   445     check(amap[a3] == gr.id(a3) && amap(gr.id(a3)) == a3, "Wrong IdMap");

   446 

   447     check(nmap.inverse()[gr.id(n0)] == n0, "Wrong IdMap::InverseMap");

   448     check(amap.inverse()[gr.id(a0)] == a0, "Wrong IdMap::InverseMap");

   449 

   450     check(nrmap.size() == 3 && armap.size() == 4,

   451           "Wrong RangeIdMap::size()");

   452 

   453     check(nrmap[n0] == 0 && nrmap(0) == n0, "Wrong RangeIdMap");

   454     check(nrmap[n1] == 1 && nrmap(1) == n1, "Wrong RangeIdMap");

   455     check(nrmap[n2] == 2 && nrmap(2) == n2, "Wrong RangeIdMap");

   456 

   457     check(armap[a0] == 0 && armap(0) == a0, "Wrong RangeIdMap");

   458     check(armap[a1] == 1 && armap(1) == a1, "Wrong RangeIdMap");

   459     check(armap[a2] == 2 && armap(2) == a2, "Wrong RangeIdMap");

   460     check(armap[a3] == 3 && armap(3) == a3, "Wrong RangeIdMap");

   461 

   462     check(nrmap.inverse()[0] == n0, "Wrong RangeIdMap::InverseMap");

   463     check(armap.inverse()[0] == a0, "Wrong RangeIdMap::InverseMap");

   464 

   465     gr.erase(n1);

   466 

   467     if (nrmap[n0] == 1) nrmap.swap(n0, n2);

   468     nrmap.swap(n2, n0);

   469     if (armap[a1] == 1) armap.swap(a1, a3);

   470     armap.swap(a3, a1);

   471 

   472     check(nrmap.size() == 2 && armap.size() == 2,

   473           "Wrong RangeIdMap::size()");

   474 

   475     check(nrmap[n0] == 1 && nrmap(1) == n0, "Wrong RangeIdMap");

   476     check(nrmap[n2] == 0 && nrmap(0) == n2, "Wrong RangeIdMap");

   477 

   478     check(armap[a1] == 1 && armap(1) == a1, "Wrong RangeIdMap");

   479     check(armap[a3] == 0 && armap(0) == a3, "Wrong RangeIdMap");

   480 

   481     check(nrmap.inverse()[0] == n2, "Wrong RangeIdMap::InverseMap");

   482     check(armap.inverse()[0] == a3, "Wrong RangeIdMap::InverseMap");

   483   }

   484 

   485   // SourceMap, TargetMap, ForwardMap, BackwardMap, InDegMap, OutDegMap

   486   {

   487     typedef ListGraph Graph;

   488     GRAPH_TYPEDEFS(Graph);

   489 

   490     checkConcept<ReadMap<Arc, Node>, SourceMap<Graph> >();

   491     checkConcept<ReadMap<Arc, Node>, TargetMap<Graph> >();

   492     checkConcept<ReadMap<Edge, Arc>, ForwardMap<Graph> >();

   493     checkConcept<ReadMap<Edge, Arc>, BackwardMap<Graph> >();

   494     checkConcept<ReadMap<Node, int>, InDegMap<Graph> >();

   495     checkConcept<ReadMap<Node, int>, OutDegMap<Graph> >();

   496 

   497     Graph gr;

   498     Node n0 = gr.addNode();

   499     Node n1 = gr.addNode();

   500     Node n2 = gr.addNode();

   501 

   502     gr.addEdge(n0,n1);

   503     gr.addEdge(n1,n2);

   504     gr.addEdge(n0,n2);

   505     gr.addEdge(n2,n1);

   506     gr.addEdge(n1,n2);

   507     gr.addEdge(n0,n1);

   508 

   509     for (EdgeIt e(gr); e != INVALID; ++e) {

   510       check(forwardMap(gr)[e] == gr.direct(e, true), "Wrong ForwardMap");

   511       check(backwardMap(gr)[e] == gr.direct(e, false), "Wrong BackwardMap");

   512     }

   513 

   514     check(mapCompare(gr,

   515           sourceMap(orienter(gr, constMap<Edge, bool>(true))),

   516           targetMap(orienter(gr, constMap<Edge, bool>(false)))),

   517           "Wrong SourceMap or TargetMap");

   518 

   519     typedef Orienter<Graph, const ConstMap<Edge, bool> > Digraph;

   520     Digraph dgr(gr, constMap<Edge, bool>(true));

   521     OutDegMap<Digraph> odm(dgr);

   522     InDegMap<Digraph> idm(dgr);

   523 

   524     check(odm[n0] == 3 && odm[n1] == 2 && odm[n2] == 1, "Wrong OutDegMap");

   525     check(idm[n0] == 0 && idm[n1] == 3 && idm[n2] == 3, "Wrong InDegMap");

   526 

   527     gr.addEdge(n2, n0);

   528 

   529     check(odm[n0] == 3 && odm[n1] == 2 && odm[n2] == 2, "Wrong OutDegMap");

   530     check(idm[n0] == 1 && idm[n1] == 3 && idm[n2] == 3, "Wrong InDegMap");

   531   }

   532 

   533   // CrossRefMap

   534   {

   535     typedef ListDigraph Graph;

   536     DIGRAPH_TYPEDEFS(Graph);

   537 

   538     checkConcept<ReadWriteMap<Node, int>,

   539                  CrossRefMap<Graph, Node, int> >();

   540     checkConcept<ReadWriteMap<Node, bool>,

   541                  CrossRefMap<Graph, Node, bool> >();

   542     checkConcept<ReadWriteMap<Node, double>,

   543                  CrossRefMap<Graph, Node, double> >();

   544 

   545     Graph gr;

   546     typedef CrossRefMap<Graph, Node, char> CRMap;

   547     CRMap map(gr);

   548 

   549     Node n0 = gr.addNode();

   550     Node n1 = gr.addNode();

   551     Node n2 = gr.addNode();

   552 

   553     map.set(n0, 'A');

   554     map.set(n1, 'B');

   555     map.set(n2, 'C');

   556 

   557     check(map[n0] == 'A' && map('A') == n0 && map.inverse()['A'] == n0,

   558           "Wrong CrossRefMap");

   559     check(map[n1] == 'B' && map('B') == n1 && map.inverse()['B'] == n1,

   560           "Wrong CrossRefMap");

   561     check(map[n2] == 'C' && map('C') == n2 && map.inverse()['C'] == n2,

   562           "Wrong CrossRefMap");

   563     check(map.count('A') == 1 && map.count('B') == 1 && map.count('C') == 1,

   564           "Wrong CrossRefMap::count()");

   565 

   566     CRMap::ValueIt it = map.beginValue();

   567     check(*it++ == 'A' && *it++ == 'B' && *it++ == 'C' &&

   568           it == map.endValue(), "Wrong value iterator");

   569 

   570     map.set(n2, 'A');

   571 

   572     check(map[n0] == 'A' && map[n1] == 'B' && map[n2] == 'A',

   573           "Wrong CrossRefMap");

   574     check(map('A') == n0 && map.inverse()['A'] == n0, "Wrong CrossRefMap");

   575     check(map('B') == n1 && map.inverse()['B'] == n1, "Wrong CrossRefMap");

   576     check(map('C') == INVALID && map.inverse()['C'] == INVALID,

   577           "Wrong CrossRefMap");

   578     check(map.count('A') == 2 && map.count('B') == 1 && map.count('C') == 0,

   579           "Wrong CrossRefMap::count()");

   580 

   581     it = map.beginValue();

   582     check(*it++ == 'A' && *it++ == 'A' && *it++ == 'B' &&

   583           it == map.endValue(), "Wrong value iterator");

   584 

   585     map.set(n0, 'C');

   586 

   587     check(map[n0] == 'C' && map[n1] == 'B' && map[n2] == 'A',

   588           "Wrong CrossRefMap");

   589     check(map('A') == n2 && map.inverse()['A'] == n2, "Wrong CrossRefMap");

   590     check(map('B') == n1 && map.inverse()['B'] == n1, "Wrong CrossRefMap");

   591     check(map('C') == n0 && map.inverse()['C'] == n0, "Wrong CrossRefMap");

   592     check(map.count('A') == 1 && map.count('B') == 1 && map.count('C') == 1,

   593           "Wrong CrossRefMap::count()");

   594 

   595     it = map.beginValue();

   596     check(*it++ == 'A' && *it++ == 'B' && *it++ == 'C' &&

   597           it == map.endValue(), "Wrong value iterator");

   598   }

   599 

   600   // CrossRefMap

   601   {

   602     typedef SmartDigraph Graph;

   603     DIGRAPH_TYPEDEFS(Graph);

   604 

   605     checkConcept<ReadWriteMap<Node, int>,

   606                  CrossRefMap<Graph, Node, int> >();

   607 

   608     Graph gr;

   609     typedef CrossRefMap<Graph, Node, char> CRMap;

   610     typedef CRMap::ValueIterator ValueIt;

   611     CRMap map(gr);

   612 

   613     Node n0 = gr.addNode();

   614     Node n1 = gr.addNode();

   615     Node n2 = gr.addNode();

   616 

   617     map.set(n0, 'A');

   618     map.set(n1, 'B');

   619     map.set(n2, 'C');

   620     map.set(n2, 'A');

   621     map.set(n0, 'C');

   622 

   623     check(map[n0] == 'C' && map[n1] == 'B' && map[n2] == 'A',

   624           "Wrong CrossRefMap");

   625     check(map('A') == n2 && map.inverse()['A'] == n2, "Wrong CrossRefMap");

   626     check(map('B') == n1 && map.inverse()['B'] == n1, "Wrong CrossRefMap");

   627     check(map('C') == n0 && map.inverse()['C'] == n0, "Wrong CrossRefMap");

   628 

   629     ValueIt it = map.beginValue();

   630     check(*it++ == 'A' && *it++ == 'B' && *it++ == 'C' &&

   631           it == map.endValue(), "Wrong value iterator");

   632   }

   633 

   634   // Iterable bool map

   635   {

   636     typedef SmartGraph Graph;

   637     typedef SmartGraph::Node Item;

   638 

   639     typedef IterableBoolMap<SmartGraph, SmartGraph::Node> Ibm;

   640     checkConcept<ReferenceMap<Item, bool, bool&, const bool&>, Ibm>();

   641 

   642     const int num = 10;

   643     Graph g;

   644     std::vector<Item> items;

   645     for (int i = 0; i < num; ++i) {

   646       items.push_back(g.addNode());

   647     }

   648 

   649     Ibm map1(g, true);

   650     int n = 0;

   651     for (Ibm::TrueIt it(map1); it != INVALID; ++it) {

   652       check(map1[static_cast<Item>(it)], "Wrong TrueIt");

   653       ++n;

   654     }

   655     check(n == num, "Wrong number");

   656 

   657     n = 0;

   658     for (Ibm::ItemIt it(map1, true); it != INVALID; ++it) {

   659         check(map1[static_cast<Item>(it)], "Wrong ItemIt for true");

   660         ++n;

   661     }

   662     check(n == num, "Wrong number");

   663     check(Ibm::FalseIt(map1) == INVALID, "Wrong FalseIt");

   664     check(Ibm::ItemIt(map1, false) == INVALID, "Wrong ItemIt for false");

   665 

   666     map1[items[5]] = true;

   667 

   668     n = 0;

   669     for (Ibm::ItemIt it(map1, true); it != INVALID; ++it) {

   670         check(map1[static_cast<Item>(it)], "Wrong ItemIt for true");

   671         ++n;

   672     }

   673     check(n == num, "Wrong number");

   674 

   675     map1[items[num / 2]] = false;

   676     check(map1[items[num / 2]] == false, "Wrong map value");

   677 

   678     n = 0;

   679     for (Ibm::TrueIt it(map1); it != INVALID; ++it) {

   680         check(map1[static_cast<Item>(it)], "Wrong TrueIt for true");

   681         ++n;

   682     }

   683     check(n == num - 1, "Wrong number");

   684 

   685     n = 0;

   686     for (Ibm::FalseIt it(map1); it != INVALID; ++it) {

   687         check(!map1[static_cast<Item>(it)], "Wrong FalseIt for true");

   688         ++n;

   689     }

   690     check(n == 1, "Wrong number");

   691 

   692     map1[items[0]] = false;

   693     check(map1[items[0]] == false, "Wrong map value");

   694 

   695     map1[items[num - 1]] = false;

   696     check(map1[items[num - 1]] == false, "Wrong map value");

   697 

   698     n = 0;

   699     for (Ibm::TrueIt it(map1); it != INVALID; ++it) {

   700         check(map1[static_cast<Item>(it)], "Wrong TrueIt for true");

   701         ++n;

   702     }

   703     check(n == num - 3, "Wrong number");

   704     check(map1.trueNum() == num - 3, "Wrong number");

   705 

   706     n = 0;

   707     for (Ibm::FalseIt it(map1); it != INVALID; ++it) {

   708         check(!map1[static_cast<Item>(it)], "Wrong FalseIt for true");

   709         ++n;

   710     }

   711     check(n == 3, "Wrong number");

   712     check(map1.falseNum() == 3, "Wrong number");

   713   }

   714 

   715   // Iterable int map

   716   {

   717     typedef SmartGraph Graph;

   718     typedef SmartGraph::Node Item;

   719     typedef IterableIntMap<SmartGraph, SmartGraph::Node> Iim;

   720 

   721     checkConcept<ReferenceMap<Item, int, int&, const int&>, Iim>();

   722 

   723     const int num = 10;

   724     Graph g;

   725     std::vector<Item> items;

   726     for (int i = 0; i < num; ++i) {

   727       items.push_back(g.addNode());

   728     }

   729 

   730     Iim map1(g);

   731     check(map1.size() == 0, "Wrong size");

   732 

   733     for (int i = 0; i < num; ++i) {

   734       map1[items[i]] = i;

   735     }

   736     check(map1.size() == num, "Wrong size");

   737 

   738     for (int i = 0; i < num; ++i) {

   739       Iim::ItemIt it(map1, i);

   740       check(static_cast<Item>(it) == items[i], "Wrong value");

   741       ++it;

   742       check(static_cast<Item>(it) == INVALID, "Wrong value");

   743     }

   744 

   745     for (int i = 0; i < num; ++i) {

   746       map1[items[i]] = i % 2;

   747     }

   748     check(map1.size() == 2, "Wrong size");

   749 

   750     int n = 0;

   751     for (Iim::ItemIt it(map1, 0); it != INVALID; ++it) {

   752       check(map1[static_cast<Item>(it)] == 0, "Wrong value");

   753       ++n;

   754     }

   755     check(n == (num + 1) / 2, "Wrong number");

   756 

   757     for (Iim::ItemIt it(map1, 1); it != INVALID; ++it) {

   758       check(map1[static_cast<Item>(it)] == 1, "Wrong value");

   759       ++n;

   760     }

   761     check(n == num, "Wrong number");

   762 

   763   }

   764 

   765   // Iterable value map

   766   {

   767     typedef SmartGraph Graph;

   768     typedef SmartGraph::Node Item;

   769     typedef IterableValueMap<SmartGraph, SmartGraph::Node, double> Ivm;

   770 

   771     checkConcept<ReadWriteMap<Item, double>, Ivm>();

   772 

   773     const int num = 10;

   774     Graph g;

   775     std::vector<Item> items;

   776     for (int i = 0; i < num; ++i) {

   777       items.push_back(g.addNode());

   778     }

   779 

   780     Ivm map1(g, 0.0);

   781     check(distance(map1.beginValue(), map1.endValue()) == 1, "Wrong size");

   782     check(*map1.beginValue() == 0.0, "Wrong value");

   783 

   784     for (int i = 0; i < num; ++i) {

   785       map1.set(items[i], static_cast<double>(i));

   786     }

   787     check(distance(map1.beginValue(), map1.endValue()) == num, "Wrong size");

   788 

   789     for (int i = 0; i < num; ++i) {

   790       Ivm::ItemIt it(map1, static_cast<double>(i));

   791       check(static_cast<Item>(it) == items[i], "Wrong value");

   792       ++it;

   793       check(static_cast<Item>(it) == INVALID, "Wrong value");

   794     }

   795 

   796     for (Ivm::ValueIt vit = map1.beginValue();

   797          vit != map1.endValue(); ++vit) {

   798       check(map1[static_cast<Item>(Ivm::ItemIt(map1, *vit))] == *vit,

   799             "Wrong ValueIt");

   800     }

   801 

   802     for (int i = 0; i < num; ++i) {

   803       map1.set(items[i], static_cast<double>(i % 2));

   804     }

   805     check(distance(map1.beginValue(), map1.endValue()) == 2, "Wrong size");

   806 

   807     int n = 0;

   808     for (Ivm::ItemIt it(map1, 0.0); it != INVALID; ++it) {

   809       check(map1[static_cast<Item>(it)] == 0.0, "Wrong value");

   810       ++n;

   811     }

   812     check(n == (num + 1) / 2, "Wrong number");

   813 

   814     for (Ivm::ItemIt it(map1, 1.0); it != INVALID; ++it) {

   815       check(map1[static_cast<Item>(it)] == 1.0, "Wrong value");

   816       ++n;

   817     }

   818     check(n == num, "Wrong number");

   819 

   820   }

   821 

   822   // Graph map utilities:

   823   // mapMin(), mapMax(), mapMinValue(), mapMaxValue()

   824   // mapFind(), mapFindIf(), mapCount(), mapCountIf()

   825   // mapCopy(), mapCompare(), mapFill()

   826   {

   827     DIGRAPH_TYPEDEFS(SmartDigraph);

   828 

   829     SmartDigraph g;

   830     Node n1 = g.addNode();

   831     Node n2 = g.addNode();

   832     Node n3 = g.addNode();

   833 

   834     SmartDigraph::NodeMap<int> map1(g);

   835     SmartDigraph::ArcMap<char> map2(g);

   836     ConstMap<Node, A> cmap1 = A();

   837     ConstMap<Arc, C> cmap2 = C(0);

   838 

   839     map1[n1] = 10;

   840     map1[n2] = 5;

   841     map1[n3] = 12;

   842 

   843     // mapMin(), mapMax(), mapMinValue(), mapMaxValue()

   844     check(mapMin(g, map1) == n2, "Wrong mapMin()");

   845     check(mapMax(g, map1) == n3, "Wrong mapMax()");

   846     check(mapMin(g, map1, std::greater<int>()) == n3, "Wrong mapMin()");

   847     check(mapMax(g, map1, std::greater<int>()) == n2, "Wrong mapMax()");

   848     check(mapMinValue(g, map1) == 5, "Wrong mapMinValue()");

   849     check(mapMaxValue(g, map1) == 12, "Wrong mapMaxValue()");

   850 

   851     check(mapMin(g, map2) == INVALID, "Wrong mapMin()");

   852     check(mapMax(g, map2) == INVALID, "Wrong mapMax()");

   853 

   854     check(mapMin(g, cmap1) != INVALID, "Wrong mapMin()");

   855     check(mapMax(g, cmap2) == INVALID, "Wrong mapMax()");

   856 

   857     Arc a1 = g.addArc(n1, n2);

   858     Arc a2 = g.addArc(n1, n3);

   859     Arc a3 = g.addArc(n2, n3);

   860     Arc a4 = g.addArc(n3, n1);

   861 

   862     map2[a1] = 'b';

   863     map2[a2] = 'a';

   864     map2[a3] = 'b';

   865     map2[a4] = 'c';

   866 

   867     // mapMin(), mapMax(), mapMinValue(), mapMaxValue()

   868     check(mapMin(g, map2) == a2, "Wrong mapMin()");

   869     check(mapMax(g, map2) == a4, "Wrong mapMax()");

   870     check(mapMin(g, map2, std::greater<int>()) == a4, "Wrong mapMin()");

   871     check(mapMax(g, map2, std::greater<int>()) == a2, "Wrong mapMax()");

   872     check(mapMinValue(g, map2, std::greater<int>()) == 'c',

   873           "Wrong mapMinValue()");

   874     check(mapMaxValue(g, map2, std::greater<int>()) == 'a',

   875           "Wrong mapMaxValue()");

   876 

   877     check(mapMin(g, cmap1) != INVALID, "Wrong mapMin()");

   878     check(mapMax(g, cmap2) != INVALID, "Wrong mapMax()");

   879     check(mapMaxValue(g, cmap2) == C(0), "Wrong mapMaxValue()");

   880 

   881     check(mapMin(g, composeMap(functorToMap(&createC), map2)) == a2,

   882           "Wrong mapMin()");

   883     check(mapMax(g, composeMap(functorToMap(&createC), map2)) == a4,

   884           "Wrong mapMax()");

   885     check(mapMinValue(g, composeMap(functorToMap(&createC), map2)) == C('a'),

   886           "Wrong mapMinValue()");

   887     check(mapMaxValue(g, composeMap(functorToMap(&createC), map2)) == C('c'),

   888           "Wrong mapMaxValue()");

   889 

   890     // mapFind(), mapFindIf()

   891     check(mapFind(g, map1, 5) == n2, "Wrong mapFind()");

   892     check(mapFind(g, map1, 6) == INVALID, "Wrong mapFind()");

   893     check(mapFind(g, map2, 'a') == a2, "Wrong mapFind()");

   894     check(mapFind(g, map2, 'e') == INVALID, "Wrong mapFind()");

   895     check(mapFind(g, cmap2, C(0)) == ArcIt(g), "Wrong mapFind()");

   896     check(mapFind(g, cmap2, C(1)) == INVALID, "Wrong mapFind()");

   897 

   898     check(mapFindIf(g, map1, Less<int>(7)) == n2,

   899           "Wrong mapFindIf()");

   900     check(mapFindIf(g, map1, Less<int>(5)) == INVALID,

   901           "Wrong mapFindIf()");

   902     check(mapFindIf(g, map2, Less<char>('d')) == ArcIt(g),

   903           "Wrong mapFindIf()");

   904     check(mapFindIf(g, map2, Less<char>('a')) == INVALID,

   905           "Wrong mapFindIf()");

   906 

   907     // mapCount(), mapCountIf()

   908     check(mapCount(g, map1, 5) == 1, "Wrong mapCount()");

   909     check(mapCount(g, map1, 6) == 0, "Wrong mapCount()");

   910     check(mapCount(g, map2, 'a') == 1, "Wrong mapCount()");

   911     check(mapCount(g, map2, 'b') == 2, "Wrong mapCount()");

   912     check(mapCount(g, map2, 'e') == 0, "Wrong mapCount()");

   913     check(mapCount(g, cmap2, C(0)) == 4, "Wrong mapCount()");

   914     check(mapCount(g, cmap2, C(1)) == 0, "Wrong mapCount()");

   915 

   916     check(mapCountIf(g, map1, Less<int>(11)) == 2,

   917           "Wrong mapCountIf()");

   918     check(mapCountIf(g, map1, Less<int>(13)) == 3,

   919           "Wrong mapCountIf()");

   920     check(mapCountIf(g, map1, Less<int>(5)) == 0,

   921           "Wrong mapCountIf()");

   922     check(mapCountIf(g, map2, Less<char>('d')) == 4,

   923           "Wrong mapCountIf()");

   924     check(mapCountIf(g, map2, Less<char>('c')) == 3,

   925           "Wrong mapCountIf()");

   926     check(mapCountIf(g, map2, Less<char>('a')) == 0,

   927           "Wrong mapCountIf()");

   928 

   929     // MapIt, ConstMapIt

   930 /*

   931 These tests can be used after applying bugfix #330

   932     typedef SmartDigraph::NodeMap<int>::MapIt MapIt;

   933     typedef SmartDigraph::NodeMap<int>::ConstMapIt ConstMapIt;

   934     check(*std::min_element(MapIt(map1), MapIt(INVALID)) == 5,

   935           "Wrong NodeMap<>::MapIt");

   936     check(*std::max_element(ConstMapIt(map1), ConstMapIt(INVALID)) == 12,

   937           "Wrong NodeMap<>::MapIt");

   938 

   939     int sum = 0;

   940     std::for_each(MapIt(map1), MapIt(INVALID), Sum<int>(sum));

   941     check(sum == 27, "Wrong NodeMap<>::MapIt");

   942     std::for_each(ConstMapIt(map1), ConstMapIt(INVALID), Sum<int>(sum));

   943     check(sum == 54, "Wrong NodeMap<>::ConstMapIt");

   944 */

   945 

   946     // mapCopy(), mapCompare(), mapFill()

   947     check(mapCompare(g, map1, map1), "Wrong mapCompare()");

   948     check(mapCompare(g, cmap2, cmap2), "Wrong mapCompare()");

   949     check(mapCompare(g, map1, shiftMap(map1, 0)), "Wrong mapCompare()");

   950     check(mapCompare(g, map2, scaleMap(map2, 1)), "Wrong mapCompare()");

   951     check(!mapCompare(g, map1, shiftMap(map1, 1)), "Wrong mapCompare()");

   952 

   953     SmartDigraph::NodeMap<int> map3(g, 0);

   954     SmartDigraph::ArcMap<char> map4(g, 'a');

   955 

   956     check(!mapCompare(g, map1, map3), "Wrong mapCompare()");

   957     check(!mapCompare(g, map2, map4), "Wrong mapCompare()");

   958 

   959     mapCopy(g, map1, map3);

   960     mapCopy(g, map2, map4);

   961 

   962     check(mapCompare(g, map1, map3), "Wrong mapCompare() or mapCopy()");

   963     check(mapCompare(g, map2, map4), "Wrong mapCompare() or mapCopy()");

   964 

   965     Undirector<SmartDigraph> ug(g);

   966     Undirector<SmartDigraph>::EdgeMap<char> umap1(ug, 'x');

   967     Undirector<SmartDigraph>::ArcMap<double> umap2(ug, 3.14);

   968 

   969     check(!mapCompare(g, map2, umap1), "Wrong mapCompare() or mapCopy()");

   970     check(!mapCompare(g, umap1, map2), "Wrong mapCompare() or mapCopy()");

   971     check(!mapCompare(ug, map2, umap1), "Wrong mapCompare() or mapCopy()");

   972     check(!mapCompare(ug, umap1, map2), "Wrong mapCompare() or mapCopy()");

   973 

   974     mapCopy(g, map2, umap1);

   975 

   976     check(mapCompare(g, map2, umap1), "Wrong mapCompare() or mapCopy()");

   977     check(mapCompare(g, umap1, map2), "Wrong mapCompare() or mapCopy()");

   978     check(mapCompare(ug, map2, umap1), "Wrong mapCompare() or mapCopy()");

   979     check(mapCompare(ug, umap1, map2), "Wrong mapCompare() or mapCopy()");

   980 

   981     mapCopy(g, map2, umap1);

   982     mapCopy(g, umap1, map2);

   983     mapCopy(ug, map2, umap1);

   984     mapCopy(ug, umap1, map2);

   985 

   986     check(!mapCompare(ug, umap1, umap2), "Wrong mapCompare() or mapCopy()");

   987     mapCopy(ug, umap1, umap2);

   988     check(mapCompare(ug, umap1, umap2), "Wrong mapCompare() or mapCopy()");

   989 

   990     check(!mapCompare(g, map1, constMap<Node>(2)), "Wrong mapCompare()");

   991     mapFill(g, map1, 2);

   992     check(mapCompare(g, constMap<Node>(2), map1), "Wrong mapFill()");

   993 

   994     check(!mapCompare(g, map2, constMap<Arc>('z')), "Wrong mapCompare()");

   995     mapCopy(g, constMap<Arc>('z'), map2);

   996     check(mapCompare(g, constMap<Arc>('z'), map2), "Wrong mapCopy()");

   997   }

   998 

   999   return 0;

  1000 }
lemon-main