test/min_mean_cycle_test.cc
changeset 865 d48d79b11f5b
parent 769 e746fb14e680
child 877 141f9c0db4a3
equal deleted inserted replaced
4:8835cddcc0e6 5:c757fe254a7c
    23 #include <lemon/lgf_reader.h>
    23 #include <lemon/lgf_reader.h>
    24 #include <lemon/path.h>
    24 #include <lemon/path.h>
    25 #include <lemon/concepts/digraph.h>
    25 #include <lemon/concepts/digraph.h>
    26 #include <lemon/concept_check.h>
    26 #include <lemon/concept_check.h>
    27 
    27 
    28 #include <lemon/karp.h>
    28 #include <lemon/karp_mmc.h>
    29 #include <lemon/hartmann_orlin.h>
    29 #include <lemon/hartmann_orlin_mmc.h>
    30 #include <lemon/howard.h>
    30 #include <lemon/howard_mmc.h>
    31 
    31 
    32 #include "test_tools.h"
    32 #include "test_tools.h"
    33 
    33 
    34 using namespace lemon;
    34 using namespace lemon;
    35 
    35 
    61   "6 7    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";
    62   "7 7    4    4    4   -1   0  0  0  1\n";
    63 
    63 
    64                         
    64                         
    65 // Check the interface of an MMC algorithm
    65 // Check the interface of an MMC algorithm
    66 template <typename GR, typename Value>
    66 template <typename GR, typename Cost>
    67 struct MmcClassConcept
    67 struct MmcClassConcept
    68 {
    68 {
    69   template <typename MMC>
    69   template <typename MMC>
    70   struct Constraints {
    70   struct Constraints {
    71     void constraints() {
    71     void constraints() {
    72       const Constraints& me = *this;
    72       const Constraints& me = *this;
    73 
    73 
    74       typedef typename MMC
    74       typedef typename MMC
    75         ::template SetPath<ListPath<GR> >
    75         ::template SetPath<ListPath<GR> >
    76         ::template SetLargeValue<Value>
    76         ::template SetLargeCost<Cost>
    77         ::Create MmcAlg;
    77         ::Create MmcAlg;
    78       MmcAlg mmc(me.g, me.length);
    78       MmcAlg mmc(me.g, me.cost);
    79       const MmcAlg& const_mmc = mmc;
    79       const MmcAlg& const_mmc = mmc;
    80       
    80       
    81       typename MmcAlg::Tolerance tol = const_mmc.tolerance();
    81       typename MmcAlg::Tolerance tol = const_mmc.tolerance();
    82       mmc.tolerance(tol);
    82       mmc.tolerance(tol);
    83       
    83       
    84       b = mmc.cycle(p).run();
    84       b = mmc.cycle(p).run();
    85       b = mmc.findMinMean();
    85       b = mmc.findCycleMean();
    86       b = mmc.findCycle();
    86       b = mmc.findCycle();
    87 
    87 
    88       v = const_mmc.cycleLength();
    88       v = const_mmc.cycleCost();
    89       i = const_mmc.cycleArcNum();
    89       i = const_mmc.cycleSize();
    90       d = const_mmc.cycleMean();
    90       d = const_mmc.cycleMean();
    91       p = const_mmc.cycle();
    91       p = const_mmc.cycle();
    92     }
    92     }
    93 
    93 
    94     typedef concepts::ReadMap<typename GR::Arc, Value> LM;
    94     typedef concepts::ReadMap<typename GR::Arc, Cost> CM;
    95   
    95   
    96     GR g;
    96     GR g;
    97     LM length;
    97     CM cost;
    98     ListPath<GR> p;
    98     ListPath<GR> p;
    99     Value v;
    99     Cost v;
   100     int i;
   100     int i;
   101     double d;
   101     double d;
   102     bool b;
   102     bool b;
   103   };
   103   };
   104 };
   104 };
   106 // Perform a test with the given parameters
   106 // Perform a test with the given parameters
   107 template <typename MMC>
   107 template <typename MMC>
   108 void checkMmcAlg(const SmartDigraph& gr,
   108 void checkMmcAlg(const SmartDigraph& gr,
   109                  const SmartDigraph::ArcMap<int>& lm,
   109                  const SmartDigraph::ArcMap<int>& lm,
   110                  const SmartDigraph::ArcMap<int>& cm,
   110                  const SmartDigraph::ArcMap<int>& cm,
   111                  int length, int size) {
   111                  int cost, int size) {
   112   MMC alg(gr, lm);
   112   MMC alg(gr, lm);
   113   alg.findMinMean();
   113   alg.findCycleMean();
   114   check(alg.cycleMean() == static_cast<double>(length) / size,
   114   check(alg.cycleMean() == static_cast<double>(cost) / size,
   115         "Wrong cycle mean");
   115         "Wrong cycle mean");
   116   alg.findCycle();
   116   alg.findCycle();
   117   check(alg.cycleLength() == length && alg.cycleArcNum() == size,
   117   check(alg.cycleCost() == cost && alg.cycleSize() == size,
   118         "Wrong path");
   118         "Wrong path");
   119   SmartDigraph::ArcMap<int> cycle(gr, 0);
   119   SmartDigraph::ArcMap<int> cycle(gr, 0);
   120   for (typename MMC::Path::ArcIt a(alg.cycle()); a != INVALID; ++a) {
   120   for (typename MMC::Path::ArcIt a(alg.cycle()); a != INVALID; ++a) {
   121     ++cycle[a];
   121     ++cycle[a];
   122   }
   122   }
   146 
   146 
   147   // Check the interface
   147   // Check the interface
   148   {
   148   {
   149     typedef concepts::Digraph GR;
   149     typedef concepts::Digraph GR;
   150 
   150 
   151     // Karp
   151     // KarpMmc
   152     checkConcept< MmcClassConcept<GR, int>,
   152     checkConcept< MmcClassConcept<GR, int>,
   153                   Karp<GR, concepts::ReadMap<GR::Arc, int> > >();
   153                   KarpMmc<GR, concepts::ReadMap<GR::Arc, int> > >();
   154     checkConcept< MmcClassConcept<GR, float>,
   154     checkConcept< MmcClassConcept<GR, float>,
   155                   Karp<GR, concepts::ReadMap<GR::Arc, float> > >();
   155                   KarpMmc<GR, concepts::ReadMap<GR::Arc, float> > >();
   156     
   156     
   157     // HartmannOrlin
   157     // HartmannOrlinMmc
   158     checkConcept< MmcClassConcept<GR, int>,
   158     checkConcept< MmcClassConcept<GR, int>,
   159                   HartmannOrlin<GR, concepts::ReadMap<GR::Arc, int> > >();
   159                   HartmannOrlinMmc<GR, concepts::ReadMap<GR::Arc, int> > >();
   160     checkConcept< MmcClassConcept<GR, float>,
   160     checkConcept< MmcClassConcept<GR, float>,
   161                   HartmannOrlin<GR, concepts::ReadMap<GR::Arc, float> > >();
   161                   HartmannOrlinMmc<GR, concepts::ReadMap<GR::Arc, float> > >();
   162     
   162     
   163     // Howard
   163     // HowardMmc
   164     checkConcept< MmcClassConcept<GR, int>,
   164     checkConcept< MmcClassConcept<GR, int>,
   165                   Howard<GR, concepts::ReadMap<GR::Arc, int> > >();
   165                   HowardMmc<GR, concepts::ReadMap<GR::Arc, int> > >();
   166     checkConcept< MmcClassConcept<GR, float>,
   166     checkConcept< MmcClassConcept<GR, float>,
   167                   Howard<GR, concepts::ReadMap<GR::Arc, float> > >();
   167                   HowardMmc<GR, concepts::ReadMap<GR::Arc, float> > >();
   168 
   168 
   169     if (IsSameType<Howard<GR, concepts::ReadMap<GR::Arc, int> >::LargeValue,
   169     check((IsSameType<HowardMmc<GR, concepts::ReadMap<GR::Arc, int> >
   170           long_int>::result == 0) check(false, "Wrong LargeValue type");
   170            ::LargeCost, long_int>::result == 1), "Wrong LargeCost type");
   171     if (IsSameType<Howard<GR, concepts::ReadMap<GR::Arc, float> >::LargeValue,
   171     check((IsSameType<HowardMmc<GR, concepts::ReadMap<GR::Arc, float> >
   172           double>::result == 0) check(false, "Wrong LargeValue type");
   172            ::LargeCost, double>::result == 1), "Wrong LargeCost type");
   173   }
   173   }
   174 
   174 
   175   // Run various tests
   175   // Run various tests
   176   {
   176   {
   177     typedef SmartDigraph GR;
   177     typedef SmartDigraph GR;
   192       arcMap("c3", c3).
   192       arcMap("c3", c3).
   193       arcMap("c4", c4).
   193       arcMap("c4", c4).
   194       run();
   194       run();
   195 
   195 
   196     // Karp
   196     // Karp
   197     checkMmcAlg<Karp<GR, IntArcMap> >(gr, l1, c1,  6, 3);
   197     checkMmcAlg<KarpMmc<GR, IntArcMap> >(gr, l1, c1,  6, 3);
   198     checkMmcAlg<Karp<GR, IntArcMap> >(gr, l2, c2,  5, 2);
   198     checkMmcAlg<KarpMmc<GR, IntArcMap> >(gr, l2, c2,  5, 2);
   199     checkMmcAlg<Karp<GR, IntArcMap> >(gr, l3, c3,  0, 1);
   199     checkMmcAlg<KarpMmc<GR, IntArcMap> >(gr, l3, c3,  0, 1);
   200     checkMmcAlg<Karp<GR, IntArcMap> >(gr, l4, c4, -1, 1);
   200     checkMmcAlg<KarpMmc<GR, IntArcMap> >(gr, l4, c4, -1, 1);
   201 
   201 
   202     // HartmannOrlin
   202     // HartmannOrlin
   203     checkMmcAlg<HartmannOrlin<GR, IntArcMap> >(gr, l1, c1,  6, 3);
   203     checkMmcAlg<HartmannOrlinMmc<GR, IntArcMap> >(gr, l1, c1,  6, 3);
   204     checkMmcAlg<HartmannOrlin<GR, IntArcMap> >(gr, l2, c2,  5, 2);
   204     checkMmcAlg<HartmannOrlinMmc<GR, IntArcMap> >(gr, l2, c2,  5, 2);
   205     checkMmcAlg<HartmannOrlin<GR, IntArcMap> >(gr, l3, c3,  0, 1);
   205     checkMmcAlg<HartmannOrlinMmc<GR, IntArcMap> >(gr, l3, c3,  0, 1);
   206     checkMmcAlg<HartmannOrlin<GR, IntArcMap> >(gr, l4, c4, -1, 1);
   206     checkMmcAlg<HartmannOrlinMmc<GR, IntArcMap> >(gr, l4, c4, -1, 1);
   207 
   207 
   208     // Howard
   208     // Howard
   209     checkMmcAlg<Howard<GR, IntArcMap> >(gr, l1, c1,  6, 3);
   209     checkMmcAlg<HowardMmc<GR, IntArcMap> >(gr, l1, c1,  6, 3);
   210     checkMmcAlg<Howard<GR, IntArcMap> >(gr, l2, c2,  5, 2);
   210     checkMmcAlg<HowardMmc<GR, IntArcMap> >(gr, l2, c2,  5, 2);
   211     checkMmcAlg<Howard<GR, IntArcMap> >(gr, l3, c3,  0, 1);
   211     checkMmcAlg<HowardMmc<GR, IntArcMap> >(gr, l3, c3,  0, 1);
   212     checkMmcAlg<Howard<GR, IntArcMap> >(gr, l4, c4, -1, 1);
   212     checkMmcAlg<HowardMmc<GR, IntArcMap> >(gr, l4, c4, -1, 1);
   213   }
   213   }
   214 
   214 
   215   return 0;
   215   return 0;
   216 }
   216 }