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