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:  *
kpeter@810:  * Copyright (C) 2003-2009
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@812: #include <lemon/karp.h>
kpeter@813: #include <lemon/hartmann_orlin.h>
kpeter@812: #include <lemon/howard.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: 
kpeter@810:                         
kpeter@810: // Check the interface of an MMC algorithm
kpeter@810: template <typename GR, typename Value>
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@810:         ::template SetLargeValue<Value>
kpeter@810:         ::Create MmcAlg;
kpeter@810:       MmcAlg mmc(me.g, me.length);
kpeter@810:       const MmcAlg& const_mmc = mmc;
kpeter@810:       
kpeter@816:       typename MmcAlg::Tolerance tol = const_mmc.tolerance();
kpeter@816:       mmc.tolerance(tol);
kpeter@816:       
kpeter@810:       b = mmc.cycle(p).run();
kpeter@810:       b = mmc.findMinMean();
kpeter@810:       b = mmc.findCycle();
kpeter@810: 
kpeter@810:       v = const_mmc.cycleLength();
kpeter@810:       i = const_mmc.cycleArcNum();
kpeter@810:       d = const_mmc.cycleMean();
kpeter@810:       p = const_mmc.cycle();
kpeter@810:     }
kpeter@810: 
kpeter@810:     typedef concepts::ReadMap<typename GR::Arc, Value> LM;
kpeter@810:   
kpeter@810:     GR g;
kpeter@810:     LM length;
kpeter@810:     ListPath<GR> p;
kpeter@810:     Value 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@810:                  int length, int size) {
kpeter@810:   MMC alg(gr, lm);
kpeter@810:   alg.findMinMean();
kpeter@810:   check(alg.cycleMean() == static_cast<double>(length) / size,
kpeter@810:         "Wrong cycle mean");
kpeter@810:   alg.findCycle();
kpeter@810:   check(alg.cycleLength() == length && alg.cycleArcNum() == 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@812:     // Karp
kpeter@812:     checkConcept< MmcClassConcept<GR, int>,
kpeter@812:                   Karp<GR, concepts::ReadMap<GR::Arc, int> > >();
kpeter@812:     checkConcept< MmcClassConcept<GR, float>,
kpeter@812:                   Karp<GR, concepts::ReadMap<GR::Arc, float> > >();
kpeter@810:     
kpeter@813:     // HartmannOrlin
kpeter@813:     checkConcept< MmcClassConcept<GR, int>,
kpeter@813:                   HartmannOrlin<GR, concepts::ReadMap<GR::Arc, int> > >();
kpeter@813:     checkConcept< MmcClassConcept<GR, float>,
kpeter@813:                   HartmannOrlin<GR, concepts::ReadMap<GR::Arc, float> > >();
kpeter@813:     
kpeter@812:     // Howard
kpeter@812:     checkConcept< MmcClassConcept<GR, int>,
kpeter@812:                   Howard<GR, concepts::ReadMap<GR::Arc, int> > >();
kpeter@812:     checkConcept< MmcClassConcept<GR, float>,
kpeter@812:                   Howard<GR, concepts::ReadMap<GR::Arc, float> > >();
kpeter@812: 
kpeter@812:     if (IsSameType<Howard<GR, concepts::ReadMap<GR::Arc, int> >::LargeValue,
kpeter@812:           long_int>::result == 0) check(false, "Wrong LargeValue type");
kpeter@812:     if (IsSameType<Howard<GR, concepts::ReadMap<GR::Arc, float> >::LargeValue,
kpeter@812:           double>::result == 0) check(false, "Wrong LargeValue type");
kpeter@810:   }
kpeter@810: 
kpeter@810:   // Run various tests
kpeter@810:   {
kpeter@810:     typedef SmartDigraph GR;
kpeter@810:     DIGRAPH_TYPEDEFS(GR);
kpeter@810:     
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);
kpeter@810:     
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@812:     checkMmcAlg<Karp<GR, IntArcMap> >(gr, l1, c1,  6, 3);
kpeter@812:     checkMmcAlg<Karp<GR, IntArcMap> >(gr, l2, c2,  5, 2);
kpeter@812:     checkMmcAlg<Karp<GR, IntArcMap> >(gr, l3, c3,  0, 1);
kpeter@812:     checkMmcAlg<Karp<GR, IntArcMap> >(gr, l4, c4, -1, 1);
kpeter@812: 
kpeter@813:     // HartmannOrlin
kpeter@813:     checkMmcAlg<HartmannOrlin<GR, IntArcMap> >(gr, l1, c1,  6, 3);
kpeter@813:     checkMmcAlg<HartmannOrlin<GR, IntArcMap> >(gr, l2, c2,  5, 2);
kpeter@813:     checkMmcAlg<HartmannOrlin<GR, IntArcMap> >(gr, l3, c3,  0, 1);
kpeter@813:     checkMmcAlg<HartmannOrlin<GR, IntArcMap> >(gr, l4, c4, -1, 1);
kpeter@813: 
kpeter@812:     // Howard
kpeter@811:     checkMmcAlg<Howard<GR, IntArcMap> >(gr, l1, c1,  6, 3);
kpeter@811:     checkMmcAlg<Howard<GR, IntArcMap> >(gr, l2, c2,  5, 2);
kpeter@811:     checkMmcAlg<Howard<GR, IntArcMap> >(gr, l3, c3,  0, 1);
kpeter@811:     checkMmcAlg<Howard<GR, IntArcMap> >(gr, l4, c4, -1, 1);
kpeter@810:   }
kpeter@810: 
kpeter@810:   return 0;
kpeter@810: }