00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021
00022 #ifdef NDEBUG
00023 #define GECODE_ASSERTION_VARIABLE(c)
00024 #define GECODE_ASSERT(a)
00025 #else
00026 #define GECODE_ASSERTION_VARIABLE(c) c
00027 #define GECODE_ASSERT(a) assert(!me_failed(a));
00028 #endif
00029
00030
00031 namespace Gecode { namespace Int { namespace GCC {
00032
00034 template <class View>
00035 void
00036 pview(View& v){
00037 if (v.min() == v.max()) {
00038 std::cout << v.min() <<" ";
00039 } else {
00040 if (v.range()){
00041 std::cout << "["<<v.min() <<".."<<v.max()<<"] ";
00042 } else {
00043 std::cout << "{";
00044 ViewValues<View> iter(v);
00045 while(iter()){
00046 std::cout << iter.val() <<",";
00047 ++iter;
00048 }
00049 std::cout << "} ";
00050 }
00051 }
00052 }
00053
00060 enum BC {UBC = 1, LBC = 0};
00061
00062 class Edge;
00064 class VVGNode{
00065 private:
00067 Edge* e;
00069 Edge* fst;
00071 Edge* lst;
00073 Edge* ie;
00075 bool lm;
00077 bool um;
00079 bool type;
00080 public:
00082
00083
00084 VVGNode(void);
00086
00087 virtual ~VVGNode(void){};
00089 void* operator new(size_t, void*);
00090
00092
00093
00094 Edge** adj(void);
00096 Edge* first(void);
00098 Edge* last(void);
00100 Edge* inedge(void);
00102 bool get_type(void);
00104 template <BC>
00105 bool get_match_flag(void);
00107 virtual int get_info(void) = 0;
00109 virtual bool is_matched(BC) = 0;
00110
00112 virtual bool removed(void) = 0;
00114
00116
00117
00118 void first(Edge* p);
00120 void last(Edge* p);
00122 void inedge(Edge* p);
00124 void set_type(bool t);
00126 template <BC>
00127 void set_match_flag(bool f);
00129 virtual void set_info(int i) = 0;
00131 };
00132
00134 class VarNode : public VVGNode{
00135 private:
00137 Edge* ubm;
00139 Edge* lbm;
00140
00141 public:
00143 unsigned int var;
00145 unsigned int noe;
00146
00148 unsigned int xindex;
00149
00151
00152
00153 VarNode(int i, int oidx);
00155
00157
00158
00159 template <BC>
00160 Edge* get_match(void);
00162 int get_info(void);
00164 bool is_matched(BC);
00166 template <BC>
00167 bool matched(void);
00168
00170 bool removed(void);
00172
00174
00175
00176 void set_info(int i);
00178 template <BC>
00179 void set_match(Edge* m);
00181 template <BC>
00182 void match(void);
00184 template <BC>
00185 void unmatch(void);
00187 };
00188
00190 class ValNode : public VVGNode{
00191 private:
00193 int _klb;
00195 int _kub;
00197 int _kidx;
00199 int _kcount;
00200
00201
00203 int noc;
00204
00210 int lb;
00211 int ublow;
00218 int ub;
00219
00220 public:
00222 int val;
00224 int idx;
00226 int noe;
00227
00229
00230
00237 ValNode(int min, int max, int value, int kidx, int kshift, int count);
00239
00241
00242
00244 void set_maxlow(int i);
00246 int get_maxlow(void);
00247
00248
00250 void card_conflict(int c);
00252 int card_conflict(void);
00254 void red_conflict(void);
00255
00257 bool removed(void);
00258
00260 void inc(void);
00262 int kcount(void);
00264 template <BC>
00265 int incid_match(void);
00267 int kindex(void);
00269 int get_info(void);
00271 template <BC>
00272 bool matched(void);
00274 bool sink(void);
00276 bool source(void);
00278 int kmin(void);
00280 int kmax(void);
00282 template <BC>
00283 int kbound(void);
00284
00286 bool is_matched(BC);
00288
00290
00291 void kcount(int);
00293 void kindex(int);
00295 template <BC>
00296 void dec(void);
00298 template <BC>
00299 void inc(void);
00301 template <BC>
00302 int cap(void);
00304 template <BC>
00305 void set_cap(int c);
00307 template <BC>
00308 void match(void);
00310 template <BC>
00311 void unmatch(void);
00313 void reset(void);
00315 void set_info(int i);
00317 void set_kmin(int min);
00319 void set_kmax(int max);
00321 };
00322
00324 class Edge{
00325 private:
00327 VarNode* x;
00329 ValNode* v;
00331 Edge* next_edge;
00333 Edge* prev_edge;
00335 Edge* next_vedge;
00337 Edge* prev_vedge;
00343 bool mrklb;
00349 bool mrkub;
00351 bool um;
00353 bool lm;
00355 bool deleted;
00356
00357 public:
00359
00360
00364 Edge(VarNode* x, ValNode* v);
00366 void* operator new(size_t, void*);
00368
00370
00371
00378 template <BC>
00379 bool used(void);
00381 template <BC>
00382 bool matched(void);
00384 bool is_deleted(void);
00390 Edge* next(bool t) const;
00392 Edge* next(void) const;
00394 Edge* prev(void) const;
00396 Edge* vnext(void) const;
00398 Edge* vprev(void) const;
00400 VarNode* getVar(void);
00402 ValNode* getVal(void);
00407 VVGNode* getMate(bool t);
00409
00411
00412
00413 template <BC>
00414 void use(void);
00416 template <BC>
00417 void free(void);
00423 template <BC>
00424 void reset(void);
00426 template <BC>
00427 void match(void);
00429 template <BC>
00430 void unmatch(void);
00432 template <BC>
00433 void unmatch(bool t);
00435 void unlink(void);
00437 void del_edge(void);
00439 void insert_edge(void);
00441 Edge** next_ref(void);
00443 Edge** prev_ref(void);
00445 Edge** vnext_ref(void);
00447 Edge** vprev_ref(void);
00449 };
00450
00452 inline std::ostream&
00453 operator<<(std::ostream& os, VarNode* v) {
00454 os << v->var<<":{";
00455 for (Edge* e = v->first(); e != NULL; e = e->next()) {
00456 os << e->getVal()->val<<",";
00457 }
00458 os << "}(";
00459 os << v->xindex << ") ";
00460 return os;
00461 }
00462
00464 inline std::ostream&
00465 operator<<(std::ostream& os, ValNode* v) {
00466 os << v->val<<":{";
00467 for (Edge* e = v->first(); e != NULL; e = e->vnext()) {
00468 os << e->getVar()->var<<",";
00469 }
00470 os << "} ";
00471 return os;
00472 }
00473
00478 template <class View, class Card, bool isView>
00479 class VarValGraph{
00480 private:
00482 bool fail;
00484 char* mem;
00486 ViewArray<View>& x;
00488 ViewArray<View>& y;
00490 ViewArray<Card>& k;
00492 VarNode** vars;
00500 ValNode** vals;
00502 Edge* edges;
00504 int n_var;
00510 int n_val;
00512 int n_edge;
00514 int node_size;
00520 int sum_min;
00526 int sum_max;
00527 public:
00529
00530 VarValGraph(ViewArray<View>&, ViewArray<View>&, ViewArray<Card>&,
00531 int , int , int );
00533 ~VarValGraph(void);
00535
00536
00537
00543 bool failed(void);
00547 void failed(bool b);
00548
00553 bool min_require(Space* home);
00554
00563 bool sync(void);
00564
00566 void print_graph(void);
00568 template <BC>
00569 void print_matching(void);
00571 void print_match(void);
00572
00574 void print_edges(void);
00575
00577 void* operator new(size_t t);
00579 void operator delete(void* p);
00580
00588 template <BC>
00589 bool narrow(Space*);
00590
00597 template <BC>
00598 bool maximum_matching(void);
00599
00601 template <BC>
00602 void free_alternating_paths(void);
00604 template <BC>
00605 void strongly_connected_components(void);
00611 template <BC>
00612 bool augmenting_path(VVGNode*);
00613
00614 protected:
00621 template <BC>
00622 void dfs(VVGNode*,
00623 bool[], bool[], int[],
00624 Support::StaticStack<VVGNode*>&,
00625 Support::StaticStack<VVGNode*>&,
00626 int&);
00627
00629 };
00630
00631 forceinline
00632 VVGNode::VVGNode(void){}
00633
00634 forceinline void*
00635 VVGNode::operator new(size_t n, void* p){
00636 return p;
00637 }
00638
00639 forceinline Edge**
00640 VVGNode::adj(void){
00641 return &e;
00642 }
00643
00644 forceinline Edge*
00645 VVGNode::first(void){
00646 return fst;
00647 }
00648
00649 forceinline Edge*
00650 VVGNode::last(void){
00651 return lst;
00652 }
00653
00654 forceinline void
00655 VVGNode::first(Edge* p){
00656 fst = p;
00657 }
00658
00659 forceinline void
00660 VVGNode::last(Edge* p){
00661 lst = p;
00662 }
00663
00664 forceinline bool
00665 VVGNode::get_type(void){
00666 return type;
00667 }
00668
00669 forceinline void
00670 VVGNode::set_type(bool b){
00671 type = b;
00672 }
00673
00674 forceinline Edge*
00675 VVGNode::inedge(void){
00676 return ie;
00677 }
00678
00679 forceinline void
00680 VVGNode::inedge(Edge* p){
00681 ie = p;
00682 }
00683
00684 template <BC direction>
00685 forceinline void
00686 VVGNode::set_match_flag(bool b){
00687 if (direction == UBC) {
00688 um = b;
00689 } else {
00690 lm = b;
00691 }
00692 }
00693
00694 template <BC direction>
00695 forceinline bool
00696 VVGNode::get_match_flag(void){
00697 if (direction == UBC) {
00698 return um;
00699 } else {
00700 return lm;
00701 }
00702 }
00703
00704
00706
00707 forceinline bool
00708 VarNode::removed(void) {
00709 return noe == 0;
00710 }
00711
00712
00713
00714 forceinline
00715 VarNode::VarNode(int x, int orig_idx) :
00716 ubm(NULL), lbm(NULL), var(x), noe(0), xindex(orig_idx){
00717 first(NULL);
00718 last(NULL);
00719 inedge(NULL);
00720 unmatch<LBC>();
00721 unmatch<UBC>();
00722 set_type(false);
00723 }
00724
00725 forceinline bool
00726 VarNode::is_matched(BC d) {
00727 if (d == UBC) {
00728 return matched<UBC>();
00729 } else {
00730 return matched<LBC>();
00731 }
00732 }
00733
00734 template <BC direction>
00735 forceinline bool
00736 VarNode::matched(void){
00737 return get_match_flag<direction>();
00738 }
00739
00740 template <BC direction>
00741 forceinline void
00742 VarNode::match(void){
00743 set_match_flag<direction>(true);
00744 }
00745
00746 template <BC direction>
00747 forceinline void
00748 VarNode::unmatch(void){
00749 set_match_flag<direction>(false);
00750 set_match<direction>(NULL);
00751 }
00752
00753 template <BC direction>
00754 forceinline void
00755 VarNode::set_match(Edge* p){
00756 if (direction == UBC) {
00757 ubm = p;
00758 } else {
00759 lbm = p;
00760 }
00761 }
00762
00763 template <BC direction>
00764 forceinline Edge*
00765 VarNode::get_match(void){
00766 if (direction == UBC) {
00767 return ubm;
00768 } else {
00769 return lbm;
00770 }
00771 }
00772
00773 forceinline void
00774 VarNode::set_info(int i){
00775 var = i;
00776 }
00777
00778 forceinline int
00779 VarNode::get_info(void){
00780 return var;
00781 }
00782
00784
00785 forceinline void
00786 ValNode::set_maxlow(int i){
00787 assert(i >= lb);
00788 ublow = i;
00789 }
00790
00791 forceinline int
00792 ValNode::get_maxlow(void) {
00793 if (_klb == _kub) {
00794 assert(ublow == lb);
00795 }
00796
00797 return ublow;
00798 }
00799
00800
00801 forceinline void
00802 ValNode::card_conflict(int c){
00803 noc = c;
00804 }
00805
00806 forceinline void
00807 ValNode::red_conflict(void){
00808 noc--;
00809 assert(noc >= 0);
00810 }
00811
00812 forceinline int
00813 ValNode::card_conflict(void){
00814 return noc;
00815 }
00816
00817 forceinline bool
00818 ValNode::removed(void) {
00819 return noe == 0;
00820 }
00821
00822 forceinline bool
00823 ValNode::is_matched(BC d) {
00824 if (d == UBC) {
00825 return matched<UBC>();
00826 } else {
00827 return ublow == 0;
00828 }
00829 }
00830
00831 forceinline void
00832 ValNode::reset(void){
00833 lb = _klb;
00834 ublow = _kub;
00835 ub = _kub;
00836 noe = 0;
00837 }
00838
00839 template <BC direction>
00840 forceinline int
00841 ValNode::kbound(void){
00842 if (direction == UBC) {
00843 return _kub;
00844 } else {
00845 return _klb;
00846 }
00847 }
00848
00849 forceinline int
00850 ValNode::kmax(void){
00851 return _kub;
00852 }
00853
00854 forceinline int
00855 ValNode::kmin(void){
00856 return _klb;
00857 }
00858
00859 forceinline void
00860 ValNode::set_kmin(int klb){
00861 _klb = klb;
00862 }
00863
00864 forceinline void
00865 ValNode::set_kmax(int kub){
00866 _kub = kub;
00867 }
00868
00869 template <BC direction>
00870 forceinline int
00871 ValNode::cap(void){
00872 if (direction == UBC) {
00873 return ub;
00874 } else {
00875 return lb;
00876 }
00877 }
00878
00879 template <BC direction>
00880 forceinline void
00881 ValNode::dec(void){
00882 if (direction == UBC) {
00883 ub--;
00884 } else {
00885 lb--;
00886 ublow--;
00887 }
00888 }
00889
00890 template <BC direction>
00891 forceinline void
00892 ValNode::inc(void){
00893 if (direction == UBC) {
00894 ub++;
00895 } else {
00896 lb++;
00897 ublow++;
00898 }
00899 }
00900
00901 template <BC direction>
00902 forceinline void
00903 ValNode::match(void){
00904 dec<direction>();
00905 }
00906
00907 template <BC direction>
00908 forceinline void
00909 ValNode::unmatch(void){
00910 inc<direction>();
00911 }
00912
00913 template <BC direction>
00914 forceinline bool
00915 ValNode::matched(void){
00916 return ( cap<direction>() == 0);
00917 }
00918
00919 forceinline
00920 ValNode::ValNode(int min, int max, int value,
00921 int kidx, int kshift, int count) :
00922 _klb(min), _kub(max), _kidx(kidx), _kcount(count),
00923 noc(0),
00924 lb(min), ublow(max), ub(max),
00925 val(value), idx(kshift), noe(0) {
00926 first(NULL);
00927 last(NULL);
00928 inedge(NULL);
00929 Edge** vadjacent = adj();
00930 *vadjacent = NULL;
00931 set_type(true);
00932 }
00933
00934 template<BC direction>
00935 forceinline void
00936 ValNode::set_cap(int c){
00937 if (direction == UBC) {
00938 ub = c;
00939 } else {
00940 lb = c;
00941
00942 }
00943 }
00944
00945 forceinline void
00946 ValNode::set_info(int i){
00947 idx = i;
00948 }
00949
00950 forceinline int
00951 ValNode::get_info(void){
00952 return idx;
00953 }
00954
00955 forceinline void
00956 ValNode::inc(void) {
00957 _kcount++;
00958 }
00959
00960 forceinline int
00961 ValNode::kcount(void) {
00962 return _kcount;
00963 }
00964
00965 forceinline void
00966 ValNode::kcount(int c) {
00967 _kcount = c;
00968 }
00969
00970 forceinline void
00971 ValNode::kindex(int i){
00972 _kidx = i;
00973 }
00974
00975 forceinline int
00976 ValNode::kindex(void){
00977 return _kidx;
00978 }
00979
00981 template <BC direction>
00982 forceinline int
00983 ValNode::incid_match(void){
00984 if (direction == LBC) {
00985
00986 return _kub - ublow + _kcount;
00987 } else {
00988
00989 return _kub - ub + _kcount;
00990 }
00991 }
00992
00993
00994 forceinline bool
00995 ValNode::sink(void){
00996
00997
00998 bool is_sink = false;
00999 is_sink = (_kub - ub == noe);
01000 return is_sink;
01001 }
01002
01003 forceinline bool
01004 ValNode::source(void){
01005
01006
01007 bool is_sink = false;
01008 is_sink = (_klb - lb == noe);
01009 return is_sink;
01010 }
01011
01014 inline std::ostream&
01015 operator<<(std::ostream& os, Edge* e){
01016 if (e== NULL) {
01017 os << "(N)";
01018 } else {
01019 os << "e("<<e->getVar()->var<<","<<e->getVal()->val<<")";
01020 }
01021 return os;
01022 }
01023
01024
01025 forceinline void
01026 Edge::unlink(void){
01027
01028 Edge* p = prev_edge;
01029 Edge* n = next_edge;
01030
01031 if (p != NULL) {
01032 Edge** pnext = p->next_ref();
01033 *pnext = n;
01034 }
01035
01036 if (n != NULL) {
01037 Edge** nprev = n->prev_ref();
01038 *nprev = p;
01039 }
01040
01041 if (this == x->first()) {
01042 Edge** ref = x->adj();
01043 *ref = n;
01044 x->first(n);
01045 }
01046
01047 if (this == x->last()) {
01048 x->last(p);
01049 }
01050
01051
01052 Edge* pv = prev_vedge;
01053 Edge* nv = next_vedge;
01054
01055 if (pv != NULL) {
01056 Edge** pvnext = pv->vnext_ref();
01057 *pvnext = nv;
01058 }
01059
01060 if (nv != NULL) {
01061 Edge** nvprev = nv->vprev_ref();
01062 *nvprev = pv;
01063 }
01064
01065 if (this == v->first()) {
01066 Edge** ref = v->adj();
01067 *ref = nv;
01068 v->first(nv);
01069 }
01070
01071 if (this == v->last()) {
01072 v->last(pv);
01073 }
01074 }
01075
01076 forceinline
01077 Edge::Edge(VarNode* var, ValNode* val) :
01078 x(var), v(val),
01079 next_edge(NULL), prev_edge(NULL),
01080 next_vedge(NULL), prev_vedge(NULL),
01081 mrklb(false), mrkub(false),
01082 um(false), lm(false), deleted(false) {};
01083
01084 forceinline void*
01085 Edge::operator new(size_t, void* p){
01086 return p;
01087 }
01088
01089 template <BC direction>
01090 forceinline void
01091 Edge::use(void){
01092 if (direction == UBC) {
01093 mrkub = true;
01094 } else {
01095 mrklb = true;
01096 }
01097 }
01098
01099 template <BC direction>
01100 forceinline void
01101 Edge::free(void){
01103 if (direction == UBC) {
01104 mrkub = false;
01105 } else {
01106 mrklb = false;
01107 }
01108 }
01109
01110 template <BC direction>
01111 forceinline void
01112 Edge::reset(void){
01113 this->free<direction>();
01114 this->unmatch<direction>();
01115 }
01116
01117 template <BC direction>
01118 forceinline bool
01119 Edge::used(void){
01120 if (direction == UBC){
01121 return mrkub;
01122 } else {
01123 return mrklb;
01124 }
01125 }
01126
01127 forceinline Edge*
01128 Edge::next(void) const{
01129 return next_edge;
01130 }
01131
01132 forceinline Edge*
01133 Edge::next(bool t) const{
01134 if (t) {
01135 return next_vedge;
01136 } else {
01137 return next_edge;
01138 }
01139 }
01140
01141 forceinline Edge*
01142 Edge::vnext(void) const{
01143 return next_vedge;
01144 }
01145
01146 forceinline Edge**
01147 Edge::vnext_ref(void) {
01148 return &next_vedge;
01149 }
01150
01151 forceinline Edge*
01152 Edge::prev(void) const{
01153 return prev_edge;
01154 }
01155
01156 forceinline Edge**
01157 Edge::prev_ref(void) {
01158 return &prev_edge;
01159 }
01160
01161 forceinline Edge*
01162 Edge::vprev(void) const{
01163 return prev_vedge;
01164 }
01165
01166 forceinline Edge**
01167 Edge::vprev_ref(void) {
01168 return &prev_vedge;
01169 }
01170
01171 forceinline Edge**
01172 Edge::next_ref(void){
01173 return &next_edge;
01174 }
01175 forceinline VarNode*
01176 Edge::getVar(void){
01177 assert(x != NULL);
01178 return x;
01179 }
01180
01181 forceinline ValNode*
01182 Edge::getVal(void){
01183 assert(v != NULL);
01184 return v;
01185 }
01186
01187 forceinline VVGNode*
01188 Edge::getMate(bool type){
01189 if (type) {
01190 return x;
01191 } else {
01192 return v;
01193 }
01194 }
01195
01196 template <BC direction>
01197 forceinline void
01198 Edge::unmatch(void){
01199 if (direction == UBC) {
01200 um = false;
01201 } else {
01202 lm = false;
01203 }
01204 x->unmatch<direction>();
01205 v->unmatch<direction>();
01206 }
01207
01208 template <BC direction>
01209 forceinline void
01210 Edge::unmatch(bool node){
01211 if (direction == UBC) {
01212 um = false;
01213 } else {
01214 lm = false;
01215 }
01216 if (node) {
01217 v->template unmatch<direction>();
01218 } else {
01219 x->template unmatch<direction>();
01220 }
01221 }
01222
01223 template <BC direction>
01224 forceinline void
01225 Edge::match(void){
01226 if (direction == UBC) {
01227 um = true;
01228 x->template match<direction>();
01229 x->template set_match<direction>(this);
01230 v->template match<direction>();
01231 } else {
01232 lm = true;
01233 x->template match<direction>();
01234 x->template set_match<direction>(this);
01235 assert(x->template matched<direction>());
01236 v->template match<direction>();
01237
01238 }
01239 }
01240
01241 template <BC direction>
01242 forceinline bool
01243 Edge::matched(void){
01244 if (direction == UBC) {
01245 return um;
01246 } else {
01247 return lm;
01248 }
01249 }
01250
01251 forceinline void
01252 Edge::del_edge(void){
01253 deleted = true;
01254 }
01255
01256 forceinline void
01257 Edge::insert_edge(void){
01258 deleted = false;
01259 }
01260
01261
01262 forceinline bool
01263 Edge::is_deleted(void){
01264 return deleted;
01265 }
01266
01280 template <class View, class Card, bool isView>
01281 VarValGraph<View, Card, isView>::VarValGraph(ViewArray<View>& xref,
01282 ViewArray<View>& yref,
01283 ViewArray<Card>& kref,
01284 int noe,
01285 int smin, int smax)
01286 : fail(false),
01287 x(xref),
01288 y(yref),
01289 k(kref),
01290 n_var(x.size()),
01291 n_val(k.size()),
01292 n_edge(noe),
01293 node_size(n_var + n_val),
01294 sum_min(smin),
01295 sum_max(smax) {
01296
01297
01298 size_t edge_size = sizeof(Edge) * n_edge;
01299 size_t var_size = sizeof(VarNode) * n_var;
01300 size_t var_ptr_size = sizeof(VarNode*) * n_var;
01301 size_t val_size = sizeof(ValNode) * n_val;
01302 size_t val_ptr_size = sizeof(ValNode*) * n_val;
01303 size_t size = edge_size + var_size + var_ptr_size +
01304 val_size + val_ptr_size;
01305
01306 mem = reinterpret_cast<char*>
01307 (Memory::malloc(size));
01308 edges = reinterpret_cast<Edge*>
01309 (mem);
01310 VarNode* vars_ptr = reinterpret_cast<VarNode*>
01311 (mem + edge_size);
01312 ValNode* vals_ptr = reinterpret_cast<ValNode*>
01313 (mem + edge_size + var_size);
01314 vars = reinterpret_cast<VarNode**>
01315 (mem + edge_size + var_size + val_size);
01316 vals = reinterpret_cast<ValNode**>
01317 (mem + edge_size + var_size + val_size + var_ptr_size);
01318
01319 for (int i = n_val; i--; ){
01320 int kmi = k[i].min();
01321 int kma = k[i].max();
01322 int kc = k[i].counter();
01323 if (kc != kma) {
01324 if (kmi >= kc) {
01325 kmi -=kc;
01326 assert(kmi >=0);
01327 } else {
01328 kmi = 0;
01329 }
01330 kma -= kc;
01331 assert (kma > 0);
01332 vals[i] = new (vals_ptr + i)
01333 ValNode(kmi, kma, k[i].card(), i, i + n_var, kc);
01334 } else {
01335 vals[i] = new (vals_ptr + i)
01336 ValNode(0, 0, k[i].card(), i, i + n_var, kc);
01337 }
01338 }
01339
01340 for (int i = n_var; i--; ){
01341
01342 vars[i] = new (vars_ptr + i) VarNode(i, i);
01343 VarNode* vrn = vars[i];
01344
01345 Edge** xadjacent = vrn->adj();
01346
01347 ViewValues<View> xiter(x[i]);
01348 int j = 0;
01349 for (; xiter(); ++xiter){
01350 int v = xiter.val();
01351
01352 while(vals[j]->val < v){
01353 j++;
01354 }
01355 ValNode* vln = vals[j];
01356 *xadjacent = new (edges) Edge(vars_ptr + i, vals_ptr + j);
01357 vrn->noe++;
01358 if (vrn->first() == NULL) {
01359 vrn->first(*xadjacent);
01360 }
01361 Edge* oldprev = vrn->last();
01362 vrn->last(*xadjacent);
01363 Edge** newprev = vrn->last()->prev_ref();
01364 *newprev = oldprev;
01365
01366 if (vln->first() == NULL) {
01367 vln->first(*xadjacent);
01368 vln->last(*xadjacent);
01369 vln->noe++;
01370 } else {
01371 Edge* old = vln->first();
01372 vln->first(*xadjacent);
01373 Edge** newnext = vln->first()->vnext_ref();
01374 *newnext = old;
01375 Edge** setprev = old->vprev_ref();
01376 *setprev = vln->first();
01377 vln->noe++;
01378 }
01379 edges++;
01380 xadjacent = (*xadjacent)->next_ref();
01381 }
01382 *xadjacent = NULL;
01383 }
01384 }
01385
01386 template <class View, class Card, bool isView>
01387 forceinline bool
01388 VarValGraph<View, Card, isView>::failed(void){
01389 return fail;
01390 }
01391
01392 template <class View, class Card, bool isView>
01393 forceinline void
01394 VarValGraph<View, Card, isView>::failed(bool b){
01395 fail = b;
01396 }
01397
01398
01399
01400 template <class View, class Card, bool isView>
01401 inline bool
01402 VarValGraph<View, Card, isView>::min_require(Space* home){
01403 bool modified = false;
01404 for (int i = n_val; i--; ) {
01405 ValNode* vln = vals[i];
01406 if (vln->noe > 0) {
01407 if (k[i].min() == vln->noe) {
01408
01409 for (Edge* e = vln->first(); e != NULL; e = e->vnext()) {
01410 VarNode* vrn = e->getVar();
01411 int vi = vrn->get_info();
01412 for (Edge* f = vrn->first(); f != NULL; f = f->next()) {
01413 if (f != e) {
01414 ValNode* w = f->getVal();
01415 w->noe--;
01416 vrn->noe--;
01417 f->del_edge();
01418 f->unlink();
01419 }
01420 }
01421 assert(vrn->noe == 1);
01422 modified |= x[vi].modified();
01423
01424 GECODE_ASSERTION_VARIABLE(ModEvent me =)
01425 x[vi].eq(home, vln->val);
01426 GECODE_ASSERT(me);
01427 vars[vi] = vars[--n_var];
01428 vars[vi]->set_info(vi);
01429
01430 int n = x.size();
01431 x[vi] = x[--n];
01432
01433 x.size(n);
01434
01435 node_size--;
01436 vln->noe--;
01437 }
01438
01439
01440 int vidx = vln->kindex();
01441 if (isView) {
01442 GECODE_ASSERTION_VARIABLE(ModEvent me =)
01443 k[vidx].eq(home, k[vidx].min());
01444 GECODE_ASSERT(me);
01445 }
01446 k[vidx].counter(k[vidx].min());
01447 modified |= k[vidx].modified();
01448
01449 vln->template set_cap<UBC>(0);
01450 vln->template set_cap<LBC>(0);
01451 vln->set_maxlow(0);
01452
01453 if (sum_min && sum_min >= k[vidx].min()) {
01454 sum_min -= k[vidx].min();
01455 }
01456 assert(sum_min >=0);
01457
01458 if (sum_max && sum_max >= k[vidx].max()) {
01459 sum_max -= k[vidx].max();
01460 }
01461 assert(sum_max >=0);
01462 }
01463 } else {
01464 vals[i]->template set_cap<UBC>(0);
01465 vals[i]->template set_cap<LBC>(0);
01466 vals[i]->set_maxlow(0);
01467 vals[i]->set_kmax(0);
01468 vals[i]->set_kmin(0);
01469
01470 }
01471
01472 if (isView) {
01473 if (k[i].counter() == 0) {
01474 ModEvent klq = k[i].lq(home, vals[i]->noe);
01475 if (me_failed(klq)) {
01476 failed(true);
01477 }
01478 }
01479 modified |= k[i].modified() && k[i].max() != vals[i]->noe;
01480 }
01481 }
01482
01483 for (int i = n_val; i--; ) {
01484 vals[i]->set_info(n_var + i);
01485 }
01486
01487 return modified;
01488 }
01489
01490 template <class View, class Card, bool isView>
01491 inline bool
01492 VarValGraph<View, Card, isView>::sync(void){
01493 GECODE_AUTOARRAY(VVGNode*, re, node_size);
01494 int n_re = 0;
01495
01496
01497 if (isView) {
01498 for (int i = n_val; i--; ) {
01499 ValNode* v = vals[i];
01500 int inc_ubc = v->template incid_match<UBC>();
01501 int inc_lbc = v->template incid_match<LBC>();
01502 if (v->noe == 0) {
01503 inc_ubc = 0;
01504 inc_lbc = 0;
01505 }
01506 int rm = v->kmax() - k[i].max();
01507
01508 if (k[i].max() < v->kmax() || k[i].min() > v->kmin()) {
01509 if (k[i].max() != k[i].counter() || k[i].max() == 0) {
01510
01511 v->set_kmax(k[i].max());
01512 v->set_kmin(k[i].min());
01513
01514
01515 if (inc_ubc <= k[i].max()) {
01516
01517 v->template set_cap<UBC>(k[i].max() - (inc_ubc));
01518 v->set_maxlow(k[i].max() - (inc_lbc));
01519 if (v->kmin() == v->kmax()) {
01520 v->template set_cap<LBC>(k[i].max() - (inc_lbc));
01521 }
01522 } else {
01523
01524
01525 if (v->template cap<UBC>()) {
01526 v->template set_cap<UBC>(k[i].max());
01527 }
01528 v->set_maxlow(k[i].max() - (inc_lbc));
01529 if (v->kmin() == v->kmax()) {
01530 v->template set_cap<LBC>(k[i].max() - (inc_lbc));
01531 }
01532 v->card_conflict(rm);
01533 }
01534 }
01535 }
01536 if (inc_lbc < k[i].min() && v->noe > 0) {
01537
01538 v->template set_cap<LBC>(k[i].min() - inc_lbc);
01539 re[n_re] = v;
01540 n_re++;
01541 }
01542 }
01543
01544 for (int i = n_var; i--; ) {
01545 Edge* mub = vars[i]->template get_match<UBC>();
01546 if (mub != NULL) {
01547 ValNode* vu = mub->getVal();
01548 if (! (vars[i]->noe == 1) ) {
01549 if (vu->card_conflict()) {
01550 vu->red_conflict();
01551 mub->template unmatch<UBC>(vars[i]->get_type());
01552 re[n_re] = vars[i];
01553 n_re++;
01554 }
01555 }
01556 }
01557 }
01558 }
01559
01560
01561 assert(x.size() == n_var);
01562 for (int i = n_var; i--; ) {
01563
01564 VarNode* vrn = vars[i];
01565 if(x[i].size() != vrn->noe){
01566
01567 if (x[i].assigned()) {
01568 int v = x[i].val();
01569 ValNode* rv = NULL;
01570 int rv_idx = 0;
01571 Edge* mub = vrn->template get_match<UBC>();
01572 if (mub != NULL) {
01573 if (v != mub->getVal()->val) {
01574 mub->template unmatch<UBC>();
01575 re[n_re] = vars[i];
01576 n_re++;
01577 }
01578 }
01579
01580 Edge* mlb = vrn->template get_match<LBC>();
01581 if (mlb != NULL) {
01582 ValNode* vln = mlb->getVal();
01583 if (v != vln->val) {
01584 mlb->template unmatch<LBC>();
01585 int nom = vln->template incid_match<LBC>();
01586
01587 bool cond = nom < vln->kmin();
01588 if (cond) {
01589 re[n_re] = vln;
01590 n_re++;
01591 }
01592 }
01593 }
01594
01595 for (Edge* e = vrn->first(); e != NULL; e = e->next()){
01596 ValNode* vln = e->getVal();
01597 if (vln->val != v) {
01598 vrn->noe--;
01599 e->getVal()->noe--;
01600 e->del_edge();
01601 e->unlink();
01602 } else {
01603 rv = e->getVal();
01604 rv_idx = rv->kindex();
01605 }
01606 }
01607 } else {
01608
01609
01610 ViewValues<View> xiter(x[i]);
01611 Edge* mub = vrn->template get_match<UBC>();
01612 Edge* mlb = vrn->template get_match<LBC>();
01613 Edge** p = vrn->adj();
01614 Edge* e = *p;
01615 do {
01616
01617 while (e != NULL && e->getVal()->val < xiter.val()) {
01618
01619 e->getVal()->noe--;
01620 vrn->noe--;
01621 e->del_edge();
01622 e->unlink();
01623 e = e ->next();
01624 *p = e;
01625 }
01626
01627 assert(xiter.val() == e->getVal()->val);
01628
01629
01630 e->template free<UBC>();
01631 e->template free<LBC>();
01632 ++xiter;
01633 p = e->next_ref();
01634 e = e->next();
01635 } while (xiter());
01636 *p = NULL;
01637 while (e) {
01638 e->getVar()->noe--;
01639 e->getVal()->noe--;
01640 e->del_edge();
01641 e->unlink();
01642 e = e->next();
01643 }
01644
01645 if (mub != NULL){
01646 if (mub->is_deleted()) {
01647 mub->template unmatch<UBC>();
01648 re[n_re] = vars[i];
01649 n_re++;
01650 }
01651 }
01652
01653
01654 if (mlb != NULL) {
01655 if (mlb->is_deleted()) {
01656 ValNode* vln = mlb->getVal();
01657 mlb->template unmatch<LBC>();
01658 int nom = vln->template incid_match<LBC>();
01659 bool cond = nom < vln->kmin();
01660 if (cond) {
01661 re[n_re] = vln;
01662 n_re++;
01663 }
01664 }
01665 }
01666 }
01667 }
01668 vars[i]->set_info(i);
01669 }
01670
01671 for (int i = n_val; i--; ) {
01672 if (k[i].min() > vals[i]->noe && k[i].counter() == 0) {
01673 failed(true);
01674 return false;
01675 }
01676 vals[i]->set_info(n_var + i);
01677 }
01678
01679 if (n_re == 0) {
01680
01681 return true;
01682 } else {
01683
01684
01685 bool repaired = true;
01686 while (n_re ) {
01687 n_re--;
01688 assert(re[n_re] != NULL);
01689 if (!(re[n_re]->removed())) {
01690 if (!(re[n_re]->get_type())) {
01691 VarNode* vrn = reinterpret_cast<VarNode*> (re[n_re]);
01692 if (!vrn->template matched<UBC>()) {
01693 repaired &= augmenting_path<UBC>(vrn);
01694 }
01695 } else {
01696 assert(re[n_re]->get_type());
01697 ValNode* vln = reinterpret_cast<ValNode*> (re[n_re]);
01698 while(!vln->template matched<LBC>()) {
01699 repaired &= augmenting_path<LBC>(vln);
01700 if (!repaired) {
01701 break;
01702 }
01703 }
01704 }
01705 }
01706 }
01707 return repaired;
01708 }
01709 }
01710
01711 template <class View, class Card, bool isView> template <BC direction>
01712 inline bool
01713 VarValGraph<View, Card, isView>::narrow(Space* home){
01714
01715 bool shared = false;
01716 for (int i = n_var; i--; ) {
01717 VarNode* vrn = vars[i];
01718 if (vrn->noe == 1) {
01719 Edge* e = vrn->first();
01720 shared |= x[i].modified();
01721 ValNode* v = e->getVal();
01722 e->template free<direction>();
01723 GECODE_ASSERTION_VARIABLE(ModEvent me=)
01724 x[i].eq(home, v->val);
01725 GECODE_ASSERT(me);
01726 v->inc();
01727 }
01728 }
01729 for (int i = n_val; i--; ) {
01730 ValNode* v = vals[i];
01731 if (isView) {
01732 if (k[i].counter() == 0) {
01733 ModEvent klq = k[i].lq(home, v->noe);
01734 if (me_failed(klq)) {
01735 failed(true);
01736 return false;
01737 }
01738 }
01739 }
01740
01741 if (v->noe > 0) {
01742
01743 if (isView) {
01744 ModEvent klq = k[i].lq(home, v->noe);
01745 if (me_failed(klq)) {
01746 failed(true);
01747 return false;
01748 }
01749 }
01750
01751
01752
01753
01754 if (v->kcount() == v->kmax()) {
01755 int vidx = v->kindex();
01756
01757 k[i].counter(v->kcount());
01758
01759 if (isView) {
01760 if (!k[i].assigned()) {
01761 ModEvent me = k[i].eq(home, k[i].counter());
01762 if (me_failed(me)) {
01763 failed(true);
01764 return false;
01765 }
01766 }
01767 }
01768
01769 bool delall = false;
01770 if (v->card_conflict() &&
01771 v->noe > v->kmax()) {
01772 delall = true;
01773
01774 }
01775
01776 for (Edge* e = v->last(); e != NULL; e = e->vprev()) {
01777 VarNode* vrn = e->getVar();
01778 if (vrn->noe == 1) {
01779 vrn->noe--;
01780 v->noe--;
01781 int vi= vrn->get_info();
01782
01783 int n = x.size();
01784 x[vi] = x[--n];
01785
01786 x.size(n);
01787
01788 vars[vi] = vars[--n_var];
01789 vars[vi]->set_info(vi);
01790 node_size--;
01791 e->del_edge();
01792 e->unlink();
01793
01794 } else {
01795 if (delall) {
01796 GECODE_ASSERTION_VARIABLE(ModEvent me=)
01797 x[vrn->get_info()].nq(home, v->val);
01798 GECODE_ASSERT(me)
01799 vrn->noe--;
01800 v->noe--;
01801 e->del_edge();
01802 e->unlink();
01803 }
01804 }
01805 }
01806 v->template set_cap<UBC>(0);
01807 v->template set_cap<LBC>(0);
01808 v->set_maxlow(0);
01809 if (sum_min && sum_min >= k[vidx].min()) {
01810 sum_min -= k[vidx].min();
01811 }
01812 assert(sum_min >=0);
01813
01814 if (sum_max && sum_max >= k[vidx].max()) {
01815 sum_max -= k[vidx].max();
01816 }
01817
01818 assert(sum_max >=0);
01819
01820 } else {
01821 int cur = v->kcount();
01822 if (cur > 0) {
01823 v->kcount(0);
01824 }
01825 }
01826 }
01827 }
01828 for (int i = n_var; i--; ) {
01829 vars[i]->set_info(i);
01830
01831 }
01832
01833 for (int i = n_val; i--; ) {
01834 if (vals[i]->noe == 0) {
01835 vals[i]->template set_cap<UBC>(0);
01836 vals[i]->template set_cap<LBC>(0);
01837 vals[i]->set_maxlow(0);
01838 }
01839 vals[i]->set_info(n_var + i);
01840 }
01841
01842 for (int i = n_var; i--; ) {
01843 if (vars[i]->noe > 1){
01844 for (Edge* e = vars[i]->first(); e != NULL; e = e->next()){
01845 bool keepedge = false;
01846 keepedge = (e->template matched<direction>() ||
01847 e->template used<direction>());
01848 if (!keepedge) {
01849 ValNode* v = e->getVal();
01850 shared |= x[i].modified();
01851 GECODE_ASSERTION_VARIABLE(ModEvent me=)
01852 x[i].nq(home, v->val);
01853 GECODE_ASSERT(me)
01854 } else {
01855 e->template free<direction>();
01856 }
01857 }
01858 }
01859 }
01860 return shared;
01861 }
01862
01863 template <class View, class Card, bool isView> template <BC direction>
01864 inline bool
01865 VarValGraph<View, Card, isView>::maximum_matching(void){
01866
01867 int required_size = 0;
01868 int card_match = 0;
01869
01870 if (direction == UBC) {
01871 required_size = n_var;
01872 } else {
01873 required_size = sum_min;
01874 }
01875
01876
01877
01878
01879 for (int i = n_val; i--; ){
01880 ValNode* vln = vals[i];
01881 for (Edge* e = vln->first(); e != NULL ; e = e->vnext()) {
01882 VarNode* vrn = e->getVar();
01883 if (!vrn->template matched<direction>() &&
01884 !vln->template matched<direction>()) {
01885 e->template match<direction>();
01886 card_match++;
01887 }
01888 }
01889 }
01890
01891 if (card_match < required_size) {
01892 if (direction == LBC) {
01893
01894 GECODE_AUTOARRAY(ValNode*, free, n_val);
01895 int f = 0;
01896
01897 for (int i = n_val; i--; ) {
01898 ValNode* vln = vals[i];
01899 if (!vln->template matched<direction>()) {
01900 free[f++] = vln;
01901 }
01902 }
01903
01904 for (int i = 0; i < f; i++) {
01905 while(!free[i]->template matched<direction>()) {
01906 if (augmenting_path<direction>(free[i])) {
01907 card_match++;
01908 } else {
01909 break;
01910 }
01911 }
01912 }
01913 } else {
01914 GECODE_AUTOARRAY(VarNode*, free, n_var);
01915 int f = 0;
01916
01917 for (int i = n_var; i--; ) {
01918 VarNode* vrn = vars[i];
01919 if (!vrn->template matched<direction>()) {
01920 free[f++] = vrn;
01921 }
01922 }
01923
01924 for (int i = 0; i < f; i++) {
01925 if (!free[i]->template matched<direction>()) {
01926 if (augmenting_path<direction>(free[i])) {
01927 card_match++;
01928 }
01929 }
01930 }
01931 }
01932 }
01933 return (card_match >= required_size);
01934 }
01935
01936 template <class View, class Card, bool isView> template<BC direction>
01937 inline bool
01938 VarValGraph<View, Card, isView>::augmenting_path(VVGNode* v){
01939 Support::StaticStack<VVGNode*> ns(node_size);
01940 GECODE_AUTOARRAY(bool, visited, node_size);
01941 GECODE_AUTOARRAY(Edge*, start, node_size);
01942
01943
01944 assert(!v->is_matched(direction));
01945
01946
01947 VVGNode* sn = v;
01948
01949
01950 bool sp = sn->get_type();
01951
01952
01953
01954
01955 for (int i = node_size; i--; ){
01956 visited[i] = false;
01957 }
01958
01959 for (int i = node_size; i--; ){
01960 if (i >= n_var) {
01961 vals[i - n_var]->inedge(NULL);
01962 start[i] = vals[i - n_var]->first();
01963 } else {
01964 vars[i]->inedge(NULL);
01965 start[i] = vars[i]->first();
01966 }
01967 }
01968
01969 v->inedge(NULL);
01970 ns.push(v);
01971 visited[v->get_info()] = true;
01972 while (!ns.empty()) {
01973 VVGNode* v = ns.top();
01974 Edge* e = NULL;
01975 if (v->get_type() == sp) {
01976
01977 e = start[v->get_info()];
01978 while (e != NULL && e->template matched<direction>()) {
01979 e = e->next(v->get_type());
01980 }
01981 } else {
01982 e = start[v->get_info()];
01983 while (e != NULL && !e->template matched<direction>()) {
01984 e = e->next(v->get_type());
01985 }
01986 start[v->get_info()] = e;
01987 }
01988 if (e != NULL) {
01989 start[v->get_info()] = e->next(v->get_type());
01990 VVGNode* w = e->getMate(v->get_type());
01991 if (!visited[w->get_info()]) {
01992
01993 if (!w->is_matched(direction) && w->get_type() != sp) {
01994 if (v->inedge() != NULL) {
01995
01996 e->template match<direction>();
01997 break;
01998 } else {
01999
02000 e->template match<direction>();
02001 ns.pop();
02002 return true;
02003 }
02004 } else {
02005 w->inedge(e);
02006 visited[w->get_info()] = true;
02007
02008 ns.push(w);
02009 }
02010 }
02011 } else {
02012
02013 ns.pop();
02014 }
02015 }
02016
02017 bool pathfound = false;
02018 if (!ns.empty()) {
02019 pathfound = true;
02020 }
02021
02022 while (!ns.empty()) {
02023 VVGNode* t = ns.top();
02024 if (t != sn) {
02025 Edge* in = t->inedge();
02026 if (t->get_type() != sp) {
02027 assert(in != NULL);
02028 in->template match<direction>();
02029 } else {
02030
02031 if (!sp) {
02032 in->template unmatch<direction>(!sp);
02033 } else {
02034 in->template unmatch<direction>();
02035 }
02036 }
02037 ns.pop();
02038 } else {
02039 ns.pop();
02040 }
02041 }
02042 return pathfound;
02043 }
02044
02045 template <class View, class Card, bool isView> template<BC direction>
02046 inline void
02047 VarValGraph<View, Card, isView>::free_alternating_paths(void){
02048 Support::StaticStack<VVGNode*> ns(node_size);
02049 GECODE_AUTOARRAY(bool, visited, node_size);
02050
02051 for (int i = node_size; i--; ){
02052 visited[i] = false;
02053 }
02054
02055 if (direction == LBC) {
02056
02057
02058
02059 for (int i = n_var; i--; ){
02060 if(!vars[i]->is_matched(LBC)){
02061
02062 ns.push(vars[i]);
02063 visited[vars[i]->get_info()] = true;
02064 }
02065 }
02066 for (int i = n_val; i--; ){
02067 if(!vals[i]->is_matched(LBC)){
02068
02069 ns.push(vals[i]);
02070 visited[vals[i]->get_info()] = true;
02071 }
02072 }
02073
02074 } else {
02075
02076
02077
02078
02079 for (int i = n_val; i--; ){
02080 if(!vals[i]->is_matched(UBC)){
02081
02082 ns.push(vals[i]);
02083 visited[vals[i]->get_info()] = true;
02084 }
02085 }
02086 }
02087
02088 while(!ns.empty()){
02089 VVGNode* node = ns.top();
02090 ns.pop();
02091 if (node->get_type()) {
02092
02093 ValNode* vln = reinterpret_cast<ValNode*> (node);
02094 for (Edge* cur = vln->first(); cur != NULL; cur = cur->vnext()){
02095 VarNode* mate = cur->getVar();
02096 bool follow = false;
02097 switch (direction) {
02098
02099 case LBC: {
02100 follow = cur->template matched<direction>();
02101 break;
02102 }
02103 case UBC: {
02104 follow = !cur->template matched<direction>();
02105 break;
02106 }
02107 }
02108 if (follow) {
02109
02110 cur->template use<direction>();
02111 if (!visited[mate->get_info()]) {
02112 ns.push(mate);
02113 visited[mate->get_info()] = true;
02114 }
02115 }
02116 }
02117 } else {
02118
02119 VarNode* vrn = reinterpret_cast<VarNode*> (node);
02120 switch (direction) {
02121
02122 case LBC: {
02123 for (Edge* cur = vrn->first(); cur != NULL; cur = cur->next()){
02124 ValNode* mate = cur->getVal();
02125 if (!cur->template matched<LBC>()) {
02126 cur->template use<LBC>();
02127 if (!visited[mate->get_info()]) {
02128 ns.push(mate);
02129 visited[mate->get_info()] = true;
02130 }
02131 }
02132 }
02133 break;
02134 }
02135
02136 case UBC: {
02137 Edge* cur = vrn->template get_match<UBC>();
02138 if (cur != NULL) {
02139 cur->template use<UBC>();
02140 ValNode* mate = cur->getVal();
02141 if (!visited[mate->get_info()]) {
02142 ns.push(mate);
02143 visited[mate->get_info()] = true;
02144 }
02145 }
02146 break;
02147 }
02148 }
02149 }
02150 }
02151 }
02152
02153 template <class View, class Card, bool isView> template <BC direction>
02154 inline void
02155 VarValGraph<View, Card, isView>::dfs(VVGNode* v,
02156 bool inscc[],
02157 bool in_unfinished[],
02158 int dfsnum[],
02159 Support::StaticStack<VVGNode*>& roots,
02160 Support::StaticStack<VVGNode*>& unfinished,
02161 int& count){
02162 count++;
02163 int v_index = v->get_info();
02164 dfsnum[v_index] = count;
02165 inscc[v_index] = true;
02166 in_unfinished[v_index] = true;
02167
02168 unfinished.push(v);
02169 roots.push(v);
02170 for (Edge* e = v->first(); e != NULL; e = e->next(v->get_type())) {
02171 bool condition = false;
02172
02173 if (direction == LBC) {
02174
02175 if (v->get_type()) {
02176 condition = e->template matched<LBC>();
02177 } else {
02178 condition = !e->template matched<LBC>();
02179 }
02180
02181 } else {
02182 if (v->get_type()) {
02183
02184 condition = !e->template matched<UBC>();
02185 } else {
02186 condition = e->template matched<UBC>();
02187 }
02188 }
02189 if (condition) {
02190 VVGNode* w = e->getMate(v->get_type());
02191 int w_index = w->get_info();
02192
02193 assert(w_index < node_size);
02194 if (!inscc[w_index]) {
02195
02196 w->inedge(e);
02197 dfs<direction>(w, inscc, in_unfinished, dfsnum,
02198 roots, unfinished, count);
02199 } else {
02200 if (in_unfinished[w_index]) {
02201
02202
02203 e->template use<direction>();
02204
02205
02206 assert(roots.top()->get_info() < node_size);
02207 while (dfsnum[roots.top()->get_info()] > dfsnum[w_index]) {
02208 roots.pop();
02209 }
02210 }
02211 }
02212 }
02213 }
02214
02215 if (v == roots.top()) {
02216 while (v != unfinished.top()) {
02217
02218 VVGNode* w = unfinished.top();
02219 Edge* ie = w->inedge();
02220 ie->template use<direction>();
02221 in_unfinished[w->get_info()] = false;
02222 unfinished.pop();
02223 }
02224 assert(v == unfinished.top());
02225 in_unfinished[v_index] = false;
02226 roots.pop();
02227 unfinished.pop();
02228 }
02229 }
02230
02231 template <class View, class Card, bool isView> template <BC direction>
02232 inline void
02233 VarValGraph<View, Card, isView>::strongly_connected_components(void){
02234 GECODE_AUTOARRAY(bool, inscc, node_size);
02235 GECODE_AUTOARRAY(bool, in_unfinished, node_size);
02236 GECODE_AUTOARRAY(int, dfsnum, node_size);
02237
02238 for (int i = node_size; i--; ) {
02239 inscc[i] = false;
02240 in_unfinished[i] = false;
02241 dfsnum[i] = 0;
02242 }
02243
02244 int count = 0;
02245 Support::StaticStack<VVGNode*> roots(node_size);
02246 Support::StaticStack<VVGNode*> unfinished(node_size);
02247
02248 for (int i = n_var; i--; ) {
02249 dfs<direction>(vars[i], inscc, in_unfinished, dfsnum,
02250 roots, unfinished, count);
02251 }
02252 }
02253
02254
02255 template <class View, class Card, bool isView>
02256 void
02257 VarValGraph<View, Card, isView>::print_match(void) {
02258 print_matching<UBC>();
02259 print_matching<LBC>();
02260 }
02261
02262
02263 template <class View, class Card, bool isView>
02264 void
02265 VarValGraph<View, Card, isView>::print_edges(void) {
02266 for (int i = 0; i < n_var; i++) {
02267 std::cout << vars[i]->var<<": ";
02268 for (Edge* e = vars[i]->first(); e != NULL; e = e->next()) {
02269 bool ml = e->template matched<LBC>();
02270 bool ul = e->template used<LBC>();
02271 bool mu = e->template matched<UBC>();
02272 bool uu = e->template used<UBC>();
02273 bool condition = (ml || ul || mu || uu);
02274 if (ml) {
02275 std::cout << e->getVal()->val<<" mL, ";
02276 }
02277 if (ul) {
02278 std::cout << e->getVal()->val<<" uL, ";
02279 }
02280 if (mu) {
02281 std::cout << e->getVal()->val<<" mU, ";
02282 }
02283 if (uu) {
02284 std::cout << e->getVal()->val<<" uU, ";
02285 }
02286 if (!condition) {
02287 std::cout << e->getVal()->val<<" x ";
02288 }
02289 }
02290 std::cout <<"\n";
02291 }
02292 std::cout <<"\n";
02293 }
02294
02295
02296 template <class View, class Card, bool isView> template <BC direction>
02297 void
02298 VarValGraph<View, Card, isView>::print_matching(void) {
02299 if (direction == UBC) {
02300 std::cout << "UBM - check:\n";
02301 } else {
02302 std::cout << "LBM - check:\n";
02303 }
02304
02305 for (int i = 0; i < n_var; i++ ){
02306 std::cout << vars[i]->var <<" ";
02307 if (vars[i]->template matched<direction>()) {
02308 if (vars[i]->template get_match<direction>() == NULL) {
02309 std::cout << "N ";
02310 } else {
02311 std::cout << vars[i]->template get_match<direction>() << " ";
02312 std::cout << vars[i]->template get_match<direction>()->getVal()->val << " ";
02313 }
02314 }
02315 std::cout << " <==" << vars[i] <<"\n";
02316 }
02317 std::cout <<"\n";
02318
02319 for (int i = 0; i < n_val; i++ ){
02320 if (vals[i]->template matched<direction>()) {
02321 std::cout << "X ";
02322 } else {
02323 std::cout << "- ";
02324 }
02325 std::cout << vals[i]->template cap<direction>() << " ";
02326 std::cout << vals[i]->get_maxlow() << " ";
02327 std::cout << vals[i]->val << " <==";
02328 for (Edge* e = vals[i]->first(); e != NULL; e = e->vnext()) {
02329 if (e->template matched<direction>()) {
02330 std::cout << e->getVar()->var << ",";
02331 }
02332 }
02333 std::cout <<"\n";
02334 }
02335 std::cout <<"\n";
02336 }
02337
02338 template <class View, class Card, bool isView>
02339 void
02340 VarValGraph<View, Card, isView>::print_graph(void) {
02341 std::cout << "Graph-size = "<<node_size<<" ";
02342 std::cout << "sum_min ="<<sum_min << " & "
02343 << "sum_max ="<<sum_max << "\n";
02344 std::cout << "X-Partition: \n";
02345 for (int i = 0; i < n_var; i++) {
02346 VarNode* vrn = vars[i];
02347 std::cout << "X("<<vars[i]->get_info()<<") ";
02348 std::cout << "["<<vrn->xindex <<"]";
02349 std::cout << "|"<<vrn->noe <<"|";
02350 std::cout << "{";
02351 for (Edge* e = vrn->first(); e != NULL; e = e->next()){
02352 assert(e != NULL);
02353 assert(e->getVal() != NULL);
02354 std::cout << e->getVal()->val<<",";
02355 }
02356 std::cout <<"}\t";
02357 std::cout << "F"<<vrn->first() << ", L" << vrn->last() << " ";
02358 std::cout <<"\n";
02359 }
02360 std::cout <<"\n";
02361
02362 std::cout << "V-Partition: \n";
02363 for (int i = 0; i < n_val; i++) {
02364 ValNode* vln = vals[i];
02365 std::cout << vln->val <<" ";
02366 std::cout << "V(" << i << ") ";
02367 std::cout << "k(" << vln->kmin() << "," <<vln->kmax() << ") ";
02368 std::cout << "c(" << vln->template cap<LBC>() << ","
02369 << vln->template cap<UBC>() << ") ";
02370 std::cout << "ublow: "<<vln->get_maxlow() <<" ";
02371 std::cout << "|"<<vln->noe <<"|";
02372 std::cout << "{";
02373 if (vln->noe == 0 || vln->first() == NULL) {
02374 std::cout << "EMPTY";
02375 } else {
02376 for(Edge* c = vln->first(); c != NULL; c = c->vnext()){
02377 assert(c != NULL);
02378 assert(c->getVar() != NULL);
02379 std::cout << c->getVar()->var << ",";
02380 }
02381 }
02382 std::cout <<"}\t";
02383 std::cout <<"\t";
02384 if (vln->noe == 0 || vln->first() == NULL) {
02385 std::cout <<"no-ptr";
02386 } else {
02387 std::cout << "F"<<vln->first() << ", L" <<vln->last() << " ";
02388 }
02389 std::cout <<"\n";
02390 }
02391 std::cout <<"\n";
02392 }
02393
02394
02395 template <class View, class Card, bool isView>
02396 forceinline
02397 VarValGraph<View, Card, isView>::~VarValGraph(void){
02398 Memory::free(mem);
02399 }
02400
02401 template <class View, class Card, bool isView>
02402 forceinline void*
02403 VarValGraph<View, Card, isView>::operator new(size_t t){
02404 return Memory::malloc(t);
02405 }
02406
02407 template <class View, class Card, bool isView>
02408 forceinline void
02409 VarValGraph<View, Card, isView>::operator delete(void* p){
02410 Memory::free(p);
02411 }
02412
02413
02414 }}}
02415
02416
02417
02418