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