RhodeCode

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

 *

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

 *

 * Copyright (C) 2003-2009

 * 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/min_mean_cycle.h>

#include <lemon/path.h>

#include <lemon/concepts/digraph.h>

#include <lemon/concept_check.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 Value>

struct MmcClassConcept

{

  template <typename MMC>

  struct Constraints {

    void constraints() {

      const Constraints& me = *this;

      typedef typename MMC

        ::template SetPath<ListPath<GR> >

        ::template SetLargeValue<Value>

        ::Create MmcAlg;

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

      const MmcAlg& const_mmc = mmc;

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

      b = mmc.findMinMean();

      b = mmc.findCycle();

      v = const_mmc.cycleLength();

      i = const_mmc.cycleArcNum();

      d = const_mmc.cycleMean();

      p = const_mmc.cycle();

    }

    typedef concepts::ReadMap<typename GR::Arc, Value> LM;

    GR g;

    LM length;

    ListPath<GR> p;

    Value 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 length, int size) {

  MMC alg(gr, lm);

  alg.findMinMean();

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

        "Wrong cycle mean");

  alg.findCycle();

  check(alg.cycleLength() == length && alg.cycleArcNum() == 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;

    typedef MinMeanCycle<GR, concepts::ReadMap<GR::Arc, int> > IntMmcAlg;

    typedef MinMeanCycle<GR, concepts::ReadMap<GR::Arc, float> > FloatMmcAlg;

    checkConcept<MmcClassConcept<GR, int>, IntMmcAlg>();

    checkConcept<MmcClassConcept<GR, float>, FloatMmcAlg>();

    if (IsSameType<IntMmcAlg::LargeValue, long_int>::result == 0)

      check(false, "Wrong LargeValue type");

    if (IsSameType<FloatMmcAlg::LargeValue, double>::result == 0)

      check(false, "Wrong LargeValue 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();

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

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

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

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

  }

  return 0;

}

#include <limits>

  min_mean_cycle_test

	test/min_mean_cycle_test \

test_min_mean_cycle_test_SOURCES = test/min_mean_cycle_test.cc

#define check(rc, msg)                                                  \

  {                                                                     \

    if(!(rc)) {                                                         \

      std::cerr << __FILE__ ":" << __LINE__ << ": error: "              \

                << msg << std::endl;                                    \

      abort();                                                          \

    } else { }                                                          \

  }                                                                     \