00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021
00022
00023
00024
00025
00026
00027
00028
00029
00030
00031
00032
00033
00034
00035
00036
00037
00038
00039
00040
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
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
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
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
00795
00796 return _kub - ub == noe;
00797 }
00798
00799 forceinline bool
00800 ValNode::source(void) const {
00801
00802
00803 return _klb - lb == noe;
00804 }
00805
00806
00807
00808
00809
00810
00811
00812 forceinline void
00813 Edge::unlink(void) {
00814
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
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
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
01049 Edge** xadjacent = vars[i]->adj();
01050
01051 int j = 0;
01052 for (ViewValues<IntView> xi(x[i]); xi(); ++xi) {
01053
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
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
01153 NodeStack re(r,2*n_node);
01154
01155
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
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
01170 v->kmax(k[i].max());
01171 v->kmin(k[i].min());
01172
01173
01174 if (inc_ubc <= k[i].max()) {
01175
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
01182
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
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
01218 if (x[i].assigned()) {
01219 int v = x[i].val();
01220 Edge* mub = vrn->get_match(UBC);
01221 if ((mub != NULL) && (v != mub->getVal()->val)) {
01222 mub->unmatch(UBC);
01223 re.push(vars[i]);
01224 }
01225
01226 Edge* mlb = vrn->get_match(LBC);
01227 if (mlb != NULL) {
01228 ValNode* vln = mlb->getVal();
01229 if (v != vln->val) {
01230 mlb->unmatch(LBC);
01231 if (vln->incid_match(LBC) < vln->kmin())
01232 re.push(vln);
01233 }
01234 }
01235
01236 for (Edge* e = vrn->first(); e != NULL; e = e->next()) {
01237 ValNode* vln = e->getVal();
01238 if (vln->val != v) {
01239 vrn->noe--;
01240 e->getVal()->noe--;
01241 e->del_edge();
01242 e->unlink();
01243 }
01244 }
01245 } else {
01246
01247
01248 ViewValues<IntView> xiter(x[i]);
01249 Edge* mub = vrn->get_match(UBC);
01250 Edge* mlb = vrn->get_match(LBC);
01251 Edge** p = vrn->adj();
01252 Edge* e = *p;
01253 do {
01254
01255 while (e != NULL && (e->getVal()->val < xiter.val())) {
01256
01257 e->getVal()->noe--;
01258 vrn->noe--;
01259 e->del_edge();
01260 e->unlink();
01261 e = e ->next();
01262 *p = e;
01263 }
01264
01265 assert(xiter.val() == e->getVal()->val);
01266
01267
01268 e->free(UBC);
01269 e->free(LBC);
01270 ++xiter;
01271 p = e->next_ref();
01272 e = e->next();
01273 } while (xiter());
01274 *p = NULL;
01275 while (e) {
01276 e->getVar()->noe--;
01277 e->getVal()->noe--;
01278 e->del_edge();
01279 e->unlink();
01280 e = e->next();
01281 }
01282
01283 if ((mub != NULL) && mub->deleted()) {
01284 mub->unmatch(UBC);
01285 re.push(vars[i]);
01286 }
01287
01288
01289 if ((mlb != NULL) && mlb->deleted()) {
01290 ValNode* vln = mlb->getVal();
01291 mlb->unmatch(LBC);
01292 if (vln->incid_match(LBC) < vln->kmin())
01293 re.push(vln);
01294 }
01295 }
01296 }
01297 vars[i]->index(i);
01298 }
01299
01300 for (int i = n_val; i--; ) {
01301 if ((k[i].min() > vals[i]->noe) && (k[i].counter() == 0))
01302 return ES_FAILED;
01303 vals[i]->index(n_var + i);
01304 }
01305
01306
01307 while (!re.empty()) {
01308 Node* n = re.pop();
01309 if (!n->removed()) {
01310 if (!n->type()) {
01311 VarNode* vrn = static_cast<VarNode*>(n);
01312 if (!vrn->matched(UBC) && !augmenting_path<UBC>(home,vrn))
01313 return ES_FAILED;
01314 } else {
01315 ValNode* vln = static_cast<ValNode*>(n);
01316 while (!vln->matched(LBC))
01317 if (!augmenting_path<LBC>(home,vln))
01318 return ES_FAILED;
01319 }
01320 }
01321 }
01322
01323 return ES_OK;
01324 }
01325
01326 template<class Card> template<BC bc>
01327 inline ExecStatus
01328 VarValGraph<Card>::narrow(Space& home,
01329 ViewArray<IntView>& x, ViewArray<Card>& k) {
01330 for (int i = n_var; i--; )
01331 if (vars[i]->noe == 1) {
01332 ValNode* v = vars[i]->first()->getVal();
01333 vars[i]->first()->free(bc);
01334 GECODE_ME_CHECK(x[i].eq(home, v->val));
01335 v->inc();
01336 }
01337
01338 for (int i = n_val; i--; ) {
01339 ValNode* v = vals[i];
01340 if (Card::propagate && (k[i].counter() == 0))
01341 GECODE_ME_CHECK(k[i].lq(home, v->noe));
01342 if (v->noe > 0) {
01343 if (Card::propagate)
01344 GECODE_ME_CHECK(k[i].lq(home, v->noe));
01345
01346
01347
01348
01349 if (v->kcount() == v->kmax()) {
01350 int vidx = v->kindex();
01351
01352 k[i].counter(v->kcount());
01353
01354 if (Card::propagate)
01355 GECODE_ME_CHECK(k[i].eq(home, k[i].counter()));
01356
01357 bool delall = v->card_conflict() && (v->noe > v->kmax());
01358
01359 for (Edge* e = v->last(); e != NULL; e = e->vprev()) {
01360 VarNode* vrn = e->getVar();
01361 if (vrn->noe == 1) {
01362 vrn->noe--;
01363 v->noe--;
01364 int vi= vrn->index();
01365
01366 x.move_lst(vi);
01367 vars[vi] = vars[--n_var];
01368 vars[vi]->index(vi);
01369 n_node--;
01370 e->del_edge();
01371 e->unlink();
01372
01373 } else if (delall) {
01374 GECODE_ME_CHECK(x[vrn->index()].nq(home, v->val));
01375 vrn->noe--;
01376 v->noe--;
01377 e->del_edge();
01378 e->unlink();
01379 }
01380 }
01381 v->cap(UBC,0);
01382 v->cap(LBC,0);
01383 v->maxlow(0);
01384 if (sum_min >= k[vidx].min())
01385 sum_min -= k[vidx].min();
01386 if (sum_max >= k[vidx].max())
01387 sum_max -= k[vidx].max();
01388
01389 } else if (v->kcount() > 0) {
01390 v->kcount(0);
01391 }
01392 }
01393 }
01394 for (int i = n_var; i--; )
01395 vars[i]->index(i);
01396
01397 for (int i = n_val; i--; ) {
01398 if (vals[i]->noe == 0) {
01399 vals[i]->cap(UBC,0);
01400 vals[i]->cap(LBC,0);
01401 vals[i]->maxlow(0);
01402 }
01403 vals[i]->index(n_var + i);
01404 }
01405
01406 for (int i = n_var; i--; ) {
01407 if (vars[i]->noe > 1) {
01408 for (Edge* e = vars[i]->first(); e != NULL; e = e->next()) {
01409 if (!e->matched(bc) && !e->used(bc)) {
01410 GECODE_ME_CHECK(x[i].nq(home, e->getVal()->val));
01411 } else {
01412 e->free(bc);
01413 }
01414 }
01415 }
01416 }
01417 return ES_OK;
01418 }
01419
01420 template<class Card> template<BC bc>
01421 forceinline bool
01422 VarValGraph<Card>::augmenting_path(Space& home, Node* v) {
01423 Region r(home);
01424 NodeStack ns(r,n_node);
01425 BitSet visited(r,static_cast<unsigned int>(n_node));
01426 Edge** start = r.alloc<Edge*>(n_node);
01427
01428
01429 Node* sn = v;
01430
01431
01432 bool sp = sn->type();
01433
01434
01435
01436
01437 for (int i = n_node; i--; )
01438 if (i >= n_var) {
01439 vals[i-n_var]->inedge(NULL);
01440 start[i] = vals[i-n_var]->first();
01441 } else {
01442 vars[i]->inedge(NULL);
01443 start[i] = vars[i]->first();
01444 }
01445
01446 v->inedge(NULL);
01447 ns.push(v);
01448 visited.set(static_cast<unsigned int>(v->index()));
01449 while (!ns.empty()) {
01450 Node* vv = ns.top();
01451 Edge* e = NULL;
01452 if (vv->type() == sp) {
01453 e = start[vv->index()];
01454 while ((e != NULL) && e->matched(bc))
01455 e = e->next(vv->type());
01456 } else {
01457 e = start[vv->index()];
01458 while ((e != NULL) && !e->matched(bc))
01459 e = e->next(vv->type());
01460 start[vv->index()] = e;
01461 }
01462 if (e != NULL) {
01463 start[vv->index()] = e->next(vv->type());
01464 Node* w = e->getMate(vv->type());
01465 if (!visited.get(static_cast<unsigned int>(w->index()))) {
01466
01467 bool m = w->type() ?
01468 static_cast<ValNode*>(w)->matched(bc) :
01469 static_cast<VarNode*>(w)->matched(bc);
01470 if (!m && w->type() != sp) {
01471 if (vv->inedge() != NULL) {
01472
01473 e->match(bc);
01474 break;
01475 } else {
01476
01477 e->match(bc);
01478 ns.pop();
01479 return true;
01480 }
01481 } else {
01482 w->inedge(e);
01483 visited.set(static_cast<unsigned int>(w->index()));
01484
01485 ns.push(w);
01486 }
01487 }
01488 } else {
01489
01490 ns.pop();
01491 }
01492 }
01493
01494 bool pathfound = !ns.empty();
01495
01496 while (!ns.empty()) {
01497 Node* t = ns.pop();
01498 if (t != sn) {
01499 Edge* in = t->inedge();
01500 if (t->type() != sp) {
01501 in->match(bc);
01502 } else if (!sp) {
01503 in->unmatch(bc,!sp);
01504 } else {
01505 in->unmatch(bc);
01506 }
01507 }
01508 }
01509 return pathfound;
01510 }
01511
01512 template<class Card> template<BC bc>
01513 inline ExecStatus
01514 VarValGraph<Card>::maximum_matching(Space& home) {
01515 int card_match = 0;
01516
01517
01518 for (int i = n_val; i--; )
01519 for (Edge* e = vals[i]->first(); e != NULL ; e = e->vnext())
01520 if (!e->getVar()->matched(bc) && !vals[i]->matched(bc)) {
01521 e->match(bc); card_match++;
01522 }
01523
01524 Region r(home);
01525 switch (bc) {
01526 case LBC:
01527 if (card_match < sum_min) {
01528 Support::StaticStack<ValNode*,Region> free(r,n_val);
01529
01530
01531 for (int i = n_val; i--; )
01532 if (!vals[i]->matched(LBC))
01533 free.push(vals[i]);
01534
01535 while (!free.empty()) {
01536 ValNode* v = free.pop();
01537 while (!v->matched(LBC))
01538 if (augmenting_path<LBC>(home,v))
01539 card_match++;
01540 else
01541 break;
01542 }
01543
01544 return (card_match >= sum_min) ? ES_OK : ES_FAILED;
01545 } else {
01546 return ES_OK;
01547 }
01548 break;
01549 case UBC:
01550 if (card_match < n_var) {
01551 Support::StaticStack<VarNode*,Region> free(r,n_var);
01552
01553
01554 for (int i = n_var; i--; )
01555 if (!vars[i]->matched(UBC))
01556 free.push(vars[i]);
01557
01558 while (!free.empty()) {
01559 VarNode* v = free.pop();
01560 if (!v->matched(UBC) && augmenting_path<UBC>(home,v))
01561 card_match++;
01562 }
01563
01564 return (card_match >= n_var) ? ES_OK : ES_FAILED;
01565 } else {
01566 return ES_OK;
01567 }
01568 break;
01569 default: GECODE_NEVER;
01570 }
01571 GECODE_NEVER;
01572 return ES_FAILED;
01573 }
01574
01575
01576 template<class Card> template<BC bc>
01577 forceinline void
01578 VarValGraph<Card>::free_alternating_paths(Space& home) {
01579 Region r(home);
01580 NodeStack ns(r,n_node);
01581 BitSet visited(r,static_cast<unsigned int>(n_node));
01582
01583 switch (bc) {
01584 case LBC:
01585
01586
01587
01588 for (int i = n_var; i--; )
01589 if (!vars[i]->matched(LBC)) {
01590 ns.push(vars[i]);
01591 visited.set(static_cast<unsigned int>(vars[i]->index()));
01592 }
01593 for (int i = n_val; i--; )
01594 if (!vals[i]->matched(LBC)) {
01595 ns.push(vals[i]);
01596 visited.set(static_cast<unsigned int>(vals[i]->index()));
01597 }
01598 break;
01599 case UBC:
01600
01601
01602 for (int i = n_val; i--; )
01603 if (!vals[i]->matched(UBC)) {
01604 ns.push(vals[i]);
01605 visited.set(static_cast<unsigned int>(vals[i]->index()));
01606 }
01607 break;
01608 default: GECODE_NEVER;
01609 }
01610
01611 while (!ns.empty()) {
01612 Node* node = ns.pop();
01613 if (node->type()) {
01614
01615 ValNode* vln = static_cast<ValNode*>(node);
01616
01617 for (Edge* cur = vln->first(); cur != NULL; cur = cur->vnext()) {
01618 VarNode* mate = cur->getVar();
01619 switch (bc) {
01620 case LBC:
01621 if (cur->matched(LBC)) {
01622
01623 cur->use(LBC);
01624 if (!visited.get(static_cast<unsigned int>(mate->index()))) {
01625 ns.push(mate);
01626 visited.set(static_cast<unsigned int>(mate->index()));
01627 }
01628 }
01629 break;
01630 case UBC:
01631 if (!cur->matched(UBC)) {
01632
01633 cur->use(UBC);
01634 if (!visited.get(static_cast<unsigned int>(mate->index()))) {
01635 ns.push(mate);
01636 visited.set(static_cast<unsigned int>(mate->index()));
01637 }
01638 }
01639 break;
01640 default: GECODE_NEVER;
01641 }
01642 }
01643
01644 } else {
01645
01646 VarNode* vrn = static_cast<VarNode*>(node);
01647
01648 switch (bc) {
01649 case LBC:
01650
01651 for (Edge* cur = vrn->first(); cur != NULL; cur = cur->next()) {
01652 ValNode* mate = cur->getVal();
01653 if (!cur->matched(LBC)) {
01654 cur->use(LBC);
01655 if (!visited.get(static_cast<unsigned int>(mate->index()))) {
01656 ns.push(mate);
01657 visited.set(static_cast<unsigned int>(mate->index()));
01658 }
01659 }
01660 }
01661 break;
01662 case UBC:
01663
01664 {
01665 Edge* cur = vrn->get_match(UBC);
01666 if (cur != NULL) {
01667 cur->use(UBC);
01668 ValNode* mate = cur->getVal();
01669 if (!visited.get(static_cast<unsigned int>(mate->index()))) {
01670 ns.push(mate);
01671 visited.set(static_cast<unsigned int>(mate->index()));
01672 }
01673 }
01674 }
01675 break;
01676 default: GECODE_NEVER;
01677 }
01678 }
01679 }
01680 }
01681
01682 template<class Card> template<BC bc>
01683 void
01684 VarValGraph<Card>::dfs(Node* v,
01685 BitSet& inscc, BitSet& in_unfinished, int dfsnum[],
01686 NodeStack& roots, NodeStack& unfinished,
01687 int& count) {
01688 count++;
01689 int v_index = v->index();
01690 dfsnum[v_index] = count;
01691 inscc.set(static_cast<unsigned int>(v_index));
01692 in_unfinished.set(static_cast<unsigned int>(v_index));
01693
01694 unfinished.push(v);
01695 roots.push(v);
01696 for (Edge* e = v->first(); e != NULL; e = e->next(v->type())) {
01697 bool m;
01698 switch (bc) {
01699 case LBC:
01700 m = v->type() ? e->matched(LBC) : !e->matched(LBC);
01701 break;
01702 case UBC:
01703 m = v->type() ? !e->matched(UBC) : e->matched(UBC);
01704 break;
01705 default: GECODE_NEVER;
01706 }
01707 if (m) {
01708 Node* w = e->getMate(v->type());
01709 int w_index = w->index();
01710
01711 assert(w_index < n_node);
01712 if (!inscc.get(static_cast<unsigned int>(w_index))) {
01713
01714 w->inedge(e);
01715 dfs<bc>(w, inscc, in_unfinished, dfsnum,
01716 roots, unfinished, count);
01717 } else if (in_unfinished.get(static_cast<unsigned int>(w_index))) {
01718
01719
01720 e->use(bc);
01721
01722
01723 assert(roots.top()->index() < n_node);
01724 while (dfsnum[roots.top()->index()] > dfsnum[w_index]) {
01725 roots.pop();
01726 }
01727 }
01728 }
01729 }
01730
01731 if (v == roots.top()) {
01732 while (v != unfinished.top()) {
01733
01734 Node* w = unfinished.top();
01735 w->inedge()->use(bc);
01736 in_unfinished.clear(static_cast<unsigned int>(w->index()));
01737 unfinished.pop();
01738 }
01739 assert(v == unfinished.top());
01740 in_unfinished.clear(static_cast<unsigned int>(v_index));
01741 roots.pop();
01742 unfinished.pop();
01743 }
01744 }
01745
01746 template<class Card> template<BC bc>
01747 forceinline void
01748 VarValGraph<Card>::strongly_connected_components(Space& home) {
01749 Region r(home);
01750 BitSet inscc(r,static_cast<unsigned int>(n_node));
01751 BitSet in_unfinished(r,static_cast<unsigned int>(n_node));
01752 int* dfsnum = r.alloc<int>(n_node);
01753
01754 for (int i = n_node; i--; )
01755 dfsnum[i]=0;
01756
01757 int count = 0;
01758 NodeStack roots(r,n_node);
01759 NodeStack unfinished(r,n_node);
01760
01761 for (int i = n_var; i--; )
01762 dfs<bc>(vars[i], inscc, in_unfinished, dfsnum,
01763 roots, unfinished, count);
01764 }
01765
01766 template<class Card>
01767 forceinline void*
01768 VarValGraph<Card>::operator new(size_t t, Space& home) {
01769 return home.ralloc(t);
01770 }
01771
01772 }}}
01773
01774
01775
01776