test/min_mean_cycle_test.cc
author Alpar Juttner <alpar@cs.elte.hu>
Sun, 11 Aug 2013 21:56:21 +0200
changeset 1098 cf6084618b1b
parent 1012 21a9f829ab68
permissions -rw-r--r--
Merge headmerge to the default branch
kpeter@763
     1
/* -*- mode: C++; indent-tabs-mode: nil; -*-
kpeter@763
     2
 *
kpeter@763
     3
 * This file is a part of LEMON, a generic C++ optimization library.
kpeter@763
     4
 *
alpar@1092
     5
 * Copyright (C) 2003-2013
kpeter@763
     6
 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
kpeter@763
     7
 * (Egervary Research Group on Combinatorial Optimization, EGRES).
kpeter@763
     8
 *
kpeter@763
     9
 * Permission to use, modify and distribute this software is granted
kpeter@763
    10
 * provided that this copyright notice appears in all copies. For
kpeter@763
    11
 * precise terms see the accompanying LICENSE file.
kpeter@763
    12
 *
kpeter@763
    13
 * This software is provided "AS IS" with no warranty of any kind,
kpeter@763
    14
 * express or implied, and with no claim as to its suitability for any
kpeter@763
    15
 * purpose.
kpeter@763
    16
 *
kpeter@763
    17
 */
kpeter@763
    18
kpeter@763
    19
#include <iostream>
kpeter@763
    20
#include <sstream>
kpeter@763
    21
kpeter@763
    22
#include <lemon/smart_graph.h>
kpeter@763
    23
#include <lemon/lgf_reader.h>
kpeter@763
    24
#include <lemon/path.h>
kpeter@763
    25
#include <lemon/concepts/digraph.h>
kpeter@763
    26
#include <lemon/concept_check.h>
kpeter@763
    27
kpeter@864
    28
#include <lemon/karp_mmc.h>
kpeter@864
    29
#include <lemon/hartmann_orlin_mmc.h>
kpeter@864
    30
#include <lemon/howard_mmc.h>
kpeter@765
    31
kpeter@763
    32
#include "test_tools.h"
kpeter@763
    33
kpeter@763
    34
using namespace lemon;
kpeter@763
    35
kpeter@763
    36
char test_lgf[] =
kpeter@763
    37
  "@nodes\n"
kpeter@763
    38
  "label\n"
kpeter@763
    39
  "1\n"
kpeter@763
    40
  "2\n"
kpeter@763
    41
  "3\n"
kpeter@763
    42
  "4\n"
kpeter@763
    43
  "5\n"
kpeter@763
    44
  "6\n"
kpeter@763
    45
  "7\n"
kpeter@763
    46
  "@arcs\n"
kpeter@763
    47
  "    len1 len2 len3 len4  c1 c2 c3 c4\n"
kpeter@763
    48
  "1 2    1    1    1    1   0  0  0  0\n"
kpeter@763
    49
  "2 4    5    5    5    5   1  0  0  0\n"
kpeter@763
    50
  "2 3    8    8    8    8   0  0  0  0\n"
kpeter@763
    51
  "3 2   -2    0    0    0   1  0  0  0\n"
kpeter@763
    52
  "3 4    4    4    4    4   0  0  0  0\n"
kpeter@763
    53
  "3 7   -4   -4   -4   -4   0  0  0  0\n"
kpeter@763
    54
  "4 1    2    2    2    2   0  0  0  0\n"
kpeter@763
    55
  "4 3    3    3    3    3   1  0  0  0\n"
kpeter@763
    56
  "4 4    3    3    0    0   0  0  1  0\n"
kpeter@763
    57
  "5 2    4    4    4    4   0  0  0  0\n"
kpeter@763
    58
  "5 6    3    3    3    3   0  1  0  0\n"
kpeter@763
    59
  "6 5    2    2    2    2   0  1  0  0\n"
kpeter@763
    60
  "6 4   -1   -1   -1   -1   0  0  0  0\n"
kpeter@763
    61
  "6 7    1    1    1    1   0  0  0  0\n"
kpeter@763
    62
  "7 7    4    4    4   -1   0  0  0  1\n";
kpeter@763
    63
alpar@877
    64
kpeter@763
    65
// Check the interface of an MMC algorithm
kpeter@864
    66
template <typename GR, typename Cost>
kpeter@763
    67
struct MmcClassConcept
kpeter@763
    68
{
kpeter@763
    69
  template <typename MMC>
kpeter@763
    70
  struct Constraints {
kpeter@763
    71
    void constraints() {
kpeter@763
    72
      const Constraints& me = *this;
kpeter@763
    73
kpeter@763
    74
      typedef typename MMC
kpeter@763
    75
        ::template SetPath<ListPath<GR> >
kpeter@864
    76
        ::template SetLargeCost<Cost>
kpeter@763
    77
        ::Create MmcAlg;
kpeter@864
    78
      MmcAlg mmc(me.g, me.cost);
kpeter@763
    79
      const MmcAlg& const_mmc = mmc;
alpar@877
    80
kpeter@769
    81
      typename MmcAlg::Tolerance tol = const_mmc.tolerance();
kpeter@769
    82
      mmc.tolerance(tol);
alpar@877
    83
kpeter@763
    84
      b = mmc.cycle(p).run();
kpeter@864
    85
      b = mmc.findCycleMean();
kpeter@763
    86
      b = mmc.findCycle();
kpeter@763
    87
kpeter@864
    88
      v = const_mmc.cycleCost();
kpeter@864
    89
      i = const_mmc.cycleSize();
kpeter@763
    90
      d = const_mmc.cycleMean();
kpeter@763
    91
      p = const_mmc.cycle();
kpeter@763
    92
    }
kpeter@763
    93
kpeter@864
    94
    typedef concepts::ReadMap<typename GR::Arc, Cost> CM;
alpar@877
    95
kpeter@763
    96
    GR g;
kpeter@864
    97
    CM cost;
kpeter@763
    98
    ListPath<GR> p;
kpeter@864
    99
    Cost v;
kpeter@763
   100
    int i;
kpeter@763
   101
    double d;
kpeter@763
   102
    bool b;
kpeter@763
   103
  };
kpeter@763
   104
};
kpeter@763
   105
kpeter@763
   106
// Perform a test with the given parameters
kpeter@763
   107
template <typename MMC>
kpeter@763
   108
void checkMmcAlg(const SmartDigraph& gr,
kpeter@763
   109
                 const SmartDigraph::ArcMap<int>& lm,
kpeter@763
   110
                 const SmartDigraph::ArcMap<int>& cm,
kpeter@864
   111
                 int cost, int size) {
kpeter@763
   112
  MMC alg(gr, lm);
kpeter@1012
   113
  check(alg.findCycleMean(), "Wrong result");
kpeter@864
   114
  check(alg.cycleMean() == static_cast<double>(cost) / size,
kpeter@763
   115
        "Wrong cycle mean");
kpeter@763
   116
  alg.findCycle();
kpeter@864
   117
  check(alg.cycleCost() == cost && alg.cycleSize() == size,
kpeter@763
   118
        "Wrong path");
kpeter@763
   119
  SmartDigraph::ArcMap<int> cycle(gr, 0);
kpeter@763
   120
  for (typename MMC::Path::ArcIt a(alg.cycle()); a != INVALID; ++a) {
kpeter@763
   121
    ++cycle[a];
kpeter@763
   122
  }
kpeter@763
   123
  for (SmartDigraph::ArcIt a(gr); a != INVALID; ++a) {
kpeter@763
   124
    check(cm[a] == cycle[a], "Wrong path");
kpeter@763
   125
  }
kpeter@763
   126
}
kpeter@763
   127
kpeter@763
   128
// Class for comparing types
kpeter@763
   129
template <typename T1, typename T2>
kpeter@763
   130
struct IsSameType {
kpeter@763
   131
  static const int result = 0;
kpeter@763
   132
};
kpeter@763
   133
kpeter@763
   134
template <typename T>
kpeter@763
   135
struct IsSameType<T,T> {
kpeter@763
   136
  static const int result = 1;
kpeter@763
   137
};
kpeter@763
   138
kpeter@763
   139
kpeter@763
   140
int main() {
kpeter@763
   141
  #ifdef LEMON_HAVE_LONG_LONG
kpeter@763
   142
    typedef long long long_int;
kpeter@763
   143
  #else
kpeter@763
   144
    typedef long long_int;
kpeter@763
   145
  #endif
kpeter@763
   146
kpeter@763
   147
  // Check the interface
kpeter@763
   148
  {
kpeter@763
   149
    typedef concepts::Digraph GR;
kpeter@765
   150
kpeter@864
   151
    // KarpMmc
kpeter@765
   152
    checkConcept< MmcClassConcept<GR, int>,
kpeter@864
   153
                  KarpMmc<GR, concepts::ReadMap<GR::Arc, int> > >();
kpeter@765
   154
    checkConcept< MmcClassConcept<GR, float>,
kpeter@864
   155
                  KarpMmc<GR, concepts::ReadMap<GR::Arc, float> > >();
alpar@877
   156
kpeter@864
   157
    // HartmannOrlinMmc
kpeter@766
   158
    checkConcept< MmcClassConcept<GR, int>,
kpeter@864
   159
                  HartmannOrlinMmc<GR, concepts::ReadMap<GR::Arc, int> > >();
kpeter@766
   160
    checkConcept< MmcClassConcept<GR, float>,
kpeter@864
   161
                  HartmannOrlinMmc<GR, concepts::ReadMap<GR::Arc, float> > >();
alpar@877
   162
kpeter@864
   163
    // HowardMmc
kpeter@765
   164
    checkConcept< MmcClassConcept<GR, int>,
kpeter@864
   165
                  HowardMmc<GR, concepts::ReadMap<GR::Arc, int> > >();
kpeter@765
   166
    checkConcept< MmcClassConcept<GR, float>,
kpeter@864
   167
                  HowardMmc<GR, concepts::ReadMap<GR::Arc, float> > >();
kpeter@765
   168
kpeter@864
   169
    check((IsSameType<HowardMmc<GR, concepts::ReadMap<GR::Arc, int> >
kpeter@864
   170
           ::LargeCost, long_int>::result == 1), "Wrong LargeCost type");
kpeter@864
   171
    check((IsSameType<HowardMmc<GR, concepts::ReadMap<GR::Arc, float> >
kpeter@864
   172
           ::LargeCost, double>::result == 1), "Wrong LargeCost type");
kpeter@763
   173
  }
kpeter@763
   174
kpeter@763
   175
  // Run various tests
kpeter@763
   176
  {
kpeter@763
   177
    typedef SmartDigraph GR;
kpeter@763
   178
    DIGRAPH_TYPEDEFS(GR);
alpar@877
   179
kpeter@763
   180
    GR gr;
kpeter@763
   181
    IntArcMap l1(gr), l2(gr), l3(gr), l4(gr);
kpeter@763
   182
    IntArcMap c1(gr), c2(gr), c3(gr), c4(gr);
alpar@877
   183
kpeter@763
   184
    std::istringstream input(test_lgf);
kpeter@763
   185
    digraphReader(gr, input).
kpeter@763
   186
      arcMap("len1", l1).
kpeter@763
   187
      arcMap("len2", l2).
kpeter@763
   188
      arcMap("len3", l3).
kpeter@763
   189
      arcMap("len4", l4).
kpeter@763
   190
      arcMap("c1", c1).
kpeter@763
   191
      arcMap("c2", c2).
kpeter@763
   192
      arcMap("c3", c3).
kpeter@763
   193
      arcMap("c4", c4).
kpeter@763
   194
      run();
kpeter@763
   195
kpeter@765
   196
    // Karp
kpeter@864
   197
    checkMmcAlg<KarpMmc<GR, IntArcMap> >(gr, l1, c1,  6, 3);
kpeter@864
   198
    checkMmcAlg<KarpMmc<GR, IntArcMap> >(gr, l2, c2,  5, 2);
kpeter@864
   199
    checkMmcAlg<KarpMmc<GR, IntArcMap> >(gr, l3, c3,  0, 1);
kpeter@864
   200
    checkMmcAlg<KarpMmc<GR, IntArcMap> >(gr, l4, c4, -1, 1);
kpeter@765
   201
kpeter@766
   202
    // HartmannOrlin
kpeter@864
   203
    checkMmcAlg<HartmannOrlinMmc<GR, IntArcMap> >(gr, l1, c1,  6, 3);
kpeter@864
   204
    checkMmcAlg<HartmannOrlinMmc<GR, IntArcMap> >(gr, l2, c2,  5, 2);
kpeter@864
   205
    checkMmcAlg<HartmannOrlinMmc<GR, IntArcMap> >(gr, l3, c3,  0, 1);
kpeter@864
   206
    checkMmcAlg<HartmannOrlinMmc<GR, IntArcMap> >(gr, l4, c4, -1, 1);
kpeter@766
   207
kpeter@765
   208
    // Howard
kpeter@864
   209
    checkMmcAlg<HowardMmc<GR, IntArcMap> >(gr, l1, c1,  6, 3);
kpeter@864
   210
    checkMmcAlg<HowardMmc<GR, IntArcMap> >(gr, l2, c2,  5, 2);
kpeter@864
   211
    checkMmcAlg<HowardMmc<GR, IntArcMap> >(gr, l3, c3,  0, 1);
kpeter@864
   212
    checkMmcAlg<HowardMmc<GR, IntArcMap> >(gr, l4, c4, -1, 1);
alpar@1092
   213
kpeter@1012
   214
    // Howard with iteration limit
kpeter@1012
   215
    HowardMmc<GR, IntArcMap> mmc(gr, l1);
kpeter@1012
   216
    check((mmc.findCycleMean(2) == HowardMmc<GR, IntArcMap>::ITERATION_LIMIT),
kpeter@1012
   217
      "Wrong termination cause");
kpeter@1012
   218
    check((mmc.findCycleMean(4) == HowardMmc<GR, IntArcMap>::OPTIMAL),
kpeter@1012
   219
      "Wrong termination cause");
kpeter@763
   220
  }
kpeter@763
   221
kpeter@763
   222
  return 0;
kpeter@763
   223
}