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