/* -*- mode: C++; indent-tabs-mode: nil; -*-

  *

  * This file is a part of LEMON, a generic C++ optimization library.

  *

  * Copyright (C) 2003-2010

  * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport

  * (Egervary Research Group on Combinatorial Optimization, EGRES).

  *

  * Permission to use, modify and distribute this software is granted

  * provided that this copyright notice appears in all copies. For

  * precise terms see the accompanying LICENSE file.

  *

  * This software is provided "AS IS" with no warranty of any kind,

  * express or implied, and with no claim as to its suitability for any

  * purpose.

  *

  */

 #include <iostream>

 #include <sstream>

 #include <lemon/smart_graph.h>

 #include <lemon/lgf_reader.h>

 #include <lemon/path.h>

 #include <lemon/concepts/digraph.h>

 #include <lemon/concept_check.h>

 #include <lemon/karp_mmc.h>

 #include <lemon/hartmann_orlin_mmc.h>

 #include <lemon/howard_mmc.h>

 #include "test_tools.h"

 using namespace lemon;

 char test_lgf[] =

   "@nodes\n"

   "label\n"

   "1\n"

   "2\n"

   "3\n"

   "4\n"

   "5\n"

   "6\n"

   "7\n"

   "@arcs\n"

   "    len1 len2 len3 len4  c1 c2 c3 c4\n"

   "1 2    1    1    1    1   0  0  0  0\n"

   "2 4    5    5    5    5   1  0  0  0\n"

   "2 3    8    8    8    8   0  0  0  0\n"

   "3 2   -2    0    0    0   1  0  0  0\n"

   "3 4    4    4    4    4   0  0  0  0\n"

   "3 7   -4   -4   -4   -4   0  0  0  0\n"

   "4 1    2    2    2    2   0  0  0  0\n"

   "4 3    3    3    3    3   1  0  0  0\n"

   "4 4    3    3    0    0   0  0  1  0\n"

   "5 2    4    4    4    4   0  0  0  0\n"

   "5 6    3    3    3    3   0  1  0  0\n"

   "6 5    2    2    2    2   0  1  0  0\n"

   "6 4   -1   -1   -1   -1   0  0  0  0\n"

   "6 7    1    1    1    1   0  0  0  0\n"

   "7 7    4    4    4   -1   0  0  0  1\n";

 // Check the interface of an MMC algorithm

 template <typename GR, typename Cost>

 struct MmcClassConcept

 {

   template <typename MMC>

   struct Constraints {

     void constraints() {

       const Constraints& me = *this;

       typedef typename MMC

         ::template SetPath<ListPath<GR> >

         ::template SetLargeCost<Cost>

         ::Create MmcAlg;

       MmcAlg mmc(me.g, me.cost);

       const MmcAlg& const_mmc = mmc;

       typename MmcAlg::Tolerance tol = const_mmc.tolerance();

       mmc.tolerance(tol);

       b = mmc.cycle(p).run();

       b = mmc.findCycleMean();

       b = mmc.findCycle();

       v = const_mmc.cycleCost();

       i = const_mmc.cycleSize();

       d = const_mmc.cycleMean();

       p = const_mmc.cycle();

     }

     typedef concepts::ReadMap<typename GR::Arc, Cost> CM;

     GR g;

     CM cost;

     ListPath<GR> p;

     Cost v;

     int i;

     double d;

     bool b;

   };

 };

 // Perform a test with the given parameters

 template <typename MMC>

 void checkMmcAlg(const SmartDigraph& gr,

                  const SmartDigraph::ArcMap<int>& lm,

                  const SmartDigraph::ArcMap<int>& cm,

                  int cost, int size) {

   MMC alg(gr, lm);

   check(alg.findCycleMean(), "Wrong result");

   check(alg.cycleMean() == static_cast<double>(cost) / size,

         "Wrong cycle mean");

   alg.findCycle();

   check(alg.cycleCost() == cost && alg.cycleSize() == size,

         "Wrong path");

   SmartDigraph::ArcMap<int> cycle(gr, 0);

   for (typename MMC::Path::ArcIt a(alg.cycle()); a != INVALID; ++a) {

     ++cycle[a];

   }

   for (SmartDigraph::ArcIt a(gr); a != INVALID; ++a) {

     check(cm[a] == cycle[a], "Wrong path");

   }

 }

 // Class for comparing types

 template <typename T1, typename T2>

 struct IsSameType {

   static const int result = 0;

 };

 template <typename T>

 struct IsSameType<T,T> {

   static const int result = 1;

 };

 int main() {

   #ifdef LEMON_HAVE_LONG_LONG

     typedef long long long_int;

   #else

     typedef long long_int;

   #endif

   // Check the interface

   {

     typedef concepts::Digraph GR;

     // KarpMmc

     checkConcept< MmcClassConcept<GR, int>,

                   KarpMmc<GR, concepts::ReadMap<GR::Arc, int> > >();

     checkConcept< MmcClassConcept<GR, float>,

                   KarpMmc<GR, concepts::ReadMap<GR::Arc, float> > >();

     // HartmannOrlinMmc

     checkConcept< MmcClassConcept<GR, int>,

                   HartmannOrlinMmc<GR, concepts::ReadMap<GR::Arc, int> > >();

     checkConcept< MmcClassConcept<GR, float>,

                   HartmannOrlinMmc<GR, concepts::ReadMap<GR::Arc, float> > >();

     // HowardMmc

     checkConcept< MmcClassConcept<GR, int>,

                   HowardMmc<GR, concepts::ReadMap<GR::Arc, int> > >();

     checkConcept< MmcClassConcept<GR, float>,

                   HowardMmc<GR, concepts::ReadMap<GR::Arc, float> > >();

     check((IsSameType<HowardMmc<GR, concepts::ReadMap<GR::Arc, int> >

            ::LargeCost, long_int>::result == 1), "Wrong LargeCost type");

     check((IsSameType<HowardMmc<GR, concepts::ReadMap<GR::Arc, float> >

            ::LargeCost, double>::result == 1), "Wrong LargeCost type");

   }

   // Run various tests

   {

     typedef SmartDigraph GR;

     DIGRAPH_TYPEDEFS(GR);

     GR gr;

     IntArcMap l1(gr), l2(gr), l3(gr), l4(gr);

     IntArcMap c1(gr), c2(gr), c3(gr), c4(gr);

     std::istringstream input(test_lgf);

     digraphReader(gr, input).

       arcMap("len1", l1).

       arcMap("len2", l2).

       arcMap("len3", l3).

       arcMap("len4", l4).

       arcMap("c1", c1).

       arcMap("c2", c2).

       arcMap("c3", c3).

       arcMap("c4", c4).

       run();

     // Karp

     checkMmcAlg<KarpMmc<GR, IntArcMap> >(gr, l1, c1,  6, 3);

     checkMmcAlg<KarpMmc<GR, IntArcMap> >(gr, l2, c2,  5, 2);

     checkMmcAlg<KarpMmc<GR, IntArcMap> >(gr, l3, c3,  0, 1);

     checkMmcAlg<KarpMmc<GR, IntArcMap> >(gr, l4, c4, -1, 1);

     // HartmannOrlin

     checkMmcAlg<HartmannOrlinMmc<GR, IntArcMap> >(gr, l1, c1,  6, 3);

     checkMmcAlg<HartmannOrlinMmc<GR, IntArcMap> >(gr, l2, c2,  5, 2);

     checkMmcAlg<HartmannOrlinMmc<GR, IntArcMap> >(gr, l3, c3,  0, 1);

     checkMmcAlg<HartmannOrlinMmc<GR, IntArcMap> >(gr, l4, c4, -1, 1);

     // Howard

     checkMmcAlg<HowardMmc<GR, IntArcMap> >(gr, l1, c1,  6, 3);

     checkMmcAlg<HowardMmc<GR, IntArcMap> >(gr, l2, c2,  5, 2);

     checkMmcAlg<HowardMmc<GR, IntArcMap> >(gr, l3, c3,  0, 1);

     checkMmcAlg<HowardMmc<GR, IntArcMap> >(gr, l4, c4, -1, 1);

     // Howard with iteration limit

     HowardMmc<GR, IntArcMap> mmc(gr, l1);

     check((mmc.findCycleMean(2) == HowardMmc<GR, IntArcMap>::ITERATION_LIMIT),

       "Wrong termination cause");

     check((mmc.findCycleMean(4) == HowardMmc<GR, IntArcMap>::OPTIMAL),

       "Wrong termination cause");

   }

   return 0;

 }