Generated on Thu Jul 6 07:06:44 2006 for Gecode by doxygen 1.4.7

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