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, 2003
00007  *
00008  *  Last modified:
00009  *     $Date: 2005-10-23 16:23:09 +0200 (Sun, 23 Oct 2005) $ by $Author: schulte $
00010  *     $Revision: 2403 $
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 <climits>
00023 
00024 #include "support/dynamic-array.hh"
00025 #include "support/static-stack.hh"
00026 
00027 #include "iter.hh"
00028 
00029 namespace Gecode { namespace Int { namespace Distinct {
00030 
00038   template <class T>
00039   class CombPtrFlag {
00040   private:
00042     ptrdiff_t cpf;
00043   public:
00045     CombPtrFlag(T* p1, T* p2);
00047     void init(T* p1, T* p2);
00049     T* ptr(T* p) const;
00051     int is_set(void) const;
00053     void set(void);
00055     void unset(void);
00056   };
00057 
00062   class BiLink {
00063   private:
00064     BiLink* _prev; BiLink* _next;
00065   public:
00066     BiLink(void);
00067 
00068     BiLink* prev(void) const; void prev(BiLink*);
00069     BiLink* next(void) const; void next(BiLink*);
00070 
00071     void add(BiLink*);
00072     void unlink(void);
00073 
00074     void mark(void);
00075     bool marked(void) const;
00076 
00077     bool empty(void) const;
00078   };
00079 
00080   template <class View> class Edge;
00081 
00091   template <class View>
00092   class Node : public BiLink {
00093   public:
00094     unsigned int pre, low, comp;
00095 
00096     Node(void);
00097 
00098     Edge<View>* edge_fst(void) const;
00099     Edge<View>* edge_lst(void) const;
00100 
00101     static void* operator new(size_t, void*);
00102   };
00103 
00108   template <class View>
00109   class ValNode : public Node<View> {
00110   protected:
00111     const int _val; Edge<View>* _matching;
00112   public:
00113     ValNode(int);
00114     int val(void) const;
00115     void matching(Edge<View>*);
00116     Edge<View>* matching(void) const;
00117   };
00118 
00123   template <class View>
00124   class ViewNode : public Node<View> {
00125   protected:
00126     Edge<View>* _val_edges; View _view;
00127   public:
00128     ViewNode(View);
00129     Edge<View>*  val_edges(void) const;
00130     Edge<View>** val_edges_ref(void);
00131 
00132     View view(void) const;
00133   };
00134 
00139   template <class View>
00140   class Edge : public BiLink {
00141   protected:
00142     Edge<View>*              _next_edge;
00143     CombPtrFlag<Node<View> > sd;
00144   public:
00145     Edge(Node<View>*, Node<View>*);
00146 
00147     Node<View>* dst(Node<View>*) const;
00148 
00149     ViewNode<View>* view(ValNode<View>*) const;
00150     ValNode<View>* val(ViewNode<View>*) const;
00151 
00152     bool used(Node<View>*) const;
00153     void use(void);
00154     void free(void);
00155 
00156     void revert(Node<View>*);
00157 
00158     Edge<View>*  next_edge(void) const;
00159     Edge<View>** next_edge_ref(void);
00160 
00161     Edge<View>* next(void) const;
00162     static void* operator new(size_t, void*);
00163   };
00164 
00165 }}}
00166 
00167 #include "int/distinct/combptr.icc"
00168 #include "int/distinct/bilink.icc"
00169 #include "int/distinct/node.icc"
00170 #include "int/distinct/edge.icc"
00171 
00172 namespace Gecode { namespace Int { namespace Distinct {
00173 
00178   template <class View>
00179   class Dom<View>::ViewValGraph {
00180   protected:
00181     ViewNode<View>** view; int n_view;
00182     ValNode<View>** val; int n_val;
00183     char* mem;
00184     unsigned int count;
00185     unsigned int cnt0;
00186     unsigned int cnt1;
00187     Support::StaticStack<Node<View>*> n_s;
00188   public:
00189     ViewValGraph(ViewArray<View>&, const int*, int, unsigned int);
00190     ~ViewValGraph(void);
00191 
00192     size_t size;
00193 
00194     bool initial_match(void);
00195 
00196     void mark(void);
00197     bool tell(Space*);
00198 
00199     bool overflow(void) const;
00200 
00201     bool sync(void);
00202 
00203   protected:
00204     bool search_match(ViewNode<View>*);
00205     bool match(ViewNode<View>*);
00206     void scc(Node<View>*);
00207 
00208   public:
00209     // Memory management
00210     static void* operator new(size_t);
00211     static void  operator delete(void*);
00212   };
00213 
00214 
00215   template <class View>
00216   Dom<View>::ViewValGraph::ViewValGraph(ViewArray<View>& x, const int* val_inf,
00217                                 int n_val0, unsigned int n_edges)
00218     :  n_view(x.size()), n_val(n_val0),
00219        count(0), cnt0(0), cnt1(0), n_s(n_view+n_val)
00220   {
00221     size_t edge_size  = sizeof(Edge<View>) * n_edges;
00222     size_t views_size = sizeof(ViewNode<View>) * n_view;
00223     size_t view_size  = sizeof(ViewNode<View>*) * n_view;
00224     size_t vals_size  = sizeof(ValNode<View>) * n_val;
00225     size_t val_size   = sizeof(ValNode<View>*) * n_val;
00226     size_t size = edge_size +
00227       views_size + view_size + vals_size + val_size;
00228     mem = reinterpret_cast<char*>(Memory::malloc(size));
00229     Edge<View>*     edges      = reinterpret_cast<Edge<View>*>(mem);
00230     ViewNode<View>* view_nodes = reinterpret_cast<ViewNode<View>*>
00231       (mem+edge_size);
00232     ValNode<View>*  val_nodes  = reinterpret_cast<ValNode<View>*>
00233       (mem+edge_size+views_size);
00234     view = reinterpret_cast<ViewNode<View>**>
00235       (mem+edge_size+views_size+vals_size);
00236     val  = reinterpret_cast<ValNode<View>**>
00237       (mem+edge_size+views_size+vals_size+view_size);
00238 
00239     // Init value nodes
00240     for (int i = n_val; i--; )
00241       val[i] = new (val_nodes + i) ValNode<View>(val_inf[i]);
00242 
00243     // Init view nodes
00244     for (int i = n_view; i--; ) {
00245       view[i] = new (view_nodes + i) ViewNode<View>(x[i]);
00246       Edge<View>** edge_p = view[i]->val_edges_ref();
00247       ViewValues<View> x_i(x[i]);
00248       int j = 0;
00249       while (x_i()) {
00250         while (val_inf[j] < x_i.val())
00251           j++;
00252         *edge_p = new (edges++) Edge<View>(val_nodes+j,view_nodes+i);
00253         edge_p = (*edge_p)->next_edge_ref();
00254         ++x_i;
00255       }
00256       *edge_p = NULL;
00257     }
00258   }
00259 
00260   template <class View>
00261   bool
00262   Dom<View>::ViewValGraph::search_match(ViewNode<View>* x) {
00263     for (Edge<View>* e = x->val_edges(); e; e = e->next_edge())
00264       if (!e->val(x)->matching()) {
00265         e->revert(x); e->val(x)->matching(e);
00266         return true;
00267       }
00268     x->comp = count;
00269     for (Edge<View>* e = x->val_edges(); e; e = e->next_edge()) {
00270       ValNode<View>* n = e->val(x);
00271       ViewNode<View>* y = n->matching()->view(n);
00272       if ((y->comp < count) && search_match(y)) {
00273         n->matching()->revert(n);
00274         e->revert(x); n->matching(e);
00275         return true;
00276       }
00277     }
00278     return false;
00279   }
00280 
00281   template <class View>
00282   forceinline bool
00283   Dom<View>::ViewValGraph::match(ViewNode<View>* x) {
00284     assert(x->edge_fst() == x->edge_lst());
00285     count++;
00286     return search_match(x);
00287   }
00288 
00289   template <class View>
00290   bool
00291   Dom<View>::ViewValGraph::initial_match(void) {
00292     for (int i = n_view; i--; )
00293       if (!match(view[i]))
00294         return false;
00295     return true;
00296   }
00297 
00298   template <class View>
00299   void
00300   Dom<View>::ViewValGraph::scc(Node<View>* w) {
00301     w->pre = cnt0;
00302     w->low = cnt0;
00303     unsigned int min = cnt0++;
00304     n_s.push(w);
00305     for (Edge<View>* e = w->edge_fst(); e != w->edge_lst(); e = e->next()) {
00306       Node<View>* v = e->dst(w);
00307       if (v->pre < count)
00308         scc(v);
00309       if (v->low < min)
00310         min = v->low;
00311     }
00312     if (min < w->low) {
00313       w->low = min;
00314       return;
00315     }
00316     do {
00317       Node<View>* v = n_s.pop();
00318       v->comp = cnt1;
00319       v->low  = UINT_MAX;
00320     } while (n_s.last() != w);
00321     cnt1++;
00322   }
00323 
00324   template <class View>
00325   forceinline void
00326   Dom<View>::ViewValGraph::mark(void) {
00327     // Marks all edges as used that are on simple paths in the graph
00328     // that start from a free (unmatched node) by depth-first-search
00329     n_s.reset();
00330     // Insert all free nodes: they can be only value nodes as we
00331     // have a maximum matching covering all view nodes
00332     count++;
00333     for (int i = n_val; i--; )
00334       if (!val[i]->matching())
00335         // Is it orphaned?
00336         if (val[i]->empty()) {
00337           val[i] = val[--n_val];
00338         } else {
00339           val[i]->comp = count;
00340           n_s.push(val[i]);
00341         }
00342 
00343     // Invariant: only value nodes are on the stack!
00344     while (!n_s.empty()) {
00345       ValNode<View>* n = static_cast<ValNode<View>*>(n_s.pop());
00346       for (Edge<View>* e = n->edge_fst(); e != n->edge_lst(); e = e->next()) {
00347         // Get the value node
00348         e->use();
00349         ViewNode<View>* x = e->view(n);
00350         if (x->comp < count) {
00351           x->comp = count;
00352           assert(x->edge_fst()->next() == x->edge_lst());
00353           ValNode<View>* m = x->edge_fst()->val(x);
00354           x->edge_fst()->use();
00355           if (m->comp < count) {
00356             m->comp = count;
00357             n_s.push(m);
00358           }
00359         }
00360       }
00361     }
00362 
00363     count++;
00364     cnt0 = count;
00365     cnt1 = count;
00366     n_s.reset();
00367     for (int i = n_view; i--; )
00368       if (view[i]->comp < count)
00369         scc(view[i]);
00370     count = cnt0+1;
00371   }
00372 
00373   template <class View>
00374   forceinline bool
00375   Dom<View>::ViewValGraph::tell(Space* home) {
00376     bool shared = false;
00377     // Tell constraints and also eliminate nodes and edges
00378     for (int i = n_view; i--; )
00379       if (!view[i]->edge_fst()->used(view[i])) {
00380         shared |= view[i]->view().modified();
00381         view[i]->view().eq(home,view[i]->edge_fst()->val(view[i])->val());
00382         view[i]->edge_fst()->val(view[i])->matching(NULL);
00383         view[i] = view[--n_view];
00384       } else {
00385         for (Edge<View>* e = view[i]->val_edges(); e; e = e->next_edge())
00386           if (!e->used(view[i])) {
00387             shared |= view[i]->view().modified();
00388             view[i]->view().nq(home,e->val(view[i])->val());
00389           }
00390       }
00391     return shared;
00392   }
00393 
00394   template <class View>
00395   forceinline bool
00396   Dom<View>::ViewValGraph::overflow(void) const {
00397     return count > (UINT_MAX >> 1);
00398   }
00399 
00400   template <class View>
00401   bool
00402   Dom<View>::ViewValGraph::sync(void) {
00403     // Stack for view nodes to be rematched
00404     GECODE_AUTOARRAY(ViewNode<View>*,re,n_view);
00405     int n_re = 0;
00406     // Synchronize nodes
00407     for (int i = n_view; i--; ) {
00408       ViewNode<View>* x = view[i];
00409       if (x->view().assigned()) {
00410         x->edge_fst()->val(x)->matching(NULL);
00411         for (Edge<View>* e = x->val_edges(); e; e = e->next_edge())
00412           e->unlink();
00413         view[i] = view[--n_view];
00414       } else {
00415         ViewValues<View> n(x->view());
00416         Edge<View>*  m = x->edge_fst();      // Matching edge
00417         Edge<View>** p = x->val_edges_ref();
00418         Edge<View>*  e = *p;
00419         do {
00420           while (e->val(x)->val() < n.val()) {
00421             // Skip edge
00422             e->unlink(); e->mark();
00423             e = e->next_edge();
00424             *p = e;
00425           }
00426           assert(n.val() == e->val(x)->val());
00427           // This edge must be kept
00428           e->free();
00429           ++n;
00430           p = e->next_edge_ref();
00431           e = e->next_edge();
00432         } while (n());
00433         *p = NULL;
00434         while (e) {
00435           e->unlink(); e->mark();
00436           e = e->next_edge();
00437         }
00438         if (m->marked()) {
00439           // Matching has been deleted!
00440           m->val(x)->matching(NULL);
00441           re[n_re++] = x;
00442         }
00443       }
00444     }
00445     while (n_re--)
00446       if (!match(re[n_re]))
00447         return false;
00448     return true;
00449   }
00450 
00451   template <class View>
00452   Dom<View>::ViewValGraph::~ViewValGraph(void) {
00453     Memory::free(mem);
00454   }
00455 
00456   template <class View>
00457   forceinline void*
00458   Dom<View>::ViewValGraph::operator new(size_t s) {
00459     return Memory::malloc(s);
00460   }
00461   template <class View>
00462   forceinline void
00463   Dom<View>::ViewValGraph::operator delete(void* p) {
00464     Memory::free(p);
00465   }
00466 
00467 
00468 
00469   /*
00470    * The propagator proper
00471    *
00472    */
00473 
00474   template <class View>
00475   forceinline
00476   Dom<View>::Dom(Space* home, ViewArray<View>& x)
00477     : NaryPropagator<View,PC_INT_DOM>(home,x,true),
00478       vvg(NULL) {}
00479 
00480   template <class View>
00481   ExecStatus
00482   Dom<View>::post(Space* home, ViewArray<View>& x) {
00483     if (x.size() == 2)
00484       return Rel::Nq<View>::post(home,x[0],x[1]);
00485     if (x.size() > 2) {
00486       if (x.same())
00487         return ES_FAILED;
00488       // Do bounds propagation to make view-value graph smaller
00489       if (prop_bnd<View,false>(home,x) == ES_FAILED)
00490         return ES_FAILED;
00491       (void) new (home) Dom<View>(home,x);
00492     }
00493     return ES_OK;
00494   }
00495 
00496   template <class View>
00497   forceinline
00498   Dom<View>::Dom(Space* home, bool share, Dom<View>& p)
00499     : NaryPropagator<View,PC_INT_DOM>(home,share,p), vvg(NULL) {}
00500 
00501   template <class View>
00502   Dom<View>::~Dom(void) {
00503     delete vvg;
00504   }
00505 
00506   template <class View>
00507   void
00508   Dom<View>::flush(void) {
00509     delete vvg; vvg = NULL;
00510   }
00511 
00512   template <class View>
00513   size_t
00514   Dom<View>::size(void) const {
00515     return (vvg != NULL) ? vvg->size : 0;
00516   }
00517 
00518   template <class View>
00519   PropCost
00520   Dom<View>::cost(void) const {
00521     return cost_lo(x.size(),
00522                    (View::pme(this) == ME_INT_VAL)
00523                    ? PC_LINEAR_LO : PC_CUBIC_LO);
00524   }
00525 
00526   template <class View>
00527   Actor*
00528   Dom<View>::copy(Space* home, bool share) {
00529     return new (home) Dom<View>(home,share,*this);
00530   }
00531 
00532   template <class View>
00533   ExecStatus
00534   Dom<View>::propagate(Space* home) {
00535     if (View::pme(this) == ME_INT_VAL) {
00536       ExecStatus es = prop_val<View,false>(home,x);
00537       if ((es == ES_FAILED) || (es == ES_SUBSUMED))
00538         return es;
00539       if (es == ES_FIX)
00540         return this->ES_FIX_PARTIAL(View::pme(ME_INT_DOM));
00541       if (prop_bnd<View,false>(home,x) == ES_FAILED)
00542         return ES_FAILED;
00543       es = prop_val<View,true>(home,x);
00544       if ((es == ES_FAILED) || (es == ES_SUBSUMED))
00545         return es;
00546       return this->ES_FIX_PARTIAL(View::pme(ME_INT_DOM));      
00547     }
00548 
00549     if (x.size() == 2) {
00550       GECODE_ES_CHECK(Rel::Nq<View>::post(home,x[0],x[1]));
00551       return ES_SUBSUMED;
00552     }
00553 
00554     if ((vvg != NULL) && vvg->overflow()) {
00555       delete vvg;
00556       vvg = NULL;
00557     }
00558     
00559     if (vvg == NULL) {
00560       // Find value information for construction of view value graph
00561       Support::DynamicArray<int> val_inf(64);
00562       int          n_val = 0;
00563       unsigned int size  = 0;
00564       // Fill value array
00565       {
00566         GECODE_AUTOARRAY(ViewRanges<View>,x_r,x.size());
00567         for (int i = x.size(); i--; ) {
00568           ViewRanges<View> r(x[i]); x_r[i] = r;
00569           size += x[i].size();
00570         }
00571         Iter::Ranges::NaryUnion<ViewRanges<View> > xu(x_r, x.size());
00572         while (xu()) {
00573           for (int v = xu.min(); v <= xu.max(); v++)
00574             val_inf[n_val++] = v;
00575           ++xu;
00576         }
00577       }
00578 
00579       if (n_val < x.size())
00580         return ES_FAILED;
00581 
00582       vvg = new ViewValGraph(x,val_inf,n_val,size);
00583       if (!vvg->initial_match())
00584         return ES_FAILED;
00585     } else {
00586       if (!vvg->sync())
00587         return ES_FAILED;
00588     }
00589 
00590     vvg->mark();
00591     return vvg->tell(home) ? ES_NOFIX : ES_FIX;
00592 
00593   }
00594 
00595 }}}
00596 
00597 // STATISTICS: int-prop
00598