Generated on Mon Nov 30 23:53:27 2009 for Gecode by doxygen 1.6.1

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: 2009-10-05 20:36:54 +0200 (Mon, 05 Oct 2009) $ by $Author: schulte $
00017  *     $Revision: 9838 $
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     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,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(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(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(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,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]); visited.set(vars[i]->index());
01592         }
01593       for (int i = n_val; i--; )
01594         if (!vals[i]->matched(LBC)) {
01595           ns.push(vals[i]); visited.set(vals[i]->index());
01596         }
01597       break;
01598     case UBC:
01599       // clearly, after a maximum matching on the x variables
01600       // corresponding to a set cover on x there are NO free var nodes
01601       for (int i = n_val; i--; )
01602         if (!vals[i]->matched(UBC)) {
01603           ns.push(vals[i]); visited.set(vals[i]->index());
01604         }
01605       break;
01606     default: GECODE_NEVER;
01607     }
01608 
01609     while (!ns.empty()) {
01610       Node* node = ns.pop();
01611       if (node->type()) {
01612         // ValNode
01613         ValNode* vln = static_cast<ValNode*>(node);
01614 
01615         for (Edge* cur = vln->first(); cur != NULL; cur = cur->vnext()) {
01616           VarNode* mate = cur->getVar();
01617           switch (bc) {
01618           case LBC:
01619             if (cur->matched(LBC)) {
01620               // mark the edge
01621               cur->use(LBC);
01622               if (!visited.get(mate->index())) {
01623                 ns.push(mate); visited.set(mate->index());
01624               }
01625             }
01626             break;
01627           case UBC:
01628             if (!cur->matched(UBC)) {
01629               // mark the edge
01630               cur->use(UBC);
01631               if (!visited.get(mate->index())) {
01632                 ns.push(mate); visited.set(mate->index());
01633               }
01634             }
01635             break;
01636           default: GECODE_NEVER;
01637           }
01638         }
01639 
01640       } else {
01641         // VarNode
01642         VarNode* vrn = static_cast<VarNode*>(node);
01643 
01644         switch (bc) {
01645         case LBC: 
01646           // after LBC-matching we can follow every unmatched edge
01647           for (Edge* cur = vrn->first(); cur != NULL; cur = cur->next()) {
01648             ValNode* mate = cur->getVal();
01649             if (!cur->matched(LBC)) {
01650               cur->use(LBC);
01651               if (!visited.get(mate->index())) {
01652                 ns.push(mate); visited.set(mate->index());
01653               }
01654             }
01655           }
01656           break;
01657         case UBC: 
01658           // after UBC-matching we can only follow a matched edge
01659           {
01660             Edge* cur = vrn->get_match(UBC);
01661             if (cur != NULL) {
01662               cur->use(UBC);
01663               ValNode* mate = cur->getVal();
01664               if (!visited.get(mate->index())) {
01665                 ns.push(mate); visited.set(mate->index());
01666               }
01667             }
01668           }
01669           break;
01670         default: GECODE_NEVER;
01671         }
01672       }
01673     }
01674   }
01675 
01676   template<class Card> template<BC bc>
01677   void
01678   VarValGraph<Card>::dfs(Node* v,
01679                          BitSet& inscc, BitSet& in_unfinished, int dfsnum[],
01680                          NodeStack& roots, NodeStack& unfinished,
01681                          int& count) {
01682     count++;
01683     int v_index            = v->index();
01684     dfsnum[v_index]        = count;
01685     inscc.set(v_index);
01686     in_unfinished.set(v_index);
01687 
01688     unfinished.push(v);
01689     roots.push(v);
01690     for (Edge* e = v->first(); e != NULL; e = e->next(v->type())) {
01691       bool m;
01692       switch (bc) {
01693       case LBC:
01694         m = v->type() ? e->matched(LBC) : !e->matched(LBC);
01695         break;
01696       case UBC:
01697         m = v->type() ? !e->matched(UBC) : e->matched(UBC);
01698         break;
01699       default: GECODE_NEVER;
01700       }
01701       if (m) {
01702         Node* w = e->getMate(v->type());
01703         int w_index = w->index();
01704 
01705         assert(w_index < n_node);
01706         if (!inscc.get(w_index)) {
01707           // w is an uncompleted scc
01708           w->inedge(e);
01709           dfs<bc>(w, inscc, in_unfinished, dfsnum,
01710                   roots, unfinished, count);
01711         } else if (in_unfinished.get(w_index)) {
01712           // even alternating cycle found mark the edge closing the cycle,
01713           // completing the scc
01714           e->use(bc);
01715           // if w belongs to an scc we detected earlier
01716           // merge components
01717           assert(roots.top()->index() < n_node);
01718           while (dfsnum[roots.top()->index()] > dfsnum[w_index]) {
01719             roots.pop();
01720           }
01721         }
01722       }
01723     }
01724 
01725     if (v == roots.top()) {
01726       while (v != unfinished.top()) {
01727         // w belongs to the scc with root v
01728         Node* w = unfinished.top();
01729         w->inedge()->use(bc);
01730         in_unfinished.clear(w->index());
01731         unfinished.pop();
01732       }
01733       assert(v == unfinished.top());
01734       in_unfinished.clear(v_index);
01735       roots.pop();
01736       unfinished.pop();
01737     }
01738   }
01739 
01740   template<class Card> template<BC bc>
01741   forceinline void
01742   VarValGraph<Card>::strongly_connected_components(Space& home) {
01743     Region r(home);
01744     BitSet inscc(r,n_node);
01745     BitSet in_unfinished(r,n_node);
01746     int* dfsnum = r.alloc<int>(n_node);
01747 
01748     for (int i = n_node; i--; )
01749       dfsnum[i]=0;
01750 
01751     int count = 0;
01752     NodeStack roots(r,n_node);
01753     NodeStack unfinished(r,n_node);
01754 
01755     for (int i = n_var; i--; )
01756       dfs<bc>(vars[i], inscc, in_unfinished, dfsnum,
01757               roots, unfinished, count);
01758   }
01759 
01760   template<class Card>
01761   forceinline void*
01762   VarValGraph<Card>::operator new(size_t t, Space& home) {
01763     return home.ralloc(t);
01764   }
01765 
01766 }}}
01767 
01768 // STATISTICS: int-prop
01769 
01770