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: 2009-05-18 10:33:43 +0200 (Mon, 18 May 2009) $ by $Author: schulte $
 *     $Revision: 9136 $
 *
 *  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>
#include <gecode/support/timer.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 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 d = 5;

      const unsigned int steal_limit = 3;
      const unsigned int initial_delay = 5;
    }

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

    class Stop;

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

    class GECODE_SEARCH_EXPORT Stop {
    public:
      Stop(void);
      virtual bool stop(const Statistics& s, const Options& o) = 0;
      virtual ~Stop(void);
    };

    class GECODE_SEARCH_EXPORT MemoryStop : public Stop {
    protected:
      size_t l;
    public:
      MemoryStop(size_t l);
      size_t limit(void) const;
      void limit(size_t l);
      virtual bool stop(const Statistics& s, const Options& o);
    };

    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);
    };


    class Engine {
    public:
      virtual Space* next(void) = 0;
      virtual Search::Statistics statistics(void) const = 0;
      virtual bool stopped(void) const = 0;
      virtual ~Engine(void) {}
    };

    namespace Sequential {}

    namespace Parallel {}

  }

}

#include <gecode/search/statistics.hpp>
#include <gecode/search/stop.hpp>
#include <gecode/search/options.hpp>

namespace Gecode {

  template <class T>
  class DFS {
  private:
    Search::Engine* e;
  public:
    DFS(T* s, const Search::Options& o=Search::Options::def);
    T* next(void);
    Search::Statistics statistics(void) const;
    bool stopped(void) const;
    ~DFS(void);
  };

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



  template <class T>
  class BAB {
  private:
    Search::Engine* e;
  public:
    BAB(T* s, const Search::Options& o=Search::Options::def);
    T* next(void);
    Search::Statistics statistics(void) const;
    bool stopped(void) const;
    ~BAB(void);
  };

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



  template <class T>
  class Restart {
  private:
    Search::Engine* e;
  public:
    Restart(T* s, const Search::Options& o=Search::Options::def);
    T* next(void);
    Search::Statistics statistics(void) const;
    bool stopped(void) const;
    ~Restart(void);
  };

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



  template <class T>
  class LDS {
  private:
    Search::Engine* e;
  public:
    LDS(T* s, const Search::Options& o=Search::Options::def);
    T* next(void);
    Search::Statistics statistics(void) const;
    bool stopped(void) const;
    ~LDS(void);
  };

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

}

#include <gecode/search/dfs.hpp>
#include <gecode/search/bab.hpp>
#include <gecode/search/restart.hpp>
#include <gecode/search/lds.hpp>

#endif

// STATISTICS: search-other