Generated on Wed Jan 4 17:49:09 2006 for Gecode by doxygen 1.4.6

dom.icc

Go to the documentation of this file.
00001 /*
00002  *  Main authors:
00003  *     Christian Schulte <schulte@gecode.org>
00004  *
00005  *  Copyright:
00006  *     Christian Schulte, 2004
00007  *
00008  *  Last modified:
00009  *     $Date: 2005-11-01 09:35:50 +0100 (Tue, 01 Nov 2005) $ by $Author: schulte $
00010  *     $Revision: 2457 $
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 #include "iter.hh"
00023 
00024 #include "support/static-stack.hh"
00025 #include "support/block-allocator.hh"
00026 
00027 namespace Gecode { namespace Int { namespace Regular {
00028 
00029   template <class View>
00030   forceinline
00031   Dom<View>::Dom(Space* home, ViewArray<View>& x, DFA& d)
00032     : NaryPropagator<View,PC_INT_DOM>(home,x,true),
00033       dfa(d), lg(NULL) {
00034   }
00035 
00036   template <class View>
00037   ExecStatus
00038   Dom<View>::post(Space* home, ViewArray<View>& x, DFA& d) {
00039     (void) new (home) Dom<View>(home,x,d);
00040     return ES_OK;
00041   }
00042 
00043   template <class View>
00044   forceinline
00045   Dom<View>::Dom(Space* home, bool share, Dom<View>& p)
00046     : NaryPropagator<View,PC_INT_DOM>(home,share,p), lg(NULL) {
00047     dfa.update(share,p.dfa);
00048   }
00049 
00050   template <class View>
00051   Dom<View>::~Dom(void) {
00052     delete lg;
00053   }
00054 
00055   template <class View>
00056   void
00057   Dom<View>::flush(void) {
00058     delete lg; lg = NULL;
00059   }
00060 
00061   template <class View>
00062   size_t
00063   Dom<View>::size(void) const {
00064     return (lg != NULL) ? lg->size() : 0;
00065   }
00066 
00067   template <class View>
00068   PropCost
00069   Dom<View>::cost(void) const {
00070     return cost_hi(this->x.size(), PC_LINEAR_HI);
00071   }
00072 
00073   template <class View>
00074   Actor*
00075   Dom<View>::copy(Space* home, bool share) {
00076     return new (home) Dom<View>(home,share,*this);
00077   }
00078 
00079   /*
00080    * Classes for the layered graph
00081    *
00082    */
00083 
00087   class State {
00088   public:
00089     unsigned int i_deg;
00090     unsigned int o_deg;
00091   };
00092 
00093   class Edge;
00094   typedef Support::BlockAllocator<Edge> EdgeAllocator;
00095 
00099   class Edge : public Support::BlockClient<Edge> {
00100   public:
00101     int    val;
00102     State* i_state;
00103     State* o_state;
00104     Edge*  next;
00105   };
00106 
00111   const int MOD_NONE  = 0; 
00112   const int MOD_IDEG  = 1; 
00113   const int MOD_ODEG  = 2; 
00114 
00115 
00119   class Layer {
00120   public:
00121     Edge*        edges;
00122     unsigned int size;
00123     int          modified;
00124   };
00125 
00127   template <class View>
00128   class Dom<View>::LayeredGraph {
00129   private:
00130     unsigned int  n_unassigned;
00131     EdgeAllocator ea;
00132     size_t        state_size;
00133     State*        state_mem;
00134     Layer         _layer;    // One addional layer (makes layers[-1] okay)
00135     Layer         layers[2]; // Dynamically adjusted (also allow layers[...+1])
00136   public:
00138     LayeredGraph(ViewArray<View> x, const DFA& d);
00140     ~LayeredGraph(void);
00141 
00143     ExecStatus prune_initial(Space* home, ViewArray<View> x);
00145     ExecStatus prune(Space* home, ViewArray<View> x);
00146 
00148     size_t size(void) const;
00149     static void* operator new(size_t,int);
00150     static void  operator delete(void*);
00151     static void  operator delete(void*,int);
00152   };
00153 
00154 
00155 
00160   class EdgeRanges {
00161   private:
00162     const Edge* e1; const Edge* e2;
00163   public:
00164     EdgeRanges(void);
00165     EdgeRanges(const Edge*);
00166     void init(const Edge*);
00167     bool operator()(void) const;
00168     void operator++(void);
00169     int min(void) const;
00170     int max(void) const;
00171     unsigned int width(void) const;
00172   };
00173 
00174   forceinline
00175   EdgeRanges::EdgeRanges(void) {}
00176   forceinline
00177   EdgeRanges::EdgeRanges(const Edge* e)
00178     : e1(e), e2(e) {
00179     assert(e1);
00180     // e2 always points to the end of  the interval
00181     while ((e2->next != NULL) && (e2->next->val <= e2->val+1))
00182       e2 = e2->next;
00183   }
00184   forceinline void
00185   EdgeRanges::init(const Edge* e) {
00186     e1=e; e2=e;
00187     assert(e1);
00188     // e2 always points to the end of  the interval
00189     while ((e2->next != NULL) && (e2->next->val <= e2->val+1))
00190       e2 = e2->next;
00191   }
00192 
00193   forceinline bool
00194   EdgeRanges::operator()(void) const {
00195     return e1 != NULL;
00196   }
00197 
00198   forceinline void
00199   EdgeRanges::operator++(void) {
00200     e1 = e2->next;
00201     if (e1 != NULL) {
00202       e2 = e1;
00203       while ((e2->next != NULL) && (e2->next->val <= e2->val+1))
00204         e2 = e2->next;
00205     }
00206   }
00207 
00208   forceinline int
00209   EdgeRanges::min(void) const {
00210     return e1->val;
00211   }
00212   forceinline int
00213   EdgeRanges::max(void) const {
00214     return e2->val;
00215   }
00216   forceinline unsigned int
00217   EdgeRanges::width(void) const {
00218     return max()-min()+1;
00219   }
00220 
00221 
00222 
00223   /*
00224    * The layered graph
00225    *
00226    */
00227 
00228   template <class View>
00229   forceinline
00230   Dom<View>::LayeredGraph::LayeredGraph(ViewArray<View> x, const DFA& dfa)
00231     : n_unassigned(x.size()) {
00232     int n = x.size();
00233     unsigned int n_states = dfa.n_states();
00234 
00235     // Allocate memory
00236     state_size = sizeof(State)*(n+1)*n_states;
00237     state_mem  = reinterpret_cast<State*>(Memory::malloc(state_size));
00238 
00239 
00240     // Initialize states (indegree and outdegree)
00241     for (int i = (n+1)*n_states; i--; ) {
00242       state_mem[i].i_deg = 0;
00243       state_mem[i].o_deg = 0;
00244     }
00245 
00246     // Mark initial state as being reachable
00247     state_mem[0].i_deg = 1;
00248 
00249     // Mark final states as reachable as well
00250     for (int s = dfa.final_fst(); s < dfa.final_lst(); s++)
00251       state_mem[n*n_states + s].o_deg = 1;
00252 
00253     // First pass: add transitions
00254     for (int i = 0; i < n; i++) {
00255       Edge** p = &layers[i].edges;
00256       // Enter links leaving reachable states (indegree != 0)
00257       DFA::Transitions  t_a(dfa);
00258       ViewRanges<View>    rx(x[i]);
00259       while (rx() && t_a()) {
00260         const DFA::Transition* t = t_a.transition();
00261         // Compute pointers to states
00262         State* i_state = state_mem + (i  )*n_states + t->i_state;
00263         State* o_state = state_mem + (i+1)*n_states + t->o_state;
00264         if (t->symbol > rx.max()) {
00265           ++rx;
00266         } else if ((t->symbol >= rx.min()) && (i_state->i_deg > 0)) {
00267           // Add new transition as state is reachable
00268           i_state->o_deg++; o_state->i_deg++;
00269           Edge* e = new (ea) Edge;
00270           e->i_state = i_state;
00271           e->val     = t->symbol;
00272           e->o_state = o_state;
00273           *p = e;
00274           p = &e->next;
00275           ++t_a;
00276         } else {
00277           ++t_a;
00278         }
00279       }
00280       // Write endmarker for edges
00281       *p = NULL;
00282     }
00283   }
00284 
00285   template <class View>
00286   forceinline ExecStatus
00287   Dom<View>::LayeredGraph::prune_initial(Space* home, ViewArray<View> x) {
00288     // Second pass: prune all transitions that do not lead to final state
00289     for (int i = x.size(); i--; ) {
00290       Edge** p = &layers[i].edges;
00291       Edge*  e = *p;
00292       while (e != NULL) {
00293         if (e->o_state->o_deg != 0) {
00294           // This state is still reachable, keep edge
00295           p = &e->next;
00296         } else {
00297           // Unreachable state, prune edge
00298           *p = e->next;
00299           e->i_state->o_deg--; e->o_state->i_deg--;
00300         }
00301         e = e->next;
00302       }
00303       *p = NULL;
00304     }
00305 
00306     // Tell back variable domains
00307     ExecStatus es = ES_FIX;
00308     for (int i=x.size(); i--; ) {
00309       if (layers[i].edges == NULL)
00310         return ES_FAILED;
00311       if (x[i].modified())
00312         es = ES_NOFIX;
00313       EdgeRanges er(layers[i].edges);
00314       if (x[i].modified()) {
00315         GECODE_ME_CHECK(x[i].inter(home,er));
00316       } else {
00317         x[i].narrow(home,er);
00318       }
00319       // Initialize size and modification data
00320       layers[i].modified = MOD_NONE;
00321       layers[i].size     = x[i].size();
00322       if (layers[i].size == 1)
00323         n_unassigned--;
00324     }
00325     return (n_unassigned == 0) ? ES_SUBSUMED : es;
00326   }
00327 
00328   template <class View>
00329   forceinline ExecStatus
00330   Dom<View>::LayeredGraph::prune(Space* home, ViewArray<View> x) {
00331     int n = x.size();
00332     // Prune edges for which no value support exists
00333     for (int i = 0; i < n; i++)
00334       if (layers[i].size != x[i].size()) {
00335         layers[i].size = x[i].size();
00336         if (layers[i].size == 1)
00337           n_unassigned--;
00338         Edge** p = &layers[i].edges;
00339         Edge*  e = *p;
00340         ViewRanges<View> rx(x[i]);
00341         while (rx() && (e != NULL)) {
00342           if (e->val > rx.max()) {
00343             ++rx;
00344           } else if ((e->val < rx.min()) || (e->i_state->i_deg == 0)) {
00345             // Adapt states
00346             if ((--e->i_state->o_deg) == 0)
00347               layers[i-1].modified |= MOD_ODEG;
00348             if ((--e->o_state->i_deg) == 0)
00349               layers[i+1].modified |= MOD_IDEG;
00350             // Remove this edge
00351             *p = e->next; e = e->next;
00352           } else {
00353             // Keep edge
00354             p = &e->next; e = e->next;
00355           }
00356         }
00357         *p = NULL;
00358         // Remove all remainign edges
00359         while (e != NULL) {
00360           // Adapt states
00361           if (--e->i_state->o_deg == 0)
00362             layers[i-1].modified |= MOD_ODEG;
00363           if (--e->o_state->i_deg == 0)
00364             layers[i+1].modified |= MOD_IDEG;
00365           e = e->next;
00366         }
00367         // Write endmarker for edges
00368       }  else if (layers[i].modified & MOD_IDEG) {
00369         assert(layers[i].size == x[i].size());
00370         Edge** p = &layers[i].edges;
00371         Edge*  e = *p;
00372         while (e != NULL) {
00373           if (e->i_state->i_deg == 0) {
00374             // Adapt states
00375             if (--e->i_state->o_deg == 0)
00376               layers[i-1].modified |= MOD_ODEG;
00377             if (--e->o_state->i_deg == 0)
00378               layers[i+1].modified |= MOD_IDEG;
00379             // Remove this edge
00380             *p = e->next;
00381           } else {
00382             // Keep edge
00383             p = &e->next;
00384           }
00385           e = e->next;
00386         }
00387         // Write endmarker for edges
00388         *p = NULL;
00389       }
00390 
00391     for (int i=n; i--; )
00392       if (layers[i].modified & MOD_ODEG) {
00393         Edge** p = &layers[i].edges;
00394         Edge*  e = *p;
00395         while (e != NULL) {
00396           if (e->o_state->o_deg != 0) {
00397             // This state is still reachable, keep edge
00398             p = &e->next;
00399           } else {
00400             // Unreachable state, prune edge
00401             if (--e->i_state->o_deg == 0)
00402               layers[i-1].modified |= MOD_ODEG;
00403             --e->o_state->i_deg;
00404             *p = e->next;
00405           }
00406           e = e->next;
00407         }
00408         *p = NULL;
00409       }
00410     // Tell back variable domains
00411     ExecStatus es = ES_FIX;
00412     for (int i=n; i--; )
00413       if (layers[i].modified) {
00414         layers[i].modified = MOD_NONE;
00415         if (layers[i].edges == NULL)
00416           return ES_FAILED;
00417         if (x[i].modified())
00418           es = ES_NOFIX;
00419         EdgeRanges er(layers[i].edges);
00420         if (x[i].modified()) {
00421           GECODE_ME_CHECK(x[i].inter(home,er));
00422         } else {
00423           x[i].narrow(home,er);
00424         }
00425         if (layers[i].size != x[i].size()) {
00426           layers[i].size = x[i].size();
00427           if (layers[i].size == 1)
00428             n_unassigned--;
00429         }
00430       }
00431     return (n_unassigned == 0) ? ES_SUBSUMED : es;
00432   }
00433 
00434   template <class View>
00435   forceinline
00436   Dom<View>::LayeredGraph::~LayeredGraph(void) {
00437     Memory::free(state_mem);
00438   }
00439 
00440   template <class View>
00441   forceinline size_t
00442   Dom<View>::LayeredGraph::size(void) const {
00443     return state_size + ea.size();
00444   }
00445 
00446   template <class View>
00447   forceinline void
00448   Dom<View>::LayeredGraph::operator delete(void* p) {
00449     Memory::free(p);
00450   }
00451 
00452   template <class View>
00453   forceinline void
00454   Dom<View>::LayeredGraph::operator delete(void* p, int) {
00455     Memory::free(p);
00456   }
00457 
00458   template <class View>
00459   forceinline void*
00460   Dom<View>::LayeredGraph::operator new(size_t s, int n) {
00461     // n ist the number of variables
00462     return Memory::malloc(sizeof(LayeredGraph) + n*sizeof(Layer));
00463   }
00464 
00465   template <class View>
00466   ExecStatus
00467   Dom<View>::propagate(Space* home) {
00468     if (lg == NULL) {
00469       lg = new (this->x.size()) LayeredGraph(this->x,dfa);
00470       return lg->prune_initial(home,this->x);
00471     } else {
00472       return lg->prune(home,this->x);
00473     }
00474   }
00475 
00476 }}}
00477 
00478 // STATISTICS: int-prop
00479