test/maps_test.cc
author Peter Kovacs <kpeter@inf.elte.hu>
Fri, 17 Apr 2009 18:04:36 +0200
changeset 609 e6927fe719e6
parent 440 88ed40ad0d4f
child 684 7b1a6e963018
child 693 7bda7860e0a8
permissions -rw-r--r--
Support >= and <= constraints in NetworkSimplex (#219, #234)

By default the same inequality constraints are supported as by
Circulation (the GEQ form), but the LEQ form can also be selected
using the problemType() function.

The documentation of the min. cost flow module is reworked and
extended with important notes and explanations about the different
variants of the problem and about the dual solution and optimality
conditions.
alpar@209
     1
/* -*- mode: C++; indent-tabs-mode: nil; -*-
alpar@25
     2
 *
alpar@209
     3
 * This file is a part of LEMON, a generic C++ optimization library.
alpar@25
     4
 *
alpar@440
     5
 * Copyright (C) 2003-2009
alpar@25
     6
 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
alpar@25
     7
 * (Egervary Research Group on Combinatorial Optimization, EGRES).
alpar@25
     8
 *
alpar@25
     9
 * Permission to use, modify and distribute this software is granted
alpar@25
    10
 * provided that this copyright notice appears in all copies. For
alpar@25
    11
 * precise terms see the accompanying LICENSE file.
alpar@25
    12
 *
alpar@25
    13
 * This software is provided "AS IS" with no warranty of any kind,
alpar@25
    14
 * express or implied, and with no claim as to its suitability for any
alpar@25
    15
 * purpose.
alpar@25
    16
 *
alpar@25
    17
 */
alpar@25
    18
alpar@25
    19
#include <deque>
alpar@25
    20
#include <set>
alpar@25
    21
alpar@25
    22
#include <lemon/concept_check.h>
alpar@25
    23
#include <lemon/concepts/maps.h>
alpar@25
    24
#include <lemon/maps.h>
alpar@25
    25
alpar@25
    26
#include "test_tools.h"
alpar@25
    27
alpar@25
    28
using namespace lemon;
alpar@25
    29
using namespace lemon::concepts;
alpar@25
    30
alpar@25
    31
struct A {};
alpar@25
    32
inline bool operator<(A, A) { return true; }
alpar@25
    33
struct B {};
alpar@25
    34
kpeter@94
    35
class C {
kpeter@94
    36
  int x;
kpeter@94
    37
public:
kpeter@94
    38
  C(int _x) : x(_x) {}
kpeter@94
    39
};
kpeter@94
    40
alpar@25
    41
class F {
alpar@25
    42
public:
alpar@25
    43
  typedef A argument_type;
alpar@25
    44
  typedef B result_type;
alpar@25
    45
kpeter@80
    46
  B operator()(const A&) const { return B(); }
kpeter@80
    47
private:
kpeter@80
    48
  F& operator=(const F&);
alpar@25
    49
};
alpar@25
    50
kpeter@80
    51
int func(A) { return 3; }
alpar@25
    52
kpeter@80
    53
int binc(int a, B) { return a+1; }
alpar@25
    54
kpeter@80
    55
typedef ReadMap<A, double> DoubleMap;
kpeter@80
    56
typedef ReadWriteMap<A, double> DoubleWriteMap;
kpeter@80
    57
typedef ReferenceMap<A, double, double&, const double&> DoubleRefMap;
alpar@25
    58
kpeter@80
    59
typedef ReadMap<A, bool> BoolMap;
alpar@25
    60
typedef ReadWriteMap<A, bool> BoolWriteMap;
kpeter@80
    61
typedef ReferenceMap<A, bool, bool&, const bool&> BoolRefMap;
alpar@25
    62
alpar@25
    63
int main()
kpeter@80
    64
{
kpeter@80
    65
  // Map concepts
alpar@25
    66
  checkConcept<ReadMap<A,B>, ReadMap<A,B> >();
kpeter@94
    67
  checkConcept<ReadMap<A,C>, ReadMap<A,C> >();
alpar@25
    68
  checkConcept<WriteMap<A,B>, WriteMap<A,B> >();
kpeter@94
    69
  checkConcept<WriteMap<A,C>, WriteMap<A,C> >();
alpar@25
    70
  checkConcept<ReadWriteMap<A,B>, ReadWriteMap<A,B> >();
kpeter@94
    71
  checkConcept<ReadWriteMap<A,C>, ReadWriteMap<A,C> >();
alpar@25
    72
  checkConcept<ReferenceMap<A,B,B&,const B&>, ReferenceMap<A,B,B&,const B&> >();
kpeter@94
    73
  checkConcept<ReferenceMap<A,C,C&,const C&>, ReferenceMap<A,C,C&,const C&> >();
alpar@25
    74
kpeter@80
    75
  // NullMap
kpeter@80
    76
  {
kpeter@80
    77
    checkConcept<ReadWriteMap<A,B>, NullMap<A,B> >();
kpeter@80
    78
    NullMap<A,B> map1;
kpeter@80
    79
    NullMap<A,B> map2 = map1;
kpeter@80
    80
    map1 = nullMap<A,B>();
kpeter@80
    81
  }
kpeter@80
    82
kpeter@80
    83
  // ConstMap
kpeter@80
    84
  {
kpeter@80
    85
    checkConcept<ReadWriteMap<A,B>, ConstMap<A,B> >();
kpeter@123
    86
    checkConcept<ReadWriteMap<A,C>, ConstMap<A,C> >();
kpeter@80
    87
    ConstMap<A,B> map1;
deba@136
    88
    ConstMap<A,B> map2 = B();
kpeter@80
    89
    ConstMap<A,B> map3 = map1;
kpeter@80
    90
    map1 = constMap<A>(B());
kpeter@123
    91
    map1 = constMap<A,B>();
kpeter@80
    92
    map1.setAll(B());
kpeter@123
    93
    ConstMap<A,C> map4(C(1));
kpeter@123
    94
    ConstMap<A,C> map5 = map4;
kpeter@123
    95
    map4 = constMap<A>(C(2));
kpeter@123
    96
    map4.setAll(C(3));
kpeter@82
    97
kpeter@80
    98
    checkConcept<ReadWriteMap<A,int>, ConstMap<A,int> >();
kpeter@80
    99
    check(constMap<A>(10)[A()] == 10, "Something is wrong with ConstMap");
kpeter@80
   100
kpeter@80
   101
    checkConcept<ReadWriteMap<A,int>, ConstMap<A,Const<int,10> > >();
kpeter@123
   102
    ConstMap<A,Const<int,10> > map6;
kpeter@123
   103
    ConstMap<A,Const<int,10> > map7 = map6;
kpeter@123
   104
    map6 = constMap<A,int,10>();
kpeter@123
   105
    map7 = constMap<A,Const<int,10> >();
alpar@210
   106
    check(map6[A()] == 10 && map7[A()] == 10,
alpar@210
   107
          "Something is wrong with ConstMap");
kpeter@80
   108
  }
kpeter@80
   109
kpeter@80
   110
  // IdentityMap
kpeter@80
   111
  {
kpeter@80
   112
    checkConcept<ReadMap<A,A>, IdentityMap<A> >();
kpeter@80
   113
    IdentityMap<A> map1;
kpeter@80
   114
    IdentityMap<A> map2 = map1;
kpeter@80
   115
    map1 = identityMap<A>();
kpeter@82
   116
kpeter@80
   117
    checkConcept<ReadMap<double,double>, IdentityMap<double> >();
alpar@210
   118
    check(identityMap<double>()[1.0] == 1.0 &&
alpar@210
   119
          identityMap<double>()[3.14] == 3.14,
kpeter@80
   120
          "Something is wrong with IdentityMap");
kpeter@80
   121
  }
kpeter@80
   122
kpeter@80
   123
  // RangeMap
kpeter@80
   124
  {
kpeter@80
   125
    checkConcept<ReferenceMap<int,B,B&,const B&>, RangeMap<B> >();
kpeter@80
   126
    RangeMap<B> map1;
kpeter@80
   127
    RangeMap<B> map2(10);
kpeter@80
   128
    RangeMap<B> map3(10,B());
kpeter@80
   129
    RangeMap<B> map4 = map1;
kpeter@80
   130
    RangeMap<B> map5 = rangeMap<B>();
kpeter@80
   131
    RangeMap<B> map6 = rangeMap<B>(10);
kpeter@80
   132
    RangeMap<B> map7 = rangeMap(10,B());
kpeter@80
   133
kpeter@80
   134
    checkConcept< ReferenceMap<int, double, double&, const double&>,
kpeter@80
   135
                  RangeMap<double> >();
kpeter@80
   136
    std::vector<double> v(10, 0);
kpeter@80
   137
    v[5] = 100;
kpeter@80
   138
    RangeMap<double> map8(v);
kpeter@80
   139
    RangeMap<double> map9 = rangeMap(v);
kpeter@80
   140
    check(map9.size() == 10 && map9[2] == 0 && map9[5] == 100,
kpeter@80
   141
          "Something is wrong with RangeMap");
kpeter@80
   142
  }
kpeter@80
   143
kpeter@80
   144
  // SparseMap
kpeter@80
   145
  {
kpeter@80
   146
    checkConcept<ReferenceMap<A,B,B&,const B&>, SparseMap<A,B> >();
kpeter@80
   147
    SparseMap<A,B> map1;
deba@136
   148
    SparseMap<A,B> map2 = B();
kpeter@80
   149
    SparseMap<A,B> map3 = sparseMap<A,B>();
kpeter@80
   150
    SparseMap<A,B> map4 = sparseMap<A>(B());
kpeter@80
   151
kpeter@80
   152
    checkConcept< ReferenceMap<double, int, int&, const int&>,
kpeter@80
   153
                  SparseMap<double, int> >();
kpeter@80
   154
    std::map<double, int> m;
kpeter@80
   155
    SparseMap<double, int> map5(m);
kpeter@80
   156
    SparseMap<double, int> map6(m,10);
kpeter@80
   157
    SparseMap<double, int> map7 = sparseMap(m);
kpeter@80
   158
    SparseMap<double, int> map8 = sparseMap(m,10);
kpeter@80
   159
alpar@210
   160
    check(map5[1.0] == 0 && map5[3.14] == 0 &&
alpar@210
   161
          map6[1.0] == 10 && map6[3.14] == 10,
kpeter@80
   162
          "Something is wrong with SparseMap");
kpeter@80
   163
    map5[1.0] = map6[3.14] = 100;
alpar@210
   164
    check(map5[1.0] == 100 && map5[3.14] == 0 &&
alpar@210
   165
          map6[1.0] == 10 && map6[3.14] == 100,
kpeter@80
   166
          "Something is wrong with SparseMap");
kpeter@80
   167
  }
kpeter@80
   168
kpeter@80
   169
  // ComposeMap
kpeter@80
   170
  {
kpeter@80
   171
    typedef ComposeMap<DoubleMap, ReadMap<B,A> > CompMap;
kpeter@80
   172
    checkConcept<ReadMap<B,double>, CompMap>();
alpar@507
   173
    CompMap map1 = CompMap(DoubleMap(),ReadMap<B,A>());
kpeter@80
   174
    CompMap map2 = composeMap(DoubleMap(), ReadMap<B,A>());
kpeter@82
   175
kpeter@80
   176
    SparseMap<double, bool> m1(false); m1[3.14] = true;
kpeter@80
   177
    RangeMap<double> m2(2); m2[0] = 3.0; m2[1] = 3.14;
alpar@210
   178
    check(!composeMap(m1,m2)[0] && composeMap(m1,m2)[1],
alpar@210
   179
          "Something is wrong with ComposeMap")
kpeter@80
   180
  }
kpeter@80
   181
kpeter@80
   182
  // CombineMap
kpeter@80
   183
  {
kpeter@80
   184
    typedef CombineMap<DoubleMap, DoubleMap, std::plus<double> > CombMap;
kpeter@80
   185
    checkConcept<ReadMap<A,double>, CombMap>();
alpar@507
   186
    CombMap map1 = CombMap(DoubleMap(), DoubleMap());
kpeter@80
   187
    CombMap map2 = combineMap(DoubleMap(), DoubleMap(), std::plus<double>());
kpeter@80
   188
kpeter@80
   189
    check(combineMap(constMap<B,int,2>(), identityMap<B>(), &binc)[B()] == 3,
kpeter@80
   190
          "Something is wrong with CombineMap");
kpeter@80
   191
  }
kpeter@80
   192
kpeter@80
   193
  // FunctorToMap, MapToFunctor
kpeter@80
   194
  {
kpeter@80
   195
    checkConcept<ReadMap<A,B>, FunctorToMap<F,A,B> >();
kpeter@80
   196
    checkConcept<ReadMap<A,B>, FunctorToMap<F> >();
kpeter@80
   197
    FunctorToMap<F> map1;
alpar@507
   198
    FunctorToMap<F> map2 = FunctorToMap<F>(F());
kpeter@80
   199
    B b = functorToMap(F())[A()];
kpeter@80
   200
kpeter@80
   201
    checkConcept<ReadMap<A,B>, MapToFunctor<ReadMap<A,B> > >();
alpar@507
   202
    MapToFunctor<ReadMap<A,B> > map = MapToFunctor<ReadMap<A,B> >(ReadMap<A,B>());
kpeter@80
   203
alpar@210
   204
    check(functorToMap(&func)[A()] == 3,
alpar@210
   205
          "Something is wrong with FunctorToMap");
alpar@210
   206
    check(mapToFunctor(constMap<A,int>(2))(A()) == 2,
alpar@210
   207
          "Something is wrong with MapToFunctor");
alpar@210
   208
    check(mapToFunctor(functorToMap(&func))(A()) == 3 &&
alpar@210
   209
          mapToFunctor(functorToMap(&func))[A()] == 3,
kpeter@80
   210
          "Something is wrong with FunctorToMap or MapToFunctor");
kpeter@80
   211
    check(functorToMap(mapToFunctor(constMap<A,int>(2)))[A()] == 2,
kpeter@80
   212
          "Something is wrong with FunctorToMap or MapToFunctor");
kpeter@80
   213
  }
kpeter@80
   214
kpeter@80
   215
  // ConvertMap
kpeter@80
   216
  {
alpar@210
   217
    checkConcept<ReadMap<double,double>,
alpar@210
   218
      ConvertMap<ReadMap<double, int>, double> >();
kpeter@80
   219
    ConvertMap<RangeMap<bool>, int> map1(rangeMap(1, true));
kpeter@80
   220
    ConvertMap<RangeMap<bool>, int> map2 = convertMap<int>(rangeMap(2, false));
kpeter@80
   221
  }
kpeter@80
   222
kpeter@80
   223
  // ForkMap
kpeter@80
   224
  {
kpeter@80
   225
    checkConcept<DoubleWriteMap, ForkMap<DoubleWriteMap, DoubleWriteMap> >();
kpeter@82
   226
kpeter@80
   227
    typedef RangeMap<double> RM;
kpeter@80
   228
    typedef SparseMap<int, double> SM;
kpeter@80
   229
    RM m1(10, -1);
kpeter@80
   230
    SM m2(-1);
kpeter@80
   231
    checkConcept<ReadWriteMap<int, double>, ForkMap<RM, SM> >();
kpeter@80
   232
    checkConcept<ReadWriteMap<int, double>, ForkMap<SM, RM> >();
kpeter@80
   233
    ForkMap<RM, SM> map1(m1,m2);
kpeter@80
   234
    ForkMap<SM, RM> map2 = forkMap(m2,m1);
kpeter@80
   235
    map2.set(5, 10);
alpar@210
   236
    check(m1[1] == -1 && m1[5] == 10 && m2[1] == -1 &&
alpar@210
   237
          m2[5] == 10 && map2[1] == -1 && map2[5] == 10,
kpeter@80
   238
          "Something is wrong with ForkMap");
kpeter@80
   239
  }
kpeter@82
   240
kpeter@80
   241
  // Arithmetic maps:
kpeter@80
   242
  // - AddMap, SubMap, MulMap, DivMap
kpeter@80
   243
  // - ShiftMap, ShiftWriteMap, ScaleMap, ScaleWriteMap
kpeter@80
   244
  // - NegMap, NegWriteMap, AbsMap
kpeter@80
   245
  {
kpeter@80
   246
    checkConcept<DoubleMap, AddMap<DoubleMap,DoubleMap> >();
kpeter@80
   247
    checkConcept<DoubleMap, SubMap<DoubleMap,DoubleMap> >();
kpeter@80
   248
    checkConcept<DoubleMap, MulMap<DoubleMap,DoubleMap> >();
kpeter@80
   249
    checkConcept<DoubleMap, DivMap<DoubleMap,DoubleMap> >();
kpeter@82
   250
kpeter@80
   251
    ConstMap<int, double> c1(1.0), c2(3.14);
kpeter@80
   252
    IdentityMap<int> im;
kpeter@80
   253
    ConvertMap<IdentityMap<int>, double> id(im);
alpar@210
   254
    check(addMap(c1,id)[0] == 1.0  && addMap(c1,id)[10] == 11.0,
alpar@210
   255
          "Something is wrong with AddMap");
alpar@210
   256
    check(subMap(id,c1)[0] == -1.0 && subMap(id,c1)[10] == 9.0,
alpar@210
   257
          "Something is wrong with SubMap");
alpar@210
   258
    check(mulMap(id,c2)[0] == 0    && mulMap(id,c2)[2]  == 6.28,
alpar@210
   259
          "Something is wrong with MulMap");
alpar@210
   260
    check(divMap(c2,id)[1] == 3.14 && divMap(c2,id)[2]  == 1.57,
alpar@210
   261
          "Something is wrong with DivMap");
kpeter@82
   262
kpeter@80
   263
    checkConcept<DoubleMap, ShiftMap<DoubleMap> >();
kpeter@80
   264
    checkConcept<DoubleWriteMap, ShiftWriteMap<DoubleWriteMap> >();
kpeter@80
   265
    checkConcept<DoubleMap, ScaleMap<DoubleMap> >();
kpeter@80
   266
    checkConcept<DoubleWriteMap, ScaleWriteMap<DoubleWriteMap> >();
kpeter@80
   267
    checkConcept<DoubleMap, NegMap<DoubleMap> >();
kpeter@80
   268
    checkConcept<DoubleWriteMap, NegWriteMap<DoubleWriteMap> >();
kpeter@80
   269
    checkConcept<DoubleMap, AbsMap<DoubleMap> >();
alpar@25
   270
kpeter@80
   271
    check(shiftMap(id, 2.0)[1] == 3.0 && shiftMap(id, 2.0)[10] == 12.0,
kpeter@80
   272
          "Something is wrong with ShiftMap");
alpar@210
   273
    check(shiftWriteMap(id, 2.0)[1] == 3.0 &&
alpar@210
   274
          shiftWriteMap(id, 2.0)[10] == 12.0,
kpeter@80
   275
          "Something is wrong with ShiftWriteMap");
kpeter@80
   276
    check(scaleMap(id, 2.0)[1] == 2.0 && scaleMap(id, 2.0)[10] == 20.0,
kpeter@80
   277
          "Something is wrong with ScaleMap");
alpar@210
   278
    check(scaleWriteMap(id, 2.0)[1] == 2.0 &&
alpar@210
   279
          scaleWriteMap(id, 2.0)[10] == 20.0,
kpeter@80
   280
          "Something is wrong with ScaleWriteMap");
kpeter@80
   281
    check(negMap(id)[1] == -1.0 && negMap(id)[-10] == 10.0,
kpeter@80
   282
          "Something is wrong with NegMap");
kpeter@80
   283
    check(negWriteMap(id)[1] == -1.0 && negWriteMap(id)[-10] == 10.0,
kpeter@80
   284
          "Something is wrong with NegWriteMap");
kpeter@80
   285
    check(absMap(id)[1] == 1.0 && absMap(id)[-10] == 10.0,
kpeter@80
   286
          "Something is wrong with AbsMap");
kpeter@80
   287
  }
kpeter@82
   288
kpeter@82
   289
  // Logical maps:
kpeter@82
   290
  // - TrueMap, FalseMap
kpeter@82
   291
  // - AndMap, OrMap
kpeter@82
   292
  // - NotMap, NotWriteMap
kpeter@82
   293
  // - EqualMap, LessMap
kpeter@80
   294
  {
kpeter@82
   295
    checkConcept<BoolMap, TrueMap<A> >();
kpeter@82
   296
    checkConcept<BoolMap, FalseMap<A> >();
kpeter@82
   297
    checkConcept<BoolMap, AndMap<BoolMap,BoolMap> >();
kpeter@82
   298
    checkConcept<BoolMap, OrMap<BoolMap,BoolMap> >();
kpeter@80
   299
    checkConcept<BoolMap, NotMap<BoolMap> >();
kpeter@80
   300
    checkConcept<BoolWriteMap, NotWriteMap<BoolWriteMap> >();
kpeter@82
   301
    checkConcept<BoolMap, EqualMap<DoubleMap,DoubleMap> >();
kpeter@82
   302
    checkConcept<BoolMap, LessMap<DoubleMap,DoubleMap> >();
kpeter@82
   303
kpeter@82
   304
    TrueMap<int> tm;
kpeter@82
   305
    FalseMap<int> fm;
kpeter@80
   306
    RangeMap<bool> rm(2);
kpeter@80
   307
    rm[0] = true; rm[1] = false;
alpar@210
   308
    check(andMap(tm,rm)[0] && !andMap(tm,rm)[1] &&
alpar@210
   309
          !andMap(fm,rm)[0] && !andMap(fm,rm)[1],
kpeter@82
   310
          "Something is wrong with AndMap");
alpar@210
   311
    check(orMap(tm,rm)[0] && orMap(tm,rm)[1] &&
alpar@210
   312
          orMap(fm,rm)[0] && !orMap(fm,rm)[1],
kpeter@82
   313
          "Something is wrong with OrMap");
alpar@210
   314
    check(!notMap(rm)[0] && notMap(rm)[1],
alpar@210
   315
          "Something is wrong with NotMap");
alpar@210
   316
    check(!notWriteMap(rm)[0] && notWriteMap(rm)[1],
alpar@210
   317
          "Something is wrong with NotWriteMap");
kpeter@82
   318
kpeter@82
   319
    ConstMap<int, double> cm(2.0);
kpeter@82
   320
    IdentityMap<int> im;
kpeter@82
   321
    ConvertMap<IdentityMap<int>, double> id(im);
kpeter@82
   322
    check(lessMap(id,cm)[1] && !lessMap(id,cm)[2] && !lessMap(id,cm)[3],
kpeter@82
   323
          "Something is wrong with LessMap");
kpeter@82
   324
    check(!equalMap(id,cm)[1] && equalMap(id,cm)[2] && !equalMap(id,cm)[3],
kpeter@82
   325
          "Something is wrong with EqualMap");
kpeter@80
   326
  }
alpar@209
   327
kpeter@167
   328
  // LoggerBoolMap
kpeter@159
   329
  {
kpeter@159
   330
    typedef std::vector<int> vec;
kpeter@159
   331
    vec v1;
kpeter@159
   332
    vec v2(10);
alpar@210
   333
    LoggerBoolMap<std::back_insert_iterator<vec> >
alpar@210
   334
      map1(std::back_inserter(v1));
kpeter@167
   335
    LoggerBoolMap<vec::iterator> map2(v2.begin());
kpeter@159
   336
    map1.set(10, false);
kpeter@159
   337
    map1.set(20, true);   map2.set(20, true);
kpeter@159
   338
    map1.set(30, false);  map2.set(40, false);
kpeter@159
   339
    map1.set(50, true);   map2.set(50, true);
kpeter@159
   340
    map1.set(60, true);   map2.set(60, true);
kpeter@159
   341
    check(v1.size() == 3 && v2.size() == 10 &&
alpar@210
   342
          v1[0]==20 && v1[1]==50 && v1[2]==60 &&
alpar@210
   343
          v2[0]==20 && v2[1]==50 && v2[2]==60,
kpeter@167
   344
          "Something is wrong with LoggerBoolMap");
alpar@209
   345
kpeter@159
   346
    int i = 0;
kpeter@167
   347
    for ( LoggerBoolMap<vec::iterator>::Iterator it = map2.begin();
kpeter@159
   348
          it != map2.end(); ++it )
kpeter@167
   349
      check(v1[i++] == *it, "Something is wrong with LoggerBoolMap");
kpeter@159
   350
  }
alpar@25
   351
alpar@25
   352
  return 0;
alpar@25
   353
}