dom-sup.hpp
Go to the documentation of this file.
00001 /* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */ 00002 /* 00003 * Main authors: 00004 * Patrick Pekczynski <pekczynski@ps.uni-sb.de> 00005 * 00006 * Contributing authors: 00007 * Christian Schulte <schulte@gecode.org> 00008 * Guido Tack <tack@gecode.org> 00009 * 00010 * Copyright: 00011 * Patrick Pekczynski, 2005 00012 * Christian Schulte, 2009 00013 * Guido Tack, 2009 00014 * 00015 * Last modified: 00016 * $Date: 2010-07-14 17:46:18 +0200 (Wed, 14 Jul 2010) $ by $Author: schulte $ 00017 * $Revision: 11192 $ 00018 * 00019 * This file is part of Gecode, the generic constraint 00020 * development environment: 00021 * http://www.gecode.org 00022 * 00023 * Permission is hereby granted, free of charge, to any person obtaining 00024 * a copy of this software and associated documentation files (the 00025 * "Software"), to deal in the Software without restriction, including 00026 * without limitation the rights to use, copy, modify, merge, publish, 00027 * distribute, sublicense, and/or sell copies of the Software, and to 00028 * permit persons to whom the Software is furnished to do so, subject to 00029 * the following conditions: 00030 * 00031 * The above copyright notice and this permission notice shall be 00032 * included in all copies or substantial portions of the Software. 00033 * 00034 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, 00035 * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF 00036 * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND 00037 * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE 00038 * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION 00039 * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION 00040 * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE. 00041 * 00042 */ 00043 00044 namespace Gecode { namespace Int { namespace GCC { 00045 00052 enum BC {UBC = 1, LBC = 0}; 00053 00054 class Edge; 00056 class Node { 00057 protected: 00059 Edge* e; 00061 Edge* fst; 00063 Edge* lst; 00065 Edge* ie; 00067 int idx; 00069 enum NodeFlag { 00071 NF_NONE = 0, 00073 NF_VAL = 1 << 0, 00075 NF_M_LBC = 1 << 1, 00077 NF_M_UBC = 1 << 2 00078 }; 00080 unsigned char nf; 00081 public: 00083 int noe; 00084 00086 00087 00088 Node(void); 00090 Node(NodeFlag nf, int i); 00092 00094 00095 00096 bool type(void) const; 00098 Edge** adj(void); 00100 Edge* first(void) const; 00102 Edge* last(void) const; 00104 Edge* inedge(void) const; 00106 int index(void) const; 00108 bool removed(void) const; 00110 00112 00113 00114 void first(Edge* p); 00116 void last(Edge* p); 00118 void inedge(Edge* p); 00120 void index(int i); 00122 00124 00125 00126 static void* operator new(size_t s, Space& home); 00128 static void operator delete(void*, Space&) {}; 00130 static void operator delete(void*) {}; 00132 }; 00133 00135 class VarNode : public Node { 00136 protected: 00138 Edge* ubm; 00140 Edge* lbm; 00141 public: 00143 00144 00145 VarNode(void); 00147 VarNode(int i); 00149 00151 00152 00153 Edge* get_match(BC bc) const; 00155 bool matched(BC bc) const; 00157 00159 00160 00161 void set_match(BC bc, Edge* m); 00163 void match(BC bc); 00165 void unmatch(BC bc); 00167 }; 00168 00170 class ValNode : public Node { 00171 protected: 00173 int _klb; 00175 int _kub; 00177 int _kidx; 00179 int _kcount; 00181 int noc; 00183 int lb; 00185 int ublow; 00187 int ub; 00188 public: 00190 int val; 00191 00193 00194 00195 ValNode(void); 00203 ValNode(int min, int max, int value, int kidx, int kshift, int count); 00205 00207 00208 00209 int maxlow(void) const; 00211 void card_conflict(int c); 00213 int card_conflict(void) const; 00215 void red_conflict(void); 00217 void inc(void); 00219 int kcount(void) const; 00221 int incid_match(BC bc) const; 00223 int kindex(void) const; 00225 bool matched(BC bc) const; 00227 bool sink(void) const; 00229 bool source(void) const; 00231 int kmin(void) const; 00233 int kmax(void) const; 00235 int kbound(BC bc) const; 00237 00239 00240 00241 void maxlow(int i); 00243 void kcount(int); 00245 void kindex(int); 00247 void dec(BC bc); 00249 void inc(BC bc); 00251 int cap(BC bc) const; 00253 void cap(BC bc, int c); 00255 void match(BC bc); 00257 void unmatch(BC bc); 00259 void reset(void); 00261 void kmin(int min); 00263 void kmax(int max); 00265 }; 00266 00268 class Edge { 00269 private: 00271 VarNode* x; 00273 ValNode* v; 00275 Edge* next_edge; 00277 Edge* prev_edge; 00279 Edge* next_vedge; 00281 Edge* prev_vedge; 00283 enum EdgeFlag { 00285 EF_NONE = 0, 00287 EF_MRKLB = 1 << 0, 00289 EF_MRKUB = 1 << 1, 00291 EF_LM = 1 << 2, 00293 EF_UM = 1 << 3, 00295 EF_DEL = 1 << 4 00296 }; 00298 unsigned char ef; 00299 public: 00301 00302 00303 Edge(void) {} 00308 Edge(VarNode* x, ValNode* v); 00310 00312 00313 00314 bool used(BC bc) const; 00316 bool matched(BC bc) const; 00318 bool deleted(void) const; 00324 Edge* next(bool t) const; 00326 Edge* next(void) const; 00328 Edge* prev(void) const; 00330 Edge* vnext(void) const; 00332 Edge* vprev(void) const; 00334 VarNode* getVar(void) const; 00336 ValNode* getVal(void) const; 00341 Node* getMate(bool t) const; 00343 00345 00346 00347 void use(BC bc); 00349 void free(BC bc); 00351 void reset(BC bc); 00353 void match(BC bc); 00355 void unmatch(BC bc); 00357 void unmatch(BC bc, bool t); 00359 void unlink(void); 00361 void del_edge(void); 00363 void insert_edge(void); 00365 Edge** next_ref(void); 00367 Edge** prev_ref(void); 00369 Edge** vnext_ref(void); 00371 Edge** vprev_ref(void); 00373 00375 00376 00377 static void* operator new(size_t s, Space& home); 00379 static void operator delete(void*, Space&) {}; 00381 static void operator delete(void*) {}; 00383 }; 00384 00385 00390 template<class Card> 00391 class VarValGraph { 00392 private: 00394 typedef Support::StaticStack<Node*,Region> NodeStack; 00396 typedef Support::BitSet<Region> BitSet; 00398 VarNode** vars; 00406 ValNode** vals; 00408 int n_var; 00414 int n_val; 00416 int n_node; 00422 int sum_min; 00428 int sum_max; 00429 public: 00431 00432 00438 VarValGraph(Space& home, 00439 ViewArray<IntView>& x, ViewArray<Card>& k, 00440 int smin, int smax); 00442 00443 00444 00445 ExecStatus min_require(Space& home, 00446 ViewArray<IntView>& x, ViewArray<Card>& k); 00447 00456 ExecStatus sync(Space& home, 00457 ViewArray<IntView>& x, ViewArray<Card>& k); 00459 template<BC> 00460 ExecStatus narrow(Space& home, 00461 ViewArray<IntView>& x, ViewArray<Card>& k); 00462 00469 template<BC> 00470 ExecStatus maximum_matching(Space& home); 00471 00473 template<BC> 00474 void free_alternating_paths(Space& home); 00476 template<BC> 00477 void strongly_connected_components(Space& home); 00483 template<BC> 00484 bool augmenting_path(Space& home, Node*); 00485 00486 protected: 00493 template<BC> 00494 void dfs(Node*, BitSet&, BitSet&, int[], 00495 NodeStack&, NodeStack&, int&); 00496 00498 public: 00500 void* operator new(size_t t, Space& home); 00502 void operator delete(void*, Space&) {} 00503 }; 00504 00505 00506 00507 /* 00508 * Nodes 00509 * 00510 */ 00511 forceinline 00512 Node::Node(void) {} 00513 forceinline 00514 Node::Node(NodeFlag nf0, int i) 00515 : e(NULL), fst(NULL), lst(NULL), ie(NULL), idx(i), 00516 nf(static_cast<unsigned char>(nf0)), noe(0) {} 00517 00518 forceinline Edge** 00519 Node::adj(void) { 00520 return &e; 00521 } 00522 forceinline Edge* 00523 Node::first(void) const { 00524 return fst; 00525 } 00526 forceinline Edge* 00527 Node::last(void) const { 00528 return lst; 00529 } 00530 forceinline void 00531 Node::first(Edge* p) { 00532 fst = p; 00533 } 00534 forceinline void 00535 Node::last(Edge* p) { 00536 lst = p; 00537 } 00538 forceinline bool 00539 Node::type(void) const { 00540 return (nf & NF_VAL) != 0; 00541 } 00542 forceinline Edge* 00543 Node::inedge(void) const { 00544 return ie; 00545 } 00546 forceinline void 00547 Node::inedge(Edge* p) { 00548 ie = p; 00549 } 00550 forceinline bool 00551 Node::removed(void) const { 00552 return noe == 0; 00553 } 00554 forceinline void 00555 Node::index(int i) { 00556 idx = i; 00557 } 00558 forceinline int 00559 Node::index(void) const { 00560 return idx; 00561 } 00562 00563 forceinline void* 00564 Node::operator new(size_t s, Space& home) { 00565 return home.ralloc(s); 00566 } 00567 00568 00569 00570 /* 00571 * Variable nodes 00572 * 00573 */ 00574 forceinline 00575 VarNode::VarNode(void) {} 00576 00577 forceinline 00578 VarNode::VarNode(int x) : 00579 Node(NF_NONE,x), ubm(NULL), lbm(NULL) {} 00580 00581 forceinline bool 00582 VarNode::matched(BC bc) const { 00583 if (bc == UBC) 00584 return (nf & NF_M_UBC) != 0; 00585 else 00586 return (nf & NF_M_LBC) != 0; 00587 } 00588 00589 forceinline void 00590 VarNode::match(BC bc) { 00591 if (bc == UBC) 00592 nf |= NF_M_UBC; 00593 else 00594 nf |= NF_M_LBC; 00595 } 00596 00597 forceinline void 00598 VarNode::set_match(BC bc, Edge* p) { 00599 if (bc == UBC) 00600 ubm = p; 00601 else 00602 lbm = p; 00603 } 00604 00605 forceinline void 00606 VarNode::unmatch(BC bc) { 00607 if (bc == UBC) { 00608 nf &= ~NF_M_UBC; ubm = NULL; 00609 } else { 00610 nf &= ~NF_M_LBC; lbm = NULL; 00611 } 00612 } 00613 00614 forceinline Edge* 00615 VarNode::get_match(BC bc) const { 00616 if (bc == UBC) 00617 return ubm; 00618 else 00619 return lbm; 00620 } 00621 00622 00623 00624 00625 /* 00626 * Value nodes 00627 * 00628 */ 00629 forceinline 00630 ValNode::ValNode(void) {} 00631 00632 forceinline 00633 ValNode::ValNode(int min, int max, int value, 00634 int kidx, int kshift, int count) : 00635 Node(NF_VAL,kshift), _klb(min), _kub(max), _kidx(kidx), _kcount(count), 00636 noc(0), 00637 lb(min), ublow(max), ub(max), 00638 val(value) {} 00639 00640 forceinline void 00641 ValNode::maxlow(int i) { 00642 assert(i >= lb); 00643 ublow = i; 00644 } 00645 00646 forceinline int 00647 ValNode::maxlow(void) const { 00648 if (_klb == _kub) { 00649 assert(ublow == lb); 00650 } 00651 return ublow; 00652 } 00653 00654 00655 forceinline void 00656 ValNode::card_conflict(int c) { 00657 noc = c; 00658 } 00659 00660 forceinline void 00661 ValNode::red_conflict(void) { 00662 noc--; 00663 assert(noc >= 0); 00664 } 00665 00666 forceinline int 00667 ValNode::card_conflict(void) const { 00668 return noc; 00669 } 00670 00671 forceinline int 00672 ValNode::cap(BC bc) const { 00673 if (bc == UBC) 00674 return ub; 00675 else 00676 return lb; 00677 } 00678 forceinline bool 00679 ValNode::matched(BC bc) const { 00680 return cap(bc) == 0; 00681 } 00682 00683 forceinline void 00684 ValNode::reset(void) { 00685 lb = _klb; 00686 ublow = _kub; 00687 ub = _kub; 00688 noe = 0; 00689 } 00690 00691 forceinline int 00692 ValNode::kbound(BC bc) const { 00693 if (bc == UBC) { 00694 return _kub; 00695 } else { 00696 return _klb; 00697 } 00698 } 00699 00700 forceinline int 00701 ValNode::kmax(void) const { 00702 return _kub; 00703 } 00704 00705 forceinline int 00706 ValNode::kmin(void) const { 00707 return _klb; 00708 } 00709 00710 forceinline void 00711 ValNode::kmin(int klb) { 00712 _klb = klb; 00713 } 00714 00715 forceinline void 00716 ValNode::kmax(int kub) { 00717 _kub = kub; 00718 } 00719 00720 00721 forceinline void 00722 ValNode::dec(BC bc) { 00723 if (bc == UBC) { 00724 ub--; 00725 } else { 00726 lb--; ublow--; 00727 } 00728 } 00729 00730 forceinline void 00731 ValNode::inc(BC bc) { 00732 if (bc == UBC) { 00733 ub++; 00734 } else { 00735 lb++; ublow++; 00736 } 00737 } 00738 00739 forceinline void 00740 ValNode::match(BC bc) { 00741 dec(bc); 00742 } 00743 00744 forceinline void 00745 ValNode::unmatch(BC bc) { 00746 inc(bc); 00747 } 00748 00749 forceinline void 00750 ValNode::cap(BC bc, int c) { 00751 if (bc == UBC) 00752 ub = c; 00753 else 00754 lb = c; 00755 } 00756 00757 forceinline void 00758 ValNode::inc(void) { 00759 _kcount++; 00760 } 00761 00762 forceinline int 00763 ValNode::kcount(void) const { 00764 return _kcount; 00765 } 00766 00767 forceinline void 00768 ValNode::kcount(int c) { 00769 _kcount = c; 00770 } 00771 00772 forceinline void 00773 ValNode::kindex(int i) { 00774 _kidx = i; 00775 } 00776 00777 forceinline int 00778 ValNode::kindex(void) const { 00779 return _kidx; 00780 } 00781 00783 forceinline int 00784 ValNode::incid_match(BC bc) const { 00785 if (bc == LBC) 00786 return _kub - ublow + _kcount; 00787 else 00788 return _kub - ub + _kcount; 00789 } 00790 00791 00792 forceinline bool 00793 ValNode::sink(void) const { 00794 // there are only incoming edges 00795 // in case of the UBC-matching 00796 return _kub - ub == noe; 00797 } 00798 00799 forceinline bool 00800 ValNode::source(void) const { 00801 // there are only incoming edges 00802 // in case of the UBC-matching 00803 return _klb - lb == noe; 00804 } 00805 00806 00807 00808 /* 00809 * Edges 00810 * 00811 */ 00812 forceinline void 00813 Edge::unlink(void) { 00814 // unlink from variable side 00815 Edge* p = prev_edge; 00816 Edge* n = next_edge; 00817 00818 if (p != NULL) 00819 *p->next_ref() = n; 00820 if (n != NULL) 00821 *n->prev_ref() = p; 00822 00823 if (this == x->first()) { 00824 Edge** ref = x->adj(); 00825 *ref = n; 00826 x->first(n); 00827 } 00828 00829 if (this == x->last()) 00830 x->last(p); 00831 00832 // unlink from value side 00833 Edge* pv = prev_vedge; 00834 Edge* nv = next_vedge; 00835 00836 if (pv != NULL) 00837 *pv->vnext_ref() = nv; 00838 if (nv != NULL) 00839 *nv->vprev_ref() = pv; 00840 if (this == v->first()) { 00841 Edge** ref = v->adj(); 00842 *ref = nv; 00843 v->first(nv); 00844 } 00845 if (this == v->last()) 00846 v->last(pv); 00847 } 00848 00849 forceinline 00850 Edge::Edge(VarNode* var, ValNode* val) : 00851 x(var), v(val), 00852 next_edge(NULL), prev_edge(NULL), 00853 next_vedge(NULL), prev_vedge(NULL), ef(EF_NONE) {} 00854 00855 forceinline void 00856 Edge::use(BC bc) { 00857 if (bc == UBC) 00858 ef |= EF_MRKUB; 00859 else 00860 ef |= EF_MRKLB; 00861 } 00862 forceinline void 00863 Edge::free(BC bc) { 00864 if (bc == UBC) 00865 ef &= ~EF_MRKUB; 00866 else 00867 ef &= ~EF_MRKLB; 00868 } 00869 forceinline bool 00870 Edge::used(BC bc) const { 00871 if (bc == UBC) 00872 return (ef & EF_MRKUB) != 0; 00873 else 00874 return (ef & EF_MRKLB) != 0; 00875 } 00876 forceinline Edge* 00877 Edge::next(void) const { 00878 return next_edge; 00879 } 00880 forceinline Edge* 00881 Edge::next(bool t) const { 00882 if (t) { 00883 return next_vedge; 00884 } else { 00885 return next_edge; 00886 } 00887 } 00888 00889 forceinline Edge* 00890 Edge::vnext(void) const { 00891 return next_vedge; 00892 } 00893 forceinline Edge** 00894 Edge::vnext_ref(void) { 00895 return &next_vedge; 00896 } 00897 forceinline Edge* 00898 Edge::prev(void) const { 00899 return prev_edge; 00900 } 00901 forceinline Edge** 00902 Edge::prev_ref(void) { 00903 return &prev_edge; 00904 } 00905 forceinline Edge* 00906 Edge::vprev(void) const { 00907 return prev_vedge; 00908 } 00909 forceinline Edge** 00910 Edge::vprev_ref(void) { 00911 return &prev_vedge; 00912 } 00913 forceinline Edge** 00914 Edge::next_ref(void) { 00915 return &next_edge; 00916 } 00917 forceinline VarNode* 00918 Edge::getVar(void) const { 00919 assert(x != NULL); 00920 return x; 00921 } 00922 00923 forceinline ValNode* 00924 Edge::getVal(void) const { 00925 assert(v != NULL); 00926 return v; 00927 } 00928 00929 forceinline Node* 00930 Edge::getMate(bool type) const { 00931 if (type) 00932 return x; 00933 else 00934 return v; 00935 } 00936 00937 forceinline void 00938 Edge::unmatch(BC bc) { 00939 if (bc == UBC) 00940 ef &= ~EF_UM; 00941 else 00942 ef &= ~EF_LM; 00943 x->unmatch(bc); v->unmatch(bc); 00944 } 00945 00946 forceinline void 00947 Edge::unmatch(BC bc, bool node) { 00948 if (bc == UBC) 00949 ef &= ~EF_UM; 00950 else 00951 ef &= ~EF_LM; 00952 if (node) 00953 v->unmatch(bc); 00954 else 00955 x->unmatch(bc); 00956 } 00957 00958 forceinline void 00959 Edge::reset(BC bc) { 00960 free(bc); unmatch(bc); 00961 } 00962 00963 forceinline void 00964 Edge::match(BC bc) { 00965 if (bc == UBC) 00966 ef |= EF_UM; 00967 else 00968 ef |= EF_LM; 00969 x->match(bc); 00970 x->set_match(bc,this); 00971 v->match(bc); 00972 } 00973 00974 forceinline bool 00975 Edge::matched(BC bc) const { 00976 if (bc == UBC) 00977 return (ef & EF_UM) != 0; 00978 else 00979 return (ef & EF_LM) != 0; 00980 } 00981 00982 forceinline void 00983 Edge::del_edge(void) { 00984 ef |= EF_DEL; 00985 } 00986 00987 forceinline void 00988 Edge::insert_edge(void) { 00989 ef &= ~EF_DEL; 00990 } 00991 00992 00993 forceinline bool 00994 Edge::deleted(void) const { 00995 return (ef & EF_DEL) != 0; 00996 } 00997 00998 forceinline void* 00999 Edge::operator new(size_t s, Space& home) { 01000 return home.ralloc(s); 01001 } 01002 01003 01004 /* 01005 * Variable value graph 01006 * 01007 */ 01008 template<class Card> 01009 VarValGraph<Card>::VarValGraph(Space& home, 01010 ViewArray<IntView>& x, ViewArray<Card>& k, 01011 int smin, int smax) 01012 : n_var(x.size()), 01013 n_val(k.size()), 01014 n_node(n_var + n_val), 01015 sum_min(smin), 01016 sum_max(smax) { 01017 01018 unsigned int noe = 0; 01019 for (int i=x.size(); i--; ) 01020 noe += x[i].size(); 01021 01022 vars = home.alloc<VarNode*>(n_var); 01023 vals = home.alloc<ValNode*>(n_val); 01024 01025 for (int i = n_val; i--; ) { 01026 int kmi = k[i].min(); 01027 int kma = k[i].max(); 01028 int kc = k[i].counter(); 01029 if (kc != kma) { 01030 if (kmi >= kc) { 01031 kmi -=kc; 01032 assert(kmi >=0); 01033 } else { 01034 kmi = 0; 01035 } 01036 kma -= kc; 01037 assert (kma > 0); 01038 vals[i] = new (home) 01039 ValNode(kmi, kma, k[i].card(), i, i + n_var, kc); 01040 } else { 01041 vals[i] = new (home) 01042 ValNode(0, 0, k[i].card(), i, i + n_var, kc); 01043 } 01044 } 01045 01046 for (int i = n_var; i--; ) { 01047 vars[i] = new (home) VarNode(i); 01048 // get the space for the edges of the varnode 01049 Edge** xadjacent = vars[i]->adj(); 01050 01051 int j = 0; 01052 for (ViewValues<IntView> xi(x[i]); xi(); ++xi) { 01053 // get the correct index for the value 01054 while(vals[j]->val < xi.val()) 01055 j++; 01056 *xadjacent = new (home) Edge(vars[i],vals[j]); 01057 vars[i]->noe++; 01058 if (vars[i]->first() == NULL) 01059 vars[i]->first(*xadjacent); 01060 Edge* oldprev = vars[i]->last(); 01061 vars[i]->last(*xadjacent); 01062 *vars[i]->last()->prev_ref() = oldprev; 01063 01064 if (vals[j]->first() == NULL) { 01065 vals[j]->first(*xadjacent); 01066 vals[j]->last(*xadjacent); 01067 } else { 01068 Edge* old = vals[j]->first(); 01069 vals[j]->first(*xadjacent); 01070 *vals[j]->first()->vnext_ref() = old; 01071 *old->vprev_ref() = vals[j]->first(); 01072 } 01073 vals[j]->noe++; 01074 xadjacent = (*xadjacent)->next_ref(); 01075 } 01076 *xadjacent = NULL; 01077 } 01078 } 01079 01080 01081 template<class Card> 01082 inline ExecStatus 01083 VarValGraph<Card>::min_require(Space& home, 01084 ViewArray<IntView>& x, 01085 ViewArray<Card>& k) { 01086 for (int i = n_val; i--; ) { 01087 ValNode* vln = vals[i]; 01088 if (vln->noe > 0) { 01089 if (k[i].min() == vln->noe) { 01090 // all variable nodes reachable from vln should be equal to vln->val 01091 for (Edge* e = vln->first(); e != NULL; e = e->vnext()) { 01092 VarNode* vrn = e->getVar(); 01093 for (Edge* f = vrn->first(); f != NULL; f = f->next()) 01094 if (f != e) { 01095 ValNode* w = f->getVal(); 01096 w->noe--; 01097 vrn->noe--; 01098 f->del_edge(); 01099 f->unlink(); 01100 } 01101 assert(vrn->noe == 1); 01102 01103 int vi = vrn->index(); 01104 GECODE_ME_CHECK(x[vi].eq(home, vln->val)); 01105 01106 vars[vi] = vars[--n_var]; 01107 vars[vi]->index(vi); 01108 x.move_lst(vi); 01109 n_node--; 01110 vln->noe--; 01111 } 01112 01113 01114 int vidx = vln->kindex(); 01115 if (Card::propagate) 01116 GECODE_ME_CHECK(k[vidx].eq(home, k[vidx].min())); 01117 01118 k[vidx].counter(k[vidx].min()); 01119 01120 vln->cap(UBC,0); 01121 vln->cap(LBC,0); 01122 vln->maxlow(0); 01123 01124 if (sum_min >= k[vidx].min()) 01125 sum_min -= k[vidx].min(); 01126 if (sum_max >= k[vidx].max()) 01127 sum_max -= k[vidx].max(); 01128 } 01129 } else { 01130 vals[i]->cap(UBC,0); 01131 vals[i]->cap(LBC,0); 01132 vals[i]->maxlow(0); 01133 vals[i]->kmax(0); 01134 vals[i]->kmin(0); 01135 } 01136 01137 if (Card::propagate && (k[i].counter() == 0)) 01138 GECODE_ME_CHECK(k[i].lq(home, vals[i]->noe)); 01139 } 01140 01141 for (int i = n_val; i--; ) 01142 vals[i]->index(n_var + i); 01143 01144 return ES_OK; 01145 } 01146 01147 template<class Card> 01148 inline ExecStatus 01149 VarValGraph<Card>::sync(Space& home, 01150 ViewArray<IntView>& x, ViewArray<Card>& k) { 01151 Region r(home); 01152 // A node can be pushed twice (once when checking cardinality and later again) 01153 NodeStack re(r,2*n_node); 01154 01155 // synchronize cardinality variables 01156 if (Card::propagate) { 01157 for (int i = n_val; i--; ) { 01158 ValNode* v = vals[i]; 01159 int inc_ubc = v->incid_match(UBC); 01160 int inc_lbc = v->incid_match(LBC); 01161 if (v->noe == 0) { 01162 inc_ubc = 0; 01163 inc_lbc = 0; 01164 } 01165 int rm = v->kmax() - k[i].max(); 01166 // the cardinality bounds have been modified 01167 if ((k[i].max() < v->kmax()) || (k[i].min() > v->kmin())) { 01168 if ((k[i].max() != k[i].counter()) || (k[i].max() == 0)) { 01169 // update the bounds 01170 v->kmax(k[i].max()); 01171 v->kmin(k[i].min()); 01172 01173 //everything is fine 01174 if (inc_ubc <= k[i].max()) { 01175 // adjust capacities 01176 v->cap(UBC, k[i].max() - inc_ubc); 01177 v->maxlow(k[i].max() - inc_lbc); 01178 if (v->kmin() == v->kmax()) 01179 v->cap(LBC, k[i].max() - inc_lbc); 01180 } else { 01181 // set cap to max and resolve conflicts on view side 01182 // set to full capacity for later rescheduling 01183 if (v->cap(UBC)) 01184 v->cap(UBC,k[i].max()); 01185 v->maxlow(k[i].max() - (inc_lbc)); 01186 if (v->kmin() == v->kmax()) 01187 v->cap(LBC,k[i].max() - (inc_lbc)); 01188 v->card_conflict(rm); 01189 } 01190 } 01191 } 01192 if (inc_lbc < k[i].min() && v->noe > 0) { 01193 v->cap(LBC, k[i].min() - inc_lbc); 01194 re.push(v); 01195 } 01196 } 01197 01198 for (int i = n_var; i--; ) { 01199 Edge* mub = vars[i]->get_match(UBC); 01200 if (mub != NULL) { 01201 ValNode* vu = mub->getVal(); 01202 if ((vars[i]->noe != 1) && vu->card_conflict()) { 01203 vu->red_conflict(); 01204 mub->unmatch(UBC,vars[i]->type()); 01205 re.push(vars[i]); 01206 } 01207 } 01208 } 01209 } 01210 01211 // go on with synchronization 01212 assert(x.size() == n_var); 01213 for (int i = n_var; i--; ) { 01214 01215 VarNode* vrn = vars[i]; 01216 if (static_cast<int>(x[i].size()) != vrn->noe) { 01217 // if the variable is already assigned 01218 if (x[i].assigned()) { 01219 int v = x[i].val(); 01220 ValNode* rv = NULL; 01221 int rv_idx = 0; 01222 Edge* mub = vrn->get_match(UBC); 01223 if ((mub != NULL) && (v != mub->getVal()->val)) { 01224 mub->unmatch(UBC); 01225 re.push(vars[i]); 01226 } 01227 01228 Edge* mlb = vrn->get_match(LBC); 01229 if (mlb != NULL) { 01230 ValNode* vln = mlb->getVal(); 01231 if (v != vln->val) { 01232 mlb->unmatch(LBC); 01233 if (vln->incid_match(LBC) < vln->kmin()) 01234 re.push(vln); 01235 } 01236 } 01237 01238 for (Edge* e = vrn->first(); e != NULL; e = e->next()) { 01239 ValNode* vln = e->getVal(); 01240 if (vln->val != v) { 01241 vrn->noe--; 01242 e->getVal()->noe--; 01243 e->del_edge(); 01244 e->unlink(); 01245 } else { 01246 rv = e->getVal(); 01247 rv_idx = rv->kindex(); 01248 } 01249 } 01250 } else { 01251 01252 // delete the edge 01253 ViewValues<IntView> xiter(x[i]); 01254 Edge* mub = vrn->get_match(UBC); 01255 Edge* mlb = vrn->get_match(LBC); 01256 Edge** p = vrn->adj(); 01257 Edge* e = *p; 01258 do { 01259 // search the edge that has to be deleted 01260 while (e != NULL && (e->getVal()->val < xiter.val())) { 01261 // Skip edge 01262 e->getVal()->noe--; 01263 vrn->noe--; 01264 e->del_edge(); 01265 e->unlink(); 01266 e = e ->next(); 01267 *p = e; 01268 } 01269 01270 assert(xiter.val() == e->getVal()->val); 01271 01272 // This edge must be kept 01273 e->free(UBC); 01274 e->free(LBC); 01275 ++xiter; 01276 p = e->next_ref(); 01277 e = e->next(); 01278 } while (xiter()); 01279 *p = NULL; 01280 while (e) { 01281 e->getVar()->noe--; 01282 e->getVal()->noe--; 01283 e->del_edge(); 01284 e->unlink(); 01285 e = e->next(); 01286 } 01287 01288 if ((mub != NULL) && mub->deleted()) { 01289 mub->unmatch(UBC); 01290 re.push(vars[i]); 01291 } 01292 01293 //lower bound matching can be zero 01294 if ((mlb != NULL) && mlb->deleted()) { 01295 ValNode* vln = mlb->getVal(); 01296 mlb->unmatch(LBC); 01297 if (vln->incid_match(LBC) < vln->kmin()) 01298 re.push(vln); 01299 } 01300 } 01301 } 01302 vars[i]->index(i); 01303 } 01304 01305 for (int i = n_val; i--; ) { 01306 if ((k[i].min() > vals[i]->noe) && (k[i].counter() == 0)) 01307 return ES_FAILED; 01308 vals[i]->index(n_var + i); 01309 } 01310 01311 // start repair 01312 while (!re.empty()) { 01313 Node* n = re.pop(); 01314 if (!n->removed()) { 01315 if (!n->type()) { 01316 VarNode* vrn = static_cast<VarNode*>(n); 01317 if (!vrn->matched(UBC) && !augmenting_path<UBC>(home,vrn)) 01318 return ES_FAILED; 01319 } else { 01320 ValNode* vln = static_cast<ValNode*>(n); 01321 while (!vln->matched(LBC)) 01322 if (!augmenting_path<LBC>(home,vln)) 01323 return ES_FAILED; 01324 } 01325 } 01326 } 01327 01328 return ES_OK; 01329 } 01330 01331 template<class Card> template<BC bc> 01332 inline ExecStatus 01333 VarValGraph<Card>::narrow(Space& home, 01334 ViewArray<IntView>& x, ViewArray<Card>& k) { 01335 for (int i = n_var; i--; ) 01336 if (vars[i]->noe == 1) { 01337 ValNode* v = vars[i]->first()->getVal(); 01338 vars[i]->first()->free(bc); 01339 GECODE_ME_CHECK(x[i].eq(home, v->val)); 01340 v->inc(); 01341 } 01342 01343 for (int i = n_val; i--; ) { 01344 ValNode* v = vals[i]; 01345 if (Card::propagate && (k[i].counter() == 0)) 01346 GECODE_ME_CHECK(k[i].lq(home, v->noe)); 01347 if (v->noe > 0) { 01348 if (Card::propagate) 01349 GECODE_ME_CHECK(k[i].lq(home, v->noe)); 01350 01351 // If the maximum number of occurences of a value is reached 01352 // it cannot be consumed by another view 01353 01354 if (v->kcount() == v->kmax()) { 01355 int vidx = v->kindex(); 01356 01357 k[i].counter(v->kcount()); 01358 01359 if (Card::propagate) 01360 GECODE_ME_CHECK(k[i].eq(home, k[i].counter())); 01361 01362 bool delall = v->card_conflict() && (v->noe > v->kmax()); 01363 01364 for (Edge* e = v->last(); e != NULL; e = e->vprev()) { 01365 VarNode* vrn = e->getVar(); 01366 if (vrn->noe == 1) { 01367 vrn->noe--; 01368 v->noe--; 01369 int vi= vrn->index(); 01370 01371 x.move_lst(vi); 01372 vars[vi] = vars[--n_var]; 01373 vars[vi]->index(vi); 01374 n_node--; 01375 e->del_edge(); 01376 e->unlink(); 01377 01378 } else if (delall) { 01379 GECODE_ME_CHECK(x[vrn->index()].nq(home, v->val)); 01380 vrn->noe--; 01381 v->noe--; 01382 e->del_edge(); 01383 e->unlink(); 01384 } 01385 } 01386 v->cap(UBC,0); 01387 v->cap(LBC,0); 01388 v->maxlow(0); 01389 if (sum_min >= k[vidx].min()) 01390 sum_min -= k[vidx].min(); 01391 if (sum_max >= k[vidx].max()) 01392 sum_max -= k[vidx].max(); 01393 01394 } else if (v->kcount() > 0) { 01395 v->kcount(0); 01396 } 01397 } 01398 } 01399 for (int i = n_var; i--; ) 01400 vars[i]->index(i); 01401 01402 for (int i = n_val; i--; ) { 01403 if (vals[i]->noe == 0) { 01404 vals[i]->cap(UBC,0); 01405 vals[i]->cap(LBC,0); 01406 vals[i]->maxlow(0); 01407 } 01408 vals[i]->index(n_var + i); 01409 } 01410 01411 for (int i = n_var; i--; ) 01412 if (vars[i]->noe > 1) 01413 for (Edge* e = vars[i]->first(); e != NULL; e = e->next()) 01414 if (!e->matched(bc) && !e->used(bc)) { 01415 GECODE_ME_CHECK(x[i].nq(home, e->getVal()->val)); 01416 } else { 01417 e->free(bc); 01418 } 01419 01420 return ES_OK; 01421 } 01422 01423 template<class Card> template<BC bc> 01424 forceinline bool 01425 VarValGraph<Card>::augmenting_path(Space& home, Node* v) { 01426 Region r(home); 01427 NodeStack ns(r,n_node); 01428 BitSet visited(r,static_cast<unsigned int>(n_node)); 01429 Edge** start = r.alloc<Edge*>(n_node); 01430 01431 // keep track of the nodes that have already been visited 01432 Node* sn = v; 01433 01434 // mark the start partition 01435 bool sp = sn->type(); 01436 01437 // nodes in sp only follow free edges 01438 // nodes in V - sp only follow matched edges 01439 01440 for (int i = n_node; i--; ) 01441 if (i >= n_var) { 01442 vals[i-n_var]->inedge(NULL); 01443 start[i] = vals[i-n_var]->first(); 01444 } else { 01445 vars[i]->inedge(NULL); 01446 start[i] = vars[i]->first(); 01447 } 01448 01449 v->inedge(NULL); 01450 ns.push(v); 01451 visited.set(static_cast<unsigned int>(v->index())); 01452 while (!ns.empty()) { 01453 Node* v = ns.top(); 01454 Edge* e = NULL; 01455 if (v->type() == sp) { 01456 e = start[v->index()]; 01457 while ((e != NULL) && e->matched(bc)) 01458 e = e->next(v->type()); 01459 } else { 01460 e = start[v->index()]; 01461 while ((e != NULL) && !e->matched(bc)) 01462 e = e->next(v->type()); 01463 start[v->index()] = e; 01464 } 01465 if (e != NULL) { 01466 start[v->index()] = e->next(v->type()); 01467 Node* w = e->getMate(v->type()); 01468 if (!visited.get(static_cast<unsigned int>(w->index()))) { 01469 // unexplored path 01470 bool m = w->type() ? 01471 static_cast<ValNode*>(w)->matched(bc) : 01472 static_cast<VarNode*>(w)->matched(bc); 01473 if (!m && w->type() != sp) { 01474 if (v->inedge() != NULL) { 01475 // augmenting path of length l > 1 01476 e->match(bc); 01477 break; 01478 } else { 01479 // augmenting path of length l = 1 01480 e->match(bc); 01481 ns.pop(); 01482 return true; 01483 } 01484 } else { 01485 w->inedge(e); 01486 visited.set(static_cast<unsigned int>(w->index())); 01487 // find matching edge m incident with w 01488 ns.push(w); 01489 } 01490 } 01491 } else { 01492 // tried all outgoing edges without finding an augmenting path 01493 ns.pop(); 01494 } 01495 } 01496 01497 bool pathfound = !ns.empty(); 01498 01499 while (!ns.empty()) { 01500 Node* t = ns.pop(); 01501 if (t != sn) { 01502 Edge* in = t->inedge(); 01503 if (t->type() != sp) { 01504 in->match(bc); 01505 } else if (!sp) { 01506 in->unmatch(bc,!sp); 01507 } else { 01508 in->unmatch(bc); 01509 } 01510 } 01511 } 01512 return pathfound; 01513 } 01514 01515 template<class Card> template<BC bc> 01516 inline ExecStatus 01517 VarValGraph<Card>::maximum_matching(Space& home) { 01518 int card_match = 0; 01519 // find an intial matching in O(n*d) 01520 // greedy algorithm 01521 for (int i = n_val; i--; ) 01522 for (Edge* e = vals[i]->first(); e != NULL ; e = e->vnext()) 01523 if (!e->getVar()->matched(bc) && !vals[i]->matched(bc)) { 01524 e->match(bc); card_match++; 01525 } 01526 01527 Region r(home); 01528 switch (bc) { 01529 case LBC: 01530 if (card_match < sum_min) { 01531 Support::StaticStack<ValNode*,Region> free(r,n_val); 01532 01533 // find failed nodes 01534 for (int i = n_val; i--; ) 01535 if (!vals[i]->matched(LBC)) 01536 free.push(vals[i]); 01537 01538 while (!free.empty()) { 01539 ValNode* v = free.pop(); 01540 while (!v->matched(LBC)) 01541 if (augmenting_path<LBC>(home,v)) 01542 card_match++; 01543 else 01544 break; 01545 } 01546 01547 return (card_match >= sum_min) ? ES_OK : ES_FAILED; 01548 } else { 01549 return ES_OK; 01550 } 01551 break; 01552 case UBC: 01553 if (card_match < n_var) { 01554 Support::StaticStack<VarNode*,Region> free(r,n_var); 01555 01556 // find failed nodes 01557 for (int i = n_var; i--; ) 01558 if (!vars[i]->matched(UBC)) 01559 free.push(vars[i]); 01560 01561 while (!free.empty()) { 01562 VarNode* v = free.pop(); 01563 if (!v->matched(UBC) && augmenting_path<UBC>(home,v)) 01564 card_match++; 01565 } 01566 01567 return (card_match >= n_var) ? ES_OK : ES_FAILED; 01568 } else { 01569 return ES_OK; 01570 } 01571 break; 01572 default: GECODE_NEVER; 01573 } 01574 GECODE_NEVER; 01575 return ES_FAILED; 01576 } 01577 01578 01579 template<class Card> template<BC bc> 01580 forceinline void 01581 VarValGraph<Card>::free_alternating_paths(Space& home) { 01582 Region r(home); 01583 NodeStack ns(r,n_node); 01584 BitSet visited(r,static_cast<unsigned int>(n_node)); 01585 01586 switch (bc) { 01587 case LBC: 01588 // after a maximum matching on the value nodes there still can be 01589 // free value nodes, hence we have to consider ALL nodes whether 01590 // they are the starting point of an even alternating path in G 01591 for (int i = n_var; i--; ) 01592 if (!vars[i]->matched(LBC)) { 01593 ns.push(vars[i]); 01594 visited.set(static_cast<unsigned int>(vars[i]->index())); 01595 } 01596 for (int i = n_val; i--; ) 01597 if (!vals[i]->matched(LBC)) { 01598 ns.push(vals[i]); 01599 visited.set(static_cast<unsigned int>(vals[i]->index())); 01600 } 01601 break; 01602 case UBC: 01603 // clearly, after a maximum matching on the x variables 01604 // corresponding to a set cover on x there are NO free var nodes 01605 for (int i = n_val; i--; ) 01606 if (!vals[i]->matched(UBC)) { 01607 ns.push(vals[i]); 01608 visited.set(static_cast<unsigned int>(vals[i]->index())); 01609 } 01610 break; 01611 default: GECODE_NEVER; 01612 } 01613 01614 while (!ns.empty()) { 01615 Node* node = ns.pop(); 01616 if (node->type()) { 01617 // ValNode 01618 ValNode* vln = static_cast<ValNode*>(node); 01619 01620 for (Edge* cur = vln->first(); cur != NULL; cur = cur->vnext()) { 01621 VarNode* mate = cur->getVar(); 01622 switch (bc) { 01623 case LBC: 01624 if (cur->matched(LBC)) { 01625 // mark the edge 01626 cur->use(LBC); 01627 if (!visited.get(static_cast<unsigned int>(mate->index()))) { 01628 ns.push(mate); 01629 visited.set(static_cast<unsigned int>(mate->index())); 01630 } 01631 } 01632 break; 01633 case UBC: 01634 if (!cur->matched(UBC)) { 01635 // mark the edge 01636 cur->use(UBC); 01637 if (!visited.get(static_cast<unsigned int>(mate->index()))) { 01638 ns.push(mate); 01639 visited.set(static_cast<unsigned int>(mate->index())); 01640 } 01641 } 01642 break; 01643 default: GECODE_NEVER; 01644 } 01645 } 01646 01647 } else { 01648 // VarNode 01649 VarNode* vrn = static_cast<VarNode*>(node); 01650 01651 switch (bc) { 01652 case LBC: 01653 // after LBC-matching we can follow every unmatched edge 01654 for (Edge* cur = vrn->first(); cur != NULL; cur = cur->next()) { 01655 ValNode* mate = cur->getVal(); 01656 if (!cur->matched(LBC)) { 01657 cur->use(LBC); 01658 if (!visited.get(static_cast<unsigned int>(mate->index()))) { 01659 ns.push(mate); 01660 visited.set(static_cast<unsigned int>(mate->index())); 01661 } 01662 } 01663 } 01664 break; 01665 case UBC: 01666 // after UBC-matching we can only follow a matched edge 01667 { 01668 Edge* cur = vrn->get_match(UBC); 01669 if (cur != NULL) { 01670 cur->use(UBC); 01671 ValNode* mate = cur->getVal(); 01672 if (!visited.get(static_cast<unsigned int>(mate->index()))) { 01673 ns.push(mate); 01674 visited.set(static_cast<unsigned int>(mate->index())); 01675 } 01676 } 01677 } 01678 break; 01679 default: GECODE_NEVER; 01680 } 01681 } 01682 } 01683 } 01684 01685 template<class Card> template<BC bc> 01686 void 01687 VarValGraph<Card>::dfs(Node* v, 01688 BitSet& inscc, BitSet& in_unfinished, int dfsnum[], 01689 NodeStack& roots, NodeStack& unfinished, 01690 int& count) { 01691 count++; 01692 int v_index = v->index(); 01693 dfsnum[v_index] = count; 01694 inscc.set(static_cast<unsigned int>(v_index)); 01695 in_unfinished.set(static_cast<unsigned int>(v_index)); 01696 01697 unfinished.push(v); 01698 roots.push(v); 01699 for (Edge* e = v->first(); e != NULL; e = e->next(v->type())) { 01700 bool m; 01701 switch (bc) { 01702 case LBC: 01703 m = v->type() ? e->matched(LBC) : !e->matched(LBC); 01704 break; 01705 case UBC: 01706 m = v->type() ? !e->matched(UBC) : e->matched(UBC); 01707 break; 01708 default: GECODE_NEVER; 01709 } 01710 if (m) { 01711 Node* w = e->getMate(v->type()); 01712 int w_index = w->index(); 01713 01714 assert(w_index < n_node); 01715 if (!inscc.get(static_cast<unsigned int>(w_index))) { 01716 // w is an uncompleted scc 01717 w->inedge(e); 01718 dfs<bc>(w, inscc, in_unfinished, dfsnum, 01719 roots, unfinished, count); 01720 } else if (in_unfinished.get(static_cast<unsigned int>(w_index))) { 01721 // even alternating cycle found mark the edge closing the cycle, 01722 // completing the scc 01723 e->use(bc); 01724 // if w belongs to an scc we detected earlier 01725 // merge components 01726 assert(roots.top()->index() < n_node); 01727 while (dfsnum[roots.top()->index()] > dfsnum[w_index]) { 01728 roots.pop(); 01729 } 01730 } 01731 } 01732 } 01733 01734 if (v == roots.top()) { 01735 while (v != unfinished.top()) { 01736 // w belongs to the scc with root v 01737 Node* w = unfinished.top(); 01738 w->inedge()->use(bc); 01739 in_unfinished.clear(static_cast<unsigned int>(w->index())); 01740 unfinished.pop(); 01741 } 01742 assert(v == unfinished.top()); 01743 in_unfinished.clear(static_cast<unsigned int>(v_index)); 01744 roots.pop(); 01745 unfinished.pop(); 01746 } 01747 } 01748 01749 template<class Card> template<BC bc> 01750 forceinline void 01751 VarValGraph<Card>::strongly_connected_components(Space& home) { 01752 Region r(home); 01753 BitSet inscc(r,static_cast<unsigned int>(n_node)); 01754 BitSet in_unfinished(r,static_cast<unsigned int>(n_node)); 01755 int* dfsnum = r.alloc<int>(n_node); 01756 01757 for (int i = n_node; i--; ) 01758 dfsnum[i]=0; 01759 01760 int count = 0; 01761 NodeStack roots(r,n_node); 01762 NodeStack unfinished(r,n_node); 01763 01764 for (int i = n_var; i--; ) 01765 dfs<bc>(vars[i], inscc, in_unfinished, dfsnum, 01766 roots, unfinished, count); 01767 } 01768 01769 template<class Card> 01770 forceinline void* 01771 VarValGraph<Card>::operator new(size_t t, Space& home) { 01772 return home.ralloc(t); 01773 } 01774 01775 }}} 01776 01777 // STATISTICS: int-prop 01778 01779