Generated on Thu Mar 22 10:39:38 2012 for Gecode by doxygen 1.6.3

dom-sup.hpp

Go to the documentation of this file.
00001 /* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */
00002 /*
00003  *  Main authors:
00004  *     Patrick Pekczynski <pekczynski@ps.uni-sb.de>
00005  *
00006  *  Contributing authors:
00007  *     Christian Schulte <schulte@gecode.org>
00008  *     Guido Tack <tack@gecode.org>
00009  *
00010  *  Copyright:
00011  *     Patrick Pekczynski, 2005
00012  *     Christian Schulte, 2009
00013  *     Guido Tack, 2009
00014  *
00015  *  Last modified:
00016  *     $Date: 2011-09-01 15:04:29 +0200 (Thu, 01 Sep 2011) $ by $Author: schulte $
00017  *     $Revision: 12384 $
00018  *
00019  *  This file is part of Gecode, the generic constraint
00020  *  development environment:
00021  *     http://www.gecode.org
00022  *
00023  *  Permission is hereby granted, free of charge, to any person obtaining
00024  *  a copy of this software and associated documentation files (the
00025  *  "Software"), to deal in the Software without restriction, including
00026  *  without limitation the rights to use, copy, modify, merge, publish,
00027  *  distribute, sublicense, and/or sell copies of the Software, and to
00028  *  permit persons to whom the Software is furnished to do so, subject to
00029  *  the following conditions:
00030  *
00031  *  The above copyright notice and this permission notice shall be
00032  *  included in all copies or substantial portions of the Software.
00033  *
00034  *  THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
00035  *  EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
00036  *  MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
00037  *  NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
00038  *  LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
00039  *  OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
00040  *  WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
00041  *
00042  */
00043 
00044 namespace Gecode { namespace Int { namespace GCC {
00045 
00052   enum BC {UBC = 1, LBC = 0};
00053 
00054   class Edge;
00056   class Node {
00057   protected:
00059     Edge* e;
00061     Edge* fst;
00063     Edge* lst;
00065     Edge* ie;
00067     int idx;
00069     enum NodeFlag {
00071       NF_NONE  = 0,
00073       NF_VAL   = 1 << 0,
00075       NF_M_LBC = 1 << 1,
00077       NF_M_UBC = 1 << 2
00078     };
00080     unsigned char nf;
00081   public:
00083     int noe;
00084 
00086 
00087 
00088     Node(void);
00090     Node(NodeFlag nf, int i);
00092 
00094 
00095 
00096     bool type(void) const;
00098     Edge** adj(void);
00100     Edge* first(void) const;
00102     Edge* last(void) const;
00104     Edge* inedge(void) const;
00106     int index(void) const;
00108     bool removed(void) const;
00110 
00112 
00113 
00114     void first(Edge* p);
00116     void last(Edge* p);
00118     void inedge(Edge* p);
00120     void index(int i);
00122 
00124 
00125 
00126     static void* operator new(size_t s, Space& home);
00128     static void operator delete(void*, Space&) {};
00130     static void  operator delete(void*) {};
00132   };
00133 
00135   class VarNode : public Node {
00136   protected:
00138     Edge* ubm;
00140     Edge* lbm;
00141   public:
00143 
00144 
00145     VarNode(void);
00147     VarNode(int i);
00149 
00151 
00152 
00153     Edge* get_match(BC bc) const;
00155     bool matched(BC bc) const;
00157 
00159 
00160 
00161     void set_match(BC bc, Edge* m);
00163     void match(BC bc);
00165     void unmatch(BC bc);
00167   };
00168 
00170   class ValNode : public Node {
00171   protected:
00173     int _klb;
00175     int _kub;
00177     int _kidx;
00179     int _kcount;
00181     int noc;
00183     int lb;
00185     int ublow;
00187     int ub;
00188   public:
00190     int val;
00191 
00193 
00194 
00195     ValNode(void);
00203     ValNode(int min, int max, int value, int kidx, int kshift, int count);
00205 
00207 
00208 
00209     int maxlow(void) const;
00211     void card_conflict(int c);
00213     int card_conflict(void) const;
00215     void red_conflict(void);
00217     void inc(void);
00219     int kcount(void) const;
00221     int incid_match(BC bc) const;
00223     int kindex(void) const;
00225     bool matched(BC bc) const;
00227     bool sink(void) const;
00229     bool source(void) const;
00231     int kmin(void) const;
00233     int kmax(void) const;
00235     int kbound(BC bc) const;
00237 
00239 
00240 
00241     void maxlow(int i);
00243     void kcount(int);
00245     void kindex(int);
00247     void dec(BC bc);
00249     void inc(BC bc);
00251     int cap(BC bc) const;
00253     void cap(BC bc, int c);
00255     void match(BC bc);
00257     void unmatch(BC bc);
00259     void reset(void);
00261     void kmin(int min);
00263     void kmax(int max);
00265   };
00266 
00268   class Edge {
00269   private:
00271     VarNode* x;
00273     ValNode* v;
00275     Edge* next_edge;
00277     Edge* prev_edge;
00279     Edge* next_vedge;
00281     Edge* prev_vedge;
00283     enum EdgeFlag {
00285       EF_NONE  = 0,
00287       EF_MRKLB = 1 << 0,
00289       EF_MRKUB = 1 << 1,
00291       EF_LM    = 1 << 2,
00293       EF_UM    = 1 << 3,
00295       EF_DEL   = 1 << 4
00296     };
00298     unsigned char ef;
00299   public:
00301 
00302 
00303     Edge(void) {}
00308     Edge(VarNode* x, ValNode* v);
00310 
00312 
00313 
00314     bool used(BC bc) const;
00316     bool matched(BC bc) const;
00318     bool deleted(void) const;
00324     Edge* next(bool t) const;
00326     Edge* next(void) const;
00328     Edge* prev(void) const;
00330     Edge* vnext(void) const;
00332     Edge* vprev(void) const;
00334     VarNode* getVar(void) const;
00336     ValNode* getVal(void) const;
00341     Node* getMate(bool t) const;
00343 
00345 
00346 
00347     void use(BC bc);
00349     void free(BC bc);
00351     void reset(BC bc);
00353     void match(BC bc);
00355     void unmatch(BC bc);
00357     void unmatch(BC bc, bool t);
00359     void unlink(void);
00361     void del_edge(void);
00363     void insert_edge(void);
00365     Edge** next_ref(void);
00367     Edge** prev_ref(void);
00369     Edge** vnext_ref(void);
00371     Edge** vprev_ref(void);
00373 
00375 
00376 
00377     static void* operator new(size_t s, Space& home);
00379     static void operator delete(void*, Space&) {};
00381     static void operator delete(void*) {};
00383   };
00384 
00385 
00390   template<class Card>
00391   class VarValGraph {
00392   private:
00394     typedef Support::StaticStack<Node*,Region> NodeStack;
00396     typedef Support::BitSet<Region> BitSet;
00398     VarNode** vars;
00406     ValNode** vals;
00408     int n_var;
00414     int n_val;
00416     int n_node;
00422     int sum_min;
00428     int sum_max;
00429   public:
00431 
00432 
00438     VarValGraph(Space& home,
00439                 ViewArray<IntView>& x, ViewArray<Card>& k,
00440                 int smin, int smax);
00442 
00443 
00444 
00445     ExecStatus min_require(Space& home, 
00446                            ViewArray<IntView>& x, ViewArray<Card>& k);
00447 
00456     ExecStatus sync(Space& home,
00457                     ViewArray<IntView>& x, ViewArray<Card>& k);
00459     template<BC>
00460     ExecStatus narrow(Space& home,
00461                       ViewArray<IntView>& x, ViewArray<Card>& k);
00462 
00469     template<BC>
00470     ExecStatus maximum_matching(Space& home);
00471 
00473     template<BC>
00474     void free_alternating_paths(Space& home);
00476     template<BC>
00477     void strongly_connected_components(Space& home);
00483     template<BC>
00484     bool augmenting_path(Space& home, Node*);
00485 
00486   protected:
00493     template<BC>
00494     void dfs(Node*, BitSet&, BitSet&, int[],
00495              NodeStack&, NodeStack&, int&);
00496 
00498   public:
00500     void* operator new(size_t t, Space& home);
00502     void operator delete(void*, Space&) {}
00503   };
00504 
00505 
00506 
00507   /*
00508    * Nodes
00509    *
00510    */
00511   forceinline
00512   Node::Node(void) {}
00513   forceinline
00514   Node::Node(NodeFlag nf0, int i) 
00515     : e(NULL), fst(NULL), lst(NULL), ie(NULL), idx(i), 
00516       nf(static_cast<unsigned char>(nf0)), noe(0) {}
00517 
00518   forceinline Edge**
00519   Node::adj(void) {
00520     return &e;
00521   }
00522   forceinline  Edge*
00523   Node::first(void) const {
00524     return fst;
00525   }
00526   forceinline Edge*
00527   Node::last(void) const {
00528     return lst;
00529   }
00530   forceinline void
00531   Node::first(Edge* p) {
00532     fst = p;
00533   }
00534   forceinline void
00535   Node::last(Edge* p) {
00536     lst = p;
00537   }
00538   forceinline bool
00539   Node::type(void) const {
00540     return (nf & NF_VAL) != 0;
00541   }
00542   forceinline Edge*
00543   Node::inedge(void) const {
00544     return ie;
00545   }
00546   forceinline void
00547   Node::inedge(Edge* p) {
00548     ie = p;
00549   }
00550   forceinline bool
00551   Node::removed(void) const {
00552     return noe == 0;
00553   }
00554   forceinline void
00555   Node::index(int i) {
00556     idx = i;
00557   }
00558   forceinline int
00559   Node::index(void) const {
00560     return idx;
00561   }
00562 
00563   forceinline void*
00564   Node::operator new(size_t s, Space& home) {
00565     return home.ralloc(s);
00566   }
00567 
00568 
00569 
00570   /*
00571    * Variable nodes
00572    *
00573    */
00574   forceinline
00575   VarNode::VarNode(void) {}
00576 
00577   forceinline
00578   VarNode::VarNode(int x) :
00579     Node(NF_NONE,x), ubm(NULL), lbm(NULL) {}
00580 
00581   forceinline bool
00582   VarNode::matched(BC bc) const {
00583     if (bc == UBC)
00584       return (nf & NF_M_UBC) != 0;
00585     else
00586       return (nf & NF_M_LBC) != 0;
00587   }
00588 
00589   forceinline void
00590   VarNode::match(BC bc) {
00591     if (bc == UBC)
00592       nf |= NF_M_UBC;
00593     else
00594       nf |= NF_M_LBC;
00595   }
00596 
00597   forceinline void
00598   VarNode::set_match(BC bc, Edge* p) {
00599     if (bc == UBC)
00600       ubm = p;
00601     else
00602       lbm = p;
00603   }
00604 
00605   forceinline void
00606   VarNode::unmatch(BC bc) {
00607     if (bc == UBC) {
00608       nf &= ~NF_M_UBC; ubm = NULL;
00609     } else {
00610       nf &= ~NF_M_LBC; lbm = NULL;
00611     }
00612   }
00613 
00614   forceinline Edge*
00615   VarNode::get_match(BC bc) const {
00616     if (bc == UBC)
00617       return ubm;
00618     else
00619       return lbm;
00620   }
00621 
00622 
00623 
00624 
00625   /*
00626    * Value nodes
00627    *
00628    */
00629   forceinline
00630   ValNode::ValNode(void) {}
00631 
00632   forceinline
00633   ValNode::ValNode(int min, int max, int value,
00634                    int kidx, int kshift, int count) :
00635     Node(NF_VAL,kshift), _klb(min), _kub(max), _kidx(kidx), _kcount(count),
00636     noc(0),
00637     lb(min), ublow(max), ub(max),
00638     val(value) {}
00639 
00640   forceinline void
00641   ValNode::maxlow(int i) {
00642     assert(i >= lb);
00643     ublow = i;
00644   }
00645 
00646   forceinline int
00647   ValNode::maxlow(void) const {
00648     if (_klb == _kub) {
00649       assert(ublow == lb);
00650     }
00651     return ublow;
00652   }
00653 
00654 
00655   forceinline void
00656   ValNode::card_conflict(int c) {
00657     noc = c;
00658   }
00659 
00660   forceinline void
00661   ValNode::red_conflict(void) {
00662     noc--;
00663     assert(noc >= 0);
00664   }
00665 
00666   forceinline int
00667   ValNode::card_conflict(void) const {
00668     return noc;
00669   }
00670 
00671   forceinline int
00672   ValNode::cap(BC bc) const {
00673     if (bc == UBC)
00674       return ub;
00675     else
00676       return lb;
00677   }
00678   forceinline bool
00679   ValNode::matched(BC bc) const {
00680     return cap(bc) == 0;
00681   }
00682 
00683   forceinline void
00684   ValNode::reset(void) {
00685     lb = _klb;
00686     ublow = _kub;
00687     ub = _kub;
00688     noe = 0;
00689   }
00690 
00691   forceinline int
00692   ValNode::kbound(BC bc) const {
00693     if (bc == UBC) {
00694       return _kub;
00695     } else {
00696       return _klb;
00697     }
00698   }
00699 
00700   forceinline int
00701   ValNode::kmax(void) const {
00702     return _kub;
00703   }
00704 
00705   forceinline int
00706   ValNode::kmin(void) const {
00707     return _klb;
00708   }
00709 
00710   forceinline void
00711   ValNode::kmin(int klb) {
00712     _klb = klb;
00713   }
00714 
00715   forceinline void
00716   ValNode::kmax(int kub) {
00717     _kub = kub;
00718   }
00719 
00720 
00721   forceinline void
00722   ValNode::dec(BC bc) {
00723     if (bc == UBC) {
00724       ub--;
00725     } else {
00726       lb--; ublow--;
00727     }
00728   }
00729 
00730   forceinline void
00731   ValNode::inc(BC bc) {
00732     if (bc == UBC) {
00733       ub++;
00734     } else {
00735       lb++; ublow++;
00736     }
00737   }
00738 
00739   forceinline void
00740   ValNode::match(BC bc) {
00741     dec(bc);
00742   }
00743 
00744   forceinline void
00745   ValNode::unmatch(BC bc) {
00746     inc(bc);
00747   }
00748 
00749   forceinline void
00750   ValNode::cap(BC bc, int c) {
00751     if (bc == UBC)
00752       ub = c;
00753     else
00754       lb = c;
00755   }
00756 
00757   forceinline void
00758   ValNode::inc(void) {
00759     _kcount++;
00760   }
00761 
00762   forceinline int
00763   ValNode::kcount(void) const {
00764     return _kcount;
00765   }
00766 
00767   forceinline void
00768   ValNode::kcount(int c) {
00769     _kcount = c;
00770   }
00771 
00772   forceinline void
00773   ValNode::kindex(int i) {
00774     _kidx = i;
00775   }
00776 
00777   forceinline int
00778   ValNode::kindex(void) const {
00779     return _kidx;
00780   }
00781 
00783   forceinline int
00784   ValNode::incid_match(BC bc) const {
00785     if (bc == LBC)
00786       return _kub - ublow + _kcount;
00787     else
00788       return _kub - ub + _kcount;
00789   }
00790 
00791 
00792   forceinline bool
00793   ValNode::sink(void) const {
00794     // there are only incoming edges
00795     // in case of the UBC-matching
00796     return _kub - ub == noe;
00797   }
00798 
00799   forceinline bool
00800   ValNode::source(void) const {
00801     // there are only incoming edges
00802     // in case of the UBC-matching
00803     return _klb - lb == noe;
00804   }
00805 
00806 
00807 
00808   /*
00809    * Edges
00810    *
00811    */
00812   forceinline void
00813   Edge::unlink(void) {
00814     // unlink from variable side
00815     Edge* p = prev_edge;
00816     Edge* n = next_edge;
00817 
00818     if (p != NULL)
00819       *p->next_ref() = n;
00820     if (n != NULL)
00821       *n->prev_ref() = p;
00822 
00823     if (this == x->first()) {
00824       Edge** ref = x->adj();
00825       *ref = n;
00826       x->first(n);
00827     }
00828 
00829     if (this == x->last())
00830       x->last(p);
00831 
00832     // unlink from value side
00833     Edge* pv = prev_vedge;
00834     Edge* nv = next_vedge;
00835 
00836     if (pv != NULL)
00837       *pv->vnext_ref() = nv;
00838     if (nv != NULL)
00839       *nv->vprev_ref() = pv;
00840     if (this == v->first()) {
00841       Edge** ref = v->adj();
00842       *ref = nv;
00843       v->first(nv);
00844     }
00845     if (this == v->last())
00846       v->last(pv);
00847   }
00848 
00849   forceinline
00850   Edge::Edge(VarNode* var, ValNode* val) :
00851     x(var), v(val),
00852     next_edge(NULL), prev_edge(NULL),
00853     next_vedge(NULL), prev_vedge(NULL), ef(EF_NONE) {}
00854 
00855   forceinline void
00856   Edge::use(BC bc) {
00857     if (bc == UBC)
00858       ef |= EF_MRKUB;
00859     else
00860       ef |= EF_MRKLB;
00861   }
00862   forceinline void
00863   Edge::free(BC bc) {
00864     if (bc == UBC)
00865       ef &= ~EF_MRKUB;
00866     else
00867       ef &= ~EF_MRKLB;
00868   }
00869   forceinline bool
00870   Edge::used(BC bc) const {
00871     if (bc == UBC)
00872       return (ef & EF_MRKUB) != 0;
00873     else
00874       return (ef & EF_MRKLB) != 0;
00875   }
00876   forceinline Edge*
00877   Edge::next(void) const {
00878     return next_edge;
00879   }
00880   forceinline Edge*
00881   Edge::next(bool t) const {
00882     if (t) {
00883       return next_vedge;
00884     } else {
00885       return next_edge;
00886     }
00887   }
00888 
00889   forceinline Edge*
00890   Edge::vnext(void) const {
00891     return next_vedge;
00892   }
00893   forceinline Edge**
00894   Edge::vnext_ref(void) {
00895     return &next_vedge;
00896   }
00897   forceinline Edge*
00898   Edge::prev(void) const {
00899     return prev_edge;
00900   }
00901   forceinline Edge**
00902   Edge::prev_ref(void) {
00903     return &prev_edge;
00904   }
00905   forceinline Edge*
00906   Edge::vprev(void) const {
00907     return prev_vedge;
00908   }
00909   forceinline Edge**
00910   Edge::vprev_ref(void) {
00911     return &prev_vedge;
00912   }
00913   forceinline Edge**
00914   Edge::next_ref(void) {
00915     return &next_edge;
00916   }
00917   forceinline VarNode*
00918   Edge::getVar(void) const {
00919     assert(x != NULL);
00920     return x;
00921   }
00922 
00923   forceinline ValNode*
00924   Edge::getVal(void) const {
00925     assert(v != NULL);
00926     return v;
00927   }
00928 
00929   forceinline Node*
00930   Edge::getMate(bool type) const {
00931     if (type)
00932       return x;
00933     else
00934       return v;
00935   }
00936 
00937   forceinline void
00938   Edge::unmatch(BC bc) {
00939     if (bc == UBC)
00940       ef &= ~EF_UM;
00941     else
00942       ef &= ~EF_LM;
00943     x->unmatch(bc); v->unmatch(bc);
00944   }
00945 
00946   forceinline void
00947   Edge::unmatch(BC bc, bool node) {
00948     if (bc == UBC)
00949       ef &= ~EF_UM;
00950     else
00951       ef &= ~EF_LM;
00952     if (node)
00953       v->unmatch(bc);
00954     else
00955       x->unmatch(bc);
00956   }
00957 
00958   forceinline void
00959   Edge::reset(BC bc) {
00960     free(bc); unmatch(bc);
00961   }
00962 
00963   forceinline void
00964   Edge::match(BC bc) {
00965     if (bc == UBC)
00966       ef |= EF_UM;
00967     else
00968       ef |= EF_LM;
00969     x->match(bc);
00970     x->set_match(bc,this);
00971     v->match(bc);
00972   }
00973 
00974   forceinline bool
00975   Edge::matched(BC bc) const {
00976     if (bc == UBC)
00977       return (ef & EF_UM) != 0;
00978     else
00979       return (ef & EF_LM) != 0;
00980   }
00981 
00982   forceinline void
00983   Edge::del_edge(void) {
00984     ef |= EF_DEL;
00985   }
00986 
00987   forceinline void
00988   Edge::insert_edge(void) {
00989     ef &= ~EF_DEL;
00990   }
00991 
00992 
00993   forceinline bool
00994   Edge::deleted(void) const {
00995     return (ef & EF_DEL) != 0;
00996   }
00997 
00998   forceinline void*
00999   Edge::operator new(size_t s, Space& home) {
01000     return home.ralloc(s);
01001   }
01002 
01003 
01004   /*
01005    * Variable value graph
01006    *
01007    */
01008   template<class Card>
01009   VarValGraph<Card>::VarValGraph(Space& home,
01010                                  ViewArray<IntView>& x, ViewArray<Card>& k,
01011                                  int smin, int smax)
01012     : n_var(x.size()),
01013       n_val(k.size()),
01014       n_node(n_var + n_val),
01015       sum_min(smin),
01016       sum_max(smax) {
01017 
01018     unsigned int noe = 0;
01019     for (int i=x.size(); i--; )
01020       noe += x[i].size();
01021 
01022     vars = home.alloc<VarNode*>(n_var);
01023     vals = home.alloc<ValNode*>(n_val);
01024 
01025     for (int i = n_val; i--; ) {
01026       int kmi = k[i].min();
01027       int kma = k[i].max();
01028       int kc  = k[i].counter();
01029       if (kc != kma) {
01030         if (kmi >= kc) {
01031           kmi -=kc;
01032           assert(kmi >=0);
01033         } else {
01034           kmi = 0;
01035         }
01036         kma -= kc;
01037         assert (kma > 0);
01038         vals[i] = new (home)
01039           ValNode(kmi, kma, k[i].card(), i, i + n_var, kc);
01040       } else {
01041         vals[i] = new (home)
01042           ValNode(0, 0, k[i].card(), i, i + n_var, kc);
01043       }
01044     }
01045 
01046     for (int i = n_var; i--; ) {
01047       vars[i] = new (home) VarNode(i);
01048       // get the space for the edges of the varnode
01049       Edge** xadjacent = vars[i]->adj();
01050 
01051       int j = 0;
01052       for (ViewValues<IntView> xi(x[i]); xi(); ++xi) {
01053         // get the correct index for the value
01054         while(vals[j]->val < xi.val())
01055           j++;
01056         *xadjacent = new (home) Edge(vars[i],vals[j]);
01057         vars[i]->noe++;
01058         if (vars[i]->first() == NULL)
01059           vars[i]->first(*xadjacent);
01060         Edge* oldprev  = vars[i]->last();
01061         vars[i]->last(*xadjacent);
01062         *vars[i]->last()->prev_ref() = oldprev;
01063 
01064         if (vals[j]->first() == NULL) {
01065           vals[j]->first(*xadjacent);
01066           vals[j]->last(*xadjacent);
01067         } else {
01068           Edge* old = vals[j]->first();
01069           vals[j]->first(*xadjacent);
01070           *vals[j]->first()->vnext_ref() = old;
01071           *old->vprev_ref() = vals[j]->first();
01072         }
01073         vals[j]->noe++;
01074         xadjacent = (*xadjacent)->next_ref();
01075       }
01076       *xadjacent = NULL;
01077     }
01078   }
01079 
01080 
01081   template<class Card>
01082   inline ExecStatus
01083   VarValGraph<Card>::min_require(Space& home, 
01084                                  ViewArray<IntView>& x,
01085                                  ViewArray<Card>& k) {
01086     for (int i = n_val; i--; ) {
01087       ValNode* vln = vals[i];
01088       if (vln->noe > 0) {
01089         if (k[i].min() == vln->noe) {
01090           // all variable nodes reachable from vln should be equal to vln->val
01091           for (Edge* e = vln->first(); e != NULL; e = e->vnext()) {
01092             VarNode* vrn = e->getVar();
01093             for (Edge* f = vrn->first(); f != NULL; f = f->next())
01094               if (f != e) {
01095                 ValNode* w = f->getVal();
01096                 w->noe--;
01097                 vrn->noe--;
01098                 f->del_edge();
01099                 f->unlink();
01100               }
01101             assert(vrn->noe == 1);
01102 
01103             int vi = vrn->index();
01104             GECODE_ME_CHECK(x[vi].eq(home, vln->val));
01105 
01106             vars[vi] = vars[--n_var];
01107             vars[vi]->index(vi);
01108             x.move_lst(vi);
01109             n_node--;
01110             vln->noe--;
01111           }
01112 
01113 
01114           int vidx = vln->kindex();
01115           if (Card::propagate)
01116             GECODE_ME_CHECK(k[vidx].eq(home, k[vidx].min()));
01117 
01118           k[vidx].counter(k[vidx].min());
01119 
01120           vln->cap(UBC,0);
01121           vln->cap(LBC,0);
01122           vln->maxlow(0);
01123 
01124           if (sum_min >= k[vidx].min())
01125             sum_min -= k[vidx].min();
01126           if (sum_max >= k[vidx].max())
01127             sum_max -= k[vidx].max();
01128         }
01129       } else {
01130         vals[i]->cap(UBC,0);
01131         vals[i]->cap(LBC,0);
01132         vals[i]->maxlow(0);
01133         vals[i]->kmax(0);
01134         vals[i]->kmin(0);
01135       }
01136 
01137       if (Card::propagate && (k[i].counter() == 0))
01138         GECODE_ME_CHECK(k[i].lq(home, vals[i]->noe));
01139     }
01140 
01141     for (int i = n_val; i--; )
01142       vals[i]->index(n_var + i);
01143 
01144     return ES_OK;
01145   }
01146 
01147   template<class Card>
01148   inline ExecStatus
01149   VarValGraph<Card>::sync(Space& home,
01150                           ViewArray<IntView>& x, ViewArray<Card>& k) {
01151     Region r(home);
01152     // A node can be pushed twice (once when checking cardinality and later again)
01153     NodeStack re(r,2*n_node);
01154 
01155     // synchronize cardinality variables
01156     if (Card::propagate) {
01157       for (int i = n_val; i--; ) {
01158         ValNode* v = vals[i];
01159         int inc_ubc = v->incid_match(UBC);
01160         int inc_lbc = v->incid_match(LBC);
01161         if (v->noe == 0) {
01162           inc_ubc = 0;
01163           inc_lbc = 0;
01164         }
01165         int rm = v->kmax() - k[i].max();
01166         // the cardinality bounds have been modified
01167         if ((k[i].max() < v->kmax()) || (k[i].min() > v->kmin())) {
01168           if ((k[i].max() != k[i].counter()) || (k[i].max() == 0)) {
01169             // update the bounds
01170             v->kmax(k[i].max());
01171             v->kmin(k[i].min());
01172 
01173             //everything is fine
01174             if (inc_ubc <= k[i].max()) {
01175               // adjust capacities
01176               v->cap(UBC, k[i].max() - inc_ubc);
01177               v->maxlow(k[i].max() - inc_lbc);
01178               if (v->kmin() == v->kmax())
01179                 v->cap(LBC, k[i].max() - inc_lbc);
01180             } else {
01181               // set cap to max and resolve conflicts on view side
01182               // set to full capacity for later rescheduling
01183               if (v->cap(UBC))
01184                 v->cap(UBC,k[i].max());
01185               v->maxlow(k[i].max() - (inc_lbc));
01186               if (v->kmin() == v->kmax())
01187                 v->cap(LBC,k[i].max() - (inc_lbc));
01188               v->card_conflict(rm);
01189             }
01190           }
01191         }
01192         if (inc_lbc < k[i].min() && v->noe > 0) {
01193           v->cap(LBC, k[i].min() - inc_lbc);
01194           re.push(v);
01195         }
01196       }
01197 
01198       for (int i = n_var; i--; ) {
01199         Edge* mub = vars[i]->get_match(UBC);
01200         if (mub != NULL) {
01201           ValNode* vu = mub->getVal();
01202           if ((vars[i]->noe != 1) && vu->card_conflict()) {
01203             vu->red_conflict();
01204             mub->unmatch(UBC,vars[i]->type());
01205             re.push(vars[i]);
01206           }
01207         }
01208       }
01209     }
01210 
01211     // go on with synchronization
01212     assert(x.size() == n_var);
01213     for (int i = n_var; i--; ) {
01214 
01215       VarNode* vrn = vars[i];
01216       if (static_cast<int>(x[i].size()) != vrn->noe) {
01217         // if the variable is already assigned
01218         if (x[i].assigned()) {
01219           int  v = x[i].val();
01220           ValNode* rv = NULL;
01221           Edge* mub = vrn->get_match(UBC);
01222           if ((mub != NULL) && (v != mub->getVal()->val)) {
01223             mub->unmatch(UBC);
01224             re.push(vars[i]);
01225           }
01226 
01227           Edge* mlb = vrn->get_match(LBC);
01228           if (mlb != NULL) {
01229             ValNode* vln = mlb->getVal();
01230             if (v != vln->val) {
01231               mlb->unmatch(LBC);
01232               if (vln->incid_match(LBC) < vln->kmin())
01233                 re.push(vln);
01234             }
01235           }
01236 
01237           for (Edge* e = vrn->first(); e != NULL; e = e->next()) {
01238             ValNode* vln = e->getVal();
01239             if (vln->val != v) {
01240               vrn->noe--;
01241               e->getVal()->noe--;
01242               e->del_edge();
01243               e->unlink();
01244             } else {
01245               rv = e->getVal();
01246             }
01247           }
01248         } else {
01249 
01250           // delete the edge
01251           ViewValues<IntView> xiter(x[i]);
01252           Edge*  mub = vrn->get_match(UBC);
01253           Edge*  mlb = vrn->get_match(LBC);
01254           Edge** p   = vrn->adj();
01255           Edge*  e   = *p;
01256           do {
01257             // search the edge that has to be deleted
01258             while (e != NULL && (e->getVal()->val < xiter.val())) {
01259               // Skip edge
01260               e->getVal()->noe--;
01261               vrn->noe--;
01262               e->del_edge();
01263               e->unlink();
01264               e = e ->next();
01265               *p = e;
01266             }
01267 
01268             assert(xiter.val() == e->getVal()->val);
01269 
01270             // This edge must be kept
01271             e->free(UBC);
01272             e->free(LBC);
01273             ++xiter;
01274             p = e->next_ref();
01275             e = e->next();
01276           } while (xiter());
01277           *p = NULL;
01278           while (e) {
01279             e->getVar()->noe--;
01280             e->getVal()->noe--;
01281             e->del_edge();
01282             e->unlink();
01283             e = e->next();
01284           }
01285 
01286           if ((mub != NULL) && mub->deleted()) {
01287             mub->unmatch(UBC);
01288             re.push(vars[i]);
01289           }
01290 
01291           //lower bound matching can be zero
01292           if ((mlb != NULL) && mlb->deleted()) {
01293             ValNode* vln = mlb->getVal();
01294             mlb->unmatch(LBC);
01295             if (vln->incid_match(LBC) < vln->kmin())
01296               re.push(vln);
01297           }
01298         }
01299       }
01300       vars[i]->index(i);
01301     }
01302 
01303     for (int i = n_val; i--; ) {
01304       if ((k[i].min() > vals[i]->noe) && (k[i].counter() == 0))
01305         return ES_FAILED;
01306       vals[i]->index(n_var + i);
01307     }
01308 
01309     // start repair
01310     while (!re.empty()) {
01311       Node* n = re.pop();
01312       if (!n->removed()) {
01313         if (!n->type()) {
01314           VarNode* vrn = static_cast<VarNode*>(n);
01315           if (!vrn->matched(UBC) && !augmenting_path<UBC>(home,vrn))
01316             return ES_FAILED;
01317         } else {
01318           ValNode* vln = static_cast<ValNode*>(n);
01319           while (!vln->matched(LBC))
01320             if (!augmenting_path<LBC>(home,vln))
01321               return ES_FAILED;
01322         }
01323       }
01324     }
01325 
01326     return ES_OK;
01327   }
01328 
01329   template<class Card> template<BC bc>
01330   inline ExecStatus
01331   VarValGraph<Card>::narrow(Space& home, 
01332                             ViewArray<IntView>& x, ViewArray<Card>& k) {
01333     for (int i = n_var; i--; )
01334       if (vars[i]->noe == 1) {
01335         ValNode* v = vars[i]->first()->getVal();
01336         vars[i]->first()->free(bc);
01337         GECODE_ME_CHECK(x[i].eq(home, v->val));
01338         v->inc();
01339       }
01340 
01341     for (int i = n_val; i--; ) {
01342       ValNode* v = vals[i];
01343       if (Card::propagate && (k[i].counter() == 0))
01344         GECODE_ME_CHECK(k[i].lq(home, v->noe));
01345       if (v->noe > 0) {
01346         if (Card::propagate)
01347           GECODE_ME_CHECK(k[i].lq(home, v->noe));
01348 
01349         // If the maximum number of occurences of a value is reached
01350         // it cannot be consumed by another view
01351 
01352         if (v->kcount() == v->kmax()) {
01353           int vidx = v->kindex();
01354 
01355           k[i].counter(v->kcount());
01356 
01357           if (Card::propagate)
01358             GECODE_ME_CHECK(k[i].eq(home, k[i].counter()));
01359 
01360           bool delall = v->card_conflict() && (v->noe > v->kmax());
01361 
01362           for (Edge* e = v->last(); e != NULL; e = e->vprev()) {
01363             VarNode* vrn = e->getVar();
01364             if (vrn->noe == 1) {
01365               vrn->noe--;
01366               v->noe--;
01367               int vi= vrn->index();
01368 
01369               x.move_lst(vi);
01370               vars[vi] = vars[--n_var];
01371               vars[vi]->index(vi);
01372               n_node--;
01373               e->del_edge();
01374               e->unlink();
01375 
01376             } else if (delall) {
01377               GECODE_ME_CHECK(x[vrn->index()].nq(home, v->val));
01378               vrn->noe--;
01379               v->noe--;
01380               e->del_edge();
01381               e->unlink();
01382             }
01383           }
01384           v->cap(UBC,0);
01385           v->cap(LBC,0);
01386           v->maxlow(0);
01387           if (sum_min >= k[vidx].min())
01388             sum_min -= k[vidx].min();
01389           if (sum_max >= k[vidx].max())
01390             sum_max -= k[vidx].max();
01391 
01392         } else if (v->kcount() > 0) {
01393           v->kcount(0);
01394         }
01395       }
01396     }
01397     for (int i = n_var; i--; )
01398       vars[i]->index(i);
01399 
01400     for (int i = n_val; i--; ) {
01401       if (vals[i]->noe == 0) {
01402         vals[i]->cap(UBC,0);
01403         vals[i]->cap(LBC,0);
01404         vals[i]->maxlow(0);
01405       }
01406       vals[i]->index(n_var + i);
01407     }
01408 
01409     for (int i = n_var; i--; )
01410       if (vars[i]->noe > 1)
01411         for (Edge* e = vars[i]->first(); e != NULL; e = e->next())
01412           if (!e->matched(bc) && !e->used(bc)) {
01413             GECODE_ME_CHECK(x[i].nq(home, e->getVal()->val));
01414           } else {
01415             e->free(bc);
01416           }
01417 
01418     return ES_OK;
01419   }
01420 
01421   template<class Card> template<BC bc>
01422   forceinline bool
01423   VarValGraph<Card>::augmenting_path(Space& home, Node* v) {
01424     Region r(home);
01425     NodeStack ns(r,n_node);
01426     BitSet visited(r,static_cast<unsigned int>(n_node));
01427     Edge** start = r.alloc<Edge*>(n_node);
01428 
01429     // keep track of the nodes that have already been visited
01430     Node* sn = v;
01431 
01432     // mark the start partition
01433     bool sp = sn->type();
01434 
01435     // nodes in sp only follow free edges
01436     // nodes in V - sp only follow matched edges
01437 
01438     for (int i = n_node; i--; )
01439       if (i >= n_var) {
01440         vals[i-n_var]->inedge(NULL);
01441         start[i] = vals[i-n_var]->first();
01442       } else {
01443         vars[i]->inedge(NULL);
01444         start[i] = vars[i]->first();
01445       }
01446 
01447     v->inedge(NULL);
01448     ns.push(v);
01449     visited.set(static_cast<unsigned int>(v->index()));
01450     while (!ns.empty()) {
01451       Node* v = ns.top();
01452       Edge* e = NULL;
01453       if (v->type() == sp) {
01454         e = start[v->index()];
01455         while ((e != NULL) && e->matched(bc))
01456           e = e->next(v->type());
01457       } else {
01458         e = start[v->index()];
01459         while ((e != NULL) && !e->matched(bc))
01460           e = e->next(v->type());
01461         start[v->index()] = e;
01462       }
01463       if (e != NULL) {
01464         start[v->index()] = e->next(v->type());
01465         Node* w = e->getMate(v->type());
01466         if (!visited.get(static_cast<unsigned int>(w->index()))) {
01467           // unexplored path
01468           bool m = w->type() ? 
01469             static_cast<ValNode*>(w)->matched(bc) :
01470             static_cast<VarNode*>(w)->matched(bc);
01471           if (!m && w->type() != sp) {
01472             if (v->inedge() != NULL) {
01473               // augmenting path of length l > 1
01474               e->match(bc);
01475               break;
01476             } else {
01477               // augmenting path of length l = 1
01478               e->match(bc);
01479               ns.pop();
01480               return true;
01481             }
01482           } else {
01483             w->inedge(e);
01484             visited.set(static_cast<unsigned int>(w->index()));
01485             // find matching edge m incident with w
01486             ns.push(w);
01487           }
01488         }
01489       } else {
01490         // tried all outgoing edges without finding an augmenting path
01491         ns.pop();
01492       }
01493     }
01494 
01495     bool pathfound = !ns.empty();
01496 
01497     while (!ns.empty()) {
01498       Node* t = ns.pop();
01499       if (t != sn) {
01500         Edge* in = t->inedge();
01501         if (t->type() != sp) {
01502           in->match(bc);
01503         } else if (!sp) {
01504           in->unmatch(bc,!sp);
01505         } else {
01506           in->unmatch(bc);
01507         }
01508       }
01509     }
01510     return pathfound;
01511   }
01512 
01513   template<class Card>  template<BC bc>
01514   inline ExecStatus
01515   VarValGraph<Card>::maximum_matching(Space& home) {
01516     int card_match = 0;
01517     // find an intial matching in O(n*d)
01518     // greedy algorithm
01519     for (int i = n_val; i--; )
01520       for (Edge* e = vals[i]->first(); e != NULL ; e = e->vnext())
01521         if (!e->getVar()->matched(bc) && !vals[i]->matched(bc)) {
01522           e->match(bc); card_match++;
01523         }
01524 
01525     Region r(home);
01526     switch (bc) {
01527     case LBC: 
01528       if (card_match < sum_min) {
01529         Support::StaticStack<ValNode*,Region> free(r,n_val);
01530 
01531         // find failed nodes
01532         for (int i = n_val; i--; )
01533           if (!vals[i]->matched(LBC))
01534             free.push(vals[i]);
01535         
01536         while (!free.empty()) {
01537           ValNode* v = free.pop();
01538           while (!v->matched(LBC))
01539             if (augmenting_path<LBC>(home,v))
01540               card_match++;
01541             else
01542               break;
01543         }
01544 
01545         return (card_match >= sum_min) ? ES_OK : ES_FAILED;
01546       } else {
01547         return ES_OK;
01548       }
01549       break;
01550     case UBC:
01551       if (card_match < n_var) {
01552         Support::StaticStack<VarNode*,Region> free(r,n_var);
01553 
01554         // find failed nodes
01555         for (int i = n_var; i--; )
01556           if (!vars[i]->matched(UBC))
01557             free.push(vars[i]);
01558 
01559         while (!free.empty()) {
01560           VarNode* v = free.pop();
01561           if (!v->matched(UBC) && augmenting_path<UBC>(home,v))
01562             card_match++;
01563         }
01564 
01565         return (card_match >= n_var) ? ES_OK : ES_FAILED;
01566       } else {
01567         return ES_OK;
01568       }
01569       break;
01570     default: GECODE_NEVER;
01571     }
01572     GECODE_NEVER;
01573     return ES_FAILED;
01574   }
01575 
01576 
01577   template<class Card> template<BC bc>
01578   forceinline void
01579   VarValGraph<Card>::free_alternating_paths(Space& home) {
01580     Region r(home);
01581     NodeStack ns(r,n_node);
01582     BitSet visited(r,static_cast<unsigned int>(n_node));
01583 
01584     switch (bc) {
01585     case LBC:
01586       // after a maximum matching on the value nodes there still can be
01587       // free value nodes, hence we have to consider ALL nodes whether
01588       // they are the starting point of an even alternating path in G
01589       for (int i = n_var; i--; )
01590         if (!vars[i]->matched(LBC)) {
01591           ns.push(vars[i]); 
01592           visited.set(static_cast<unsigned int>(vars[i]->index()));
01593         }
01594       for (int i = n_val; i--; )
01595         if (!vals[i]->matched(LBC)) {
01596           ns.push(vals[i]); 
01597           visited.set(static_cast<unsigned int>(vals[i]->index()));
01598         }
01599       break;
01600     case UBC:
01601       // clearly, after a maximum matching on the x variables
01602       // corresponding to a set cover on x there are NO free var nodes
01603       for (int i = n_val; i--; )
01604         if (!vals[i]->matched(UBC)) {
01605           ns.push(vals[i]); 
01606           visited.set(static_cast<unsigned int>(vals[i]->index()));
01607         }
01608       break;
01609     default: GECODE_NEVER;
01610     }
01611 
01612     while (!ns.empty()) {
01613       Node* node = ns.pop();
01614       if (node->type()) {
01615         // ValNode
01616         ValNode* vln = static_cast<ValNode*>(node);
01617 
01618         for (Edge* cur = vln->first(); cur != NULL; cur = cur->vnext()) {
01619           VarNode* mate = cur->getVar();
01620           switch (bc) {
01621           case LBC:
01622             if (cur->matched(LBC)) {
01623               // mark the edge
01624               cur->use(LBC);
01625               if (!visited.get(static_cast<unsigned int>(mate->index()))) {
01626                 ns.push(mate); 
01627                 visited.set(static_cast<unsigned int>(mate->index()));
01628               }
01629             }
01630             break;
01631           case UBC:
01632             if (!cur->matched(UBC)) {
01633               // mark the edge
01634               cur->use(UBC);
01635               if (!visited.get(static_cast<unsigned int>(mate->index()))) {
01636                 ns.push(mate); 
01637                 visited.set(static_cast<unsigned int>(mate->index()));
01638               }
01639             }
01640             break;
01641           default: GECODE_NEVER;
01642           }
01643         }
01644 
01645       } else {
01646         // VarNode
01647         VarNode* vrn = static_cast<VarNode*>(node);
01648 
01649         switch (bc) {
01650         case LBC: 
01651           // after LBC-matching we can follow every unmatched edge
01652           for (Edge* cur = vrn->first(); cur != NULL; cur = cur->next()) {
01653             ValNode* mate = cur->getVal();
01654             if (!cur->matched(LBC)) {
01655               cur->use(LBC);
01656               if (!visited.get(static_cast<unsigned int>(mate->index()))) {
01657                 ns.push(mate); 
01658                 visited.set(static_cast<unsigned int>(mate->index()));
01659               }
01660             }
01661           }
01662           break;
01663         case UBC: 
01664           // after UBC-matching we can only follow a matched edge
01665           {
01666             Edge* cur = vrn->get_match(UBC);
01667             if (cur != NULL) {
01668               cur->use(UBC);
01669               ValNode* mate = cur->getVal();
01670               if (!visited.get(static_cast<unsigned int>(mate->index()))) {
01671                 ns.push(mate); 
01672                 visited.set(static_cast<unsigned int>(mate->index()));
01673               }
01674             }
01675           }
01676           break;
01677         default: GECODE_NEVER;
01678         }
01679       }
01680     }
01681   }
01682 
01683   template<class Card> template<BC bc>
01684   void
01685   VarValGraph<Card>::dfs(Node* v,
01686                          BitSet& inscc, BitSet& in_unfinished, int dfsnum[],
01687                          NodeStack& roots, NodeStack& unfinished,
01688                          int& count) {
01689     count++;
01690     int v_index            = v->index();
01691     dfsnum[v_index]        = count;
01692     inscc.set(static_cast<unsigned int>(v_index));
01693     in_unfinished.set(static_cast<unsigned int>(v_index));
01694 
01695     unfinished.push(v);
01696     roots.push(v);
01697     for (Edge* e = v->first(); e != NULL; e = e->next(v->type())) {
01698       bool m;
01699       switch (bc) {
01700       case LBC:
01701         m = v->type() ? e->matched(LBC) : !e->matched(LBC);
01702         break;
01703       case UBC:
01704         m = v->type() ? !e->matched(UBC) : e->matched(UBC);
01705         break;
01706       default: GECODE_NEVER;
01707       }
01708       if (m) {
01709         Node* w = e->getMate(v->type());
01710         int w_index = w->index();
01711 
01712         assert(w_index < n_node);
01713         if (!inscc.get(static_cast<unsigned int>(w_index))) {
01714           // w is an uncompleted scc
01715           w->inedge(e);
01716           dfs<bc>(w, inscc, in_unfinished, dfsnum,
01717                   roots, unfinished, count);
01718         } else if (in_unfinished.get(static_cast<unsigned int>(w_index))) {
01719           // even alternating cycle found mark the edge closing the cycle,
01720           // completing the scc
01721           e->use(bc);
01722           // if w belongs to an scc we detected earlier
01723           // merge components
01724           assert(roots.top()->index() < n_node);
01725           while (dfsnum[roots.top()->index()] > dfsnum[w_index]) {
01726             roots.pop();
01727           }
01728         }
01729       }
01730     }
01731 
01732     if (v == roots.top()) {
01733       while (v != unfinished.top()) {
01734         // w belongs to the scc with root v
01735         Node* w = unfinished.top();
01736         w->inedge()->use(bc);
01737         in_unfinished.clear(static_cast<unsigned int>(w->index()));
01738         unfinished.pop();
01739       }
01740       assert(v == unfinished.top());
01741       in_unfinished.clear(static_cast<unsigned int>(v_index));
01742       roots.pop();
01743       unfinished.pop();
01744     }
01745   }
01746 
01747   template<class Card> template<BC bc>
01748   forceinline void
01749   VarValGraph<Card>::strongly_connected_components(Space& home) {
01750     Region r(home);
01751     BitSet inscc(r,static_cast<unsigned int>(n_node));
01752     BitSet in_unfinished(r,static_cast<unsigned int>(n_node));
01753     int* dfsnum = r.alloc<int>(n_node);
01754 
01755     for (int i = n_node; i--; )
01756       dfsnum[i]=0;
01757 
01758     int count = 0;
01759     NodeStack roots(r,n_node);
01760     NodeStack unfinished(r,n_node);
01761 
01762     for (int i = n_var; i--; )
01763       dfs<bc>(vars[i], inscc, in_unfinished, dfsnum,
01764               roots, unfinished, count);
01765   }
01766 
01767   template<class Card>
01768   forceinline void*
01769   VarValGraph<Card>::operator new(size_t t, Space& home) {
01770     return home.ralloc(t);
01771   }
01772 
01773 }}}
01774 
01775 // STATISTICS: int-prop
01776 
01777