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