Generated on Wed Jul 27 2011 15:08:36 for Gecode by doxygen 1.7.4
dom.hpp
Go to the documentation of this file.
00001 /* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */
00002 /*
00003  *  Main authors:
00004  *     Christian Schulte <schulte@gecode.org>
00005  *
00006  *  Copyright:
00007  *     Christian Schulte, 2003
00008  *
00009  *  Last modified:
00010  *     $Date: 2010-03-03 17:32:21 +0100 (Wed, 03 Mar 2010) $ by $Author: schulte $
00011  *     $Revision: 10364 $
00012  *
00013  *  This file is part of Gecode, the generic constraint
00014  *  development environment:
00015  *     http://www.gecode.org
00016  *
00017  *  Permission is hereby granted, free of charge, to any person obtaining
00018  *  a copy of this software and associated documentation files (the
00019  *  "Software"), to deal in the Software without restriction, including
00020  *  without limitation the rights to use, copy, modify, merge, publish,
00021  *  distribute, sublicense, and/or sell copies of the Software, and to
00022  *  permit persons to whom the Software is furnished to do so, subject to
00023  *  the following conditions:
00024  *
00025  *  The above copyright notice and this permission notice shall be
00026  *  included in all copies or substantial portions of the Software.
00027  *
00028  *  THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
00029  *  EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
00030  *  MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
00031  *  NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
00032  *  LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
00033  *  OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
00034  *  WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
00035  *
00036  */
00037 
00038 #include <climits>
00039 
00040 namespace Gecode { namespace Int { namespace Distinct {
00041 
00049   template<class T>
00050   class CombPtrFlag {
00051   private:
00053     ptrdiff_t cpf;
00054   public:
00056     CombPtrFlag(T* p1, T* p2);
00058     void init(T* p1, T* p2);
00060     T* ptr(T* p) const;
00062     int is_set(void) const;
00064     void set(void);
00066     void unset(void);
00067   };
00068 
00073   class BiLink {
00074   private:
00075     BiLink* _prev; BiLink* _next;
00076   public:
00077     BiLink(void);
00078 
00079     BiLink* prev(void) const; void prev(BiLink*);
00080     BiLink* next(void) const; void next(BiLink*);
00081 
00082     void add(BiLink*);
00083     void unlink(void);
00084 
00085     void mark(void);
00086     bool marked(void) const;
00087 
00088     bool empty(void) const;
00089   };
00090 
00091   template<class View> class Edge;
00092 
00102   template<class View>
00103   class Node : public BiLink {
00104   public:
00105     unsigned int low, min, comp;
00106     Edge<View>* iter;
00107 
00108     Node(void);
00109 
00110     Edge<View>* edge_fst(void) const;
00111     Edge<View>* edge_lst(void) const;
00112 
00113     static void  operator delete(void*, size_t);
00114     static void  operator delete(void*,Space&);
00115     static void* operator new(size_t, Space&);
00116   };
00117 
00122   template<class View>
00123   class ValNode : public Node<View> {
00124   protected:
00126     const int      _val;
00128     Edge<View>*    _matching;
00130     ValNode<View>* _next_val;
00131   public:
00133     ValNode(int v);
00135     ValNode(int v, ValNode<View>* n);
00137     int val(void) const;
00139     void matching(Edge<View>* m);
00141     Edge<View>* matching(void) const;
00143     ValNode<View>** next_val_ref(void);
00145     ValNode<View>* next_val(void) const;
00147     void next_val(ValNode<View>* v);
00148   };
00149 
00154   template<class View>
00155   class ViewNode : public Node<View> {
00156   protected:
00158     View        _view;
00160     Edge<View>* _val_edges;
00161   public:
00163     ViewNode(View x);
00165     Edge<View>*  val_edges(void) const;
00167     Edge<View>** val_edges_ref(void);
00169     View view(void) const;
00170   };
00171 
00176   template<class View>
00177   class Edge : public BiLink {
00178   protected:
00180     Edge<View>*              _next_edge;
00182     CombPtrFlag<Node<View> > sd;
00183   public:
00185     Edge(ValNode<View>* v, ViewNode<View>* x);
00187     Node<View>* dst(Node<View>* s) const;
00188 
00190     ViewNode<View>* view(ValNode<View>* v) const;
00192     ValNode<View>* val(ViewNode<View>* x) const;
00193 
00194     bool used(Node<View>*) const;
00195     void use(void);
00196     void free(void);
00197 
00198     void revert(Node<View>*);
00199 
00200     Edge<View>*  next_edge(void) const;
00201     Edge<View>** next_edge_ref(void);
00202 
00203     Edge<View>* next(void) const;
00204 
00205     static void  operator delete(void*, size_t);
00206     static void  operator delete(void*,Space&);
00207     static void* operator new(size_t, Space&);
00208   };
00209 
00210 }}}
00211 
00212 #include <gecode/int/distinct/combptr.hpp>
00213 #include <gecode/int/distinct/bilink.hpp>
00214 #include <gecode/int/distinct/edge.hpp>
00215 #include <gecode/int/distinct/node.hpp>
00216 
00217 namespace Gecode { namespace Int { namespace Distinct {
00218 
00219 
00220   template<class View>
00221   forceinline
00222   DomCtrl<View>::ViewValGraph::ViewValGraph(void)
00223     : view(NULL), val(NULL), count(1) {}
00224 
00225   template<class View>
00226   forceinline bool
00227   DomCtrl<View>::ViewValGraph::initialized(void) const {
00228     return view != NULL;
00229   }
00230 
00231   template<class View>
00232   forceinline bool
00233   DomCtrl<View>::ViewValGraph::match(ViewNodeStack& m, ViewNode<View>* x) {
00234     count++;
00235   start:
00236     // Try to find matching edge cheaply: is there a free edge around?
00237     {
00238       Edge<View>* e = x->val_edges();
00239       // This holds true as domains are never empty
00240       assert(e != NULL);
00241       do {
00242         if (!e->val(x)->matching()) {
00243           e->revert(x); e->val(x)->matching(e);
00244           // Found a matching, revert all edges on stack
00245           while (!m.empty()) {
00246             x = m.pop(); e = x->iter;
00247             e->val(x)->matching()->revert(e->val(x));
00248             e->revert(x); e->val(x)->matching(e);
00249           }
00250           return true;
00251         }
00252         e = e->next_edge();
00253       } while (e != NULL);
00254     }
00255     // No, find matching edge by augmenting path method
00256     Edge<View>* e = x->val_edges();
00257     do {
00258       if (e->val(x)->matching()->view(e->val(x))->min < count) {
00259         e->val(x)->matching()->view(e->val(x))->min = count;
00260         m.push(x); x->iter = e;
00261         x = e->val(x)->matching()->view(e->val(x));
00262         goto start;
00263       }
00264     next:
00265       e = e->next_edge();
00266     } while (e != NULL);
00267     if (!m.empty()) {
00268       x = m.pop(); e = x->iter; goto next;
00269     }
00270     // All nodes and edges unsuccessfully tried
00271     return false;
00272   }
00273 
00274   template<class View>
00275   forceinline void
00276   DomCtrl<View>::ViewValGraph::init(Space& home, ViewNode<View>* x) {
00277     Edge<View>** edge_p = x->val_edges_ref();
00278     ViewValues<View> xi(x->view());
00279     ValNode<View>** v = &val;
00280     while (xi() && (*v != NULL)) {
00281       if ((*v)->val() == xi.val()) {
00282         // Value node does already exist, create new edge
00283         *edge_p = new (home) Edge<View>(*v,x);
00284         edge_p = (*edge_p)->next_edge_ref();
00285         v = (*v)->next_val_ref();
00286         ++xi;
00287       } else if ((*v)->val() < xi.val()) {
00288         // Skip to next value node
00289         v = (*v)->next_val_ref();
00290       } else {
00291         // Value node does not yet exist, create and link it
00292         ValNode<View>* nv = new (home) ValNode<View>(xi.val(),*v);
00293         *v = nv; v = nv->next_val_ref();
00294         *edge_p = new (home) Edge<View>(nv,x);
00295         edge_p = (*edge_p)->next_edge_ref();
00296         ++xi; n_val++;
00297       }
00298     }
00299     // Create missing value nodes
00300     while (xi()) {
00301       ValNode<View>* nv = new (home) ValNode<View>(xi.val(),*v);
00302       *v = nv; v = nv->next_val_ref();
00303       *edge_p = new (home) Edge<View>(nv,x);
00304       edge_p = (*edge_p)->next_edge_ref();
00305       ++xi; n_val++;
00306     }
00307     *edge_p = NULL;
00308   }
00309 
00310   template<class View>
00311   ExecStatus
00312   DomCtrl<View>::ViewValGraph::init(Space& home, int n, View* x) {
00313     n_view = n;
00314     view = home.alloc<ViewNode<View>*>(n_view);
00315 
00316     // Find value information for construction of view value graph
00317     int min = x[n_view-1].min();
00318     int max = x[n_view-1].max();
00319     for (int i=n_view-1; i--; ) {
00320       min = std::min(min,x[i].min());
00321       max = std::max(max,x[i].max());
00322     }
00323 
00324     unsigned int width = static_cast<unsigned int>(max-min+1);
00325 
00326     // Definitly not enough values
00327     if (width < static_cast<unsigned int>(n_view))
00328       return ES_FAILED;
00329 
00330     // Initialize view nodes
00331     for (int i=n; i--; )
00332       view[i] = new (home) ViewNode<View>(x[i]);
00333 
00334     n_val = 0;
00335     val = NULL;
00336 
00337     Region r(home);
00338 
00339     if (static_cast<unsigned int>(n_view)*4 >= width) {
00340       // Values are dense: use a mapping
00341       ValNode<View>** val2node = r.alloc<ValNode<View>* >(width);
00342 
00343       for (unsigned int i=width; i--; )
00344         val2node[i]=NULL;
00345 
00346       for (int i=n; i--; ) {
00347         Edge<View>** edge_p = view[i]->val_edges_ref();
00348         for (ViewValues<View> xi(x[i]); xi(); ++xi) {
00349           if (val2node[xi.val()-min] == NULL)
00350             val2node[xi.val()-min] = new (home) ValNode<View>(xi.val());
00351           *edge_p = new (home) Edge<View>(val2node[xi.val()-min],view[i]);
00352           edge_p = (*edge_p)->next_edge_ref();
00353         }
00354         *edge_p = NULL;
00355       }
00356 
00357       for (unsigned int i=width; i--; )
00358         if (val2node[i] != NULL) {
00359           val2node[i]->next_val(val);
00360           val = val2node[i];
00361           n_val++;
00362         }
00363 
00364     } else {
00365       // Values are sparse
00366       for (int i=n; i--; )
00367         init(home,view[i]);
00368     }
00369 
00370     ViewNodeStack m(r,n_view);
00371     for (int i = n_view; i--; )
00372       if (!match(m,view[i]))
00373         return ES_FAILED;
00374     return ES_OK;
00375   }
00376 
00377   template<class View>
00378   forceinline void
00379   DomCtrl<View>::ViewValGraph::mark(Space& home) {
00380     Region r(home);
00381     {
00382       // Marks all edges as used that are on simple paths in the graph
00383       // that start from a free (unmatched node) by depth-first-search
00384       Support::StaticStack<ValNode<View>*,Region> visit(r,n_val);
00385 
00386       // Insert all free nodes: they can be only value nodes as we
00387       // have a maximum matching covering all view nodes
00388       count++;
00389       {
00390         ValNode<View>** v = &val;
00391         while (*v != NULL)
00392           if (!(*v)->matching()) {
00393             if ((*v)->empty()) {
00394               *v = (*v)->next_val();
00395               n_val--;
00396             } else {
00397               (*v)->min = count;
00398               visit.push(*v);
00399               v = (*v)->next_val_ref();
00400             }
00401           } else {
00402             v = (*v)->next_val_ref();
00403           }
00404       }
00405 
00406       // Invariant: only value nodes are on the stack!
00407       while (!visit.empty()) {
00408         ValNode<View>* n = visit.pop();
00409         for (Edge<View>* e = n->edge_fst(); e != n->edge_lst(); e=e->next()) {
00410           // Get the value node
00411           e->use();
00412           ViewNode<View>* x = e->view(n);
00413           if (x->min < count) {
00414             x->min = count;
00415             assert(x->edge_fst()->next() == x->edge_lst());
00416             ValNode<View>* m = x->edge_fst()->val(x);
00417             x->edge_fst()->use();
00418             if (m->min < count) {
00419               m->min = count;
00420               visit.push(m);
00421             }
00422           }
00423         }
00424       }
00425     }
00426 
00427     {
00428       Support::StaticStack<Node<View>*,Region> scc(r,n_val+n_view);
00429       Support::StaticStack<Node<View>*,Region> visit(r,n_val+n_view);
00430 
00431       count++;
00432       unsigned int cnt0 = count;
00433       unsigned int cnt1 = count;
00434 
00435       for (int i = n_view; i--; )
00436         if (view[i]->min < count) {
00437           Node<View>* w = view[i];
00438         start:
00439           w->low = w->min = cnt0++;
00440           scc.push(w);
00441           Edge<View>* e = w->edge_fst();
00442           while (e != w->edge_lst()) {
00443             if (e->dst(w)->min < count) {
00444               visit.push(w); w->iter = e;
00445               w=e->dst(w);
00446               goto start;
00447             }
00448           next:
00449             if (e->dst(w)->low < w->min)
00450               w->min = e->dst(w)->low;
00451             e = e->next();
00452           }
00453           if (w->min < w->low) {
00454             w->low = w->min;
00455           } else {
00456             Node<View>* v;
00457             do {
00458               v = scc.pop();
00459               v->comp = cnt1;
00460               v->low  = UINT_MAX;
00461             } while (v != w);
00462             cnt1++;
00463           }
00464           if (!visit.empty()) {
00465             w=visit.pop(); e=w->iter; goto next;
00466           }
00467         }
00468       count = cnt0+1;
00469     }
00470   }
00471 
00473   template<class View>
00474   class PruneVal {
00475   protected:
00477     ViewNode<View>* x;
00479     Edge<View>* e;
00480   public:
00482 
00483 
00484     PruneVal(ViewNode<View>* y);
00486 
00488 
00489 
00490     bool operator ()(void) const;
00492     void operator ++(void);
00494 
00496 
00497 
00498     int val(void) const;
00500   };
00501 
00502   template<class View>
00503   forceinline
00504   PruneVal<View>::PruneVal(ViewNode<View>* y)
00505     : x(y), e(y->val_edges()) {
00506     while ((e != NULL) && e->used(x))
00507       e = e->next_edge();
00508   }
00509   template<class View>
00510   forceinline bool
00511   PruneVal<View>::operator ()(void) const {
00512     return e != NULL;
00513   }
00514   template<class View>
00515   forceinline void
00516   PruneVal<View>::operator ++(void) {
00517     do {
00518       e = e->next_edge();
00519     } while ((e != NULL) && e->used(x));
00520   }
00521   template<class View>
00522   forceinline int
00523   PruneVal<View>::val(void) const {
00524     assert(!e->used(x));
00525     return e->val(x)->val();
00526   }
00527 
00528   template<class View>
00529   forceinline ExecStatus
00530   DomCtrl<View>::ViewValGraph::tell(Space& home, bool& assigned) {
00531     assigned = false;
00532     // Tell constraints and also eliminate nodes and edges
00533     for (int i = n_view; i--; ) {
00534       ViewNode<View>* x = view[i];
00535       if (!x->edge_fst()->used(x)) {
00536         GECODE_ME_CHECK(x->view().eq(home,x->edge_fst()->val(x)->val()));
00537         x->edge_fst()->val(x)->matching(NULL);
00538         for (Edge<View>* e = x->val_edges(); e != NULL; e = e->next_edge())
00539           e->unlink();
00540         view[i] = view[--n_view];
00541         assigned = true;
00542       } else {
00543         PruneVal<View> pv(view[i]);
00544         GECODE_ME_CHECK(view[i]->view().minus_v(home,pv,false));
00545       }
00546     }
00547     return ES_OK;
00548   }
00549 
00550   template<class View>
00551   forceinline void
00552   DomCtrl<View>::ViewValGraph::purge(void) {
00553     if (count > (UINT_MAX >> 1)) {
00554       count = 1;
00555       for (int i=n_view; i--; )
00556         view[i]->min = 0;
00557       for (ValNode<View>* v = val; v != NULL; v = v->next_val())
00558         v->min = 0;
00559     }
00560   }
00561 
00562   template<class View>
00563   bool
00564   DomCtrl<View>::ViewValGraph::sync(Space& home) {
00565     Region r(home);
00566     // Stack for view nodes to be rematched
00567     ViewNodeStack re(r,n_view);
00568     // Synchronize nodes
00569     for (int i = n_view; i--; ) {
00570       ViewNode<View>* x = view[i];
00571       if (x->view().assigned()) {
00572         x->edge_fst()->val(x)->matching(NULL);
00573         for (Edge<View>* e = x->val_edges(); e != NULL; e = e->next_edge())
00574           e->unlink();
00575         view[i] = view[--n_view];
00576       } else {
00577         ViewRanges<View> r(x->view());
00578         Edge<View>*  m = x->edge_fst();      // Matching edge
00579         Edge<View>** p = x->val_edges_ref();
00580         Edge<View>*  e = *p;
00581         do {
00582           while (e->val(x)->val() < r.min()) {
00583             // Skip edge
00584             e->unlink(); e->mark();
00585             e = e->next_edge();
00586           }
00587           *p = e;
00588           assert(r.min() == e->val(x)->val());
00589           // This edges must be kept
00590           for (unsigned int j=r.width(); j--; ) {
00591             e->free();
00592             p = e->next_edge_ref();
00593             e = e->next_edge();
00594           }
00595           ++r;
00596         } while (r());
00597         *p = NULL;
00598         while (e != NULL) {
00599           e->unlink(); e->mark();
00600           e = e->next_edge();
00601         }
00602         if (m->marked()) {
00603           // Matching has been deleted!
00604           m->val(x)->matching(NULL);
00605           re.push(x);
00606         }
00607       }
00608     }
00609     ViewNodeStack m(r,n_view);
00610     while (!re.empty())
00611       if (!match(m,re.pop()))
00612         return false;
00613     return true;
00614   }
00615 
00616 
00617 
00618   /*
00619    * The propagation controller
00620    *
00621    */
00622 
00623   template<class View>
00624   forceinline
00625   DomCtrl<View>::DomCtrl(void) {}
00626 
00627   template<class View>
00628   forceinline bool
00629   DomCtrl<View>::available(void) {
00630     return vvg.initialized();
00631   }
00632 
00633   template<class View>
00634   forceinline ExecStatus
00635   DomCtrl<View>::init(Space& home, int n, View* x) {
00636     return vvg.init(home,n,x);
00637   }
00638 
00639   template<class View>
00640   forceinline ExecStatus
00641   DomCtrl<View>::sync(Space& home) {
00642     vvg.purge();
00643     return vvg.sync(home) ? ES_OK : ES_FAILED;
00644   }
00645 
00646   template<class View>
00647   forceinline ExecStatus
00648   DomCtrl<View>::propagate(Space& home, bool& assigned) {
00649     vvg.mark(home);
00650     return vvg.tell(home,assigned);
00651   }
00652 
00653 
00654   /*
00655    * The propagator proper
00656    *
00657    */
00658 
00659   template<class View>
00660   forceinline
00661   Dom<View>::Dom(Home home, ViewArray<View>& x)
00662     : NaryPropagator<View,PC_INT_DOM>(home,x) {}
00663 
00664   template<class View>
00665   ExecStatus
00666   Dom<View>::post(Home home, ViewArray<View>& x) {
00667     if (x.size() == 2)
00668       return Rel::Nq<View>::post(home,x[0],x[1]);
00669     if (x.size() == 3)
00670       return TerDom<View>::post(home,x[0],x[1],x[2]);
00671     if (x.size() > 3) {
00672       // Do bounds propagation to make view-value graph smaller
00673       GECODE_ES_CHECK(prop_bnd<View>(home,x));
00674       (void) new (home) Dom<View>(home,x);
00675     }
00676     return ES_OK;
00677   }
00678 
00679   template<class View>
00680   forceinline
00681   Dom<View>::Dom(Space& home, bool share, Dom<View>& p)
00682     : NaryPropagator<View,PC_INT_DOM>(home,share,p) {}
00683 
00684   template<class View>
00685   PropCost
00686   Dom<View>::cost(const Space&, const ModEventDelta& med) const {
00687     if (View::me(med) == ME_INT_VAL)
00688       return PropCost::linear(PropCost::LO, x.size());
00689     else
00690       return PropCost::quadratic(PropCost::HI, x.size());
00691   }
00692 
00693   template<class View>
00694   Actor*
00695   Dom<View>::copy(Space& home, bool share) {
00696     return new (home) Dom<View>(home,share,*this);
00697   }
00698 
00699   template<class View>
00700   ExecStatus
00701   Dom<View>::propagate(Space& home, const ModEventDelta& med) {
00702     if (View::me(med) == ME_INT_VAL) {
00703       ExecStatus es = prop_val<View,false>(home,x);
00704       GECODE_ES_CHECK(es);
00705       if (x.size() < 2)
00706         return home.ES_SUBSUMED(*this);
00707       if (es == ES_FIX)
00708         return home.ES_FIX_PARTIAL(*this,View::med(ME_INT_DOM));
00709       es = prop_bnd<View>(home,x);
00710       GECODE_ES_CHECK(es);
00711       if (x.size() < 2)
00712         return home.ES_SUBSUMED(*this);
00713       es = prop_val<View,true>(home,x);
00714       GECODE_ES_CHECK(es);
00715       if (x.size() < 2)
00716         return home.ES_SUBSUMED(*this);
00717       return home.ES_FIX_PARTIAL(*this,View::med(ME_INT_DOM));
00718     }
00719 
00720     if (x.size() == 2)
00721       GECODE_REWRITE(*this,Rel::Nq<View>::post(home(*this),x[0],x[1]));
00722     if (x.size() == 3)
00723       GECODE_REWRITE(*this,TerDom<View>::post(home(*this),x[0],x[1],x[2]));
00724 
00725     if (dc.available()) {
00726       GECODE_ES_CHECK(dc.sync(home));
00727     } else {
00728       GECODE_ES_CHECK(dc.init(home,x.size(),&x[0]));
00729     }
00730 
00731     bool assigned;
00732     GECODE_ES_CHECK(dc.propagate(home,assigned));
00733 
00734     return ES_FIX;
00735   }
00736 
00737 }}}
00738 
00739 // STATISTICS: int-prop
00740