main page modules namespaces classes files
Gecode home

search for 

search.hh

Go to the documentation of this file.

/*
 *  Main authors:
 *     Christian Schulte <schulte@gecode.org>
 *     Guido Tack <tack@gecode.org>
 *
 *  Copyright:
 *     Christian Schulte, 2002
 *     Guido Tack, 2004
 *
 *  Last modified:
 *     $Date: 2006-08-04 16:06:38 +0200 (Fri, 04 Aug 2006) $ by $Author: schulte $
 *     $Revision: 3516 $
 *
 *  This file is part of Gecode, the generic constraint
 *  development environment:
 *     http://www.gecode.org
 *
 *  See the file "LICENSE" for information on usage and
 *  redistribution of this file, and for a
 *     DISCLAIMER OF ALL WARRANTIES.
 *
 */

#ifndef __GECODE_SEARCH_HH__
#define __GECODE_SEARCH_HH__

#include <ctime>

#include "gecode/kernel.hh"

/*
 * Support for DLLs under Windows
 *
 */

#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 GCC_HASCLASSVISIBILITY

#define GECODE_SEARCH_EXPORT __attribute__ ((visibility("default")))

#else

#define GECODE_SEARCH_EXPORT

#endif
#endif

#include "gecode/support/dynamic-stack.hh"

namespace Gecode {

  namespace Search {

    namespace Config {
      const unsigned int c_d = 8;
      const unsigned int a_d = 2;
    }

    class Statistics {
    public:
      unsigned long int propagate;
      unsigned long int fail;
      unsigned long int clone;
      unsigned long int commit;
      size_t memory;
      Statistics(void);
    };


    class GECODE_SEARCH_EXPORT Stop {
    public:
      Stop(void);
      virtual bool stop(const Statistics& s) = 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);
    };

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

    class GECODE_SEARCH_EXPORT TimeStop : public Stop {
    protected:
      clock_t s;
      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);
    };


    class EngineCtrl : public Statistics {
    protected:
      Stop* st;
      bool _stopped;
      size_t mem_space;
      size_t mem_cur;
      size_t mem_total;
    public:
      EngineCtrl(Stop* st, size_t sz);
      void start(void);
      bool stop(size_t sz);
      bool stopped(void) const;
      void push(const Space* s, const BranchingDesc* d);
      void constrained(const Space* s1, const Space* s2);
      void adapt(const Space* s);
      void pop(const Space* s, const BranchingDesc* d);
      void lao(const Space* s);
      void current(const Space* s);
      void reset(const Space* s);
    };

    class ReCoNode {
    protected:
      Space*               _space;
      unsigned int         _alt;
      const BranchingDesc* _desc;
    public:
      ReCoNode(Space* s, Space* c);

      Space* space(void) const;
      void space(Space* s);

      const BranchingDesc* desc(void) const;

      unsigned int alt(void) const;
      bool rightmost(void) const;
      void next(void);

      void dispose(void);
    };


    class ReCoStack {
    private:
      Support::DynamicStack<ReCoNode> ds;
      const unsigned int a_d;
    public:
      ReCoStack(unsigned int a_d);
      const BranchingDesc* push(Space* s, Space* c);
      bool next(EngineCtrl& s);
      int lc(Space*& s) const;
      void unwind(int l);
      void commit(Space* s, int i) const;
      template <bool constrained>
      Space* recompute(unsigned int& d, EngineCtrl& s);
      int entries(void) const;
      size_t stacksize(void) const;
      void reset(void);
    };

    class DfsEngine : public EngineCtrl {
    private:
      ReCoStack          rcs;
      Space*             cur;
      const unsigned int c_d;
      unsigned int       d;
    public:
      DfsEngine(unsigned int c_d, unsigned int a_d, Stop* st, size_t sz);
      void init(Space* s);
      void reset(Space* s);
      Space* explore(void);
      size_t stacksize(void) const;
      ~DfsEngine(void);
    };

    class GECODE_SEARCH_EXPORT DFS {
    protected:
      DfsEngine e;
    public:
      DFS(Space* s, unsigned int c_d, unsigned int a_d, Stop* st, size_t sz);
      Space* next(void);
      Statistics statistics(void) const;
      bool stopped(void) const;
    };

  }

  template <class T>
  class DFS : public Search::DFS {
  public:
    DFS(T* s,
        unsigned int c_d=Search::Config::c_d,
        unsigned int a_d=Search::Config::a_d,
        Search::Stop* st=NULL);
    T* next(void);
  };

  template <class T>
  T* dfs(T* s,
         unsigned int c_d=Search::Config::c_d,
         unsigned int a_d=Search::Config::a_d,
         Search::Stop* st=NULL);



  namespace Search {

    class ProbeEngine : public EngineCtrl {
    protected:
      class ProbeNode {
      private:
        Space*               _space;
        const BranchingDesc* _desc;
        unsigned int         _alt;
      public:
        ProbeNode(Space* s, const BranchingDesc* d, unsigned int a);
        Space* space(void) const;
        const BranchingDesc* desc(void) const;
        unsigned int alt(void) const;
        void next(void);
      };
      Support::DynamicStack<ProbeNode> ds;
      Space* cur;
      unsigned int d;
    public:
      ProbeEngine(Stop* st, size_t s);
      void init(Space* s, unsigned int d);
      void reset(Space* s, unsigned int d);
      size_t stacksize(void) const;
      ~ProbeEngine(void);
      Space* explore(void);
    };

    class GECODE_SEARCH_EXPORT LDS {
    protected:
      Space*       root;        
      unsigned int d_cur;       
      unsigned int d_max;       
      bool         no_solution; 
      ProbeEngine  e;           
    public:
      LDS(Space* s, unsigned int d, Stop* st, size_t sz);
      Space* next(void);
      Statistics statistics(void) const;
      bool stopped(void) const;
      ~LDS(void);
    };

  }

  template <class T>
  class LDS : public Search::LDS {
  public:
    LDS(T* s, unsigned int d, Search::Stop* st=NULL);
    T* next(void);
  };

  template <class T>
  T* lds(T* s,unsigned int d, Search::Stop* st=NULL);





  /*
   * Best solution search engines
   *
   */

  namespace Search {

    class BabEngine : public EngineCtrl {
    public:
      enum ExploreStatus {
        ES_SOLUTION,
        ES_CONSTRAIN
      };
    private:
      ReCoStack          rcs;
      Space*             cur;
      int                mark;
      ExploreStatus      es;
      Space*             best;
      const unsigned int c_d;
      unsigned int       d;
    public:
      BabEngine(unsigned int c_d, unsigned int a_d, Stop* st, size_t sz);
      void init(Space* s);
      GECODE_SEARCH_EXPORT
      ExploreStatus explore(Space*& s1, Space*& s2);
      size_t stacksize(void) const;
      ~BabEngine(void);
    };

    class GECODE_SEARCH_EXPORT BAB {
    protected:
      BabEngine e;
    public:
      BAB(Space* s, unsigned int c_d, unsigned int a_d, Stop* st, size_t sz);
      bool stopped(void) const;
      Statistics statistics(void) const;
    };

  }

  template <class T>
  class BAB : public Search::BAB {
  public:
    BAB(T* s,
        unsigned int c_d=Search::Config::c_d,
        unsigned int a_d=Search::Config::a_d,
        Search::Stop* st=NULL);
    T* next(void);
  };

  template <class T>
  T* bab(T* s,
         unsigned int c_d=Search::Config::c_d,
         unsigned int a_d=Search::Config::a_d,
         Search::Stop* st=NULL);



  template <class T>
  class Restart : public DFS<T> {
  protected:
    Space* root;
    Space* best;
  public:
    Restart(T* s,
            unsigned int c_d=Search::Config::c_d,
            unsigned int a_d=Search::Config::a_d,
            Search::Stop* st=NULL);
    ~Restart(void);
    T* next(void);
  };

  template <class T>
  T* restart(T* s,
             unsigned int c_d=Search::Config::c_d,
             unsigned int a_d=Search::Config::a_d,
             Search::Stop* st=NULL);

}

#include "gecode/search/statistics.icc"
#include "gecode/search/stop.icc"
#include "gecode/search/engine-ctrl.icc"

#include "gecode/search/reco-stack.icc"

#include "gecode/search/dfs.icc"
#include "gecode/search/lds.icc"
#include "gecode/search/bab.icc"
#include "gecode/search/restart.icc"

#endif

// STATISTICS: search-any