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), nf(nf0), noe(0) {}
00516
00517 forceinline Edge**
00518 Node::adj(void) {
00519 return &e;
00520 }
00521 forceinline Edge*
00522 Node::first(void) const {
00523 return fst;
00524 }
00525 forceinline Edge*
00526 Node::last(void) const {
00527 return lst;
00528 }
00529 forceinline void
00530 Node::first(Edge* p) {
00531 fst = p;
00532 }
00533 forceinline void
00534 Node::last(Edge* p) {
00535 lst = p;
00536 }
00537 forceinline bool
00538 Node::type(void) const {
00539 return (nf & NF_VAL) != 0;
00540 }
00541 forceinline Edge*
00542 Node::inedge(void) const {
00543 return ie;
00544 }
00545 forceinline void
00546 Node::inedge(Edge* p) {
00547 ie = p;
00548 }
00549 forceinline bool
00550 Node::removed(void) const {
00551 return noe == 0;
00552 }
00553 forceinline void
00554 Node::index(int i) {
00555 idx = i;
00556 }
00557 forceinline int
00558 Node::index(void) const {
00559 return idx;
00560 }
00561
00562 forceinline void*
00563 Node::operator new(size_t s, Space& home) {
00564 return home.ralloc(s);
00565 }
00566
00567
00568
00569
00570
00571
00572
00573 forceinline
00574 VarNode::VarNode(void) {}
00575
00576 forceinline
00577 VarNode::VarNode(int x) :
00578 Node(NF_NONE,x), ubm(NULL), lbm(NULL) {}
00579
00580 forceinline bool
00581 VarNode::matched(BC bc) const {
00582 if (bc == UBC)
00583 return (nf & NF_M_UBC) != 0;
00584 else
00585 return (nf & NF_M_LBC) != 0;
00586 }
00587
00588 forceinline void
00589 VarNode::match(BC bc) {
00590 if (bc == UBC)
00591 nf |= NF_M_UBC;
00592 else
00593 nf |= NF_M_LBC;
00594 }
00595
00596 forceinline void
00597 VarNode::set_match(BC bc, Edge* p) {
00598 if (bc == UBC)
00599 ubm = p;
00600 else
00601 lbm = p;
00602 }
00603
00604 forceinline void
00605 VarNode::unmatch(BC bc) {
00606 if (bc == UBC) {
00607 nf &= ~NF_M_UBC; ubm = NULL;
00608 } else {
00609 nf &= ~NF_M_LBC; lbm = NULL;
00610 }
00611 }
00612
00613 forceinline Edge*
00614 VarNode::get_match(BC bc) const {
00615 if (bc == UBC)
00616 return ubm;
00617 else
00618 return lbm;
00619 }
00620
00621
00622
00623
00624
00625
00626
00627
00628 forceinline
00629 ValNode::ValNode(void) {}
00630
00631 forceinline
00632 ValNode::ValNode(int min, int max, int value,
00633 int kidx, int kshift, int count) :
00634 Node(NF_VAL,kshift), _klb(min), _kub(max), _kidx(kidx), _kcount(count),
00635 noc(0),
00636 lb(min), ublow(max), ub(max),
00637 val(value) {}
00638
00639 forceinline void
00640 ValNode::maxlow(int i) {
00641 assert(i >= lb);
00642 ublow = i;
00643 }
00644
00645 forceinline int
00646 ValNode::maxlow(void) const {
00647 if (_klb == _kub) {
00648 assert(ublow == lb);
00649 }
00650 return ublow;
00651 }
00652
00653
00654 forceinline void
00655 ValNode::card_conflict(int c) {
00656 noc = c;
00657 }
00658
00659 forceinline void
00660 ValNode::red_conflict(void) {
00661 noc--;
00662 assert(noc >= 0);
00663 }
00664
00665 forceinline int
00666 ValNode::card_conflict(void) const {
00667 return noc;
00668 }
00669
00670 forceinline int
00671 ValNode::cap(BC bc) const {
00672 if (bc == UBC)
00673 return ub;
00674 else
00675 return lb;
00676 }
00677 forceinline bool
00678 ValNode::matched(BC bc) const {
00679 return cap(bc) == 0;
00680 }
00681
00682 forceinline void
00683 ValNode::reset(void) {
00684 lb = _klb;
00685 ublow = _kub;
00686 ub = _kub;
00687 noe = 0;
00688 }
00689
00690 forceinline int
00691 ValNode::kbound(BC bc) const {
00692 if (bc == UBC) {
00693 return _kub;
00694 } else {
00695 return _klb;
00696 }
00697 }
00698
00699 forceinline int
00700 ValNode::kmax(void) const {
00701 return _kub;
00702 }
00703
00704 forceinline int
00705 ValNode::kmin(void) const {
00706 return _klb;
00707 }
00708
00709 forceinline void
00710 ValNode::kmin(int klb) {
00711 _klb = klb;
00712 }
00713
00714 forceinline void
00715 ValNode::kmax(int kub) {
00716 _kub = kub;
00717 }
00718
00719
00720 forceinline void
00721 ValNode::dec(BC bc) {
00722 if (bc == UBC) {
00723 ub--;
00724 } else {
00725 lb--; ublow--;
00726 }
00727 }
00728
00729 forceinline void
00730 ValNode::inc(BC bc) {
00731 if (bc == UBC) {
00732 ub++;
00733 } else {
00734 lb++; ublow++;
00735 }
00736 }
00737
00738 forceinline void
00739 ValNode::match(BC bc) {
00740 dec(bc);
00741 }
00742
00743 forceinline void
00744 ValNode::unmatch(BC bc) {
00745 inc(bc);
00746 }
00747
00748 forceinline void
00749 ValNode::cap(BC bc, int c) {
00750 if (bc == UBC)
00751 ub = c;
00752 else
00753 lb = c;
00754 }
00755
00756 forceinline void
00757 ValNode::inc(void) {
00758 _kcount++;
00759 }
00760
00761 forceinline int
00762 ValNode::kcount(void) const {
00763 return _kcount;
00764 }
00765
00766 forceinline void
00767 ValNode::kcount(int c) {
00768 _kcount = c;
00769 }
00770
00771 forceinline void
00772 ValNode::kindex(int i) {
00773 _kidx = i;
00774 }
00775
00776 forceinline int
00777 ValNode::kindex(void) const {
00778 return _kidx;
00779 }
00780
00782 forceinline int
00783 ValNode::incid_match(BC bc) const {
00784 if (bc == LBC)
00785 return _kub - ublow + _kcount;
00786 else
00787 return _kub - ub + _kcount;
00788 }
00789
00790
00791 forceinline bool
00792 ValNode::sink(void) const {
00793
00794
00795 return _kub - ub == noe;
00796 }
00797
00798 forceinline bool
00799 ValNode::source(void) const {
00800
00801
00802 return _klb - lb == noe;
00803 }
00804
00805
00806
00807
00808
00809
00810
00811 forceinline void
00812 Edge::unlink(void) {
00813
00814 Edge* p = prev_edge;
00815 Edge* n = next_edge;
00816
00817 if (p != NULL)
00818 *p->next_ref() = n;
00819 if (n != NULL)
00820 *n->prev_ref() = p;
00821
00822 if (this == x->first()) {
00823 Edge** ref = x->adj();
00824 *ref = n;
00825 x->first(n);
00826 }
00827
00828 if (this == x->last())
00829 x->last(p);
00830
00831
00832 Edge* pv = prev_vedge;
00833 Edge* nv = next_vedge;
00834
00835 if (pv != NULL)
00836 *pv->vnext_ref() = nv;
00837 if (nv != NULL)
00838 *nv->vprev_ref() = pv;
00839 if (this == v->first()) {
00840 Edge** ref = v->adj();
00841 *ref = nv;
00842 v->first(nv);
00843 }
00844 if (this == v->last())
00845 v->last(pv);
00846 }
00847
00848 forceinline
00849 Edge::Edge(VarNode* var, ValNode* val) :
00850 x(var), v(val),
00851 next_edge(NULL), prev_edge(NULL),
00852 next_vedge(NULL), prev_vedge(NULL), ef(EF_NONE) {}
00853
00854 forceinline void
00855 Edge::use(BC bc) {
00856 if (bc == UBC)
00857 ef |= EF_MRKUB;
00858 else
00859 ef |= EF_MRKLB;
00860 }
00861 forceinline void
00862 Edge::free(BC bc) {
00863 if (bc == UBC)
00864 ef &= ~EF_MRKUB;
00865 else
00866 ef &= ~EF_MRKLB;
00867 }
00868 forceinline bool
00869 Edge::used(BC bc) const {
00870 if (bc == UBC)
00871 return (ef & EF_MRKUB) != 0;
00872 else
00873 return (ef & EF_MRKLB) != 0;
00874 }
00875 forceinline Edge*
00876 Edge::next(void) const {
00877 return next_edge;
00878 }
00879 forceinline Edge*
00880 Edge::next(bool t) const {
00881 if (t) {
00882 return next_vedge;
00883 } else {
00884 return next_edge;
00885 }
00886 }
00887
00888 forceinline Edge*
00889 Edge::vnext(void) const {
00890 return next_vedge;
00891 }
00892 forceinline Edge**
00893 Edge::vnext_ref(void) {
00894 return &next_vedge;
00895 }
00896 forceinline Edge*
00897 Edge::prev(void) const {
00898 return prev_edge;
00899 }
00900 forceinline Edge**
00901 Edge::prev_ref(void) {
00902 return &prev_edge;
00903 }
00904 forceinline Edge*
00905 Edge::vprev(void) const {
00906 return prev_vedge;
00907 }
00908 forceinline Edge**
00909 Edge::vprev_ref(void) {
00910 return &prev_vedge;
00911 }
00912 forceinline Edge**
00913 Edge::next_ref(void) {
00914 return &next_edge;
00915 }
00916 forceinline VarNode*
00917 Edge::getVar(void) const {
00918 assert(x != NULL);
00919 return x;
00920 }
00921
00922 forceinline ValNode*
00923 Edge::getVal(void) const {
00924 assert(v != NULL);
00925 return v;
00926 }
00927
00928 forceinline Node*
00929 Edge::getMate(bool type) const {
00930 if (type)
00931 return x;
00932 else
00933 return v;
00934 }
00935
00936 forceinline void
00937 Edge::unmatch(BC bc) {
00938 if (bc == UBC)
00939 ef &= ~EF_UM;
00940 else
00941 ef &= ~EF_LM;
00942 x->unmatch(bc); v->unmatch(bc);
00943 }
00944
00945 forceinline void
00946 Edge::unmatch(BC bc, bool node) {
00947 if (bc == UBC)
00948 ef &= ~EF_UM;
00949 else
00950 ef &= ~EF_LM;
00951 if (node)
00952 v->unmatch(bc);
00953 else
00954 x->unmatch(bc);
00955 }
00956
00957 forceinline void
00958 Edge::reset(BC bc) {
00959 free(bc); unmatch(bc);
00960 }
00961
00962 forceinline void
00963 Edge::match(BC bc) {
00964 if (bc == UBC)
00965 ef |= EF_UM;
00966 else
00967 ef |= EF_LM;
00968 x->match(bc);
00969 x->set_match(bc,this);
00970 v->match(bc);
00971 }
00972
00973 forceinline bool
00974 Edge::matched(BC bc) const {
00975 if (bc == UBC)
00976 return (ef & EF_UM) != 0;
00977 else
00978 return (ef & EF_LM) != 0;
00979 }
00980
00981 forceinline void
00982 Edge::del_edge(void) {
00983 ef |= EF_DEL;
00984 }
00985
00986 forceinline void
00987 Edge::insert_edge(void) {
00988 ef &= ~EF_DEL;
00989 }
00990
00991
00992 forceinline bool
00993 Edge::deleted(void) const {
00994 return (ef & EF_DEL) != 0;
00995 }
00996
00997 forceinline void*
00998 Edge::operator new(size_t s, Space& home) {
00999 return home.ralloc(s);
01000 }
01001
01002
01003
01004
01005
01006
01007 template<class Card>
01008 VarValGraph<Card>::VarValGraph(Space& home,
01009 ViewArray<IntView>& x, ViewArray<Card>& k,
01010 int smin, int smax)
01011 : n_var(x.size()),
01012 n_val(k.size()),
01013 n_node(n_var + n_val),
01014 sum_min(smin),
01015 sum_max(smax) {
01016
01017 unsigned int noe = 0;
01018 for (int i=x.size(); i--; )
01019 noe += x[i].size();
01020
01021 vars = home.alloc<VarNode*>(n_var);
01022 vals = home.alloc<ValNode*>(n_val);
01023
01024 for (int i = n_val; i--; ) {
01025 int kmi = k[i].min();
01026 int kma = k[i].max();
01027 int kc = k[i].counter();
01028 if (kc != kma) {
01029 if (kmi >= kc) {
01030 kmi -=kc;
01031 assert(kmi >=0);
01032 } else {
01033 kmi = 0;
01034 }
01035 kma -= kc;
01036 assert (kma > 0);
01037 vals[i] = new (home)
01038 ValNode(kmi, kma, k[i].card(), i, i + n_var, kc);
01039 } else {
01040 vals[i] = new (home)
01041 ValNode(0, 0, k[i].card(), i, i + n_var, kc);
01042 }
01043 }
01044
01045 for (int i = n_var; i--; ) {
01046 vars[i] = new (home) VarNode(i);
01047
01048 Edge** xadjacent = vars[i]->adj();
01049
01050 int j = 0;
01051 for (ViewValues<IntView> xi(x[i]); xi(); ++xi) {
01052
01053 while(vals[j]->val < xi.val())
01054 j++;
01055 *xadjacent = new (home) Edge(vars[i],vals[j]);
01056 vars[i]->noe++;
01057 if (vars[i]->first() == NULL)
01058 vars[i]->first(*xadjacent);
01059 Edge* oldprev = vars[i]->last();
01060 vars[i]->last(*xadjacent);
01061 *vars[i]->last()->prev_ref() = oldprev;
01062
01063 if (vals[j]->first() == NULL) {
01064 vals[j]->first(*xadjacent);
01065 vals[j]->last(*xadjacent);
01066 } else {
01067 Edge* old = vals[j]->first();
01068 vals[j]->first(*xadjacent);
01069 *vals[j]->first()->vnext_ref() = old;
01070 *old->vprev_ref() = vals[j]->first();
01071 }
01072 vals[j]->noe++;
01073 xadjacent = (*xadjacent)->next_ref();
01074 }
01075 *xadjacent = NULL;
01076 }
01077 }
01078
01079
01080 template<class Card>
01081 inline ExecStatus
01082 VarValGraph<Card>::min_require(Space& home,
01083 ViewArray<IntView>& x,
01084 ViewArray<Card>& k) {
01085 for (int i = n_val; i--; ) {
01086 ValNode* vln = vals[i];
01087 if (vln->noe > 0) {
01088 if (k[i].min() == vln->noe) {
01089
01090 for (Edge* e = vln->first(); e != NULL; e = e->vnext()) {
01091 VarNode* vrn = e->getVar();
01092 for (Edge* f = vrn->first(); f != NULL; f = f->next())
01093 if (f != e) {
01094 ValNode* w = f->getVal();
01095 w->noe--;
01096 vrn->noe--;
01097 f->del_edge();
01098 f->unlink();
01099 }
01100 assert(vrn->noe == 1);
01101
01102 int vi = vrn->index();
01103 GECODE_ME_CHECK(x[vi].eq(home, vln->val));
01104
01105 vars[vi] = vars[--n_var];
01106 vars[vi]->index(vi);
01107 x.move_lst(vi);
01108 n_node--;
01109 vln->noe--;
01110 }
01111
01112
01113 int vidx = vln->kindex();
01114 if (Card::propagate)
01115 GECODE_ME_CHECK(k[vidx].eq(home, k[vidx].min()));
01116
01117 k[vidx].counter(k[vidx].min());
01118
01119 vln->cap(UBC,0);
01120 vln->cap(LBC,0);
01121 vln->maxlow(0);
01122
01123 if (sum_min >= k[vidx].min())
01124 sum_min -= k[vidx].min();
01125 if (sum_max >= k[vidx].max())
01126 sum_max -= k[vidx].max();
01127 }
01128 } else {
01129 vals[i]->cap(UBC,0);
01130 vals[i]->cap(LBC,0);
01131 vals[i]->maxlow(0);
01132 vals[i]->kmax(0);
01133 vals[i]->kmin(0);
01134 }
01135
01136 if (Card::propagate && (k[i].counter() == 0))
01137 GECODE_ME_CHECK(k[i].lq(home, vals[i]->noe));
01138 }
01139
01140 for (int i = n_val; i--; )
01141 vals[i]->index(n_var + i);
01142
01143 return ES_OK;
01144 }
01145
01146 template<class Card>
01147 inline ExecStatus
01148 VarValGraph<Card>::sync(Space& home,
01149 ViewArray<IntView>& x, ViewArray<Card>& k) {
01150 Region r(home);
01151
01152 NodeStack re(r,2*n_node);
01153
01154
01155 if (Card::propagate) {
01156 for (int i = n_val; i--; ) {
01157 ValNode* v = vals[i];
01158 int inc_ubc = v->incid_match(UBC);
01159 int inc_lbc = v->incid_match(LBC);
01160 if (v->noe == 0) {
01161 inc_ubc = 0;
01162 inc_lbc = 0;
01163 }
01164 int rm = v->kmax() - k[i].max();
01165
01166 if ((k[i].max() < v->kmax()) || (k[i].min() > v->kmin())) {
01167 if ((k[i].max() != k[i].counter()) || (k[i].max() == 0)) {
01168
01169 v->kmax(k[i].max());
01170 v->kmin(k[i].min());
01171
01172
01173 if (inc_ubc <= k[i].max()) {
01174
01175 v->cap(UBC, k[i].max() - inc_ubc);
01176 v->maxlow(k[i].max() - inc_lbc);
01177 if (v->kmin() == v->kmax())
01178 v->cap(LBC, k[i].max() - inc_lbc);
01179 } else {
01180
01181
01182 if (v->cap(UBC))
01183 v->cap(UBC,k[i].max());
01184 v->maxlow(k[i].max() - (inc_lbc));
01185 if (v->kmin() == v->kmax())
01186 v->cap(LBC,k[i].max() - (inc_lbc));
01187 v->card_conflict(rm);
01188 }
01189 }
01190 }
01191 if (inc_lbc < k[i].min() && v->noe > 0) {
01192 v->cap(LBC, k[i].min() - inc_lbc);
01193 re.push(v);
01194 }
01195 }
01196
01197 for (int i = n_var; i--; ) {
01198 Edge* mub = vars[i]->get_match(UBC);
01199 if (mub != NULL) {
01200 ValNode* vu = mub->getVal();
01201 if ((vars[i]->noe != 1) && vu->card_conflict()) {
01202 vu->red_conflict();
01203 mub->unmatch(UBC,vars[i]->type());
01204 re.push(vars[i]);
01205 }
01206 }
01207 }
01208 }
01209
01210
01211 assert(x.size() == n_var);
01212 for (int i = n_var; i--; ) {
01213
01214 VarNode* vrn = vars[i];
01215 if (static_cast<int>(x[i].size()) != vrn->noe) {
01216
01217 if (x[i].assigned()) {
01218 int v = x[i].val();
01219 ValNode* rv = NULL;
01220 int rv_idx = 0;
01221 Edge* mub = vrn->get_match(UBC);
01222 if ((mub != NULL) && (v != mub->getVal()->val)) {
01223 mub->unmatch(UBC);
01224 re.push(vars[i]);
01225 }
01226
01227 Edge* mlb = vrn->get_match(LBC);
01228 if (mlb != NULL) {
01229 ValNode* vln = mlb->getVal();
01230 if (v != vln->val) {
01231 mlb->unmatch(LBC);
01232 if (vln->incid_match(LBC) < vln->kmin())
01233 re.push(vln);
01234 }
01235 }
01236
01237 for (Edge* e = vrn->first(); e != NULL; e = e->next()) {
01238 ValNode* vln = e->getVal();
01239 if (vln->val != v) {
01240 vrn->noe--;
01241 e->getVal()->noe--;
01242 e->del_edge();
01243 e->unlink();
01244 } else {
01245 rv = e->getVal();
01246 rv_idx = rv->kindex();
01247 }
01248 }
01249 } else {
01250
01251
01252 ViewValues<IntView> xiter(x[i]);
01253 Edge* mub = vrn->get_match(UBC);
01254 Edge* mlb = vrn->get_match(LBC);
01255 Edge** p = vrn->adj();
01256 Edge* e = *p;
01257 do {
01258
01259 while (e != NULL && (e->getVal()->val < xiter.val())) {
01260
01261 e->getVal()->noe--;
01262 vrn->noe--;
01263 e->del_edge();
01264 e->unlink();
01265 e = e ->next();
01266 *p = e;
01267 }
01268
01269 assert(xiter.val() == e->getVal()->val);
01270
01271
01272 e->free(UBC);
01273 e->free(LBC);
01274 ++xiter;
01275 p = e->next_ref();
01276 e = e->next();
01277 } while (xiter());
01278 *p = NULL;
01279 while (e) {
01280 e->getVar()->noe--;
01281 e->getVal()->noe--;
01282 e->del_edge();
01283 e->unlink();
01284 e = e->next();
01285 }
01286
01287 if ((mub != NULL) && mub->deleted()) {
01288 mub->unmatch(UBC);
01289 re.push(vars[i]);
01290 }
01291
01292
01293 if ((mlb != NULL) && mlb->deleted()) {
01294 ValNode* vln = mlb->getVal();
01295 mlb->unmatch(LBC);
01296 if (vln->incid_match(LBC) < vln->kmin())
01297 re.push(vln);
01298 }
01299 }
01300 }
01301 vars[i]->index(i);
01302 }
01303
01304 for (int i = n_val; i--; ) {
01305 if ((k[i].min() > vals[i]->noe) && (k[i].counter() == 0))
01306 return ES_FAILED;
01307 vals[i]->index(n_var + i);
01308 }
01309
01310
01311 while (!re.empty()) {
01312 Node* n = re.pop();
01313 if (!n->removed())
01314 if (!n->type()) {
01315 VarNode* vrn = static_cast<VarNode*>(n);
01316 if (!vrn->matched(UBC) && !augmenting_path<UBC>(home,vrn))
01317 return ES_FAILED;
01318 } else {
01319 ValNode* vln = static_cast<ValNode*>(n);
01320 while (!vln->matched(LBC))
01321 if (!augmenting_path<LBC>(home,vln))
01322 return ES_FAILED;
01323 }
01324 }
01325
01326 return ES_OK;
01327 }
01328
01329 template<class Card> template<BC bc>
01330 inline ExecStatus
01331 VarValGraph<Card>::narrow(Space& home,
01332 ViewArray<IntView>& x, ViewArray<Card>& k) {
01333 for (int i = n_var; i--; )
01334 if (vars[i]->noe == 1) {
01335 ValNode* v = vars[i]->first()->getVal();
01336 vars[i]->first()->free(bc);
01337 GECODE_ME_CHECK(x[i].eq(home, v->val));
01338 v->inc();
01339 }
01340
01341 for (int i = n_val; i--; ) {
01342 ValNode* v = vals[i];
01343 if (Card::propagate && (k[i].counter() == 0))
01344 GECODE_ME_CHECK(k[i].lq(home, v->noe));
01345 if (v->noe > 0) {
01346 if (Card::propagate)
01347 GECODE_ME_CHECK(k[i].lq(home, v->noe));
01348
01349
01350
01351
01352 if (v->kcount() == v->kmax()) {
01353 int vidx = v->kindex();
01354
01355 k[i].counter(v->kcount());
01356
01357 if (Card::propagate)
01358 GECODE_ME_CHECK(k[i].eq(home, k[i].counter()));
01359
01360 bool delall = v->card_conflict() && (v->noe > v->kmax());
01361
01362 for (Edge* e = v->last(); e != NULL; e = e->vprev()) {
01363 VarNode* vrn = e->getVar();
01364 if (vrn->noe == 1) {
01365 vrn->noe--;
01366 v->noe--;
01367 int vi= vrn->index();
01368
01369 x.move_lst(vi);
01370 vars[vi] = vars[--n_var];
01371 vars[vi]->index(vi);
01372 n_node--;
01373 e->del_edge();
01374 e->unlink();
01375
01376 } else if (delall) {
01377 GECODE_ME_CHECK(x[vrn->index()].nq(home, v->val));
01378 vrn->noe--;
01379 v->noe--;
01380 e->del_edge();
01381 e->unlink();
01382 }
01383 }
01384 v->cap(UBC,0);
01385 v->cap(LBC,0);
01386 v->maxlow(0);
01387 if (sum_min >= k[vidx].min())
01388 sum_min -= k[vidx].min();
01389 if (sum_max >= k[vidx].max())
01390 sum_max -= k[vidx].max();
01391
01392 } else if (v->kcount() > 0) {
01393 v->kcount(0);
01394 }
01395 }
01396 }
01397 for (int i = n_var; i--; )
01398 vars[i]->index(i);
01399
01400 for (int i = n_val; i--; ) {
01401 if (vals[i]->noe == 0) {
01402 vals[i]->cap(UBC,0);
01403 vals[i]->cap(LBC,0);
01404 vals[i]->maxlow(0);
01405 }
01406 vals[i]->index(n_var + i);
01407 }
01408
01409 for (int i = n_var; i--; )
01410 if (vars[i]->noe > 1)
01411 for (Edge* e = vars[i]->first(); e != NULL; e = e->next())
01412 if (!e->matched(bc) && !e->used(bc)) {
01413 GECODE_ME_CHECK(x[i].nq(home, e->getVal()->val));
01414 } else {
01415 e->free(bc);
01416 }
01417
01418 return ES_OK;
01419 }
01420
01421 template<class Card> template<BC bc>
01422 forceinline bool
01423 VarValGraph<Card>::augmenting_path(Space& home, Node* v) {
01424 Region r(home);
01425 NodeStack ns(r,n_node);
01426 BitSet visited(r,n_node);
01427 Edge** start = r.alloc<Edge*>(n_node);
01428
01429
01430 Node* sn = v;
01431
01432
01433 bool sp = sn->type();
01434
01435
01436
01437
01438 for (int i = n_node; i--; )
01439 if (i >= n_var) {
01440 vals[i-n_var]->inedge(NULL);
01441 start[i] = vals[i-n_var]->first();
01442 } else {
01443 vars[i]->inedge(NULL);
01444 start[i] = vars[i]->first();
01445 }
01446
01447 v->inedge(NULL);
01448 ns.push(v);
01449 visited.set(v->index());
01450 while (!ns.empty()) {
01451 Node* v = ns.top();
01452 Edge* e = NULL;
01453 if (v->type() == sp) {
01454 e = start[v->index()];
01455 while ((e != NULL) && e->matched(bc))
01456 e = e->next(v->type());
01457 } else {
01458 e = start[v->index()];
01459 while ((e != NULL) && !e->matched(bc))
01460 e = e->next(v->type());
01461 start[v->index()] = e;
01462 }
01463 if (e != NULL) {
01464 start[v->index()] = e->next(v->type());
01465 Node* w = e->getMate(v->type());
01466 if (!visited.get(w->index())) {
01467
01468 bool m = w->type() ?
01469 static_cast<ValNode*>(w)->matched(bc) :
01470 static_cast<VarNode*>(w)->matched(bc);
01471 if (!m && w->type() != sp) {
01472 if (v->inedge() != NULL) {
01473
01474 e->match(bc);
01475 break;
01476 } else {
01477
01478 e->match(bc);
01479 ns.pop();
01480 return true;
01481 }
01482 } else {
01483 w->inedge(e);
01484 visited.set(w->index());
01485
01486 ns.push(w);
01487 }
01488 }
01489 } else {
01490
01491 ns.pop();
01492 }
01493 }
01494
01495 bool pathfound = !ns.empty();
01496
01497 while (!ns.empty()) {
01498 Node* t = ns.pop();
01499 if (t != sn) {
01500 Edge* in = t->inedge();
01501 if (t->type() != sp) {
01502 in->match(bc);
01503 } else if (!sp) {
01504 in->unmatch(bc,!sp);
01505 } else {
01506 in->unmatch(bc);
01507 }
01508 }
01509 }
01510 return pathfound;
01511 }
01512
01513 template<class Card> template<BC bc>
01514 inline ExecStatus
01515 VarValGraph<Card>::maximum_matching(Space& home) {
01516 int card_match = 0;
01517
01518
01519 for (int i = n_val; i--; )
01520 for (Edge* e = vals[i]->first(); e != NULL ; e = e->vnext())
01521 if (!e->getVar()->matched(bc) && !vals[i]->matched(bc)) {
01522 e->match(bc); card_match++;
01523 }
01524
01525 Region r(home);
01526 switch (bc) {
01527 case LBC:
01528 if (card_match < sum_min) {
01529 Support::StaticStack<ValNode*,Region> free(r,n_val);
01530
01531
01532 for (int i = n_val; i--; )
01533 if (!vals[i]->matched(LBC))
01534 free.push(vals[i]);
01535
01536 while (!free.empty()) {
01537 ValNode* v = free.pop();
01538 while (!v->matched(LBC))
01539 if (augmenting_path<LBC>(home,v))
01540 card_match++;
01541 else
01542 break;
01543 }
01544
01545 return (card_match >= sum_min) ? ES_OK : ES_FAILED;
01546 } else {
01547 return ES_OK;
01548 }
01549 break;
01550 case UBC:
01551 if (card_match < n_var) {
01552 Support::StaticStack<VarNode*,Region> free(r,n_var);
01553
01554
01555 for (int i = n_var; i--; )
01556 if (!vars[i]->matched(UBC))
01557 free.push(vars[i]);
01558
01559 while (!free.empty()) {
01560 VarNode* v = free.pop();
01561 if (!v->matched(UBC) && augmenting_path<UBC>(home,v))
01562 card_match++;
01563 }
01564
01565 return (card_match >= n_var) ? ES_OK : ES_FAILED;
01566 } else {
01567 return ES_OK;
01568 }
01569 break;
01570 default: GECODE_NEVER;
01571 }
01572 GECODE_NEVER;
01573 return ES_FAILED;
01574 }
01575
01576
01577 template<class Card> template<BC bc>
01578 forceinline void
01579 VarValGraph<Card>::free_alternating_paths(Space& home) {
01580 Region r(home);
01581 NodeStack ns(r,n_node);
01582 BitSet visited(r,n_node);
01583
01584 switch (bc) {
01585 case LBC:
01586
01587
01588
01589 for (int i = n_var; i--; )
01590 if (!vars[i]->matched(LBC)) {
01591 ns.push(vars[i]); visited.set(vars[i]->index());
01592 }
01593 for (int i = n_val; i--; )
01594 if (!vals[i]->matched(LBC)) {
01595 ns.push(vals[i]); visited.set(vals[i]->index());
01596 }
01597 break;
01598 case UBC:
01599
01600
01601 for (int i = n_val; i--; )
01602 if (!vals[i]->matched(UBC)) {
01603 ns.push(vals[i]); visited.set(vals[i]->index());
01604 }
01605 break;
01606 default: GECODE_NEVER;
01607 }
01608
01609 while (!ns.empty()) {
01610 Node* node = ns.pop();
01611 if (node->type()) {
01612
01613 ValNode* vln = static_cast<ValNode*>(node);
01614
01615 for (Edge* cur = vln->first(); cur != NULL; cur = cur->vnext()) {
01616 VarNode* mate = cur->getVar();
01617 switch (bc) {
01618 case LBC:
01619 if (cur->matched(LBC)) {
01620
01621 cur->use(LBC);
01622 if (!visited.get(mate->index())) {
01623 ns.push(mate); visited.set(mate->index());
01624 }
01625 }
01626 break;
01627 case UBC:
01628 if (!cur->matched(UBC)) {
01629
01630 cur->use(UBC);
01631 if (!visited.get(mate->index())) {
01632 ns.push(mate); visited.set(mate->index());
01633 }
01634 }
01635 break;
01636 default: GECODE_NEVER;
01637 }
01638 }
01639
01640 } else {
01641
01642 VarNode* vrn = static_cast<VarNode*>(node);
01643
01644 switch (bc) {
01645 case LBC:
01646
01647 for (Edge* cur = vrn->first(); cur != NULL; cur = cur->next()) {
01648 ValNode* mate = cur->getVal();
01649 if (!cur->matched(LBC)) {
01650 cur->use(LBC);
01651 if (!visited.get(mate->index())) {
01652 ns.push(mate); visited.set(mate->index());
01653 }
01654 }
01655 }
01656 break;
01657 case UBC:
01658
01659 {
01660 Edge* cur = vrn->get_match(UBC);
01661 if (cur != NULL) {
01662 cur->use(UBC);
01663 ValNode* mate = cur->getVal();
01664 if (!visited.get(mate->index())) {
01665 ns.push(mate); visited.set(mate->index());
01666 }
01667 }
01668 }
01669 break;
01670 default: GECODE_NEVER;
01671 }
01672 }
01673 }
01674 }
01675
01676 template<class Card> template<BC bc>
01677 void
01678 VarValGraph<Card>::dfs(Node* v,
01679 BitSet& inscc, BitSet& in_unfinished, int dfsnum[],
01680 NodeStack& roots, NodeStack& unfinished,
01681 int& count) {
01682 count++;
01683 int v_index = v->index();
01684 dfsnum[v_index] = count;
01685 inscc.set(v_index);
01686 in_unfinished.set(v_index);
01687
01688 unfinished.push(v);
01689 roots.push(v);
01690 for (Edge* e = v->first(); e != NULL; e = e->next(v->type())) {
01691 bool m;
01692 switch (bc) {
01693 case LBC:
01694 m = v->type() ? e->matched(LBC) : !e->matched(LBC);
01695 break;
01696 case UBC:
01697 m = v->type() ? !e->matched(UBC) : e->matched(UBC);
01698 break;
01699 default: GECODE_NEVER;
01700 }
01701 if (m) {
01702 Node* w = e->getMate(v->type());
01703 int w_index = w->index();
01704
01705 assert(w_index < n_node);
01706 if (!inscc.get(w_index)) {
01707
01708 w->inedge(e);
01709 dfs<bc>(w, inscc, in_unfinished, dfsnum,
01710 roots, unfinished, count);
01711 } else if (in_unfinished.get(w_index)) {
01712
01713
01714 e->use(bc);
01715
01716
01717 assert(roots.top()->index() < n_node);
01718 while (dfsnum[roots.top()->index()] > dfsnum[w_index]) {
01719 roots.pop();
01720 }
01721 }
01722 }
01723 }
01724
01725 if (v == roots.top()) {
01726 while (v != unfinished.top()) {
01727
01728 Node* w = unfinished.top();
01729 w->inedge()->use(bc);
01730 in_unfinished.clear(w->index());
01731 unfinished.pop();
01732 }
01733 assert(v == unfinished.top());
01734 in_unfinished.clear(v_index);
01735 roots.pop();
01736 unfinished.pop();
01737 }
01738 }
01739
01740 template<class Card> template<BC bc>
01741 forceinline void
01742 VarValGraph<Card>::strongly_connected_components(Space& home) {
01743 Region r(home);
01744 BitSet inscc(r,n_node);
01745 BitSet in_unfinished(r,n_node);
01746 int* dfsnum = r.alloc<int>(n_node);
01747
01748 for (int i = n_node; i--; )
01749 dfsnum[i]=0;
01750
01751 int count = 0;
01752 NodeStack roots(r,n_node);
01753 NodeStack unfinished(r,n_node);
01754
01755 for (int i = n_var; i--; )
01756 dfs<bc>(vars[i], inscc, in_unfinished, dfsnum,
01757 roots, unfinished, count);
01758 }
01759
01760 template<class Card>
01761 forceinline void*
01762 VarValGraph<Card>::operator new(size_t t, Space& home) {
01763 return home.ralloc(t);
01764 }
01765
01766 }}}
01767
01768
01769
01770