Generated on Thu Jul 6 07:06:49 2006 for Gecode by doxygen 1.4.7

dfs.icc

Go to the documentation of this file.
00001 /*
00002  *  Main authors:
00003  *     Christian Schulte <schulte@gecode.org>
00004  *
00005  *  Copyright:
00006  *     Christian Schulte, 2003
00007  *
00008  *  Last modified:
00009  *     $Date: 2006-05-17 16:00:08 +0200 (Wed, 17 May 2006) $ by $Author: schulte $
00010  *     $Revision: 3226 $
00011  *
00012  *  This file is part of Gecode, the generic constraint
00013  *  development environment:
00014  *     http://www.gecode.org
00015  *
00016  *  See the file "LICENSE" for information on usage and
00017  *  redistribution of this file, and for a
00018  *     DISCLAIMER OF ALL WARRANTIES.
00019  *
00020  */
00021 
00022 namespace Gecode {
00023 
00024   namespace Search {
00025 
00026     /*
00027      * DFS engine
00028      *
00029      */
00030     forceinline
00031     DfsEngine::DfsEngine(unsigned int c_d0, unsigned int a_d0,
00032                          Stop* st, size_t sz)
00033       : EngineCtrl(st,sz), ds(a_d0), cur(NULL), c_d(c_d0), d(0) {}
00034 
00035   
00036     forceinline void
00037     DfsEngine::init(Space* s) {
00038       cur = s;
00039     }
00040 
00041     forceinline void
00042     DfsEngine::reset(Space* s) {
00043       delete cur;
00044       ds.reset();
00045       cur = s;
00046       d   = 0;
00047       EngineCtrl::reset(s);
00048     }
00049 
00050     forceinline size_t
00051     DfsEngine::stacksize(void) const {
00052       return ds.size();
00053     }
00054 
00055     forceinline Space*
00056     DfsEngine::explore(void) {
00057       start();
00058       while (true) {
00059         while (cur) {
00060           if (stop(stacksize()))
00061             return NULL;
00062           unsigned int alt;
00063           switch (cur->status(alt,propagate)) {
00064           case SS_FAILED:
00065             fail++;
00066             delete cur;
00067             cur = NULL;
00068             EngineCtrl::current(NULL);
00069             break;
00070           case SS_SOLVED:
00071             {
00072               Space* s = cur;
00073               cur = NULL;
00074               EngineCtrl::current(NULL);
00075               return s;
00076             }
00077           case SS_BRANCH:
00078             {
00079               Space* c;
00080               if ((d == 0) || (d >= c_d)) {
00081                 clone++;
00082                 c = cur->clone();
00083                 d = 1;
00084               } else {
00085                 c = NULL;
00086                 if (alt > 1)
00087                   d++;
00088               }
00089               BranchingDesc* desc = ds.push(cur,c,alt);
00090               EngineCtrl::push(c,desc);
00091               commit++;
00092               cur->commit(0, desc);
00093               break;
00094             }
00095           }
00096         }
00097         if (!ds.next(*this))
00098           return NULL;
00099         cur = ds.recompute(d,*this);
00100         EngineCtrl::current(cur);
00101       }
00102       return NULL;
00103     }
00104 
00105     forceinline
00106     DfsEngine::~DfsEngine(void) {
00107       delete cur;
00108       ds.reset();
00109     }
00110 
00111   }
00112 
00113   /*
00114    * Control for DFS search engine
00115    *
00116    */
00117 
00118   template <class T>
00119   forceinline
00120   DFS<T>::DFS(T* s, unsigned int c_d, unsigned int a_d, Search::Stop* st)
00121     : Search::DFS(s,c_d,a_d,st,sizeof(T)) {}
00122 
00123   template <class T>
00124   forceinline T*
00125   DFS<T>::next(void) {
00126     return static_cast<T*>(Search::DFS::next());
00127   }
00128 
00129 
00130 
00131   /*
00132    * DFS convenience
00133    *
00134    */
00135 
00136   template <class T>
00137   forceinline T*
00138   dfs(T* s, unsigned int c_d, unsigned int a_d, Search::Stop* st) {
00139     DFS<T> d(s,c_d,a_d,st);
00140     return static_cast<T*>(d.next());
00141   }
00142 
00143 }
00144 
00145 // STATISTICS: search-any