kpeter@810: /* -*- mode: C++; indent-tabs-mode: nil; -*-
kpeter@810:  *
kpeter@810:  * This file is a part of LEMON, a generic C++ optimization library.
kpeter@810:  *
alpar@956:  * Copyright (C) 2003-2010
kpeter@810:  * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
kpeter@810:  * (Egervary Research Group on Combinatorial Optimization, EGRES).
kpeter@810:  *
kpeter@810:  * Permission to use, modify and distribute this software is granted
kpeter@810:  * provided that this copyright notice appears in all copies. For
kpeter@810:  * precise terms see the accompanying LICENSE file.
kpeter@810:  *
kpeter@810:  * This software is provided "AS IS" with no warranty of any kind,
kpeter@810:  * express or implied, and with no claim as to its suitability for any
kpeter@810:  * purpose.
kpeter@810:  *
kpeter@810:  */
kpeter@810: 
kpeter@810: #include <iostream>
kpeter@810: #include <sstream>
kpeter@810: 
kpeter@810: #include <lemon/smart_graph.h>
kpeter@810: #include <lemon/lgf_reader.h>
kpeter@810: #include <lemon/path.h>
kpeter@810: #include <lemon/concepts/digraph.h>
kpeter@810: #include <lemon/concept_check.h>
kpeter@810: 
kpeter@942: #include <lemon/karp_mmc.h>
kpeter@942: #include <lemon/hartmann_orlin_mmc.h>
kpeter@942: #include <lemon/howard_mmc.h>
kpeter@812: 
kpeter@810: #include "test_tools.h"
kpeter@810: 
kpeter@810: using namespace lemon;
kpeter@810: 
kpeter@810: char test_lgf[] =
kpeter@810:   "@nodes\n"
kpeter@810:   "label\n"
kpeter@810:   "1\n"
kpeter@810:   "2\n"
kpeter@810:   "3\n"
kpeter@810:   "4\n"
kpeter@810:   "5\n"
kpeter@810:   "6\n"
kpeter@810:   "7\n"
kpeter@810:   "@arcs\n"
kpeter@810:   "    len1 len2 len3 len4  c1 c2 c3 c4\n"
kpeter@810:   "1 2    1    1    1    1   0  0  0  0\n"
kpeter@810:   "2 4    5    5    5    5   1  0  0  0\n"
kpeter@810:   "2 3    8    8    8    8   0  0  0  0\n"
kpeter@810:   "3 2   -2    0    0    0   1  0  0  0\n"
kpeter@810:   "3 4    4    4    4    4   0  0  0  0\n"
kpeter@810:   "3 7   -4   -4   -4   -4   0  0  0  0\n"
kpeter@810:   "4 1    2    2    2    2   0  0  0  0\n"
kpeter@810:   "4 3    3    3    3    3   1  0  0  0\n"
kpeter@810:   "4 4    3    3    0    0   0  0  1  0\n"
kpeter@810:   "5 2    4    4    4    4   0  0  0  0\n"
kpeter@810:   "5 6    3    3    3    3   0  1  0  0\n"
kpeter@810:   "6 5    2    2    2    2   0  1  0  0\n"
kpeter@810:   "6 4   -1   -1   -1   -1   0  0  0  0\n"
kpeter@810:   "6 7    1    1    1    1   0  0  0  0\n"
kpeter@810:   "7 7    4    4    4   -1   0  0  0  1\n";
kpeter@810: 
alpar@956: 
kpeter@810: // Check the interface of an MMC algorithm
kpeter@942: template <typename GR, typename Cost>
kpeter@810: struct MmcClassConcept
kpeter@810: {
kpeter@810:   template <typename MMC>
kpeter@810:   struct Constraints {
kpeter@810:     void constraints() {
kpeter@810:       const Constraints& me = *this;
kpeter@810: 
kpeter@810:       typedef typename MMC
kpeter@810:         ::template SetPath<ListPath<GR> >
kpeter@942:         ::template SetLargeCost<Cost>
kpeter@810:         ::Create MmcAlg;
kpeter@942:       MmcAlg mmc(me.g, me.cost);
kpeter@810:       const MmcAlg& const_mmc = mmc;
alpar@956: 
kpeter@816:       typename MmcAlg::Tolerance tol = const_mmc.tolerance();
kpeter@816:       mmc.tolerance(tol);
alpar@956: 
kpeter@810:       b = mmc.cycle(p).run();
kpeter@942:       b = mmc.findCycleMean();
kpeter@810:       b = mmc.findCycle();
kpeter@810: 
kpeter@942:       v = const_mmc.cycleCost();
kpeter@942:       i = const_mmc.cycleSize();
kpeter@810:       d = const_mmc.cycleMean();
kpeter@810:       p = const_mmc.cycle();
kpeter@810:     }
kpeter@810: 
kpeter@942:     typedef concepts::ReadMap<typename GR::Arc, Cost> CM;
alpar@956: 
kpeter@810:     GR g;
kpeter@942:     CM cost;
kpeter@810:     ListPath<GR> p;
kpeter@942:     Cost v;
kpeter@810:     int i;
kpeter@810:     double d;
kpeter@810:     bool b;
kpeter@810:   };
kpeter@810: };
kpeter@810: 
kpeter@810: // Perform a test with the given parameters
kpeter@810: template <typename MMC>
kpeter@810: void checkMmcAlg(const SmartDigraph& gr,
kpeter@810:                  const SmartDigraph::ArcMap<int>& lm,
kpeter@810:                  const SmartDigraph::ArcMap<int>& cm,
kpeter@942:                  int cost, int size) {
kpeter@810:   MMC alg(gr, lm);
kpeter@1178:   check(alg.findCycleMean(), "Wrong result");
kpeter@942:   check(alg.cycleMean() == static_cast<double>(cost) / size,
kpeter@810:         "Wrong cycle mean");
kpeter@810:   alg.findCycle();
kpeter@942:   check(alg.cycleCost() == cost && alg.cycleSize() == size,
kpeter@810:         "Wrong path");
kpeter@810:   SmartDigraph::ArcMap<int> cycle(gr, 0);
kpeter@810:   for (typename MMC::Path::ArcIt a(alg.cycle()); a != INVALID; ++a) {
kpeter@810:     ++cycle[a];
kpeter@810:   }
kpeter@810:   for (SmartDigraph::ArcIt a(gr); a != INVALID; ++a) {
kpeter@810:     check(cm[a] == cycle[a], "Wrong path");
kpeter@810:   }
kpeter@810: }
kpeter@810: 
kpeter@810: // Class for comparing types
kpeter@810: template <typename T1, typename T2>
kpeter@810: struct IsSameType {
kpeter@810:   static const int result = 0;
kpeter@810: };
kpeter@810: 
kpeter@810: template <typename T>
kpeter@810: struct IsSameType<T,T> {
kpeter@810:   static const int result = 1;
kpeter@810: };
kpeter@810: 
kpeter@810: 
kpeter@810: int main() {
kpeter@810:   #ifdef LEMON_HAVE_LONG_LONG
kpeter@810:     typedef long long long_int;
kpeter@810:   #else
kpeter@810:     typedef long long_int;
kpeter@810:   #endif
kpeter@810: 
kpeter@810:   // Check the interface
kpeter@810:   {
kpeter@810:     typedef concepts::Digraph GR;
kpeter@812: 
kpeter@942:     // KarpMmc
kpeter@812:     checkConcept< MmcClassConcept<GR, int>,
kpeter@942:                   KarpMmc<GR, concepts::ReadMap<GR::Arc, int> > >();
kpeter@812:     checkConcept< MmcClassConcept<GR, float>,
kpeter@942:                   KarpMmc<GR, concepts::ReadMap<GR::Arc, float> > >();
alpar@956: 
kpeter@942:     // HartmannOrlinMmc
kpeter@813:     checkConcept< MmcClassConcept<GR, int>,
kpeter@942:                   HartmannOrlinMmc<GR, concepts::ReadMap<GR::Arc, int> > >();
kpeter@813:     checkConcept< MmcClassConcept<GR, float>,
kpeter@942:                   HartmannOrlinMmc<GR, concepts::ReadMap<GR::Arc, float> > >();
alpar@956: 
kpeter@942:     // HowardMmc
kpeter@812:     checkConcept< MmcClassConcept<GR, int>,
kpeter@942:                   HowardMmc<GR, concepts::ReadMap<GR::Arc, int> > >();
kpeter@812:     checkConcept< MmcClassConcept<GR, float>,
kpeter@942:                   HowardMmc<GR, concepts::ReadMap<GR::Arc, float> > >();
kpeter@812: 
kpeter@942:     check((IsSameType<HowardMmc<GR, concepts::ReadMap<GR::Arc, int> >
kpeter@942:            ::LargeCost, long_int>::result == 1), "Wrong LargeCost type");
kpeter@942:     check((IsSameType<HowardMmc<GR, concepts::ReadMap<GR::Arc, float> >
kpeter@942:            ::LargeCost, double>::result == 1), "Wrong LargeCost type");
kpeter@810:   }
kpeter@810: 
kpeter@810:   // Run various tests
kpeter@810:   {
kpeter@810:     typedef SmartDigraph GR;
kpeter@810:     DIGRAPH_TYPEDEFS(GR);
alpar@956: 
kpeter@810:     GR gr;
kpeter@810:     IntArcMap l1(gr), l2(gr), l3(gr), l4(gr);
kpeter@810:     IntArcMap c1(gr), c2(gr), c3(gr), c4(gr);
alpar@956: 
kpeter@810:     std::istringstream input(test_lgf);
kpeter@810:     digraphReader(gr, input).
kpeter@810:       arcMap("len1", l1).
kpeter@810:       arcMap("len2", l2).
kpeter@810:       arcMap("len3", l3).
kpeter@810:       arcMap("len4", l4).
kpeter@810:       arcMap("c1", c1).
kpeter@810:       arcMap("c2", c2).
kpeter@810:       arcMap("c3", c3).
kpeter@810:       arcMap("c4", c4).
kpeter@810:       run();
kpeter@810: 
kpeter@812:     // Karp
kpeter@942:     checkMmcAlg<KarpMmc<GR, IntArcMap> >(gr, l1, c1,  6, 3);
kpeter@942:     checkMmcAlg<KarpMmc<GR, IntArcMap> >(gr, l2, c2,  5, 2);
kpeter@942:     checkMmcAlg<KarpMmc<GR, IntArcMap> >(gr, l3, c3,  0, 1);
kpeter@942:     checkMmcAlg<KarpMmc<GR, IntArcMap> >(gr, l4, c4, -1, 1);
kpeter@812: 
kpeter@813:     // HartmannOrlin
kpeter@942:     checkMmcAlg<HartmannOrlinMmc<GR, IntArcMap> >(gr, l1, c1,  6, 3);
kpeter@942:     checkMmcAlg<HartmannOrlinMmc<GR, IntArcMap> >(gr, l2, c2,  5, 2);
kpeter@942:     checkMmcAlg<HartmannOrlinMmc<GR, IntArcMap> >(gr, l3, c3,  0, 1);
kpeter@942:     checkMmcAlg<HartmannOrlinMmc<GR, IntArcMap> >(gr, l4, c4, -1, 1);
kpeter@813: 
kpeter@812:     // Howard
kpeter@942:     checkMmcAlg<HowardMmc<GR, IntArcMap> >(gr, l1, c1,  6, 3);
kpeter@942:     checkMmcAlg<HowardMmc<GR, IntArcMap> >(gr, l2, c2,  5, 2);
kpeter@942:     checkMmcAlg<HowardMmc<GR, IntArcMap> >(gr, l3, c3,  0, 1);
kpeter@942:     checkMmcAlg<HowardMmc<GR, IntArcMap> >(gr, l4, c4, -1, 1);
kpeter@1178:     
kpeter@1178:     // Howard with iteration limit
kpeter@1178:     HowardMmc<GR, IntArcMap> mmc(gr, l1);
kpeter@1178:     check((mmc.findCycleMean(2) == HowardMmc<GR, IntArcMap>::ITERATION_LIMIT),
kpeter@1178:       "Wrong termination cause");
kpeter@1178:     check((mmc.findCycleMean(4) == HowardMmc<GR, IntArcMap>::OPTIMAL),
kpeter@1178:       "Wrong termination cause");
kpeter@810:   }
kpeter@810: 
kpeter@810:   return 0;
kpeter@810: }