Generated on Mon May 10 06:46:37 2010 for Gecode by doxygen 1.6.3

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