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: 2008-07-11 10:10:11 +0200 (Fri, 11 Jul 2008) $ by $Author: tack $
 *     $Revision: 7310 $
 *
 *  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 <ctime>

#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

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 Options {
    public:
      unsigned int c_d;
      unsigned int a_d;
      Stop* stop;
      GECODE_SEARCH_EXPORT static const Options def;
      Options(void);
    };

    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);
      void reset(void);
    };

    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);
      template <class DescType>
      const BranchingDesc* nextDesc(EngineCtrl& s, int& alt,
                                    int& closedDescs);
      template <class DescType, bool inclusive>
      void closeBranch(EngineCtrl& s);
      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);
      void reset(void);
      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, const Search::Options& o=Search::Options::def);
    T* next(void);
  };

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


  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;
      bool exhausted;
    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);
      bool done(void) const;
    };

    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,
        const Search::Options& o=Search::Options::def);
    T* next(void);
  };

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





  /*
   * 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, const Search::Options& o=Search::Options::def);
    T* next(void);
  };

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



  template <class T>
  class Restart : public DFS<T> {
  protected:
    Space* root;
    Space* best;
  public:
    Restart(T* s, const Search::Options& o=Search::Options::def);
    ~Restart(void);
    T* next(void);
  };

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

}

#include "gecode/search/statistics.icc"
#include "gecode/search/stop.icc"
#include "gecode/search/options.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