test/min_mean_cycle_test.cc
changeset 974 b1744d7bdb47
parent 864 d3ea191c3412
child 1012 21a9f829ab68
equal deleted inserted replaced
5:c757fe254a7c 6:15e9263d61ff
     1 /* -*- mode: C++; indent-tabs-mode: nil; -*-
     1 /* -*- mode: C++; indent-tabs-mode: nil; -*-
     2  *
     2  *
     3  * This file is a part of LEMON, a generic C++ optimization library.
     3  * This file is a part of LEMON, a generic C++ optimization library.
     4  *
     4  *
     5  * Copyright (C) 2003-2009
     5  * Copyright (C) 2003-2010
     6  * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
     6  * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
     7  * (Egervary Research Group on Combinatorial Optimization, EGRES).
     7  * (Egervary Research Group on Combinatorial Optimization, EGRES).
     8  *
     8  *
     9  * Permission to use, modify and distribute this software is granted
     9  * Permission to use, modify and distribute this software is granted
    10  * provided that this copyright notice appears in all copies. For
    10  * provided that this copyright notice appears in all copies. For
    59   "6 5    2    2    2    2   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"
    60   "6 4   -1   -1   -1   -1   0  0  0  0\n"
    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 Cost>
    66 template <typename GR, typename Cost>
    67 struct MmcClassConcept
    67 struct MmcClassConcept
    68 {
    68 {
    69   template <typename MMC>
    69   template <typename MMC>
    75         ::template SetPath<ListPath<GR> >
    75         ::template SetPath<ListPath<GR> >
    76         ::template SetLargeCost<Cost>
    76         ::template SetLargeCost<Cost>
    77         ::Create MmcAlg;
    77         ::Create MmcAlg;
    78       MmcAlg mmc(me.g, me.cost);
    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.findCycleMean();
    85       b = mmc.findCycleMean();
    86       b = mmc.findCycle();
    86       b = mmc.findCycle();
    87 
    87 
    88       v = const_mmc.cycleCost();
    88       v = const_mmc.cycleCost();
    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, Cost> CM;
    94     typedef concepts::ReadMap<typename GR::Arc, Cost> CM;
    95   
    95 
    96     GR g;
    96     GR g;
    97     CM cost;
    97     CM cost;
    98     ListPath<GR> p;
    98     ListPath<GR> p;
    99     Cost v;
    99     Cost v;
   100     int i;
   100     int i;
   151     // KarpMmc
   151     // KarpMmc
   152     checkConcept< MmcClassConcept<GR, int>,
   152     checkConcept< MmcClassConcept<GR, int>,
   153                   KarpMmc<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                   KarpMmc<GR, concepts::ReadMap<GR::Arc, float> > >();
   155                   KarpMmc<GR, concepts::ReadMap<GR::Arc, float> > >();
   156     
   156 
   157     // HartmannOrlinMmc
   157     // HartmannOrlinMmc
   158     checkConcept< MmcClassConcept<GR, int>,
   158     checkConcept< MmcClassConcept<GR, int>,
   159                   HartmannOrlinMmc<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                   HartmannOrlinMmc<GR, concepts::ReadMap<GR::Arc, float> > >();
   161                   HartmannOrlinMmc<GR, concepts::ReadMap<GR::Arc, float> > >();
   162     
   162 
   163     // HowardMmc
   163     // HowardMmc
   164     checkConcept< MmcClassConcept<GR, int>,
   164     checkConcept< MmcClassConcept<GR, int>,
   165                   HowardMmc<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                   HowardMmc<GR, concepts::ReadMap<GR::Arc, float> > >();
   167                   HowardMmc<GR, concepts::ReadMap<GR::Arc, float> > >();
   174 
   174 
   175   // Run various tests
   175   // Run various tests
   176   {
   176   {
   177     typedef SmartDigraph GR;
   177     typedef SmartDigraph GR;
   178     DIGRAPH_TYPEDEFS(GR);
   178     DIGRAPH_TYPEDEFS(GR);
   179     
   179 
   180     GR gr;
   180     GR gr;
   181     IntArcMap l1(gr), l2(gr), l3(gr), l4(gr);
   181     IntArcMap l1(gr), l2(gr), l3(gr), l4(gr);
   182     IntArcMap c1(gr), c2(gr), c3(gr), c4(gr);
   182     IntArcMap c1(gr), c2(gr), c3(gr), c4(gr);
   183     
   183 
   184     std::istringstream input(test_lgf);
   184     std::istringstream input(test_lgf);
   185     digraphReader(gr, input).
   185     digraphReader(gr, input).
   186       arcMap("len1", l1).
   186       arcMap("len1", l1).
   187       arcMap("len2", l2).
   187       arcMap("len2", l2).
   188       arcMap("len3", l3).
   188       arcMap("len3", l3).