test/min_mean_cycle_test.cc
author Peter Kovacs <kpeter@inf.elte.hu>
Fri, 13 Nov 2009 00:11:11 +0100
changeset 816 277ef0218f0c
parent 766 97744b6dabf8
child 864 d3ea191c3412
permissions -rw-r--r--
Add citations to CycleCanceling (#180, #184)
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
 *
kpeter@763
     5
 * Copyright (C) 2003-2009
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@765
    28
#include <lemon/karp.h>
kpeter@766
    29
#include <lemon/hartmann_orlin.h>
kpeter@765
    30
#include <lemon/howard.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
kpeter@763
    64
                        
kpeter@763
    65
// Check the interface of an MMC algorithm
kpeter@763
    66
template <typename GR, typename Value>
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@763
    76
        ::template SetLargeValue<Value>
kpeter@763
    77
        ::Create MmcAlg;
kpeter@763
    78
      MmcAlg mmc(me.g, me.length);
kpeter@763
    79
      const MmcAlg& const_mmc = mmc;
kpeter@763
    80
      
kpeter@769
    81
      typename MmcAlg::Tolerance tol = const_mmc.tolerance();
kpeter@769
    82
      mmc.tolerance(tol);
kpeter@769
    83
      
kpeter@763
    84
      b = mmc.cycle(p).run();
kpeter@763
    85
      b = mmc.findMinMean();
kpeter@763
    86
      b = mmc.findCycle();
kpeter@763
    87
kpeter@763
    88
      v = const_mmc.cycleLength();
kpeter@763
    89
      i = const_mmc.cycleArcNum();
kpeter@763
    90
      d = const_mmc.cycleMean();
kpeter@763
    91
      p = const_mmc.cycle();
kpeter@763
    92
    }
kpeter@763
    93
kpeter@763
    94
    typedef concepts::ReadMap<typename GR::Arc, Value> LM;
kpeter@763
    95
  
kpeter@763
    96
    GR g;
kpeter@763
    97
    LM length;
kpeter@763
    98
    ListPath<GR> p;
kpeter@763
    99
    Value 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@763
   111
                 int length, int size) {
kpeter@763
   112
  MMC alg(gr, lm);
kpeter@763
   113
  alg.findMinMean();
kpeter@763
   114
  check(alg.cycleMean() == static_cast<double>(length) / size,
kpeter@763
   115
        "Wrong cycle mean");
kpeter@763
   116
  alg.findCycle();
kpeter@763
   117
  check(alg.cycleLength() == length && alg.cycleArcNum() == 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@765
   151
    // Karp
kpeter@765
   152
    checkConcept< MmcClassConcept<GR, int>,
kpeter@765
   153
                  Karp<GR, concepts::ReadMap<GR::Arc, int> > >();
kpeter@765
   154
    checkConcept< MmcClassConcept<GR, float>,
kpeter@765
   155
                  Karp<GR, concepts::ReadMap<GR::Arc, float> > >();
kpeter@763
   156
    
kpeter@766
   157
    // HartmannOrlin
kpeter@766
   158
    checkConcept< MmcClassConcept<GR, int>,
kpeter@766
   159
                  HartmannOrlin<GR, concepts::ReadMap<GR::Arc, int> > >();
kpeter@766
   160
    checkConcept< MmcClassConcept<GR, float>,
kpeter@766
   161
                  HartmannOrlin<GR, concepts::ReadMap<GR::Arc, float> > >();
kpeter@766
   162
    
kpeter@765
   163
    // Howard
kpeter@765
   164
    checkConcept< MmcClassConcept<GR, int>,
kpeter@765
   165
                  Howard<GR, concepts::ReadMap<GR::Arc, int> > >();
kpeter@765
   166
    checkConcept< MmcClassConcept<GR, float>,
kpeter@765
   167
                  Howard<GR, concepts::ReadMap<GR::Arc, float> > >();
kpeter@765
   168
kpeter@765
   169
    if (IsSameType<Howard<GR, concepts::ReadMap<GR::Arc, int> >::LargeValue,
kpeter@765
   170
          long_int>::result == 0) check(false, "Wrong LargeValue type");
kpeter@765
   171
    if (IsSameType<Howard<GR, concepts::ReadMap<GR::Arc, float> >::LargeValue,
kpeter@765
   172
          double>::result == 0) check(false, "Wrong LargeValue 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);
kpeter@763
   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);
kpeter@763
   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@765
   197
    checkMmcAlg<Karp<GR, IntArcMap> >(gr, l1, c1,  6, 3);
kpeter@765
   198
    checkMmcAlg<Karp<GR, IntArcMap> >(gr, l2, c2,  5, 2);
kpeter@765
   199
    checkMmcAlg<Karp<GR, IntArcMap> >(gr, l3, c3,  0, 1);
kpeter@765
   200
    checkMmcAlg<Karp<GR, IntArcMap> >(gr, l4, c4, -1, 1);
kpeter@765
   201
kpeter@766
   202
    // HartmannOrlin
kpeter@766
   203
    checkMmcAlg<HartmannOrlin<GR, IntArcMap> >(gr, l1, c1,  6, 3);
kpeter@766
   204
    checkMmcAlg<HartmannOrlin<GR, IntArcMap> >(gr, l2, c2,  5, 2);
kpeter@766
   205
    checkMmcAlg<HartmannOrlin<GR, IntArcMap> >(gr, l3, c3,  0, 1);
kpeter@766
   206
    checkMmcAlg<HartmannOrlin<GR, IntArcMap> >(gr, l4, c4, -1, 1);
kpeter@766
   207
kpeter@765
   208
    // Howard
kpeter@764
   209
    checkMmcAlg<Howard<GR, IntArcMap> >(gr, l1, c1,  6, 3);
kpeter@764
   210
    checkMmcAlg<Howard<GR, IntArcMap> >(gr, l2, c2,  5, 2);
kpeter@764
   211
    checkMmcAlg<Howard<GR, IntArcMap> >(gr, l3, c3,  0, 1);
kpeter@764
   212
    checkMmcAlg<Howard<GR, IntArcMap> >(gr, l4, c4, -1, 1);
kpeter@763
   213
  }
kpeter@763
   214
kpeter@763
   215
  return 0;
kpeter@763
   216
}