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