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 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
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
01260 while (e != NULL && (e->getVal()->val < xiter.val())) {
01261
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
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
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
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
01352
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
01432 Node* sn = v;
01433
01434
01435 bool sp = sn->type();
01436
01437
01438
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
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
01476 e->match(bc);
01477 break;
01478 } else {
01479
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
01488 ns.push(w);
01489 }
01490 }
01491 } else {
01492
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
01520
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
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
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
01589
01590
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
01604
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
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
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
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
01649 VarNode* vrn = static_cast<VarNode*>(node);
01650
01651 switch (bc) {
01652 case LBC:
01653
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
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
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
01722
01723 e->use(bc);
01724
01725
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
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
01778
01779