Generated on Mon May 10 06:46:37 2010 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: 2010-04-08 12:35:31 +0200 (Thu, 08 Apr 2010) $ by $Author: schulte $
00017  *     $Revision: 10684 $
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), nf(nf0), noe(0) {}
00516 
00517   forceinline Edge**
00518   Node::adj(void) {
00519     return &e;
00520   }
00521   forceinline  Edge*
00522   Node::first(void) const {
00523     return fst;
00524   }
00525   forceinline Edge*
00526   Node::last(void) const {
00527     return lst;
00528   }
00529   forceinline void
00530   Node::first(Edge* p) {
00531     fst = p;
00532   }
00533   forceinline void
00534   Node::last(Edge* p) {
00535     lst = p;
00536   }
00537   forceinline bool
00538   Node::type(void) const {
00539     return (nf & NF_VAL) != 0;
00540   }
00541   forceinline Edge*
00542   Node::inedge(void) const {
00543     return ie;
00544   }
00545   forceinline void
00546   Node::inedge(Edge* p) {
00547     ie = p;
00548   }
00549   forceinline bool
00550   Node::removed(void) const {
00551     return noe == 0;
00552   }
00553   forceinline void
00554   Node::index(int i) {
00555     idx = i;
00556   }
00557   forceinline int
00558   Node::index(void) const {
00559     return idx;
00560   }
00561 
00562   forceinline void*
00563   Node::operator new(size_t s, Space& home) {
00564     return home.ralloc(s);
00565   }
00566 
00567 
00568 
00569   /*
00570    * Variable nodes
00571    *
00572    */
00573   forceinline
00574   VarNode::VarNode(void) {}
00575 
00576   forceinline
00577   VarNode::VarNode(int x) :
00578     Node(NF_NONE,x), ubm(NULL), lbm(NULL) {}
00579 
00580   forceinline bool
00581   VarNode::matched(BC bc) const {
00582     if (bc == UBC)
00583       return (nf & NF_M_UBC) != 0;
00584     else
00585       return (nf & NF_M_LBC) != 0;
00586   }
00587 
00588   forceinline void
00589   VarNode::match(BC bc) {
00590     if (bc == UBC)
00591       nf |= NF_M_UBC;
00592     else
00593       nf |= NF_M_LBC;
00594   }
00595 
00596   forceinline void
00597   VarNode::set_match(BC bc, Edge* p) {
00598     if (bc == UBC)
00599       ubm = p;
00600     else
00601       lbm = p;
00602   }
00603 
00604   forceinline void
00605   VarNode::unmatch(BC bc) {
00606     if (bc == UBC) {
00607       nf &= ~NF_M_UBC; ubm = NULL;
00608     } else {
00609       nf &= ~NF_M_LBC; lbm = NULL;
00610     }
00611   }
00612 
00613   forceinline Edge*
00614   VarNode::get_match(BC bc) const {
00615     if (bc == UBC)
00616       return ubm;
00617     else
00618       return lbm;
00619   }
00620 
00621 
00622 
00623 
00624   /*
00625    * Value nodes
00626    *
00627    */
00628   forceinline
00629   ValNode::ValNode(void) {}
00630 
00631   forceinline
00632   ValNode::ValNode(int min, int max, int value,
00633                    int kidx, int kshift, int count) :
00634     Node(NF_VAL,kshift), _klb(min), _kub(max), _kidx(kidx), _kcount(count),
00635     noc(0),
00636     lb(min), ublow(max), ub(max),
00637     val(value) {}
00638 
00639   forceinline void
00640   ValNode::maxlow(int i) {
00641     assert(i >= lb);
00642     ublow = i;
00643   }
00644 
00645   forceinline int
00646   ValNode::maxlow(void) const {
00647     if (_klb == _kub) {
00648       assert(ublow == lb);
00649     }
00650     return ublow;
00651   }
00652 
00653 
00654   forceinline void
00655   ValNode::card_conflict(int c) {
00656     noc = c;
00657   }
00658 
00659   forceinline void
00660   ValNode::red_conflict(void) {
00661     noc--;
00662     assert(noc >= 0);
00663   }
00664 
00665   forceinline int
00666   ValNode::card_conflict(void) const {
00667     return noc;
00668   }
00669 
00670   forceinline int
00671   ValNode::cap(BC bc) const {
00672     if (bc == UBC)
00673       return ub;
00674     else
00675       return lb;
00676   }
00677   forceinline bool
00678   ValNode::matched(BC bc) const {
00679     return cap(bc) == 0;
00680   }
00681 
00682   forceinline void
00683   ValNode::reset(void) {
00684     lb = _klb;
00685     ublow = _kub;
00686     ub = _kub;
00687     noe = 0;
00688   }
00689 
00690   forceinline int
00691   ValNode::kbound(BC bc) const {
00692     if (bc == UBC) {
00693       return _kub;
00694     } else {
00695       return _klb;
00696     }
00697   }
00698 
00699   forceinline int
00700   ValNode::kmax(void) const {
00701     return _kub;
00702   }
00703 
00704   forceinline int
00705   ValNode::kmin(void) const {
00706     return _klb;
00707   }
00708 
00709   forceinline void
00710   ValNode::kmin(int klb) {
00711     _klb = klb;
00712   }
00713 
00714   forceinline void
00715   ValNode::kmax(int kub) {
00716     _kub = kub;
00717   }
00718 
00719 
00720   forceinline void
00721   ValNode::dec(BC bc) {
00722     if (bc == UBC) {
00723       ub--;
00724     } else {
00725       lb--; ublow--;
00726     }
00727   }
00728 
00729   forceinline void
00730   ValNode::inc(BC bc) {
00731     if (bc == UBC) {
00732       ub++;
00733     } else {
00734       lb++; ublow++;
00735     }
00736   }
00737 
00738   forceinline void
00739   ValNode::match(BC bc) {
00740     dec(bc);
00741   }
00742 
00743   forceinline void
00744   ValNode::unmatch(BC bc) {
00745     inc(bc);
00746   }
00747 
00748   forceinline void
00749   ValNode::cap(BC bc, int c) {
00750     if (bc == UBC)
00751       ub = c;
00752     else
00753       lb = c;
00754   }
00755 
00756   forceinline void
00757   ValNode::inc(void) {
00758     _kcount++;
00759   }
00760 
00761   forceinline int
00762   ValNode::kcount(void) const {
00763     return _kcount;
00764   }
00765 
00766   forceinline void
00767   ValNode::kcount(int c) {
00768     _kcount = c;
00769   }
00770 
00771   forceinline void
00772   ValNode::kindex(int i) {
00773     _kidx = i;
00774   }
00775 
00776   forceinline int
00777   ValNode::kindex(void) const {
00778     return _kidx;
00779   }
00780 
00782   forceinline int
00783   ValNode::incid_match(BC bc) const {
00784     if (bc == LBC)
00785       return _kub - ublow + _kcount;
00786     else
00787       return _kub - ub + _kcount;
00788   }
00789 
00790 
00791   forceinline bool
00792   ValNode::sink(void) const {
00793     // there are only incoming edges
00794     // in case of the UBC-matching
00795     return _kub - ub == noe;
00796   }
00797 
00798   forceinline bool
00799   ValNode::source(void) const {
00800     // there are only incoming edges
00801     // in case of the UBC-matching
00802     return _klb - lb == noe;
00803   }
00804 
00805 
00806 
00807   /*
00808    * Edges
00809    *
00810    */
00811   forceinline void
00812   Edge::unlink(void) {
00813     // unlink from variable side
00814     Edge* p = prev_edge;
00815     Edge* n = next_edge;
00816 
00817     if (p != NULL)
00818       *p->next_ref() = n;
00819     if (n != NULL)
00820       *n->prev_ref() = p;
00821 
00822     if (this == x->first()) {
00823       Edge** ref = x->adj();
00824       *ref = n;
00825       x->first(n);
00826     }
00827 
00828     if (this == x->last())
00829       x->last(p);
00830 
00831     // unlink from value side
00832     Edge* pv = prev_vedge;
00833     Edge* nv = next_vedge;
00834 
00835     if (pv != NULL)
00836       *pv->vnext_ref() = nv;
00837     if (nv != NULL)
00838       *nv->vprev_ref() = pv;
00839     if (this == v->first()) {
00840       Edge** ref = v->adj();
00841       *ref = nv;
00842       v->first(nv);
00843     }
00844     if (this == v->last())
00845       v->last(pv);
00846   }
00847 
00848   forceinline
00849   Edge::Edge(VarNode* var, ValNode* val) :
00850     x(var), v(val),
00851     next_edge(NULL), prev_edge(NULL),
00852     next_vedge(NULL), prev_vedge(NULL), ef(EF_NONE) {}
00853 
00854   forceinline void
00855   Edge::use(BC bc) {
00856     if (bc == UBC)
00857       ef |= EF_MRKUB;
00858     else
00859       ef |= EF_MRKLB;
00860   }
00861   forceinline void
00862   Edge::free(BC bc) {
00863     if (bc == UBC)
00864       ef &= ~EF_MRKUB;
00865     else
00866       ef &= ~EF_MRKLB;
00867   }
00868   forceinline bool
00869   Edge::used(BC bc) const {
00870     if (bc == UBC)
00871       return (ef & EF_MRKUB) != 0;
00872     else
00873       return (ef & EF_MRKLB) != 0;
00874   }
00875   forceinline Edge*
00876   Edge::next(void) const {
00877     return next_edge;
00878   }
00879   forceinline Edge*
00880   Edge::next(bool t) const {
00881     if (t) {
00882       return next_vedge;
00883     } else {
00884       return next_edge;
00885     }
00886   }
00887 
00888   forceinline Edge*
00889   Edge::vnext(void) const {
00890     return next_vedge;
00891   }
00892   forceinline Edge**
00893   Edge::vnext_ref(void) {
00894     return &next_vedge;
00895   }
00896   forceinline Edge*
00897   Edge::prev(void) const {
00898     return prev_edge;
00899   }
00900   forceinline Edge**
00901   Edge::prev_ref(void) {
00902     return &prev_edge;
00903   }
00904   forceinline Edge*
00905   Edge::vprev(void) const {
00906     return prev_vedge;
00907   }
00908   forceinline Edge**
00909   Edge::vprev_ref(void) {
00910     return &prev_vedge;
00911   }
00912   forceinline Edge**
00913   Edge::next_ref(void) {
00914     return &next_edge;
00915   }
00916   forceinline VarNode*
00917   Edge::getVar(void) const {
00918     assert(x != NULL);
00919     return x;
00920   }
00921 
00922   forceinline ValNode*
00923   Edge::getVal(void) const {
00924     assert(v != NULL);
00925     return v;
00926   }
00927 
00928   forceinline Node*
00929   Edge::getMate(bool type) const {
00930     if (type)
00931       return x;
00932     else
00933       return v;
00934   }
00935 
00936   forceinline void
00937   Edge::unmatch(BC bc) {
00938     if (bc == UBC)
00939       ef &= ~EF_UM;
00940     else
00941       ef &= ~EF_LM;
00942     x->unmatch(bc); v->unmatch(bc);
00943   }
00944 
00945   forceinline void
00946   Edge::unmatch(BC bc, bool node) {
00947     if (bc == UBC)
00948       ef &= ~EF_UM;
00949     else
00950       ef &= ~EF_LM;
00951     if (node)
00952       v->unmatch(bc);
00953     else
00954       x->unmatch(bc);
00955   }
00956 
00957   forceinline void
00958   Edge::reset(BC bc) {
00959     free(bc); unmatch(bc);
00960   }
00961 
00962   forceinline void
00963   Edge::match(BC bc) {
00964     if (bc == UBC)
00965       ef |= EF_UM;
00966     else
00967       ef |= EF_LM;
00968     x->match(bc);
00969     x->set_match(bc,this);
00970     v->match(bc);
00971   }
00972 
00973   forceinline bool
00974   Edge::matched(BC bc) const {
00975     if (bc == UBC)
00976       return (ef & EF_UM) != 0;
00977     else
00978       return (ef & EF_LM) != 0;
00979   }
00980 
00981   forceinline void
00982   Edge::del_edge(void) {
00983     ef |= EF_DEL;
00984   }
00985 
00986   forceinline void
00987   Edge::insert_edge(void) {
00988     ef &= ~EF_DEL;
00989   }
00990 
00991 
00992   forceinline bool
00993   Edge::deleted(void) const {
00994     return (ef & EF_DEL) != 0;
00995   }
00996 
00997   forceinline void*
00998   Edge::operator new(size_t s, Space& home) {
00999     return home.ralloc(s);
01000   }
01001 
01002 
01003   /*
01004    * Variable value graph
01005    *
01006    */
01007   template<class Card>
01008   VarValGraph<Card>::VarValGraph(Space& home,
01009                                  ViewArray<IntView>& x, ViewArray<Card>& k,
01010                                  int smin, int smax)
01011     : n_var(x.size()),
01012       n_val(k.size()),
01013       n_node(n_var + n_val),
01014       sum_min(smin),
01015       sum_max(smax) {
01016 
01017     unsigned int noe = 0;
01018     for (int i=x.size(); i--; )
01019       noe += x[i].size();
01020 
01021     vars = home.alloc<VarNode*>(n_var);
01022     vals = home.alloc<ValNode*>(n_val);
01023 
01024     for (int i = n_val; i--; ) {
01025       int kmi = k[i].min();
01026       int kma = k[i].max();
01027       int kc  = k[i].counter();
01028       if (kc != kma) {
01029         if (kmi >= kc) {
01030           kmi -=kc;
01031           assert(kmi >=0);
01032         } else {
01033           kmi = 0;
01034         }
01035         kma -= kc;
01036         assert (kma > 0);
01037         vals[i] = new (home)
01038           ValNode(kmi, kma, k[i].card(), i, i + n_var, kc);
01039       } else {
01040         vals[i] = new (home)
01041           ValNode(0, 0, k[i].card(), i, i + n_var, kc);
01042       }
01043     }
01044 
01045     for (int i = n_var; i--; ) {
01046       vars[i] = new (home) VarNode(i);
01047       // get the space for the edges of the varnode
01048       Edge** xadjacent = vars[i]->adj();
01049 
01050       int j = 0;
01051       for (ViewValues<IntView> xi(x[i]); xi(); ++xi) {
01052         // get the correct index for the value
01053         while(vals[j]->val < xi.val())
01054           j++;
01055         *xadjacent = new (home) Edge(vars[i],vals[j]);
01056         vars[i]->noe++;
01057         if (vars[i]->first() == NULL)
01058           vars[i]->first(*xadjacent);
01059         Edge* oldprev  = vars[i]->last();
01060         vars[i]->last(*xadjacent);
01061         *vars[i]->last()->prev_ref() = oldprev;
01062 
01063         if (vals[j]->first() == NULL) {
01064           vals[j]->first(*xadjacent);
01065           vals[j]->last(*xadjacent);
01066         } else {
01067           Edge* old = vals[j]->first();
01068           vals[j]->first(*xadjacent);
01069           *vals[j]->first()->vnext_ref() = old;
01070           *old->vprev_ref() = vals[j]->first();
01071         }
01072         vals[j]->noe++;
01073         xadjacent = (*xadjacent)->next_ref();
01074       }
01075       *xadjacent = NULL;
01076     }
01077   }
01078 
01079 
01080   template<class Card>
01081   inline ExecStatus
01082   VarValGraph<Card>::min_require(Space& home, 
01083                                  ViewArray<IntView>& x,
01084                                  ViewArray<Card>& k) {
01085     for (int i = n_val; i--; ) {
01086       ValNode* vln = vals[i];
01087       if (vln->noe > 0) {
01088         if (k[i].min() == vln->noe) {
01089           // all variable nodes reachable from vln should be equal to vln->val
01090           for (Edge* e = vln->first(); e != NULL; e = e->vnext()) {
01091             VarNode* vrn = e->getVar();
01092             for (Edge* f = vrn->first(); f != NULL; f = f->next())
01093               if (f != e) {
01094                 ValNode* w = f->getVal();
01095                 w->noe--;
01096                 vrn->noe--;
01097                 f->del_edge();
01098                 f->unlink();
01099               }
01100             assert(vrn->noe == 1);
01101 
01102             int vi = vrn->index();
01103             GECODE_ME_CHECK(x[vi].eq(home, vln->val));
01104 
01105             vars[vi] = vars[--n_var];
01106             vars[vi]->index(vi);
01107             x.move_lst(vi);
01108             n_node--;
01109             vln->noe--;
01110           }
01111 
01112 
01113           int vidx = vln->kindex();
01114           if (Card::propagate)
01115             GECODE_ME_CHECK(k[vidx].eq(home, k[vidx].min()));
01116 
01117           k[vidx].counter(k[vidx].min());
01118 
01119           vln->cap(UBC,0);
01120           vln->cap(LBC,0);
01121           vln->maxlow(0);
01122 
01123           if (sum_min >= k[vidx].min())
01124             sum_min -= k[vidx].min();
01125           if (sum_max >= k[vidx].max())
01126             sum_max -= k[vidx].max();
01127         }
01128       } else {
01129         vals[i]->cap(UBC,0);
01130         vals[i]->cap(LBC,0);
01131         vals[i]->maxlow(0);
01132         vals[i]->kmax(0);
01133         vals[i]->kmin(0);
01134       }
01135 
01136       if (Card::propagate && (k[i].counter() == 0))
01137         GECODE_ME_CHECK(k[i].lq(home, vals[i]->noe));
01138     }
01139 
01140     for (int i = n_val; i--; )
01141       vals[i]->index(n_var + i);
01142 
01143     return ES_OK;
01144   }
01145 
01146   template<class Card>
01147   inline ExecStatus
01148   VarValGraph<Card>::sync(Space& home,
01149                           ViewArray<IntView>& x, ViewArray<Card>& k) {
01150     Region r(home);
01151     // A node can be pushed twice (once when checking cardinality and later again)
01152     NodeStack re(r,2*n_node);
01153 
01154     // synchronize cardinality variables
01155     if (Card::propagate) {
01156       for (int i = n_val; i--; ) {
01157         ValNode* v = vals[i];
01158         int inc_ubc = v->incid_match(UBC);
01159         int inc_lbc = v->incid_match(LBC);
01160         if (v->noe == 0) {
01161           inc_ubc = 0;
01162           inc_lbc = 0;
01163         }
01164         int rm = v->kmax() - k[i].max();
01165         // the cardinality bounds have been modified
01166         if ((k[i].max() < v->kmax()) || (k[i].min() > v->kmin())) {
01167           if ((k[i].max() != k[i].counter()) || (k[i].max() == 0)) {
01168             // update the bounds
01169             v->kmax(k[i].max());
01170             v->kmin(k[i].min());
01171 
01172             //everything is fine
01173             if (inc_ubc <= k[i].max()) {
01174               // adjust capacities
01175               v->cap(UBC, k[i].max() - inc_ubc);
01176               v->maxlow(k[i].max() - inc_lbc);
01177               if (v->kmin() == v->kmax())
01178                 v->cap(LBC, k[i].max() - inc_lbc);
01179             } else {
01180               // set cap to max and resolve conflicts on view side
01181               // set to full capacity for later rescheduling
01182               if (v->cap(UBC))
01183                 v->cap(UBC,k[i].max());
01184               v->maxlow(k[i].max() - (inc_lbc));
01185               if (v->kmin() == v->kmax())
01186                 v->cap(LBC,k[i].max() - (inc_lbc));
01187               v->card_conflict(rm);
01188             }
01189           }
01190         }
01191         if (inc_lbc < k[i].min() && v->noe > 0) {
01192           v->cap(LBC, k[i].min() - inc_lbc);
01193           re.push(v);
01194         }
01195       }
01196 
01197       for (int i = n_var; i--; ) {
01198         Edge* mub = vars[i]->get_match(UBC);
01199         if (mub != NULL) {
01200           ValNode* vu = mub->getVal();
01201           if ((vars[i]->noe != 1) && vu->card_conflict()) {
01202             vu->red_conflict();
01203             mub->unmatch(UBC,vars[i]->type());
01204             re.push(vars[i]);
01205           }
01206         }
01207       }
01208     }
01209 
01210     // go on with synchronization
01211     assert(x.size() == n_var);
01212     for (int i = n_var; i--; ) {
01213 
01214       VarNode* vrn = vars[i];
01215       if (static_cast<int>(x[i].size()) != vrn->noe) {
01216         // if the variable is already assigned
01217         if (x[i].assigned()) {
01218           int  v = x[i].val();
01219           ValNode* rv = NULL;
01220           int rv_idx  = 0;
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               rv_idx = rv->kindex();
01247             }
01248           }
01249         } else {
01250 
01251           // delete the edge
01252           ViewValues<IntView> xiter(x[i]);
01253           Edge*  mub = vrn->get_match(UBC);
01254           Edge*  mlb = vrn->get_match(LBC);
01255           Edge** p   = vrn->adj();
01256           Edge*  e   = *p;
01257           do {
01258             // search the edge that has to be deleted
01259             while (e != NULL && (e->getVal()->val < xiter.val())) {
01260               // Skip edge
01261               e->getVal()->noe--;
01262               vrn->noe--;
01263               e->del_edge();
01264               e->unlink();
01265               e = e ->next();
01266               *p = e;
01267             }
01268 
01269             assert(xiter.val() == e->getVal()->val);
01270 
01271             // This edge must be kept
01272             e->free(UBC);
01273             e->free(LBC);
01274             ++xiter;
01275             p = e->next_ref();
01276             e = e->next();
01277           } while (xiter());
01278           *p = NULL;
01279           while (e) {
01280             e->getVar()->noe--;
01281             e->getVal()->noe--;
01282             e->del_edge();
01283             e->unlink();
01284             e = e->next();
01285           }
01286 
01287           if ((mub != NULL) && mub->deleted()) {
01288             mub->unmatch(UBC);
01289             re.push(vars[i]);
01290           }
01291 
01292           //lower bound matching can be zero
01293           if ((mlb != NULL) && mlb->deleted()) {
01294             ValNode* vln = mlb->getVal();
01295             mlb->unmatch(LBC);
01296             if (vln->incid_match(LBC) < vln->kmin())
01297               re.push(vln);
01298           }
01299         }
01300       }
01301       vars[i]->index(i);
01302     }
01303 
01304     for (int i = n_val; i--; ) {
01305       if ((k[i].min() > vals[i]->noe) && (k[i].counter() == 0))
01306         return ES_FAILED;
01307       vals[i]->index(n_var + i);
01308     }
01309 
01310     // start repair
01311     while (!re.empty()) {
01312       Node* n = re.pop();
01313       if (!n->removed()) {
01314         if (!n->type()) {
01315           VarNode* vrn = static_cast<VarNode*>(n);
01316           if (!vrn->matched(UBC) && !augmenting_path<UBC>(home,vrn))
01317             return ES_FAILED;
01318         } else {
01319           ValNode* vln = static_cast<ValNode*>(n);
01320           while (!vln->matched(LBC))
01321             if (!augmenting_path<LBC>(home,vln))
01322               return ES_FAILED;
01323         }
01324       }
01325     }
01326 
01327     return ES_OK;
01328   }
01329 
01330   template<class Card> template<BC bc>
01331   inline ExecStatus
01332   VarValGraph<Card>::narrow(Space& home, 
01333                             ViewArray<IntView>& x, ViewArray<Card>& k) {
01334     for (int i = n_var; i--; )
01335       if (vars[i]->noe == 1) {
01336         ValNode* v = vars[i]->first()->getVal();
01337         vars[i]->first()->free(bc);
01338         GECODE_ME_CHECK(x[i].eq(home, v->val));
01339         v->inc();
01340       }
01341 
01342     for (int i = n_val; i--; ) {
01343       ValNode* v = vals[i];
01344       if (Card::propagate && (k[i].counter() == 0))
01345         GECODE_ME_CHECK(k[i].lq(home, v->noe));
01346       if (v->noe > 0) {
01347         if (Card::propagate)
01348           GECODE_ME_CHECK(k[i].lq(home, v->noe));
01349 
01350         // If the maximum number of occurences of a value is reached
01351         // it cannot be consumed by another view
01352 
01353         if (v->kcount() == v->kmax()) {
01354           int vidx = v->kindex();
01355 
01356           k[i].counter(v->kcount());
01357 
01358           if (Card::propagate)
01359             GECODE_ME_CHECK(k[i].eq(home, k[i].counter()));
01360 
01361           bool delall = v->card_conflict() && (v->noe > v->kmax());
01362 
01363           for (Edge* e = v->last(); e != NULL; e = e->vprev()) {
01364             VarNode* vrn = e->getVar();
01365             if (vrn->noe == 1) {
01366               vrn->noe--;
01367               v->noe--;
01368               int vi= vrn->index();
01369 
01370               x.move_lst(vi);
01371               vars[vi] = vars[--n_var];
01372               vars[vi]->index(vi);
01373               n_node--;
01374               e->del_edge();
01375               e->unlink();
01376 
01377             } else if (delall) {
01378               GECODE_ME_CHECK(x[vrn->index()].nq(home, v->val));
01379               vrn->noe--;
01380               v->noe--;
01381               e->del_edge();
01382               e->unlink();
01383             }
01384           }
01385           v->cap(UBC,0);
01386           v->cap(LBC,0);
01387           v->maxlow(0);
01388           if (sum_min >= k[vidx].min())
01389             sum_min -= k[vidx].min();
01390           if (sum_max >= k[vidx].max())
01391             sum_max -= k[vidx].max();
01392 
01393         } else if (v->kcount() > 0) {
01394           v->kcount(0);
01395         }
01396       }
01397     }
01398     for (int i = n_var; i--; )
01399       vars[i]->index(i);
01400 
01401     for (int i = n_val; i--; ) {
01402       if (vals[i]->noe == 0) {
01403         vals[i]->cap(UBC,0);
01404         vals[i]->cap(LBC,0);
01405         vals[i]->maxlow(0);
01406       }
01407       vals[i]->index(n_var + i);
01408     }
01409 
01410     for (int i = n_var; i--; )
01411       if (vars[i]->noe > 1)
01412         for (Edge* e = vars[i]->first(); e != NULL; e = e->next())
01413           if (!e->matched(bc) && !e->used(bc)) {
01414             GECODE_ME_CHECK(x[i].nq(home, e->getVal()->val));
01415           } else {
01416             e->free(bc);
01417           }
01418 
01419     return ES_OK;
01420   }
01421 
01422   template<class Card> template<BC bc>
01423   forceinline bool
01424   VarValGraph<Card>::augmenting_path(Space& home, Node* v) {
01425     Region r(home);
01426     NodeStack ns(r,n_node);
01427     BitSet visited(r,n_node);
01428     Edge** start = r.alloc<Edge*>(n_node);
01429 
01430     // keep track of the nodes that have already been visited
01431     Node* sn = v;
01432 
01433     // mark the start partition
01434     bool sp = sn->type();
01435 
01436     // nodes in sp only follow free edges
01437     // nodes in V - sp only follow matched edges
01438 
01439     for (int i = n_node; i--; )
01440       if (i >= n_var) {
01441         vals[i-n_var]->inedge(NULL);
01442         start[i] = vals[i-n_var]->first();
01443       } else {
01444         vars[i]->inedge(NULL);
01445         start[i] = vars[i]->first();
01446       }
01447 
01448     v->inedge(NULL);
01449     ns.push(v);
01450     visited.set(v->index());
01451     while (!ns.empty()) {
01452       Node* v = ns.top();
01453       Edge* e = NULL;
01454       if (v->type() == sp) {
01455         e = start[v->index()];
01456         while ((e != NULL) && e->matched(bc))
01457           e = e->next(v->type());
01458       } else {
01459         e = start[v->index()];
01460         while ((e != NULL) && !e->matched(bc))
01461           e = e->next(v->type());
01462         start[v->index()] = e;
01463       }
01464       if (e != NULL) {
01465         start[v->index()] = e->next(v->type());
01466         Node* w = e->getMate(v->type());
01467         if (!visited.get(w->index())) {
01468           // unexplored path
01469           bool m = w->type() ? 
01470             static_cast<ValNode*>(w)->matched(bc) :
01471             static_cast<VarNode*>(w)->matched(bc);
01472           if (!m && w->type() != sp) {
01473             if (v->inedge() != NULL) {
01474               // augmenting path of length l > 1
01475               e->match(bc);
01476               break;
01477             } else {
01478               // augmenting path of length l = 1
01479               e->match(bc);
01480               ns.pop();
01481               return true;
01482             }
01483           } else {
01484             w->inedge(e);
01485             visited.set(w->index());
01486             // find matching edge m incident with w
01487             ns.push(w);
01488           }
01489         }
01490       } else {
01491         // tried all outgoing edges without finding an augmenting path
01492         ns.pop();
01493       }
01494     }
01495 
01496     bool pathfound = !ns.empty();
01497 
01498     while (!ns.empty()) {
01499       Node* t = ns.pop();
01500       if (t != sn) {
01501         Edge* in = t->inedge();
01502         if (t->type() != sp) {
01503           in->match(bc);
01504         } else if (!sp) {
01505           in->unmatch(bc,!sp);
01506         } else {
01507           in->unmatch(bc);
01508         }
01509       }
01510     }
01511     return pathfound;
01512   }
01513 
01514   template<class Card>  template<BC bc>
01515   inline ExecStatus
01516   VarValGraph<Card>::maximum_matching(Space& home) {
01517     int card_match = 0;
01518     // find an intial matching in O(n*d)
01519     // greedy algorithm
01520     for (int i = n_val; i--; )
01521       for (Edge* e = vals[i]->first(); e != NULL ; e = e->vnext())
01522         if (!e->getVar()->matched(bc) && !vals[i]->matched(bc)) {
01523           e->match(bc); card_match++;
01524         }
01525 
01526     Region r(home);
01527     switch (bc) {
01528     case LBC: 
01529       if (card_match < sum_min) {
01530         Support::StaticStack<ValNode*,Region> free(r,n_val);
01531 
01532         // find failed nodes
01533         for (int i = n_val; i--; )
01534           if (!vals[i]->matched(LBC))
01535             free.push(vals[i]);
01536         
01537         while (!free.empty()) {
01538           ValNode* v = free.pop();
01539           while (!v->matched(LBC))
01540             if (augmenting_path<LBC>(home,v))
01541               card_match++;
01542             else
01543               break;
01544         }
01545 
01546         return (card_match >= sum_min) ? ES_OK : ES_FAILED;
01547       } else {
01548         return ES_OK;
01549       }
01550       break;
01551     case UBC:
01552       if (card_match < n_var) {
01553         Support::StaticStack<VarNode*,Region> free(r,n_var);
01554 
01555         // find failed nodes
01556         for (int i = n_var; i--; )
01557           if (!vars[i]->matched(UBC))
01558             free.push(vars[i]);
01559 
01560         while (!free.empty()) {
01561           VarNode* v = free.pop();
01562           if (!v->matched(UBC) && augmenting_path<UBC>(home,v))
01563             card_match++;
01564         }
01565 
01566         return (card_match >= n_var) ? ES_OK : ES_FAILED;
01567       } else {
01568         return ES_OK;
01569       }
01570       break;
01571     default: GECODE_NEVER;
01572     }
01573     GECODE_NEVER;
01574     return ES_FAILED;
01575   }
01576 
01577 
01578   template<class Card> template<BC bc>
01579   forceinline void
01580   VarValGraph<Card>::free_alternating_paths(Space& home) {
01581     Region r(home);
01582     NodeStack ns(r,n_node);
01583     BitSet visited(r,n_node);
01584 
01585     switch (bc) {
01586     case LBC:
01587       // after a maximum matching on the value nodes there still can be
01588       // free value nodes, hence we have to consider ALL nodes whether
01589       // they are the starting point of an even alternating path in G
01590       for (int i = n_var; i--; )
01591         if (!vars[i]->matched(LBC)) {
01592           ns.push(vars[i]); visited.set(vars[i]->index());
01593         }
01594       for (int i = n_val; i--; )
01595         if (!vals[i]->matched(LBC)) {
01596           ns.push(vals[i]); visited.set(vals[i]->index());
01597         }
01598       break;
01599     case UBC:
01600       // clearly, after a maximum matching on the x variables
01601       // corresponding to a set cover on x there are NO free var nodes
01602       for (int i = n_val; i--; )
01603         if (!vals[i]->matched(UBC)) {
01604           ns.push(vals[i]); visited.set(vals[i]->index());
01605         }
01606       break;
01607     default: GECODE_NEVER;
01608     }
01609 
01610     while (!ns.empty()) {
01611       Node* node = ns.pop();
01612       if (node->type()) {
01613         // ValNode
01614         ValNode* vln = static_cast<ValNode*>(node);
01615 
01616         for (Edge* cur = vln->first(); cur != NULL; cur = cur->vnext()) {
01617           VarNode* mate = cur->getVar();
01618           switch (bc) {
01619           case LBC:
01620             if (cur->matched(LBC)) {
01621               // mark the edge
01622               cur->use(LBC);
01623               if (!visited.get(mate->index())) {
01624                 ns.push(mate); visited.set(mate->index());
01625               }
01626             }
01627             break;
01628           case UBC:
01629             if (!cur->matched(UBC)) {
01630               // mark the edge
01631               cur->use(UBC);
01632               if (!visited.get(mate->index())) {
01633                 ns.push(mate); visited.set(mate->index());
01634               }
01635             }
01636             break;
01637           default: GECODE_NEVER;
01638           }
01639         }
01640 
01641       } else {
01642         // VarNode
01643         VarNode* vrn = static_cast<VarNode*>(node);
01644 
01645         switch (bc) {
01646         case LBC: 
01647           // after LBC-matching we can follow every unmatched edge
01648           for (Edge* cur = vrn->first(); cur != NULL; cur = cur->next()) {
01649             ValNode* mate = cur->getVal();
01650             if (!cur->matched(LBC)) {
01651               cur->use(LBC);
01652               if (!visited.get(mate->index())) {
01653                 ns.push(mate); visited.set(mate->index());
01654               }
01655             }
01656           }
01657           break;
01658         case UBC: 
01659           // after UBC-matching we can only follow a matched edge
01660           {
01661             Edge* cur = vrn->get_match(UBC);
01662             if (cur != NULL) {
01663               cur->use(UBC);
01664               ValNode* mate = cur->getVal();
01665               if (!visited.get(mate->index())) {
01666                 ns.push(mate); visited.set(mate->index());
01667               }
01668             }
01669           }
01670           break;
01671         default: GECODE_NEVER;
01672         }
01673       }
01674     }
01675   }
01676 
01677   template<class Card> template<BC bc>
01678   void
01679   VarValGraph<Card>::dfs(Node* v,
01680                          BitSet& inscc, BitSet& in_unfinished, int dfsnum[],
01681                          NodeStack& roots, NodeStack& unfinished,
01682                          int& count) {
01683     count++;
01684     int v_index            = v->index();
01685     dfsnum[v_index]        = count;
01686     inscc.set(v_index);
01687     in_unfinished.set(v_index);
01688 
01689     unfinished.push(v);
01690     roots.push(v);
01691     for (Edge* e = v->first(); e != NULL; e = e->next(v->type())) {
01692       bool m;
01693       switch (bc) {
01694       case LBC:
01695         m = v->type() ? e->matched(LBC) : !e->matched(LBC);
01696         break;
01697       case UBC:
01698         m = v->type() ? !e->matched(UBC) : e->matched(UBC);
01699         break;
01700       default: GECODE_NEVER;
01701       }
01702       if (m) {
01703         Node* w = e->getMate(v->type());
01704         int w_index = w->index();
01705 
01706         assert(w_index < n_node);
01707         if (!inscc.get(w_index)) {
01708           // w is an uncompleted scc
01709           w->inedge(e);
01710           dfs<bc>(w, inscc, in_unfinished, dfsnum,
01711                   roots, unfinished, count);
01712         } else if (in_unfinished.get(w_index)) {
01713           // even alternating cycle found mark the edge closing the cycle,
01714           // completing the scc
01715           e->use(bc);
01716           // if w belongs to an scc we detected earlier
01717           // merge components
01718           assert(roots.top()->index() < n_node);
01719           while (dfsnum[roots.top()->index()] > dfsnum[w_index]) {
01720             roots.pop();
01721           }
01722         }
01723       }
01724     }
01725 
01726     if (v == roots.top()) {
01727       while (v != unfinished.top()) {
01728         // w belongs to the scc with root v
01729         Node* w = unfinished.top();
01730         w->inedge()->use(bc);
01731         in_unfinished.clear(w->index());
01732         unfinished.pop();
01733       }
01734       assert(v == unfinished.top());
01735       in_unfinished.clear(v_index);
01736       roots.pop();
01737       unfinished.pop();
01738     }
01739   }
01740 
01741   template<class Card> template<BC bc>
01742   forceinline void
01743   VarValGraph<Card>::strongly_connected_components(Space& home) {
01744     Region r(home);
01745     BitSet inscc(r,n_node);
01746     BitSet in_unfinished(r,n_node);
01747     int* dfsnum = r.alloc<int>(n_node);
01748 
01749     for (int i = n_node; i--; )
01750       dfsnum[i]=0;
01751 
01752     int count = 0;
01753     NodeStack roots(r,n_node);
01754     NodeStack unfinished(r,n_node);
01755 
01756     for (int i = n_var; i--; )
01757       dfs<bc>(vars[i], inscc, in_unfinished, dfsnum,
01758               roots, unfinished, count);
01759   }
01760 
01761   template<class Card>
01762   forceinline void*
01763   VarValGraph<Card>::operator new(size_t t, Space& home) {
01764     return home.ralloc(t);
01765   }
01766 
01767 }}}
01768 
01769 // STATISTICS: int-prop
01770 
01771