Generated on Wed Jan 4 17:49:10 2006 for Gecode by doxygen 1.4.6

graphsup.icc

Go to the documentation of this file.
00001 /*
00002  *  Main authors:
00003  *     Patrick Pekczynski <pekczynski@ps.uni-sb.de>
00004  *
00005  *  Copyright:
00006  *     Patrick Pekczynski, 2005
00007  *
00008  *  Last modified:
00009  *     $Date: 2005-12-06 07:46:40 +0100 (Tue, 06 Dec 2005) $ by $Author: pekczynski $
00010  *     $Revision: 2696 $
00011  *
00012  *  This file is part of Gecode, the generic constraint
00013  *  development environment:
00014  *     http://www.gecode.org
00015  *
00016  *  See the file "LICENSE" for information on usage and
00017  *  redistribution of this file, and for a
00018  *     DISCLAIMER OF ALL WARRANTIES.
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;   // del
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;           // value partition    De
00467     Edge* edges;              // edges e
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){} //no-op
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     // there are only incoming edges
00950     // in case of the UBC-matching
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     // there are only incoming edges
00959     // in case of the UBC-matching
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     // unlink from variable side
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     // unlink from value side
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){ //why is there no argument?
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     //memory allocation
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       // get the space for the edges of the varnode
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         // get the correct index for the value
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           // all variable nodes reachable from vln should be equal to vln->val
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         // the cardinality bounds have been modified
01421         if (k[i].max() < v->kmax() || k[i].min() > v->kmin()) {
01422           if (!k[i].max() == k[i].counter()) {
01423             // update the bounds
01424             v->set_kmax(k[i].max());
01425             v->set_kmin(k[i].min());
01426 
01427             //everything is fine 
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               // set cap to max and resolve conflicts on view side
01436               // set to full capacity for later rescheduling
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     // because of value propagation it is possible that
01480     // x.size < n_var => hence graphnodes have to be eliminated
01481     // variable size
01482     int xs = x.size();
01483     // graph size (variable partition) 
01484     int gs = n_var;   
01485     if (gs > xs) {
01486       GECODE_AUTOARRAY(bool, idx_used, gs);
01487       // init idx_use
01488       for (int i = gs; i--; ) {
01489         idx_used[i] = false;
01490       }
01491       // mark remaining indices in x 
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           // the node to remove
01507           VarNode* rm = vars[i];
01508           // the value node it is assigned to 
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           // repair upper bound matching
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                 // find a blocking variable node
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             // repair lower bound matching
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                 // find a blocking variable node
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     // adjust value information
01578     for (int i = n_val; i--; ) {
01579       vals[i]->set_info(n_var + i);
01580     }
01581 
01582     // go on with synchronization
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         // if the variable is already assigned
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               // less values than required
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           // delete the edge 
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             // search the edge that has to be deleted
01642             while (e != NULL && e->getVal()->val < xiter.val()) {
01643               // Skip edge
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             // This edge must be kept
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           //lower bound matching can be zero
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     // std::cout << "before end\n";
01709 
01710     if (n_re == 0) {
01711       // no repair needed
01712       // std::cout << "no repair\n";
01713       return true;
01714     } else {
01715       // start repair
01716       
01717       // resolve conflicts
01718       for (int i = n_re; i--; ) {
01719         if ( (cre[i] !=  NULL && cre[i]->is_deleted()) ||
01720              (re[i]->removed()) ) {
01721           // the conflict exists no more
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         // If the maximum number of occurences of a value is reached
01776         // it cannot be consumed by another view
01777         
01778         if (v->kcount() == v->kmax()) {
01779           k[i].counter(v->kcount());
01780 //        std::cout << "eq on : " << v->val<<"\n";
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 //        std::cout << "delall : " << v->val<<"\n";
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 //     min_require(home);
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     // find an intial matching in O(n*d)
01878     // greedy algorithm 
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         // collect free value nodes
01895         GECODE_AUTOARRAY(ValNode*, free, n_val);
01896         int f = 0;
01897         // find failed nodes
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         // find failed nodes
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     // augmenting path starting in a free var node
01946     assert(!v->is_matched(direction));
01947 
01948     // keep track of the nodes that have already been visited
01949     VVGNode* sn = v;
01950 
01951     // mark the start partition
01952     bool sp = sn->get_type(); 
01953 
01954     // nodes in sp only follow free edges
01955     // nodes in V - sp only follow matched edges
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         // follow next free edge
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           // unexplored path
01995           if (!w->is_matched(direction) && w->get_type() != sp) {
01996             if (v->inedge() != NULL) {
01997               // augmenting path of length l > 1
01998               e->template match<direction>();
01999               break;
02000             } else {
02001               // augmenting path of length l = 1
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             // find matching edge m incident with w
02010             ns.push(w);
02011           }
02012         }
02013       } else {
02014         // tried all outgoing edges without finding an augmenting path
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           // avoid defects
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     // keep track of the nodes that have already been visited
02054     for (int i = node_size; i--; ){
02055       visited[i] = false;
02056     }
02057 
02058     if (direction == LBC) {
02059       // after a maximum matching on the value nodes there still can be
02060       // free value nodes, hence we have to consider ALL nodes whether
02061       // they are the starting point of an even alternating path in G
02062       for (int i = n_var; i--; ){
02063         if(!vars[i]->is_matched(LBC)){ 
02064           // unmatched var-node
02065           ns.push(vars[i]);
02066           visited[vars[i]->get_info()] = true;
02067         }
02068       }
02069     } else {
02070       // clearly, after a maximum matching on the x variables 
02071       // corresponding to a set cover on x there are NO free var nodes
02072       //       std::cout << "alt_path for ubm: \n";
02073       // after  max_match_ub there can only be free val-nodes
02074       for (int i = n_val; i--; ){
02075         if(!vals[i]->is_matched(UBC)){ 
02076           // still capacities left
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         // ValNode
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             // edges in M_l are directed from values to variables
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             // mark the edge
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         // VarNode
02114         VarNode* vrn = reinterpret_cast<VarNode*> (node);
02115         switch (direction) {
02116           // after LBC-matching we can follow every unmatched edge
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           // after ub-matching we can only follow a matched edge
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       // LBC-matching
02168       if (direction == LBC) { 
02169         // ValNode
02170         if (v->get_type()) { 
02171           condition = e->template matched<LBC>();
02172         } else {
02173           condition = !e->template matched<LBC>();
02174         }
02175         // UBC - matching
02176       } else { 
02177         if (v->get_type()) {
02178           // in an upper bound matching a valnode only can follow unmatched edges
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           // w is an uncompleted scc
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             // even alternating cycle found mark the edge closing the cycle, 
02197             // completing the scc
02198             e->template use<direction>();
02199             // if w belongs to an scc we detected earlier
02200             // merge components
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         // w belongs to the scc with root v
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   // for debugging purposes
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         // is not matched
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 // STATISTICS: int-prop