search.hh

Go to the documentation of this file.

/* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */
/*
 *  Main authors:
 *     Christian Schulte <schulte@gecode.org>
 *     Guido Tack <tack@gecode.org>
 *
 *  Copyright:
 *     Christian Schulte, 2002
 *     Guido Tack, 2004
 *
 *  Last modified:
 *     $Date: 2015-03-17 11:17:00 +0100 (Tue, 17 Mar 2015) $ by $Author: tack $
 *     $Revision: 14443 $
 *
 *  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.
 *
 */

#ifndef __GECODE_SEARCH_HH__
#define __GECODE_SEARCH_HH__

#include <gecode/kernel.hh>

/*
 * Configure linking
 *
 */
#if !defined(GECODE_STATIC_LIBS) && \
    (defined(__CYGWIN__) || defined(__MINGW32__) || defined(_MSC_VER))

#ifdef GECODE_BUILD_SEARCH
#define GECODE_SEARCH_EXPORT __declspec( dllexport )
#else
#define GECODE_SEARCH_EXPORT __declspec( dllimport )
#endif

#else

#ifdef GECODE_GCC_HAS_CLASS_VISIBILITY
#define GECODE_SEARCH_EXPORT __attribute__ ((visibility("default")))
#else
#define GECODE_SEARCH_EXPORT
#endif

#endif

// Configure auto-linking
#ifndef GECODE_BUILD_SEARCH
#define GECODE_LIBRARY_NAME "Search"
#include <gecode/support/auto-link.hpp>
#endif


namespace Gecode { namespace Search {

  namespace Sequential {}
  
  namespace Parallel {}

  namespace Meta {}

  namespace Config {
    const bool clone = true;
    const double threads = 1.0;
    const unsigned int c_d = 8;
    const unsigned int a_d = 2;
    
    const unsigned int steal_limit = 3;
    const unsigned int initial_delay = 5;

    const unsigned int nogoods_limit = 128;
  }

}}

namespace Gecode { namespace Search {


  class GECODE_VTABLE_EXPORT UninitializedCutoff : public Exception {
  public:
    UninitializedCutoff(const char* l);
  };
}}

#include <gecode/search/exception.hpp>

namespace Gecode { namespace Search {

  class Statistics : public StatusStatistics {
  public:
    unsigned long int fail;
    unsigned long int node;
    unsigned long int depth;
    unsigned long int restart;
    unsigned long int nogood;
    Statistics(void);
    void reset(void);
    Statistics operator +(const Statistics& s);
    Statistics& operator +=(const Statistics& s);
  };

}}

#include <gecode/search/statistics.hpp>

namespace Gecode { namespace Search {

  class GECODE_SEARCH_EXPORT Cutoff {
  public:


    Cutoff(void);
    virtual unsigned long int operator ()(void) const = 0;
    virtual unsigned long int operator ++(void) = 0;
    virtual ~Cutoff(void);



    static void* operator new(size_t s);
    static void  operator delete(void* p);



    static Cutoff*
    constant(unsigned long int scale=1U);
    static Cutoff*
    linear(unsigned long int scale=1U);
    static Cutoff*
    geometric(unsigned long int scale=1U, double base=1.5);
    static Cutoff*
    luby(unsigned long int scale=1U);
    static Cutoff*
    rnd(unsigned int seed, 
        unsigned long int min, unsigned long int max, 
        unsigned long int n);
    static Cutoff*
    append(Cutoff* c1, unsigned long int n, Cutoff* c2);
    static Cutoff*
    merge(Cutoff* c1, Cutoff* c2);
    static Cutoff*
    repeat(Cutoff* c, unsigned long int n);
  };

  class GECODE_SEARCH_EXPORT CutoffConstant : public Cutoff {
  protected:
    unsigned long int c;
  public:
    CutoffConstant(unsigned long int c);
    virtual unsigned long int operator ()(void) const;
    virtual unsigned long int operator ++(void);
  };

  class GECODE_SEARCH_EXPORT CutoffLinear : public Cutoff {
  protected:
    unsigned long int scale;
    unsigned long int n;
  public:
    CutoffLinear(unsigned long int scale);
    virtual unsigned long int operator ()(void) const;
    virtual unsigned long int operator ++(void);
  };

  class GECODE_SEARCH_EXPORT CutoffLuby : public Cutoff {
  protected:
    unsigned long int i;
    unsigned long int scale;
    static const unsigned long int n_start = 63U;
    static unsigned long int start[n_start];
    static unsigned long int log(unsigned long int i);
    static unsigned long int luby(unsigned long int i);
  public:
    CutoffLuby(unsigned long int scale);
    virtual unsigned long int operator ()(void) const;
    virtual unsigned long int operator ++(void);
  };

  class GECODE_SEARCH_EXPORT CutoffGeometric : public Cutoff {
  protected:
    double n;
    double scale;
    double base;
  public:
    CutoffGeometric(unsigned long int scale, double base);
    virtual unsigned long int operator ()(void) const;
    virtual unsigned long int operator ++(void);
  };
  
  class GECODE_SEARCH_EXPORT CutoffRandom : public Cutoff {
  protected:
    Support::RandomGenerator rnd;
    unsigned long int min;
    unsigned long int n;
    unsigned long int step;
    unsigned long int cur;
  public:
    CutoffRandom(unsigned int seed, 
                 unsigned long int min, unsigned long int max, 
                 unsigned long int n);
    virtual unsigned long int operator ()(void) const;
    virtual unsigned long int operator ++(void);
  };
  
  class GECODE_SEARCH_EXPORT CutoffAppend : public Cutoff {
  protected:
    Cutoff* c1;
    Cutoff* c2;
    unsigned long int n;
  public:
    CutoffAppend(Cutoff* c1, unsigned long int n, Cutoff* c2);
    virtual unsigned long int operator ()(void) const;
    virtual unsigned long int operator ++(void);
    virtual ~CutoffAppend(void);
  };

  class GECODE_SEARCH_EXPORT CutoffMerge : public Cutoff {
  protected:
    Cutoff* c1;
    Cutoff* c2;
  public:
    CutoffMerge(Cutoff* c1, Cutoff* c2);
    virtual unsigned long int operator ()(void) const;
    virtual unsigned long int operator ++(void);
    virtual ~CutoffMerge(void);
  };

  class GECODE_SEARCH_EXPORT CutoffRepeat : public Cutoff {
  protected:
    Cutoff* c;
    // Current cutoff
    unsigned int cutoff;
    // Iteration
    unsigned long int i;
    // Number of repetitions
    unsigned long int n;
  public:
    CutoffRepeat(Cutoff* c, unsigned long int n);
    virtual unsigned long int operator ()(void) const;
    virtual unsigned long int operator ++(void);
    virtual ~CutoffRepeat(void);
  };
  
}}

#include <gecode/search/cutoff.hpp>

namespace Gecode { namespace Search {

    class Stop;

    class Options {
    public:
      bool clone;
      double threads;
      unsigned int c_d;
      unsigned int a_d;
      unsigned int nogoods_limit;
      Stop* stop;
      Cutoff* cutoff;
      GECODE_SEARCH_EXPORT static const Options def;
      Options(void);
      GECODE_SEARCH_EXPORT Options
      expand(void) const;
    };

}}

#include <gecode/search/options.hpp>

namespace Gecode { namespace Search {

  class GECODE_SEARCH_EXPORT Stop {
  public:


    Stop(void);
    virtual bool stop(const Statistics& s, const Options& o) = 0;
    virtual ~Stop(void);



    static void* operator new(size_t s);
    static void  operator delete(void* p);



    static Stop* node(unsigned long int l);
    static Stop* fail(unsigned long int l);
    static Stop* time(unsigned long int l);
  };
  
  class GECODE_SEARCH_EXPORT NodeStop : public Stop {
  protected:
    unsigned long int l;
  public:
    NodeStop(unsigned long int l);
    unsigned long int limit(void) const;
    void limit(unsigned long int l);
    virtual bool stop(const Statistics& s, const Options& o);
  };

  class GECODE_SEARCH_EXPORT FailStop : public Stop {
  protected:
    unsigned long int l;
  public:
    FailStop(unsigned long int l);
    unsigned long int limit(void) const;
    void limit(unsigned long int l);
    virtual bool stop(const Statistics& s, const Options& o);
  };
  
  class GECODE_SEARCH_EXPORT TimeStop : public Stop {
  protected:
    Support::Timer t;
    unsigned long int l;
  public:
    TimeStop(unsigned long int l);
    unsigned long int limit(void) const;
    void limit(unsigned long int l);
    void reset(void);
    virtual bool stop(const Statistics& s, const Options& o);
  };

}}

#include <gecode/search/stop.hpp>

namespace Gecode { namespace Search {

  class GECODE_SEARCH_EXPORT Engine {
  public:
    virtual Space* next(void) = 0;
    virtual Statistics statistics(void) const = 0;
    virtual bool stopped(void) const = 0;
    virtual void reset(Space* s);
    virtual NoGoods& nogoods(void);
    virtual ~Engine(void);


    static void* operator new(size_t s);
    static void  operator delete(void* p);
  };

}}

#include <gecode/search/engine.hpp>

namespace Gecode {

  template<template<class> class E, class T>
  class RBS;

}

namespace Gecode { namespace Search {

  template<class T>
  class EngineBase {
    template<template<class>class,class> friend class ::Gecode::RBS;
  protected:
    Engine* e;
    EngineBase(Engine* e = NULL);
  public:
    virtual T* next(void);
    virtual Statistics statistics(void) const;
    virtual bool stopped(void) const;
    virtual NoGoods& nogoods(void);
    virtual ~EngineBase(void);


    static void* operator new(size_t s);
    static void  operator delete(void* p);
  };

}}

#include <gecode/search/engine-base.hpp>

namespace Gecode {


  template<class T>
  class DFS : public Search::EngineBase<T> {
  public:
    DFS(T* s, const Search::Options& o=Search::Options::def);
  };

  template<class T>
  T* dfs(T* s, const Search::Options& o=Search::Options::def);

}

#include <gecode/search/dfs.hpp>

namespace Gecode {

  template<class T>
  class BAB : public Search::EngineBase<T> {
  public:
    BAB(T* s, const Search::Options& o=Search::Options::def);
  };

  template<class T>
  T* bab(T* s, const Search::Options& o=Search::Options::def);

}

#include <gecode/search/bab.hpp>

namespace Gecode {

  template<template<class> class E, class T>
  class RBS : public Search::EngineBase<T> {
      using Search::EngineBase<T>::e;
  public:
    RBS(T* s, const Search::Options& o);
  };

  template<template<class> class E, class T>
  T* rbs(T* s, const Search::Options& o);

}

#include <gecode/search/rbs.hpp>

#endif

// STATISTICS: search-other