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
01327 return ES_OK;
01328 }
01329
01330 template<class Card> template<BC bc>
01331 inline ExecStatus
01332 VarValGraph<Card>::narrow(Space& home,
01333 ViewArray<IntView>& x, ViewArray<Card>& k) {
01334 for (int i = n_var; i--; )
01335 if (vars[i]->noe == 1) {
01336 ValNode* v = vars[i]->first()->getVal();
01337 vars[i]->first()->free(bc);
01338 GECODE_ME_CHECK(x[i].eq(home, v->val));
01339 v->inc();
01340 }
01341
01342 for (int i = n_val; i--; ) {
01343 ValNode* v = vals[i];
01344 if (Card::propagate && (k[i].counter() == 0))
01345 GECODE_ME_CHECK(k[i].lq(home, v->noe));
01346 if (v->noe > 0) {
01347 if (Card::propagate)
01348 GECODE_ME_CHECK(k[i].lq(home, v->noe));
01349
01350
01351
01352
01353 if (v->kcount() == v->kmax()) {
01354 int vidx = v->kindex();
01355
01356 k[i].counter(v->kcount());
01357
01358 if (Card::propagate)
01359 GECODE_ME_CHECK(k[i].eq(home, k[i].counter()));
01360
01361 bool delall = v->card_conflict() && (v->noe > v->kmax());
01362
01363 for (Edge* e = v->last(); e != NULL; e = e->vprev()) {
01364 VarNode* vrn = e->getVar();
01365 if (vrn->noe == 1) {
01366 vrn->noe--;
01367 v->noe--;
01368 int vi= vrn->index();
01369
01370 x.move_lst(vi);
01371 vars[vi] = vars[--n_var];
01372 vars[vi]->index(vi);
01373 n_node--;
01374 e->del_edge();
01375 e->unlink();
01376
01377 } else if (delall) {
01378 GECODE_ME_CHECK(x[vrn->index()].nq(home, v->val));
01379 vrn->noe--;
01380 v->noe--;
01381 e->del_edge();
01382 e->unlink();
01383 }
01384 }
01385 v->cap(UBC,0);
01386 v->cap(LBC,0);
01387 v->maxlow(0);
01388 if (sum_min >= k[vidx].min())
01389 sum_min -= k[vidx].min();
01390 if (sum_max >= k[vidx].max())
01391 sum_max -= k[vidx].max();
01392
01393 } else if (v->kcount() > 0) {
01394 v->kcount(0);
01395 }
01396 }
01397 }
01398 for (int i = n_var; i--; )
01399 vars[i]->index(i);
01400
01401 for (int i = n_val; i--; ) {
01402 if (vals[i]->noe == 0) {
01403 vals[i]->cap(UBC,0);
01404 vals[i]->cap(LBC,0);
01405 vals[i]->maxlow(0);
01406 }
01407 vals[i]->index(n_var + i);
01408 }
01409
01410 for (int i = n_var; i--; )
01411 if (vars[i]->noe > 1)
01412 for (Edge* e = vars[i]->first(); e != NULL; e = e->next())
01413 if (!e->matched(bc) && !e->used(bc)) {
01414 GECODE_ME_CHECK(x[i].nq(home, e->getVal()->val));
01415 } else {
01416 e->free(bc);
01417 }
01418
01419 return ES_OK;
01420 }
01421
01422 template<class Card> template<BC bc>
01423 forceinline bool
01424 VarValGraph<Card>::augmenting_path(Space& home, Node* v) {
01425 Region r(home);
01426 NodeStack ns(r,n_node);
01427 BitSet visited(r,n_node);
01428 Edge** start = r.alloc<Edge*>(n_node);
01429
01430
01431 Node* sn = v;
01432
01433
01434 bool sp = sn->type();
01435
01436
01437
01438
01439 for (int i = n_node; i--; )
01440 if (i >= n_var) {
01441 vals[i-n_var]->inedge(NULL);
01442 start[i] = vals[i-n_var]->first();
01443 } else {
01444 vars[i]->inedge(NULL);
01445 start[i] = vars[i]->first();
01446 }
01447
01448 v->inedge(NULL);
01449 ns.push(v);
01450 visited.set(v->index());
01451 while (!ns.empty()) {
01452 Node* v = ns.top();
01453 Edge* e = NULL;
01454 if (v->type() == sp) {
01455 e = start[v->index()];
01456 while ((e != NULL) && e->matched(bc))
01457 e = e->next(v->type());
01458 } else {
01459 e = start[v->index()];
01460 while ((e != NULL) && !e->matched(bc))
01461 e = e->next(v->type());
01462 start[v->index()] = e;
01463 }
01464 if (e != NULL) {
01465 start[v->index()] = e->next(v->type());
01466 Node* w = e->getMate(v->type());
01467 if (!visited.get(w->index())) {
01468
01469 bool m = w->type() ?
01470 static_cast<ValNode*>(w)->matched(bc) :
01471 static_cast<VarNode*>(w)->matched(bc);
01472 if (!m && w->type() != sp) {
01473 if (v->inedge() != NULL) {
01474
01475 e->match(bc);
01476 break;
01477 } else {
01478
01479 e->match(bc);
01480 ns.pop();
01481 return true;
01482 }
01483 } else {
01484 w->inedge(e);
01485 visited.set(w->index());
01486
01487 ns.push(w);
01488 }
01489 }
01490 } else {
01491
01492 ns.pop();
01493 }
01494 }
01495
01496 bool pathfound = !ns.empty();
01497
01498 while (!ns.empty()) {
01499 Node* t = ns.pop();
01500 if (t != sn) {
01501 Edge* in = t->inedge();
01502 if (t->type() != sp) {
01503 in->match(bc);
01504 } else if (!sp) {
01505 in->unmatch(bc,!sp);
01506 } else {
01507 in->unmatch(bc);
01508 }
01509 }
01510 }
01511 return pathfound;
01512 }
01513
01514 template<class Card> template<BC bc>
01515 inline ExecStatus
01516 VarValGraph<Card>::maximum_matching(Space& home) {
01517 int card_match = 0;
01518
01519
01520 for (int i = n_val; i--; )
01521 for (Edge* e = vals[i]->first(); e != NULL ; e = e->vnext())
01522 if (!e->getVar()->matched(bc) && !vals[i]->matched(bc)) {
01523 e->match(bc); card_match++;
01524 }
01525
01526 Region r(home);
01527 switch (bc) {
01528 case LBC:
01529 if (card_match < sum_min) {
01530 Support::StaticStack<ValNode*,Region> free(r,n_val);
01531
01532
01533 for (int i = n_val; i--; )
01534 if (!vals[i]->matched(LBC))
01535 free.push(vals[i]);
01536
01537 while (!free.empty()) {
01538 ValNode* v = free.pop();
01539 while (!v->matched(LBC))
01540 if (augmenting_path<LBC>(home,v))
01541 card_match++;
01542 else
01543 break;
01544 }
01545
01546 return (card_match >= sum_min) ? ES_OK : ES_FAILED;
01547 } else {
01548 return ES_OK;
01549 }
01550 break;
01551 case UBC:
01552 if (card_match < n_var) {
01553 Support::StaticStack<VarNode*,Region> free(r,n_var);
01554
01555
01556 for (int i = n_var; i--; )
01557 if (!vars[i]->matched(UBC))
01558 free.push(vars[i]);
01559
01560 while (!free.empty()) {
01561 VarNode* v = free.pop();
01562 if (!v->matched(UBC) && augmenting_path<UBC>(home,v))
01563 card_match++;
01564 }
01565
01566 return (card_match >= n_var) ? ES_OK : ES_FAILED;
01567 } else {
01568 return ES_OK;
01569 }
01570 break;
01571 default: GECODE_NEVER;
01572 }
01573 GECODE_NEVER;
01574 return ES_FAILED;
01575 }
01576
01577
01578 template<class Card> template<BC bc>
01579 forceinline void
01580 VarValGraph<Card>::free_alternating_paths(Space& home) {
01581 Region r(home);
01582 NodeStack ns(r,n_node);
01583 BitSet visited(r,n_node);
01584
01585 switch (bc) {
01586 case LBC:
01587
01588
01589
01590 for (int i = n_var; i--; )
01591 if (!vars[i]->matched(LBC)) {
01592 ns.push(vars[i]); visited.set(vars[i]->index());
01593 }
01594 for (int i = n_val; i--; )
01595 if (!vals[i]->matched(LBC)) {
01596 ns.push(vals[i]); visited.set(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]); visited.set(vals[i]->index());
01605 }
01606 break;
01607 default: GECODE_NEVER;
01608 }
01609
01610 while (!ns.empty()) {
01611 Node* node = ns.pop();
01612 if (node->type()) {
01613
01614 ValNode* vln = static_cast<ValNode*>(node);
01615
01616 for (Edge* cur = vln->first(); cur != NULL; cur = cur->vnext()) {
01617 VarNode* mate = cur->getVar();
01618 switch (bc) {
01619 case LBC:
01620 if (cur->matched(LBC)) {
01621
01622 cur->use(LBC);
01623 if (!visited.get(mate->index())) {
01624 ns.push(mate); visited.set(mate->index());
01625 }
01626 }
01627 break;
01628 case UBC:
01629 if (!cur->matched(UBC)) {
01630
01631 cur->use(UBC);
01632 if (!visited.get(mate->index())) {
01633 ns.push(mate); visited.set(mate->index());
01634 }
01635 }
01636 break;
01637 default: GECODE_NEVER;
01638 }
01639 }
01640
01641 } else {
01642
01643 VarNode* vrn = static_cast<VarNode*>(node);
01644
01645 switch (bc) {
01646 case LBC:
01647
01648 for (Edge* cur = vrn->first(); cur != NULL; cur = cur->next()) {
01649 ValNode* mate = cur->getVal();
01650 if (!cur->matched(LBC)) {
01651 cur->use(LBC);
01652 if (!visited.get(mate->index())) {
01653 ns.push(mate); visited.set(mate->index());
01654 }
01655 }
01656 }
01657 break;
01658 case UBC:
01659
01660 {
01661 Edge* cur = vrn->get_match(UBC);
01662 if (cur != NULL) {
01663 cur->use(UBC);
01664 ValNode* mate = cur->getVal();
01665 if (!visited.get(mate->index())) {
01666 ns.push(mate); visited.set(mate->index());
01667 }
01668 }
01669 }
01670 break;
01671 default: GECODE_NEVER;
01672 }
01673 }
01674 }
01675 }
01676
01677 template<class Card> template<BC bc>
01678 void
01679 VarValGraph<Card>::dfs(Node* v,
01680 BitSet& inscc, BitSet& in_unfinished, int dfsnum[],
01681 NodeStack& roots, NodeStack& unfinished,
01682 int& count) {
01683 count++;
01684 int v_index = v->index();
01685 dfsnum[v_index] = count;
01686 inscc.set(v_index);
01687 in_unfinished.set(v_index);
01688
01689 unfinished.push(v);
01690 roots.push(v);
01691 for (Edge* e = v->first(); e != NULL; e = e->next(v->type())) {
01692 bool m;
01693 switch (bc) {
01694 case LBC:
01695 m = v->type() ? e->matched(LBC) : !e->matched(LBC);
01696 break;
01697 case UBC:
01698 m = v->type() ? !e->matched(UBC) : e->matched(UBC);
01699 break;
01700 default: GECODE_NEVER;
01701 }
01702 if (m) {
01703 Node* w = e->getMate(v->type());
01704 int w_index = w->index();
01705
01706 assert(w_index < n_node);
01707 if (!inscc.get(w_index)) {
01708
01709 w->inedge(e);
01710 dfs<bc>(w, inscc, in_unfinished, dfsnum,
01711 roots, unfinished, count);
01712 } else if (in_unfinished.get(w_index)) {
01713
01714
01715 e->use(bc);
01716
01717
01718 assert(roots.top()->index() < n_node);
01719 while (dfsnum[roots.top()->index()] > dfsnum[w_index]) {
01720 roots.pop();
01721 }
01722 }
01723 }
01724 }
01725
01726 if (v == roots.top()) {
01727 while (v != unfinished.top()) {
01728
01729 Node* w = unfinished.top();
01730 w->inedge()->use(bc);
01731 in_unfinished.clear(w->index());
01732 unfinished.pop();
01733 }
01734 assert(v == unfinished.top());
01735 in_unfinished.clear(v_index);
01736 roots.pop();
01737 unfinished.pop();
01738 }
01739 }
01740
01741 template<class Card> template<BC bc>
01742 forceinline void
01743 VarValGraph<Card>::strongly_connected_components(Space& home) {
01744 Region r(home);
01745 BitSet inscc(r,n_node);
01746 BitSet in_unfinished(r,n_node);
01747 int* dfsnum = r.alloc<int>(n_node);
01748
01749 for (int i = n_node; i--; )
01750 dfsnum[i]=0;
01751
01752 int count = 0;
01753 NodeStack roots(r,n_node);
01754 NodeStack unfinished(r,n_node);
01755
01756 for (int i = n_var; i--; )
01757 dfs<bc>(vars[i], inscc, in_unfinished, dfsnum,
01758 roots, unfinished, count);
01759 }
01760
01761 template<class Card>
01762 forceinline void*
01763 VarValGraph<Card>::operator new(size_t t, Space& home) {
01764 return home.ralloc(t);
01765 }
01766
01767 }}}
01768
01769
01770
01771