branch.cpp

Go to the documentation of this file.

/* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */
/*
 *  Main authors:
 *     Mikael Lagerkvist <lagerkvist@gecode.org>
 *
 *  Copyright:
 *     Mikael Lagerkvist, 2005
 *
 *  Last modified:
 *     $Date: 2009-05-14 00:24:31 +0200 (Thu, 14 May 2009) $ by $Author: tack $
 *     $Revision: 9095 $
 *
 *  This file is part of Gecode, the generic constraint
 *  development environment:
 *     http://www.gecode.org
 *
 *  Permission is hereby granted, free of charge, to any person obtaining
 *  a copy of this software and associated documentation files (the
 *  "Software"), to deal in the Software without restriction, including
 *  without limitation the rights to use, copy, modify, merge, publish,
 *  distribute, sublicense, and/or sell copies of the Software, and to
 *  permit persons to whom the Software is furnished to do so, subject to
 *  the following conditions:
 *
 *  The above copyright notice and this permission notice shall be
 *  included in all copies or substantial portions of the Software.
 *
 *  THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
 *  EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
 *  MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
 *  NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
 *  LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
 *  OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
 *  WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
 *
 */

#include "test/branch.hh"

#include <algorithm>
#include <map>
#include <vector>
#include <iostream>

#include <gecode/kernel.hh>
#include <gecode/int.hh>
#ifdef GECODE_HAS_SET_VARS
#include <gecode/set.hh>
#endif

#include <gecode/search.hh>

namespace Test { namespace Branch {

  class IntTestSpace : public Gecode::Space {
  public:
    Gecode::IntVarArray x;
    Gecode::IntVarBranch vara, varb;
    Gecode::IntValBranch val;
    IntTestSpace(int n, Gecode::IntSet& d)
      : x(*this, n, d), 
        vara(Gecode::INT_VAR_NONE), varb(Gecode::INT_VAR_NONE),
        val(Gecode::INT_VAL_MIN) {}
    IntTestSpace(bool share, IntTestSpace& s)
      : Gecode::Space(share,s), vara(s.vara), varb(s.varb), val(s.val) {
      x.update(*this, share, s.x);
    }
    virtual Gecode::Space* copy(bool share) {
      return new IntTestSpace(share,*this);
    }
    static void branch(Gecode::Space& _home) {
      IntTestSpace& home =
        static_cast<IntTestSpace&>(_home);
      Gecode::branch(home, home.x, 
                     Gecode::tiebreak(home.vara,home.varb), 
                     home.val);
    }
  };

  class BoolTestSpace : public Gecode::Space {
  public:
    Gecode::BoolVarArray x;
    BoolTestSpace(int n)
      : x(*this, n, 0, 1) {}
    BoolTestSpace(bool share, BoolTestSpace& s)
      : Gecode::Space(share,s) {
      x.update(*this, share, s.x);
    }
    virtual Gecode::Space* copy(bool share) {
      return new BoolTestSpace(share,*this);
    }
  };

#ifdef GECODE_HAS_SET_VARS
  class SetTestSpace : public Gecode::Space {
  public:
    Gecode::SetVarArray x;
    SetTestSpace(int n, Gecode::IntSet& d)
      : x(*this, n, Gecode::IntSet::empty, d) {}
    SetTestSpace(bool share, SetTestSpace& s)
      : Gecode::Space(share,s) {
      x.update(*this, share, s.x);
    }
    virtual Gecode::Space* copy(bool share) {
      return new SetTestSpace(share,*this);
    }
  };
#endif


  const Gecode::IntVarBranch int_var_branch[] = {
    Gecode::INT_VAR_NONE,
    Gecode::INT_VAR_RND,
    Gecode::INT_VAR_DEGREE_MIN,
    Gecode::INT_VAR_DEGREE_MAX,
    Gecode::INT_VAR_MIN_MIN,
    Gecode::INT_VAR_MIN_MAX,
    Gecode::INT_VAR_MAX_MIN,
    Gecode::INT_VAR_MAX_MAX,
    Gecode::INT_VAR_SIZE_MIN,
    Gecode::INT_VAR_SIZE_MAX,
    Gecode::INT_VAR_SIZE_DEGREE_MIN,
    Gecode::INT_VAR_SIZE_DEGREE_MAX,
    Gecode::INT_VAR_REGRET_MIN_MIN,
    Gecode::INT_VAR_REGRET_MIN_MAX,
    Gecode::INT_VAR_REGRET_MAX_MIN,
    Gecode::INT_VAR_REGRET_MAX_MAX
  };
  const int n_int_var_branch =
    sizeof(int_var_branch)/sizeof(Gecode::IntVarBranch);
  const char* int_var_branch_name[] = {
    "INT_VAR_NONE",
    "INT_VAR_RND",
    "INT_VAR_DEGREE_MIN",
    "INT_VAR_DEGREE_MAX",
    "INT_VAR_MIN_MIN",
    "INT_VAR_MIN_MAX",
    "INT_VAR_MAX_MIN",
    "INT_VAR_MAX_MAX",
    "INT_VAR_SIZE_MIN",
    "INT_VAR_SIZE_MAX",
    "INT_VAR_SIZE_DEGREE_MIN",
    "INT_VAR_SIZE_DEGREE_MAX",
    "INT_VAR_REGRET_MIN_MIN",
    "INT_VAR_REGRET_MIN_MAX",
    "INT_VAR_REGRET_MAX_MIN",
    "INT_VAR_REGRET_MAX_MAX"
  };
  const Gecode::IntValBranch int_val_branch[] = {
    Gecode::INT_VAL_MIN,
    Gecode::INT_VAL_MED,
    Gecode::INT_VAL_MAX,
    Gecode::INT_VAL_RND,
    Gecode::INT_VAL_SPLIT_MIN,
    Gecode::INT_VAL_SPLIT_MAX,
    Gecode::INT_VALUES_MIN,
    Gecode::INT_VALUES_MAX
  };
  const int n_int_val_branch =
    sizeof(int_val_branch)/sizeof(Gecode::IntValBranch);
  const char* int_val_branch_name[] = {
    "INT_VAL_MIN",
    "INT_VAL_MED",
    "INT_VAL_MAX",
    "INT_VAL_RND",
    "INT_VAL_SPLIT_MIN",
    "INT_VAL_SPLIT_MAX",
    "INT_VALUES_MIN",
    "INT_VALUES_MAX"
  };

#ifdef GECODE_HAS_SET_VARS


  const Gecode::SetVarBranch set_var_branch[] = {
    Gecode::SET_VAR_NONE,
    Gecode::SET_VAR_RND,
    Gecode::SET_VAR_DEGREE_MIN,
    Gecode::SET_VAR_DEGREE_MAX,
    Gecode::SET_VAR_MIN_MIN,
    Gecode::SET_VAR_MIN_MAX,
    Gecode::SET_VAR_MAX_MIN,
    Gecode::SET_VAR_MAX_MAX,
    Gecode::SET_VAR_SIZE_MIN,
    Gecode::SET_VAR_SIZE_MAX,
    Gecode::SET_VAR_SIZE_DEGREE_MIN,
    Gecode::SET_VAR_SIZE_DEGREE_MAX
  };
  const int n_set_var_branch =
    sizeof(set_var_branch)/sizeof(Gecode::SetVarBranch);
  const char* set_var_branch_name[] = {
    "SET_VAR_NONE",
    "SET_VAR_RND",
    "SET_VAR_DEGREE_MIN",
    "SET_VAR_DEGREE_MAX",
    "SET_VAR_MIN_MIN",
    "SET_VAR_MIN_MAX",
    "SET_VAR_MAX_MIN",
    "SET_VAR_MAX_MAX",
    "SET_VAR_SIZE_MIN",
    "SET_VAR_SIZE_MAX",
    "SET_VAR_SIZE_DEGREE_MIN",
    "SET_VAR_SIZE_DEGREE_MAX"
  };
  const Gecode::SetValBranch set_val_branch[] = {
    Gecode::SET_VAL_MIN_INC,
    Gecode::SET_VAL_MIN_EXC,
    Gecode::SET_VAL_MED_INC,
    Gecode::SET_VAL_MED_EXC,
    Gecode::SET_VAL_MAX_INC,
    Gecode::SET_VAL_MAX_EXC,
    Gecode::SET_VAL_RND_INC,
    Gecode::SET_VAL_RND_EXC
  };
  const int n_set_val_branch =
    sizeof(set_val_branch)/sizeof(Gecode::SetValBranch);
  const char* set_val_branch_name[] = {
    "SET_VAL_MIN_INC",
    "SET_VAL_MIN_EXC",
    "SET_VAL_MED_INC",
    "SET_VAL_MED_EXC",
    "SET_VAL_MAX_INC",
    "SET_VAL_MAX_EXC",
    "SET_VAL_RND_INC",
    "SET_VAL_RND_EXC"
  };
#endif

  class RunInfo {
  public:
    std::string var, val;
    unsigned int a_d, c_d;
    RunInfo(const std::string& vara, const std::string& varb,
            const std::string& valname,
            const Gecode::Search::Options& o)
      : var(vara + "::" + varb), val(valname), a_d(o.a_d), c_d(o.c_d) {}
    void print(std::ostream& o) const {
      o << "(" << var << ", " << val << ", " << a_d << ", " << c_d << ")";
    }
  };

}}

std::ostream&
operator<<(std::ostream& os, const Test::Branch::RunInfo& ri) {
  ri.print(os);
  return os;
}


namespace Test { namespace Branch {

  template <class TestSpace>
  int solutions(TestSpace* c, Gecode::Search::Options& o) {
    o.a_d = Base::rand(10);
    o.c_d = Base::rand(10);
    Gecode::DFS<TestSpace> e_s(c, o);
    delete c;

    // Find number of solutions
    int s = 0;
    do {
      Gecode::Space* ex = e_s.next();
      if (ex == NULL) break;
      delete ex;
      ++s;
    } while (true);
    return s;
  }

  IntTest::IntTest(const std::string& s, int a, const Gecode::IntSet& d)
    : Base("Int::Branch::"+s), arity(a), dom(d) {
  }

  bool
  IntTest::run(void) {
    using std::map;
    using std::vector;
    using std::string;
    using std::ostream;
    using namespace Gecode;

    // Results of tests run
    map<int, vector<RunInfo> > results;
    // Set up root space
    IntTestSpace* root = new IntTestSpace(arity,dom);
    post(*root, root->x);
    results.clear();

    for (int vara = n_int_var_branch; vara--; ) {
      for (int varb = n_int_var_branch; varb--; ) {
        for (int val = n_int_val_branch; val--; ) {
          IntTestSpace* c = static_cast<IntTestSpace*>(root->clone(false));
          c->vara = int_var_branch[vara];
          c->varb = int_var_branch[varb];
          c->val  = int_val_branch[val];
          branch(*c, &IntTestSpace::branch);
          Gecode::Search::Options o;
          results[solutions(c,o)].push_back
            (RunInfo(int_var_branch_name[vara],
                     int_var_branch_name[varb],
                     int_val_branch_name[val],
                     o));
        }
      }
    }
    if (results.size() > 1)
      goto failed;
    delete root;
    return true;
  failed:
    std::cout   << "FAILURE" << std::endl;
    for (map<int, vector<RunInfo> >::iterator it = results.begin();
         it != results.end(); ++it) {
      std::cout << "Number of solutions: " << it->first << std::endl;
      for (unsigned int i = 0; i < it->second.size(); ++i)
        std::cout << it->second[i] << " ";
      std::cout << std::endl;
    }

    delete root;
    return results.size() == 1;
  }

  BoolTest::BoolTest(const std::string& s, int a)
    : Base("Bool::Branch::"+s), arity(a) {
  }

  bool
  BoolTest::run(void) {
    using std::map;
    using std::vector;
    using std::string;
    using std::ostream;
    using namespace Gecode;

    // Results of tests run
    map<int, vector<RunInfo> > results;
    // Set up root space
    BoolTestSpace* root = new BoolTestSpace(arity);
    post(*root, root->x);
    results.clear();

    for (int vara = n_int_var_branch; vara--; ) {
      for (int varb = n_int_var_branch; varb--; ) {
        for (int val = n_int_val_branch; val--; ) {
          BoolTestSpace* c = static_cast<BoolTestSpace*>(root->clone(false));
          branch(*c, c->x,
                 tiebreak(int_var_branch[vara], int_var_branch[varb]),
                 int_val_branch[val]);
          Gecode::Search::Options o;
          results[solutions(c,o)].push_back
            (RunInfo(int_var_branch_name[vara],
                     int_var_branch_name[varb],
                     int_val_branch_name[val],
                     o));
        }
      }
    }
    if (results.size() > 1)
      goto failed;
    delete root;
    return true;
  failed:
    std::cout   << "FAILURE" << std::endl;
    for (map<int, vector<RunInfo> >::iterator it = results.begin();
         it != results.end(); ++it) {
      std::cout << "Number of solutions: " << it->first << std::endl;
      for (unsigned int i = 0; i < it->second.size(); ++i)
        std::cout << it->second[i] << " ";
      std::cout << std::endl;
    }

    delete root;
    return results.size() == 1;
  }

#ifdef GECODE_HAS_SET_VARS
  SetTest::SetTest(const std::string& s, int a, const Gecode::IntSet& d)
    : Base("Set::Branch::"+s), arity(a), dom(d) {
  }

  bool
  SetTest::run(void) {
    using std::map;
    using std::vector;
    using std::string;
    using std::ostream;
    using namespace Gecode;

    // Results of tests run
    map<int, vector<RunInfo> > results;
    // Set up root space
    SetTestSpace* root = new SetTestSpace(arity,dom);
    post(*root, root->x);
    root->status();
    results.clear();

    for (int vara = n_set_var_branch; vara--; ) {
      for (int varb = n_set_var_branch; varb--; ) {
        for (int val = n_set_val_branch; val--; ) {
          SetTestSpace* c = static_cast<SetTestSpace*>(root->clone(false));
          branch(*c, c->x,
                 tiebreak(set_var_branch[vara], set_var_branch[varb]),
                 set_val_branch[val]);
          Gecode::Search::Options o;
          results[solutions(c,o)].push_back
            (RunInfo(set_var_branch_name[vara],
                     set_var_branch_name[varb],
                     set_val_branch_name[val],
                     o));
        }
      }
    }
    if (results.size() > 1)
      goto failed;
    delete root;
    return true;
  failed:
    std::cout   << "FAILURE" << std::endl;
    for (map<int, vector<RunInfo> >::iterator it = results.begin();
         it != results.end(); ++it) {
      std::cout << "Number of solutions: " << it->first << std::endl;
      for (unsigned int i = 0; i < it->second.size(); ++i)
        std::cout << it->second[i] << " ";
      std::cout << std::endl;
    }

    delete root;
    return results.size() == 1;
  }
#endif

}}

// STATISTICS: test-branch