test/min_mean_cycle_test.cc
author Alpar Juttner <alpar@cs.elte.hu>
Sat, 10 Aug 2013 14:27:19 +0200
branch1.2
changeset 992 92d53f86d1a9
parent 864 d3ea191c3412
permissions -rw-r--r--
LEMON 1.2.4 released (e13061207f85 tagged as r1.2.4)
     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 <iostream>
    20 #include <sstream>
    21 
    22 #include <lemon/smart_graph.h>
    23 #include <lemon/lgf_reader.h>
    24 #include <lemon/path.h>
    25 #include <lemon/concepts/digraph.h>
    26 #include <lemon/concept_check.h>
    27 
    28 #include <lemon/karp_mmc.h>
    29 #include <lemon/hartmann_orlin_mmc.h>
    30 #include <lemon/howard_mmc.h>
    31 
    32 #include "test_tools.h"
    33 
    34 using namespace lemon;
    35 
    36 char test_lgf[] =
    37   "@nodes\n"
    38   "label\n"
    39   "1\n"
    40   "2\n"
    41   "3\n"
    42   "4\n"
    43   "5\n"
    44   "6\n"
    45   "7\n"
    46   "@arcs\n"
    47   "    len1 len2 len3 len4  c1 c2 c3 c4\n"
    48   "1 2    1    1    1    1   0  0  0  0\n"
    49   "2 4    5    5    5    5   1  0  0  0\n"
    50   "2 3    8    8    8    8   0  0  0  0\n"
    51   "3 2   -2    0    0    0   1  0  0  0\n"
    52   "3 4    4    4    4    4   0  0  0  0\n"
    53   "3 7   -4   -4   -4   -4   0  0  0  0\n"
    54   "4 1    2    2    2    2   0  0  0  0\n"
    55   "4 3    3    3    3    3   1  0  0  0\n"
    56   "4 4    3    3    0    0   0  0  1  0\n"
    57   "5 2    4    4    4    4   0  0  0  0\n"
    58   "5 6    3    3    3    3   0  1  0  0\n"
    59   "6 5    2    2    2    2   0  1  0  0\n"
    60   "6 4   -1   -1   -1   -1   0  0  0  0\n"
    61   "6 7    1    1    1    1   0  0  0  0\n"
    62   "7 7    4    4    4   -1   0  0  0  1\n";
    63 
    64 
    65 // Check the interface of an MMC algorithm
    66 template <typename GR, typename Cost>
    67 struct MmcClassConcept
    68 {
    69   template <typename MMC>
    70   struct Constraints {
    71     void constraints() {
    72       const Constraints& me = *this;
    73 
    74       typedef typename MMC
    75         ::template SetPath<ListPath<GR> >
    76         ::template SetLargeCost<Cost>
    77         ::Create MmcAlg;
    78       MmcAlg mmc(me.g, me.cost);
    79       const MmcAlg& const_mmc = mmc;
    80 
    81       typename MmcAlg::Tolerance tol = const_mmc.tolerance();
    82       mmc.tolerance(tol);
    83 
    84       b = mmc.cycle(p).run();
    85       b = mmc.findCycleMean();
    86       b = mmc.findCycle();
    87 
    88       v = const_mmc.cycleCost();
    89       i = const_mmc.cycleSize();
    90       d = const_mmc.cycleMean();
    91       p = const_mmc.cycle();
    92     }
    93 
    94     typedef concepts::ReadMap<typename GR::Arc, Cost> CM;
    95 
    96     GR g;
    97     CM cost;
    98     ListPath<GR> p;
    99     Cost v;
   100     int i;
   101     double d;
   102     bool b;
   103   };
   104 };
   105 
   106 // Perform a test with the given parameters
   107 template <typename MMC>
   108 void checkMmcAlg(const SmartDigraph& gr,
   109                  const SmartDigraph::ArcMap<int>& lm,
   110                  const SmartDigraph::ArcMap<int>& cm,
   111                  int cost, int size) {
   112   MMC alg(gr, lm);
   113   alg.findCycleMean();
   114   check(alg.cycleMean() == static_cast<double>(cost) / size,
   115         "Wrong cycle mean");
   116   alg.findCycle();
   117   check(alg.cycleCost() == cost && alg.cycleSize() == size,
   118         "Wrong path");
   119   SmartDigraph::ArcMap<int> cycle(gr, 0);
   120   for (typename MMC::Path::ArcIt a(alg.cycle()); a != INVALID; ++a) {
   121     ++cycle[a];
   122   }
   123   for (SmartDigraph::ArcIt a(gr); a != INVALID; ++a) {
   124     check(cm[a] == cycle[a], "Wrong path");
   125   }
   126 }
   127 
   128 // Class for comparing types
   129 template <typename T1, typename T2>
   130 struct IsSameType {
   131   static const int result = 0;
   132 };
   133 
   134 template <typename T>
   135 struct IsSameType<T,T> {
   136   static const int result = 1;
   137 };
   138 
   139 
   140 int main() {
   141   #ifdef LEMON_HAVE_LONG_LONG
   142     typedef long long long_int;
   143   #else
   144     typedef long long_int;
   145   #endif
   146 
   147   // Check the interface
   148   {
   149     typedef concepts::Digraph GR;
   150 
   151     // KarpMmc
   152     checkConcept< MmcClassConcept<GR, int>,
   153                   KarpMmc<GR, concepts::ReadMap<GR::Arc, int> > >();
   154     checkConcept< MmcClassConcept<GR, float>,
   155                   KarpMmc<GR, concepts::ReadMap<GR::Arc, float> > >();
   156 
   157     // HartmannOrlinMmc
   158     checkConcept< MmcClassConcept<GR, int>,
   159                   HartmannOrlinMmc<GR, concepts::ReadMap<GR::Arc, int> > >();
   160     checkConcept< MmcClassConcept<GR, float>,
   161                   HartmannOrlinMmc<GR, concepts::ReadMap<GR::Arc, float> > >();
   162 
   163     // HowardMmc
   164     checkConcept< MmcClassConcept<GR, int>,
   165                   HowardMmc<GR, concepts::ReadMap<GR::Arc, int> > >();
   166     checkConcept< MmcClassConcept<GR, float>,
   167                   HowardMmc<GR, concepts::ReadMap<GR::Arc, float> > >();
   168 
   169     check((IsSameType<HowardMmc<GR, concepts::ReadMap<GR::Arc, int> >
   170            ::LargeCost, long_int>::result == 1), "Wrong LargeCost type");
   171     check((IsSameType<HowardMmc<GR, concepts::ReadMap<GR::Arc, float> >
   172            ::LargeCost, double>::result == 1), "Wrong LargeCost type");
   173   }
   174 
   175   // Run various tests
   176   {
   177     typedef SmartDigraph GR;
   178     DIGRAPH_TYPEDEFS(GR);
   179 
   180     GR gr;
   181     IntArcMap l1(gr), l2(gr), l3(gr), l4(gr);
   182     IntArcMap c1(gr), c2(gr), c3(gr), c4(gr);
   183 
   184     std::istringstream input(test_lgf);
   185     digraphReader(gr, input).
   186       arcMap("len1", l1).
   187       arcMap("len2", l2).
   188       arcMap("len3", l3).
   189       arcMap("len4", l4).
   190       arcMap("c1", c1).
   191       arcMap("c2", c2).
   192       arcMap("c3", c3).
   193       arcMap("c4", c4).
   194       run();
   195 
   196     // Karp
   197     checkMmcAlg<KarpMmc<GR, IntArcMap> >(gr, l1, c1,  6, 3);
   198     checkMmcAlg<KarpMmc<GR, IntArcMap> >(gr, l2, c2,  5, 2);
   199     checkMmcAlg<KarpMmc<GR, IntArcMap> >(gr, l3, c3,  0, 1);
   200     checkMmcAlg<KarpMmc<GR, IntArcMap> >(gr, l4, c4, -1, 1);
   201 
   202     // HartmannOrlin
   203     checkMmcAlg<HartmannOrlinMmc<GR, IntArcMap> >(gr, l1, c1,  6, 3);
   204     checkMmcAlg<HartmannOrlinMmc<GR, IntArcMap> >(gr, l2, c2,  5, 2);
   205     checkMmcAlg<HartmannOrlinMmc<GR, IntArcMap> >(gr, l3, c3,  0, 1);
   206     checkMmcAlg<HartmannOrlinMmc<GR, IntArcMap> >(gr, l4, c4, -1, 1);
   207 
   208     // Howard
   209     checkMmcAlg<HowardMmc<GR, IntArcMap> >(gr, l1, c1,  6, 3);
   210     checkMmcAlg<HowardMmc<GR, IntArcMap> >(gr, l2, c2,  5, 2);
   211     checkMmcAlg<HowardMmc<GR, IntArcMap> >(gr, l3, c3,  0, 1);
   212     checkMmcAlg<HowardMmc<GR, IntArcMap> >(gr, l4, c4, -1, 1);
   213   }
   214 
   215   return 0;
   216 }