Generated on Fri May 13 2011 22:41:18 for Gecode by doxygen 1.7.1

layered-graph.hpp

Go to the documentation of this file.
00001 /* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */
00002 /*
00003  *  Main authors:
00004  *     Christian Schulte <schulte@gecode.org>
00005  *
00006  *  Copyright:
00007  *     Christian Schulte, 2004
00008  *
00009  *  Last modified:
00010  *     $Date: 2010-07-14 17:46:18 +0200 (Wed, 14 Jul 2010) $ by $Author: schulte $
00011  *     $Revision: 11192 $
00012  *
00013  *  This file is part of Gecode, the generic constraint
00014  *  development environment:
00015  *     http://www.gecode.org
00016  *
00017  *  Permission is hereby granted, free of charge, to any person obtaining
00018  *  a copy of this software and associated documentation files (the
00019  *  "Software"), to deal in the Software without restriction, including
00020  *  without limitation the rights to use, copy, modify, merge, publish,
00021  *  distribute, sublicense, and/or sell copies of the Software, and to
00022  *  permit persons to whom the Software is furnished to do so, subject to
00023  *  the following conditions:
00024  *
00025  *  The above copyright notice and this permission notice shall be
00026  *  included in all copies or substantial portions of the Software.
00027  *
00028  *  THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
00029  *  EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
00030  *  MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
00031  *  NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
00032  *  LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
00033  *  OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
00034  *  WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
00035  *
00036  */
00037 
00038 #include <climits>
00039 #include <algorithm>
00040 
00041 namespace Gecode { namespace Int { namespace Extensional {
00042 
00049   template<class Var>
00050   class VarTraits {};
00051 
00057   template<>
00058   class VarTraits<IntVar> {
00059   public:
00061     typedef Int::IntView View;
00062   };
00063 
00069   template<>
00070   class VarTraits<BoolVar> {
00071   public:
00073     typedef Int::BoolView View;
00074   };
00075 
00076 
00077   /*
00078    * States
00079    */
00080   template<class View, class Val, class Degree, class StateIdx>
00081   forceinline void
00082   LayeredGraph<View,Val,Degree,StateIdx>::State::init(void) {
00083     i_deg=o_deg=0; 
00084   }
00085 
00086   
00087   template<class View, class Val, class Degree, class StateIdx>
00088   forceinline typename LayeredGraph<View,Val,Degree,StateIdx>::State& 
00089   LayeredGraph<View,Val,Degree,StateIdx>::i_state(int i, StateIdx is) {
00090     return layers[i].states[is];
00091   }
00092   template<class View, class Val, class Degree, class StateIdx>
00093   forceinline typename LayeredGraph<View,Val,Degree,StateIdx>::State& 
00094   LayeredGraph<View,Val,Degree,StateIdx>::i_state
00095   (int i, const typename LayeredGraph<View,Val,Degree,StateIdx>::Edge& e) {
00096     return i_state(i,e.i_state);
00097   }
00098   template<class View, class Val, class Degree, class StateIdx>
00099   forceinline bool 
00100   LayeredGraph<View,Val,Degree,StateIdx>::i_dec
00101   (int i, const typename LayeredGraph<View,Val,Degree,StateIdx>::Edge& e) {
00102     return --i_state(i,e).o_deg == 0;
00103   }
00104   template<class View, class Val, class Degree, class StateIdx>
00105   forceinline typename LayeredGraph<View,Val,Degree,StateIdx>::State& 
00106   LayeredGraph<View,Val,Degree,StateIdx>::o_state(int i, StateIdx os) {
00107     return layers[i+1].states[os];
00108   }
00109   template<class View, class Val, class Degree, class StateIdx>
00110   forceinline typename LayeredGraph<View,Val,Degree,StateIdx>::State& 
00111   LayeredGraph<View,Val,Degree,StateIdx>::o_state
00112   (int i, const typename LayeredGraph<View,Val,Degree,StateIdx>::Edge& e) {
00113     return o_state(i,e.o_state);
00114   }
00115   template<class View, class Val, class Degree, class StateIdx>
00116   forceinline bool 
00117   LayeredGraph<View,Val,Degree,StateIdx>::o_dec
00118   (int i, const typename LayeredGraph<View,Val,Degree,StateIdx>::Edge& e) {
00119     return --o_state(i,e).i_deg == 0;
00120   }
00121 
00122 
00123   /*
00124    * Value iterator
00125    */
00126   template<class View, class Val, class Degree, class StateIdx>
00127   forceinline
00128   LayeredGraph<View,Val,Degree,StateIdx>::LayerValues::LayerValues(void) {}
00129   template<class View, class Val, class Degree, class StateIdx>
00130   forceinline
00131   LayeredGraph<View,Val,Degree,StateIdx>::LayerValues
00132   ::LayerValues(const Layer& l)
00133     : s1(l.support), s2(l.support+l.size) {}
00134   template<class View, class Val, class Degree, class StateIdx>
00135   forceinline void
00136   LayeredGraph<View,Val,Degree,StateIdx>::LayerValues::init(const Layer& l) {
00137     s1=l.support; s2=l.support+l.size;
00138   }
00139   template<class View, class Val, class Degree, class StateIdx>
00140   forceinline bool
00141   LayeredGraph<View,Val,Degree,StateIdx>::LayerValues
00142   ::operator ()(void) const {
00143     return s1<s2;
00144   }
00145   template<class View, class Val, class Degree, class StateIdx>
00146   forceinline void
00147   LayeredGraph<View,Val,Degree,StateIdx>::LayerValues::operator ++(void) {
00148     s1++;
00149   }
00150   template<class View, class Val, class Degree, class StateIdx>
00151   forceinline int
00152   LayeredGraph<View,Val,Degree,StateIdx>::LayerValues::val(void) const {
00153     return s1->val;
00154   }
00155 
00156 
00157   /*
00158    * Index advisors
00159    *
00160    */
00161   template<class View, class Val, class Degree, class StateIdx>
00162   forceinline
00163   LayeredGraph<View,Val,Degree,StateIdx>::Index::Index(Space& home, Propagator& p,
00164                                                        Council<Index>& c,
00165                                                        int i0)
00166     : Advisor(home,p,c), i(i0) {}
00167 
00168   template<class View, class Val, class Degree, class StateIdx>
00169   forceinline
00170   LayeredGraph<View,Val,Degree,StateIdx>::Index::Index(Space& home, bool share,
00171                                                        Index& a)
00172     : Advisor(home,share,a), i(a.i) {}
00173 
00174 
00175   /*
00176    * Index ranges
00177    *
00178    */
00179   template<class View, class Val, class Degree, class StateIdx>
00180   forceinline
00181   LayeredGraph<View,Val,Degree,StateIdx>::IndexRange::IndexRange(void)
00182     : _fst(INT_MAX), _lst(INT_MIN) {}
00183   template<class View, class Val, class Degree, class StateIdx>
00184   forceinline void
00185   LayeredGraph<View,Val,Degree,StateIdx>::IndexRange::reset(void) {
00186     _fst=INT_MAX; _lst=INT_MIN;
00187   }
00188   template<class View, class Val, class Degree, class StateIdx>
00189   forceinline void
00190   LayeredGraph<View,Val,Degree,StateIdx>::IndexRange::add(int i) {
00191     _fst=std::min(_fst,i); _lst=std::max(_lst,i);
00192   }
00193   template<class View, class Val, class Degree, class StateIdx>
00194   forceinline void
00195   LayeredGraph<View,Val,Degree,StateIdx>::IndexRange::add
00196   (const typename LayeredGraph<View,Val,Degree,StateIdx>::IndexRange& ir) {
00197     _fst=std::min(_fst,ir._fst); _lst=std::max(_lst,ir._lst);
00198   }
00199   template<class View, class Val, class Degree, class StateIdx>
00200   forceinline bool
00201   LayeredGraph<View,Val,Degree,StateIdx>::IndexRange::empty(void) const {
00202     return _fst>_lst;
00203   }
00204   template<class View, class Val, class Degree, class StateIdx>
00205   forceinline void
00206   LayeredGraph<View,Val,Degree,StateIdx>::IndexRange::lshift(int n) {
00207     if (empty())
00208       return;
00209     if (n > _lst) {
00210       reset();
00211     } else {
00212       _fst = std::max(0,_fst-n);
00213       _lst -= n;
00214     }
00215   }
00216   template<class View, class Val, class Degree, class StateIdx>
00217   forceinline int
00218   LayeredGraph<View,Val,Degree,StateIdx>::IndexRange::fst(void) const {
00219     return _fst;
00220   }
00221   template<class View, class Val, class Degree, class StateIdx>
00222   forceinline int
00223   LayeredGraph<View,Val,Degree,StateIdx>::IndexRange::lst(void) const {
00224     return _lst;
00225   }
00226 
00227 
00228 
00229   /*
00230    * The layered graph
00231    *
00232    */
00233 
00234   template<class View, class Val, class Degree, class StateIdx>
00235   template<class Var>
00236   forceinline
00237   LayeredGraph<View,Val,Degree,StateIdx>::LayeredGraph(Home home,
00238                                                        const VarArgArray<Var>& x, 
00239                                                        const DFA& dfa)
00240     : Propagator(home), c(home), n(x.size()), 
00241       max_states(static_cast<StateIdx>(dfa.n_states())) {
00242     assert(n > 0);
00243   }
00244 
00245   template<class View, class Val, class Degree, class StateIdx>
00246   forceinline void
00247   LayeredGraph<View,Val,Degree,StateIdx>::audit(void) {
00248 #ifdef GECODE_AUDIT
00249     // Check states and edge information to be consistent
00250     unsigned int n_e = 0; // Number of edges
00251     unsigned int n_s = 0; // Number of states
00252     StateIdx m_s = 0; // Maximal number of states per layer
00253     for (int i=n; i--; ) {
00254       n_s += layers[i].n_states;
00255       m_s = std::max(m_s,layers[i].n_states);
00256       for (ValSize j=layers[i].size; j--; )
00257         n_e += layers[i].support[j].n_edges;
00258     }
00259     n_s += layers[n].n_states;
00260     m_s = std::max(m_s,layers[n].n_states);
00261     assert(n_e == n_edges);
00262     assert(n_s <= n_states);
00263     assert(m_s <= max_states);
00264 #endif
00265   }
00266 
00267   template<class View, class Val, class Degree, class StateIdx>
00268   template<class Var>
00269   forceinline ExecStatus
00270   LayeredGraph<View,Val,Degree,StateIdx>::initialize(Space& home,
00271                                                      const VarArgArray<Var>& x, 
00272                                                      const DFA& dfa) {
00273 
00274     Region r(home);
00275 
00276     // Allocate memory for layers
00277     layers = home.alloc<Layer>(n+1);
00278 
00279     // Allocate temporary memory for all possible states
00280     State* states = r.alloc<State>(max_states*(n+1));
00281     for (int i=static_cast<int>(max_states)*(n+1); i--; )
00282       states[i].init();
00283     for (int i=n+1; i--; )
00284       layers[i].states = states + i*max_states;
00285 
00286     // Allocate temporary memory for edges
00287     Edge* edges = r.alloc<Edge>(dfa.max_degree());
00288 
00289     // Mark initial state as being reachable
00290     i_state(0,0).i_deg = 1;
00291 
00292     // Forward pass: add transitions
00293     for (int i=0; i<n; i++) {
00294       layers[i].x = x[i];
00295       layers[i].support = home.alloc<Support>(layers[i].x.size());
00296       ValSize j=0;
00297       // Enter links leaving reachable states (indegree != 0)
00298       for (ViewValues<View> nx(layers[i].x); nx(); ++nx) {
00299         Degree n_edges=0;
00300         for (DFA::Transitions t(dfa,nx.val()); t(); ++t)
00301           if (i_state(i,static_cast<StateIdx>(t.i_state())).i_deg != 0) {
00302             i_state(i,static_cast<StateIdx>(t.i_state())).o_deg++;
00303             o_state(i,static_cast<StateIdx>(t.o_state())).i_deg++;
00304             edges[n_edges].i_state = static_cast<StateIdx>(t.i_state());
00305             edges[n_edges].o_state = static_cast<StateIdx>(t.o_state());
00306             n_edges++;
00307           }
00308         assert(n_edges <= dfa.max_degree());
00309         // Found support for value
00310         if (n_edges > 0) {
00311           Support& s = layers[i].support[j];
00312           s.val = static_cast<Val>(nx.val());
00313           s.n_edges = n_edges;
00314           s.edges = Heap::copy(home.alloc<Edge>(n_edges),edges,n_edges);
00315           j++;
00316         }
00317       }
00318       if ((layers[i].size = j) == 0)
00319         return ES_FAILED;
00320     }
00321 
00322     // Mark final states as reachable
00323     for (int s=dfa.final_fst(); s<dfa.final_lst(); s++)
00324       if (o_state(n-1,static_cast<StateIdx>(s)).i_deg != 0)
00325         o_state(n-1,static_cast<StateIdx>(s)).o_deg = 1;
00326 
00327     // Backward pass: prune all transitions that do not lead to final state
00328     for (int i=n; i--; ) {
00329       ValSize k=0;
00330       for (ValSize j=0; j<layers[i].size; j++) {
00331         Support& s = layers[i].support[j];
00332         for (Degree d=s.n_edges; d--; )
00333           if (o_state(i,s.edges[d]).o_deg == 0) {
00334             // Adapt states
00335             i_dec(i,s.edges[d]); o_dec(i,s.edges[d]);
00336             // Prune edge
00337             s.edges[d] = s.edges[--s.n_edges];
00338           }
00339         // Value has support, copy the support information
00340         if (s.n_edges > 0)
00341           layers[i].support[k++]=s;
00342       }
00343       if ((layers[i].size = k) == 0)
00344         return ES_FAILED;
00345       LayerValues lv(layers[i]);
00346       GECODE_ME_CHECK(layers[i].x.narrow_v(home,lv,false));
00347       if (!layers[i].x.assigned())
00348         layers[i].x.subscribe(home, *new (home) Index(home,*this,c,i));
00349     }
00350 
00351     // Copy and compress states, setup other information
00352     {
00353       // State map for in-states
00354       StateIdx* i_map = r.alloc<StateIdx>(max_states);
00355       // State map for out-states
00356       StateIdx* o_map = r.alloc<StateIdx>(max_states);
00357       // Number of in-states
00358       StateIdx i_n = 0;
00359       // Number of out-states
00360       StateIdx o_n = 0;
00361 
00362       // Initialize map for in-states (special for last layer)
00363       // Degree for single final state
00364       unsigned int d = 0;
00365       for (StateIdx j=max_states; j--; )
00366         d += static_cast<unsigned int>(layers[n].states[j].i_deg);
00367       // Check whether all final states can be joined to a single state
00368       if (d > 
00369           static_cast<unsigned int>
00370           (Gecode::Support::IntTypeTraits<Degree>::max)) {
00371         // Initialize map for in-states
00372         for (StateIdx j=max_states; j--; )
00373           if ((layers[n].states[j].o_deg != 0) ||
00374               (layers[n].states[j].i_deg != 0))
00375             i_map[j]=i_n++;
00376       } else {
00377         i_n = 1;
00378         for (StateIdx j=max_states; j--; ) {
00379           layers[n].states[j].init();
00380           i_map[j] = 0;
00381         }
00382         layers[n].states[0].i_deg = static_cast<Degree>(d);
00383         layers[n].states[0].o_deg = 1;
00384       }
00385       layers[n].n_states = i_n;
00386       
00387       // Total number of states
00388       n_states = i_n;
00389       // Total number of edges
00390       n_edges = 0;
00391       // New maximal number of states
00392       StateIdx max_s = i_n;
00393 
00394       for (int i=n; i--; ) {
00395         // In-states become out-states
00396         std::swap(o_map,i_map); o_n=i_n; i_n=0;
00397         // Initialize map for in-states
00398         for (StateIdx j=max_states; j--; )
00399           if ((layers[i].states[j].o_deg != 0) ||
00400               (layers[i].states[j].i_deg != 0))
00401             i_map[j]=i_n++;
00402         layers[i].n_states = i_n;
00403         n_states += i_n;
00404         max_s = std::max(max_s,i_n);
00405 
00406         // Update states in edges
00407         for (ValSize j=layers[i].size; j--; ) {
00408           Support& s = layers[i].support[j];
00409           n_edges += s.n_edges;
00410           for (Degree d=s.n_edges; d--; ) {
00411             s.edges[d].i_state = i_map[s.edges[d].i_state];
00412             s.edges[d].o_state = o_map[s.edges[d].o_state];
00413           }
00414         }
00415       }
00416 
00417       // Allocate and copy states
00418       State* a_states = home.alloc<State>(n_states);
00419       for (int i=n+1; i--; ) {
00420         StateIdx k=0;
00421         for (StateIdx j=max_states; j--; )
00422           if ((layers[i].states[j].o_deg != 0) ||
00423               (layers[i].states[j].i_deg != 0))
00424             a_states[k++] = layers[i].states[j];
00425         assert(k == layers[i].n_states);
00426         layers[i].states = a_states;
00427         a_states += layers[i].n_states;
00428       }
00429       
00430       // Update maximal number of states
00431       max_states = max_s;
00432     }
00433 
00434     // Schedule if subsumption is needed
00435     if (c.empty())
00436       View::schedule(home,*this,ME_INT_VAL);
00437 
00438     audit();
00439     return ES_OK;
00440   }
00441 
00442   template<class View, class Val, class Degree, class StateIdx>
00443   ExecStatus
00444   LayeredGraph<View,Val,Degree,StateIdx>::advise(Space& home,
00445                                                  Advisor& _a, const Delta& d) {
00446     // Check whether state information has already been created
00447     if (layers[0].states == NULL) {
00448       State* states = home.alloc<State>(n_states);
00449       for (unsigned int i=n_states; i--; )
00450         states[i].init();
00451       layers[n].states = states;
00452       states += layers[n].n_states;
00453       for (int i=n; i--; ) {
00454         layers[i].states = states;
00455         states += layers[i].n_states;
00456         for (ValSize j=layers[i].size; j--; ) {
00457           Support& s = layers[i].support[j];
00458           for (Degree d=s.n_edges; d--; ) {
00459             i_state(i,s.edges[d]).o_deg++;
00460             o_state(i,s.edges[d]).i_deg++;
00461           }
00462         }
00463       }
00464     }
00465     
00466     Index& a = static_cast<Index&>(_a);
00467     const int i = a.i;
00468 
00469     if (layers[i].size <= layers[i].x.size()) {
00470       // Propagator has already done everything
00471       if (View::modevent(d) == ME_INT_VAL) {
00472         a.dispose(home,c);
00473         return c.empty() ? ES_NOFIX : ES_FIX;
00474       } else {
00475         return ES_FIX;
00476       }
00477     }
00478 
00479     bool i_mod = false;
00480     bool o_mod = false;
00481 
00482     if (View::modevent(d) == ME_INT_VAL) {
00483       Val n = static_cast<Val>(layers[i].x.val());
00484       ValSize j=0;
00485       for (; layers[i].support[j].val < n; j++) {
00486         Support& s = layers[i].support[j];
00487         n_edges -= s.n_edges;
00488         // Supported value not any longer in view
00489         for (Degree d=s.n_edges; d--; ) {
00490           // Adapt states
00491           o_mod |= i_dec(i,s.edges[d]);
00492           i_mod |= o_dec(i,s.edges[d]);
00493         }
00494       }
00495       assert(layers[i].support[j].val == n);
00496       layers[i].support[0] = layers[i].support[j++];
00497       ValSize s=layers[i].size;
00498       layers[i].size = 1;
00499       for (; j<s; j++) {
00500         Support& s = layers[i].support[j];
00501         n_edges -= s.n_edges;
00502         for (Degree d=s.n_edges; d--; ) {
00503           // Adapt states
00504           o_mod |= i_dec(i,s.edges[d]);
00505           i_mod |= o_dec(i,s.edges[d]);
00506         }
00507       }
00508     } else if (layers[i].x.any(d)) {
00509       ValSize j=0;
00510       ValSize k=0;
00511       ValSize s=layers[i].size;
00512       for (ViewRanges<View> rx(layers[i].x); rx() && (j<s);) {
00513         Support& s = layers[i].support[j];
00514         if (s.val < static_cast<Val>(rx.min())) {
00515           // Supported value not any longer in view
00516           n_edges -= s.n_edges;
00517           for (Degree d=s.n_edges; d--; ) {
00518             // Adapt states
00519             o_mod |= i_dec(i,s.edges[d]);
00520             i_mod |= o_dec(i,s.edges[d]);
00521           }
00522           ++j;
00523         } else if (s.val > static_cast<Val>(rx.max())) {
00524           ++rx;
00525         } else {
00526           layers[i].support[k++]=s;
00527           ++j;
00528         }
00529       }
00530       assert(k > 0);
00531       layers[i].size = k;
00532       // Remove remaining values
00533       for (; j<s; j++) {
00534         Support& s=layers[i].support[j];
00535         n_edges -= s.n_edges;
00536         for (Degree d=s.n_edges; d--; ) {
00537           // Adapt states
00538           o_mod |= i_dec(i,s.edges[d]);
00539           i_mod |= o_dec(i,s.edges[d]);
00540         }
00541       }
00542     } else {
00543       Val min = static_cast<Val>(layers[i].x.min(d));
00544       ValSize j=0;
00545       // Skip values smaller than min (to keep)
00546       for (; layers[i].support[j].val < min; j++) {}
00547       Val max = static_cast<Val>(layers[i].x.max(d));
00548       ValSize k=j;
00549       ValSize s=layers[i].size;
00550       // Remove pruned values
00551       for (; (j<s) && (layers[i].support[j].val <= max); j++) {
00552         Support& s=layers[i].support[j];
00553         n_edges -= s.n_edges;
00554         for (Degree d=s.n_edges; d--; ) {
00555           // Adapt states
00556           o_mod |= i_dec(i,s.edges[d]);
00557           i_mod |= o_dec(i,s.edges[d]);
00558         }
00559       }
00560       // Keep remaining values
00561       while (j<s)
00562         layers[i].support[k++]=layers[i].support[j++];
00563       layers[i].size =k;
00564       assert(k > 0);
00565     }
00566 
00567     audit();
00568 
00569     bool fix = true;
00570     if (o_mod && (i > 0)) {
00571       o_ch.add(i-1); fix = false;
00572      }
00573     if (i_mod && (i+1 < n)) {
00574       i_ch.add(i+1); fix = false;
00575     }
00576     if (fix) {
00577       if (View::modevent(d) == ME_INT_VAL) {
00578         a.dispose(home,c);
00579         return c.empty() ? ES_NOFIX : ES_FIX;
00580       }
00581       return ES_FIX;
00582     } else {
00583       return (View::modevent(d) == ME_INT_VAL)
00584         ? home.ES_NOFIX_DISPOSE(c,a) : ES_NOFIX;
00585     }
00586   }
00587 
00588   template<class View, class Val, class Degree, class StateIdx>
00589   forceinline size_t
00590   LayeredGraph<View,Val,Degree,StateIdx>::dispose(Space& home) {
00591     c.dispose(home);
00592     (void) Propagator::dispose(home);
00593     return sizeof(*this);
00594   }
00595 
00596   template<class View, class Val, class Degree, class StateIdx>
00597   ExecStatus
00598   LayeredGraph<View,Val,Degree,StateIdx>::propagate(Space& home,
00599                                                     const ModEventDelta&) {
00600     // Forward pass
00601     for (int i=i_ch.fst(); i<=i_ch.lst(); i++) {
00602       bool i_mod = false;
00603       bool o_mod = false;
00604       ValSize j=0;
00605       ValSize k=0;
00606       ValSize s=layers[i].size;
00607       do {
00608         Support& s=layers[i].support[j];
00609         n_edges -= s.n_edges;
00610         for (Degree d=s.n_edges; d--; )
00611           if (i_state(i,s.edges[d]).i_deg == 0) {
00612             // Adapt states
00613             o_mod |= i_dec(i,s.edges[d]);
00614             i_mod |= o_dec(i,s.edges[d]);
00615             // Remove edge
00616             s.edges[d] = s.edges[--s.n_edges];
00617           }
00618         n_edges += s.n_edges;
00619         // Check whether value is still supported
00620         if (s.n_edges == 0) {
00621           layers[i].size--;
00622           GECODE_ME_CHECK(layers[i].x.nq(home,s.val));
00623         } else {
00624           layers[i].support[k++]=s;
00625         }
00626       } while (++j<s);
00627       assert(k > 0);
00628       // Update modification information
00629       if (o_mod && (i > 0))
00630         o_ch.add(i-1);
00631       if (i_mod && (i+1 < n))
00632         i_ch.add(i+1);
00633     }
00634 
00635     // Backward pass
00636     for (int i=o_ch.lst(); i>=o_ch.fst(); i--) {
00637       bool o_mod = false;
00638       ValSize j=0;
00639       ValSize k=0;
00640       ValSize s=layers[i].size;
00641       do {
00642         Support& s=layers[i].support[j];
00643         n_edges -= s.n_edges;
00644         for (Degree d=s.n_edges; d--; )
00645           if (o_state(i,s.edges[d]).o_deg == 0) {
00646             // Adapt states
00647             o_mod |= i_dec(i,s.edges[d]);
00648             (void)   o_dec(i,s.edges[d]);
00649             // Remove edge
00650             s.edges[d] = s.edges[--s.n_edges];
00651           }
00652         n_edges += s.n_edges;
00653         // Check whether value is still supported
00654         if (s.n_edges == 0) {
00655           layers[i].size--;
00656           GECODE_ME_CHECK(layers[i].x.nq(home,s.val));
00657         } else {
00658           layers[i].support[k++]=s;
00659         }
00660       } while (++j<s);
00661       assert(k > 0);
00662       // Update modification information
00663       if (o_mod && (i > 0))
00664         o_ch.add(i-1);
00665     }
00666 
00667     a_ch.add(i_ch); i_ch.reset();
00668     a_ch.add(o_ch); o_ch.reset();
00669 
00670     audit();
00671 
00672     // Check subsumption
00673     if (c.empty())
00674       return home.ES_SUBSUMED(*this);
00675     else
00676       return ES_FIX;
00677   }
00678 
00679 
00680   template<class View, class Val, class Degree, class StateIdx>
00681   template<class Var>
00682   ExecStatus
00683   LayeredGraph<View,Val,Degree,StateIdx>::post(Home home, 
00684                                                const VarArgArray<Var>& x,
00685                                                const DFA& dfa) {
00686     if (x.size() == 0) {
00687       // Check whether the start state 0 is also a final state
00688       if ((dfa.final_fst() <= 0) && (dfa.final_lst() >= 0))
00689         return ES_OK;
00690       return ES_FAILED;
00691     }
00692     assert(x.size() > 0);
00693     for (int i=x.size(); i--; ) {
00694       DFA::Symbols s(dfa);
00695       typename VarTraits<Var>::View xi(x[i]);
00696       GECODE_ME_CHECK(xi.inter_v(home,s,false));
00697     }
00698     LayeredGraph<View,Val,Degree,StateIdx>* p =
00699       new (home) LayeredGraph<View,Val,Degree,StateIdx>(home,x,dfa);
00700     return p->initialize(home,x,dfa);
00701   }
00702 
00703   template<class View, class Val, class Degree, class StateIdx>
00704   forceinline
00705   LayeredGraph<View,Val,Degree,StateIdx>
00706   ::LayeredGraph(Space& home, bool share,
00707                  LayeredGraph<View,Val,Degree,StateIdx>& p)
00708     : Propagator(home,share,p), 
00709       n(p.n), layers(home.alloc<Layer>(n+1)),
00710       max_states(p.max_states), n_states(p.n_states), n_edges(p.n_edges) {
00711     c.update(home,share,p.c);
00712     // Do not allocate states, postpone to advise!
00713     layers[n].n_states = p.layers[n].n_states;
00714     layers[n].states = NULL;
00715     // Allocate memory for edges
00716     Edge* edges = home.alloc<Edge>(n_edges);
00717     // Copy layers
00718     for (int i=n; i--; ) {
00719       layers[i].x.update(home,share,p.layers[i].x);
00720       assert(layers[i].x.size() == p.layers[i].size);
00721       layers[i].size = p.layers[i].size;
00722       layers[i].support = home.alloc<Support>(layers[i].size);
00723       for (ValSize j=layers[i].size; j--; ) {
00724         layers[i].support[j].val = p.layers[i].support[j].val;
00725         layers[i].support[j].n_edges = p.layers[i].support[j].n_edges;
00726         assert(layers[i].support[j].n_edges > 0);
00727         layers[i].support[j].edges = 
00728           Heap::copy(edges,p.layers[i].support[j].edges,
00729                      layers[i].support[j].n_edges);
00730         edges += layers[i].support[j].n_edges;
00731       }
00732       layers[i].n_states = p.layers[i].n_states;
00733       layers[i].states = NULL;
00734     }
00735     audit();
00736   }
00737 
00738   template<class View, class Val, class Degree, class StateIdx>
00739   PropCost
00740   LayeredGraph<View,Val,Degree,StateIdx>::cost(const Space&,
00741                                                const ModEventDelta&) const {
00742     return PropCost::linear(PropCost::HI,n);
00743   }
00744 
00745   template<class View, class Val, class Degree, class StateIdx>
00746   Actor*
00747   LayeredGraph<View,Val,Degree,StateIdx>::copy(Space& home, bool share) {
00748     // Eliminate an assigned prefix
00749     {
00750       int k=0;
00751       while (layers[k].size == 1) {
00752         assert(layers[k].support[0].n_edges == 1);
00753         n_states -= layers[k].n_states;
00754         k++;
00755       }
00756       if (k > 0) {
00757         /*
00758          * The state information is always available: either the propagator
00759          * has been created (hence, also the state information has been
00760          * created), or the first variable become assigned and hence
00761          * an advisor must have been run (which then has created the state
00762          * information).
00763          */
00764         // Eliminate assigned layers
00765         n -= k; layers += k;
00766         // Eliminate edges
00767         n_edges -= static_cast<unsigned int>(k);
00768         // Update advisor indices
00769         for (Advisors<Index> as(c); as(); ++as)
00770           as.advisor().i -= k;
00771         // Update all change information
00772         a_ch.lshift(k);
00773       }
00774     }
00775     audit();
00776 
00777     // Compress states
00778     if (!a_ch.empty()) {
00779       int f = a_ch.fst();
00780       int l = a_ch.lst();
00781       assert((f >= 0) && (l <= n));
00782       Region r(home);
00783       // State map for in-states
00784       StateIdx* i_map = r.alloc<StateIdx>(max_states);
00785       // State map for out-states
00786       StateIdx* o_map = r.alloc<StateIdx>(max_states);
00787       // Number of in-states
00788       StateIdx i_n = 0;
00789       // Number of out-states
00790       StateIdx o_n = 0;
00791 
00792       n_states -= layers[l].n_states;
00793       // Initialize map for in-states and compress
00794       for (StateIdx j=0; j<layers[l].n_states; j++)
00795         if ((layers[l].states[j].i_deg != 0) ||
00796             (layers[l].states[j].o_deg != 0)) {
00797           layers[l].states[i_n]=layers[l].states[j];
00798           i_map[j]=i_n++;
00799         }
00800       layers[l].n_states = i_n;
00801       n_states += layers[l].n_states;
00802       assert(i_n > 0);
00803 
00804       // Update in-states in edges for last layer, if any
00805       if (l < n)
00806         for (ValSize j=layers[l].size; j--; ) {
00807           Support& s = layers[l].support[j];
00808           for (Degree d=s.n_edges; d--; )
00809             s.edges[d].i_state = i_map[s.edges[d].i_state];
00810         }
00811 
00812       // Update all changed layers
00813       for (int i=l-1; i>=f; i--) {
00814         // In-states become out-states
00815         std::swap(o_map,i_map); o_n=i_n; i_n=0;
00816         // Initialize map for in-states and compress
00817         n_states -= layers[i].n_states;
00818         for (StateIdx j=0; j<layers[i].n_states; j++)
00819           if ((layers[i].states[j].o_deg != 0) ||
00820               (layers[i].states[j].i_deg != 0)) {
00821             layers[i].states[i_n]=layers[i].states[j];
00822             i_map[j]=i_n++;
00823           }
00824         layers[i].n_states = i_n;
00825         n_states += layers[i].n_states;
00826         assert(i_n > 0);
00827 
00828         // Update states in edges
00829         for (ValSize j=layers[i].size; j--; ) {
00830           Support& s = layers[i].support[j];
00831           for (Degree d=s.n_edges; d--; ) {
00832             s.edges[d].i_state = i_map[s.edges[d].i_state];
00833             s.edges[d].o_state = o_map[s.edges[d].o_state];
00834           }
00835         }
00836       }
00837 
00838       // Update out-states in edges for previous layer, if any
00839       if (f > 0)
00840         for (ValSize j=layers[f-1].size; j--; ) {
00841           Support& s = layers[f-1].support[j];
00842           for (Degree d=s.n_edges; d--; )
00843             s.edges[d].o_state = i_map[s.edges[d].o_state];
00844         }
00845 
00846       a_ch.reset();
00847     }
00848     audit();
00849 
00850     return new (home) LayeredGraph<View,Val,Degree,StateIdx>(home,share,*this);
00851   }
00852 
00854   template<class Var>
00855   forceinline ExecStatus
00856   post_lgp(Home home, const VarArgArray<Var>& x, const DFA& dfa) {
00857     Gecode::Support::IntType t_state_idx =
00858       Gecode::Support::u_type(static_cast<unsigned int>(dfa.n_states()));
00859     Gecode::Support::IntType t_degree =
00860       Gecode::Support::u_type(dfa.max_degree());
00861     Gecode::Support::IntType t_val = 
00862       std::max(Support::s_type(dfa.symbol_min()),
00863                Support::s_type(dfa.symbol_max()));
00864     switch (t_val) {
00865     case Gecode::Support::IT_CHAR:
00866     case Gecode::Support::IT_SHRT:
00867       switch (t_state_idx) {
00868       case Gecode::Support::IT_CHAR:
00869         switch (t_degree) {
00870         case Gecode::Support::IT_CHAR:
00871           return Extensional::LayeredGraph
00872             <typename VarTraits<Var>::View,short int,unsigned char,unsigned char>
00873             ::post(home,x,dfa);
00874         case Gecode::Support::IT_SHRT:
00875           return Extensional::LayeredGraph
00876             <typename VarTraits<Var>::View,short int,unsigned short int,unsigned char>
00877             ::post(home,x,dfa);
00878         case Gecode::Support::IT_INT:
00879           return Extensional::LayeredGraph
00880             <typename VarTraits<Var>::View,short int,unsigned int,unsigned char>
00881             ::post(home,x,dfa);
00882         default: GECODE_NEVER;
00883         }
00884         break;
00885       case Gecode::Support::IT_SHRT:
00886         switch (t_degree) {
00887         case Gecode::Support::IT_CHAR:
00888           return Extensional::LayeredGraph
00889             <typename VarTraits<Var>::View,short int,unsigned char,unsigned short int>
00890             ::post(home,x,dfa);
00891         case Gecode::Support::IT_SHRT:
00892           return Extensional::LayeredGraph
00893             <typename VarTraits<Var>::View,short int,unsigned short int,unsigned short int>
00894             ::post(home,x,dfa);
00895         case Gecode::Support::IT_INT:
00896           return Extensional::LayeredGraph
00897             <typename VarTraits<Var>::View,short int,unsigned int,unsigned short int>
00898             ::post(home,x,dfa);
00899         default: GECODE_NEVER;
00900         }
00901         break;
00902       case Gecode::Support::IT_INT:
00903         switch (t_degree) {
00904         case Gecode::Support::IT_CHAR:
00905           return Extensional::LayeredGraph
00906             <typename VarTraits<Var>::View,short int,unsigned char,unsigned int>
00907             ::post(home,x,dfa);
00908         case Gecode::Support::IT_SHRT:
00909           return Extensional::LayeredGraph
00910             <typename VarTraits<Var>::View,short int,unsigned short int,unsigned int>
00911             ::post(home,x,dfa);
00912         case Gecode::Support::IT_INT:
00913           return Extensional::LayeredGraph
00914             <typename VarTraits<Var>::View,short int,unsigned int,unsigned int>
00915             ::post(home,x,dfa);
00916         default: GECODE_NEVER;
00917         }
00918         break;
00919       default: GECODE_NEVER;
00920       }
00921 
00922     case Gecode::Support::IT_INT:
00923       switch (t_state_idx) {
00924       case Gecode::Support::IT_CHAR:
00925         switch (t_degree) {
00926         case Gecode::Support::IT_CHAR:
00927           return Extensional::LayeredGraph
00928             <typename VarTraits<Var>::View,int,unsigned char,unsigned char>
00929             ::post(home,x,dfa);
00930         case Gecode::Support::IT_SHRT:
00931           return Extensional::LayeredGraph
00932             <typename VarTraits<Var>::View,int,unsigned short int,unsigned char>
00933             ::post(home,x,dfa);
00934         case Gecode::Support::IT_INT:
00935           return Extensional::LayeredGraph
00936             <typename VarTraits<Var>::View,int,unsigned int,unsigned char>
00937             ::post(home,x,dfa);
00938         default: GECODE_NEVER;
00939         }
00940         break;
00941       case Gecode::Support::IT_SHRT:
00942         switch (t_degree) {
00943         case Gecode::Support::IT_CHAR:
00944           return Extensional::LayeredGraph
00945             <typename VarTraits<Var>::View,int,unsigned char,unsigned short int>
00946             ::post(home,x,dfa);
00947         case Gecode::Support::IT_SHRT:
00948           return Extensional::LayeredGraph
00949             <typename VarTraits<Var>::View,int,unsigned short int,unsigned short int>
00950             ::post(home,x,dfa);
00951         case Gecode::Support::IT_INT:
00952           return Extensional::LayeredGraph
00953             <typename VarTraits<Var>::View,int,unsigned int,unsigned short int>
00954             ::post(home,x,dfa);
00955         default: GECODE_NEVER;
00956         }
00957         break;
00958       case Gecode::Support::IT_INT:
00959         switch (t_degree) {
00960         case Gecode::Support::IT_CHAR:
00961           return Extensional::LayeredGraph
00962             <typename VarTraits<Var>::View,int,unsigned char,unsigned int>
00963             ::post(home,x,dfa);
00964         case Gecode::Support::IT_SHRT:
00965           return Extensional::LayeredGraph
00966             <typename VarTraits<Var>::View,int,unsigned short int,unsigned int>
00967             ::post(home,x,dfa);
00968         case Gecode::Support::IT_INT:
00969           return Extensional::LayeredGraph
00970             <typename VarTraits<Var>::View,int,unsigned int,unsigned int>
00971             ::post(home,x,dfa);
00972         default: GECODE_NEVER;
00973         }
00974         break;
00975       default: GECODE_NEVER;
00976       }
00977 
00978     default: GECODE_NEVER;
00979     }
00980     return ES_OK;
00981   }
00982 
00983 }}}
00984 
00985 // STATISTICS: int-prop
00986