source: lemon-main/test/min_mean_cycle_test.cc @ 1059:08f2dc76e82e

/* -*- 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;
}