Generated on Thu Mar 22 10:39:38 2012 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: 2011-09-01 15:04:29 +0200 (Thu, 01 Sep 2011) $ by $Author: schulte $
00011  *     $Revision: 12384 $
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 
00360       // Initialize map for in-states (special for last layer)
00361       // Degree for single final state
00362       unsigned int d = 0;
00363       for (StateIdx j=max_states; j--; )
00364         d += static_cast<unsigned int>(layers[n].states[j].i_deg);
00365       // Check whether all final states can be joined to a single state
00366       if (d > 
00367           static_cast<unsigned int>
00368           (Gecode::Support::IntTypeTraits<Degree>::max)) {
00369         // Initialize map for in-states
00370         for (StateIdx j=max_states; j--; )
00371           if ((layers[n].states[j].o_deg != 0) ||
00372               (layers[n].states[j].i_deg != 0))
00373             i_map[j]=i_n++;
00374       } else {
00375         i_n = 1;
00376         for (StateIdx j=max_states; j--; ) {
00377           layers[n].states[j].init();
00378           i_map[j] = 0;
00379         }
00380         layers[n].states[0].i_deg = static_cast<Degree>(d);
00381         layers[n].states[0].o_deg = 1;
00382       }
00383       layers[n].n_states = i_n;
00384       
00385       // Total number of states
00386       n_states = i_n;
00387       // Total number of edges
00388       n_edges = 0;
00389       // New maximal number of states
00390       StateIdx max_s = i_n;
00391 
00392       for (int i=n; i--; ) {
00393         // In-states become out-states
00394         std::swap(o_map,i_map); i_n=0;
00395         // Initialize map for in-states
00396         for (StateIdx j=max_states; j--; )
00397           if ((layers[i].states[j].o_deg != 0) ||
00398               (layers[i].states[j].i_deg != 0))
00399             i_map[j]=i_n++;
00400         layers[i].n_states = i_n;
00401         n_states += i_n;
00402         max_s = std::max(max_s,i_n);
00403 
00404         // Update states in edges
00405         for (ValSize j=layers[i].size; j--; ) {
00406           Support& s = layers[i].support[j];
00407           n_edges += s.n_edges;
00408           for (Degree d=s.n_edges; d--; ) {
00409             s.edges[d].i_state = i_map[s.edges[d].i_state];
00410             s.edges[d].o_state = o_map[s.edges[d].o_state];
00411           }
00412         }
00413       }
00414 
00415       // Allocate and copy states
00416       State* a_states = home.alloc<State>(n_states);
00417       for (int i=n+1; i--; ) {
00418         StateIdx k=0;
00419         for (StateIdx j=max_states; j--; )
00420           if ((layers[i].states[j].o_deg != 0) ||
00421               (layers[i].states[j].i_deg != 0))
00422             a_states[k++] = layers[i].states[j];
00423         assert(k == layers[i].n_states);
00424         layers[i].states = a_states;
00425         a_states += layers[i].n_states;
00426       }
00427       
00428       // Update maximal number of states
00429       max_states = max_s;
00430     }
00431 
00432     // Schedule if subsumption is needed
00433     if (c.empty())
00434       View::schedule(home,*this,ME_INT_VAL);
00435 
00436     audit();
00437     return ES_OK;
00438   }
00439 
00440   template<class View, class Val, class Degree, class StateIdx>
00441   ExecStatus
00442   LayeredGraph<View,Val,Degree,StateIdx>::advise(Space& home,
00443                                                  Advisor& _a, const Delta& d) {
00444     // Check whether state information has already been created
00445     if (layers[0].states == NULL) {
00446       State* states = home.alloc<State>(n_states);
00447       for (unsigned int i=n_states; i--; )
00448         states[i].init();
00449       layers[n].states = states;
00450       states += layers[n].n_states;
00451       for (int i=n; i--; ) {
00452         layers[i].states = states;
00453         states += layers[i].n_states;
00454         for (ValSize j=layers[i].size; j--; ) {
00455           Support& s = layers[i].support[j];
00456           for (Degree d=s.n_edges; d--; ) {
00457             i_state(i,s.edges[d]).o_deg++;
00458             o_state(i,s.edges[d]).i_deg++;
00459           }
00460         }
00461       }
00462     }
00463     
00464     Index& a = static_cast<Index&>(_a);
00465     const int i = a.i;
00466 
00467     if (layers[i].size <= layers[i].x.size()) {
00468       // Propagator has already done everything
00469       if (View::modevent(d) == ME_INT_VAL) {
00470         a.dispose(home,c);
00471         return c.empty() ? ES_NOFIX : ES_FIX;
00472       } else {
00473         return ES_FIX;
00474       }
00475     }
00476 
00477     bool i_mod = false;
00478     bool o_mod = false;
00479 
00480     if (View::modevent(d) == ME_INT_VAL) {
00481       Val n = static_cast<Val>(layers[i].x.val());
00482       ValSize j=0;
00483       for (; layers[i].support[j].val < n; j++) {
00484         Support& s = layers[i].support[j];
00485         n_edges -= s.n_edges;
00486         // Supported value not any longer in view
00487         for (Degree d=s.n_edges; d--; ) {
00488           // Adapt states
00489           o_mod |= i_dec(i,s.edges[d]);
00490           i_mod |= o_dec(i,s.edges[d]);
00491         }
00492       }
00493       assert(layers[i].support[j].val == n);
00494       layers[i].support[0] = layers[i].support[j++];
00495       ValSize s=layers[i].size;
00496       layers[i].size = 1;
00497       for (; j<s; j++) {
00498         Support& s = layers[i].support[j];
00499         n_edges -= s.n_edges;
00500         for (Degree d=s.n_edges; d--; ) {
00501           // Adapt states
00502           o_mod |= i_dec(i,s.edges[d]);
00503           i_mod |= o_dec(i,s.edges[d]);
00504         }
00505       }
00506     } else if (layers[i].x.any(d)) {
00507       ValSize j=0;
00508       ValSize k=0;
00509       ValSize s=layers[i].size;
00510       for (ViewRanges<View> rx(layers[i].x); rx() && (j<s);) {
00511         Support& s = layers[i].support[j];
00512         if (s.val < static_cast<Val>(rx.min())) {
00513           // Supported value not any longer in view
00514           n_edges -= s.n_edges;
00515           for (Degree d=s.n_edges; d--; ) {
00516             // Adapt states
00517             o_mod |= i_dec(i,s.edges[d]);
00518             i_mod |= o_dec(i,s.edges[d]);
00519           }
00520           ++j;
00521         } else if (s.val > static_cast<Val>(rx.max())) {
00522           ++rx;
00523         } else {
00524           layers[i].support[k++]=s;
00525           ++j;
00526         }
00527       }
00528       assert(k > 0);
00529       layers[i].size = k;
00530       // Remove remaining values
00531       for (; j<s; j++) {
00532         Support& s=layers[i].support[j];
00533         n_edges -= s.n_edges;
00534         for (Degree d=s.n_edges; d--; ) {
00535           // Adapt states
00536           o_mod |= i_dec(i,s.edges[d]);
00537           i_mod |= o_dec(i,s.edges[d]);
00538         }
00539       }
00540     } else {
00541       Val min = static_cast<Val>(layers[i].x.min(d));
00542       ValSize j=0;
00543       // Skip values smaller than min (to keep)
00544       for (; layers[i].support[j].val < min; j++) {}
00545       Val max = static_cast<Val>(layers[i].x.max(d));
00546       ValSize k=j;
00547       ValSize s=layers[i].size;
00548       // Remove pruned values
00549       for (; (j<s) && (layers[i].support[j].val <= max); j++) {
00550         Support& s=layers[i].support[j];
00551         n_edges -= s.n_edges;
00552         for (Degree d=s.n_edges; d--; ) {
00553           // Adapt states
00554           o_mod |= i_dec(i,s.edges[d]);
00555           i_mod |= o_dec(i,s.edges[d]);
00556         }
00557       }
00558       // Keep remaining values
00559       while (j<s)
00560         layers[i].support[k++]=layers[i].support[j++];
00561       layers[i].size =k;
00562       assert(k > 0);
00563     }
00564 
00565     audit();
00566 
00567     bool fix = true;
00568     if (o_mod && (i > 0)) {
00569       o_ch.add(i-1); fix = false;
00570      }
00571     if (i_mod && (i+1 < n)) {
00572       i_ch.add(i+1); fix = false;
00573     }
00574     if (fix) {
00575       if (View::modevent(d) == ME_INT_VAL) {
00576         a.dispose(home,c);
00577         return c.empty() ? ES_NOFIX : ES_FIX;
00578       }
00579       return ES_FIX;
00580     } else {
00581       return (View::modevent(d) == ME_INT_VAL)
00582         ? home.ES_NOFIX_DISPOSE(c,a) : ES_NOFIX;
00583     }
00584   }
00585 
00586   template<class View, class Val, class Degree, class StateIdx>
00587   forceinline size_t
00588   LayeredGraph<View,Val,Degree,StateIdx>::dispose(Space& home) {
00589     c.dispose(home);
00590     (void) Propagator::dispose(home);
00591     return sizeof(*this);
00592   }
00593 
00594   template<class View, class Val, class Degree, class StateIdx>
00595   ExecStatus
00596   LayeredGraph<View,Val,Degree,StateIdx>::propagate(Space& home,
00597                                                     const ModEventDelta&) {
00598     // Forward pass
00599     for (int i=i_ch.fst(); i<=i_ch.lst(); i++) {
00600       bool i_mod = false;
00601       bool o_mod = false;
00602       ValSize j=0;
00603       ValSize k=0;
00604       ValSize s=layers[i].size;
00605       do {
00606         Support& s=layers[i].support[j];
00607         n_edges -= s.n_edges;
00608         for (Degree d=s.n_edges; d--; )
00609           if (i_state(i,s.edges[d]).i_deg == 0) {
00610             // Adapt states
00611             o_mod |= i_dec(i,s.edges[d]);
00612             i_mod |= o_dec(i,s.edges[d]);
00613             // Remove edge
00614             s.edges[d] = s.edges[--s.n_edges];
00615           }
00616         n_edges += s.n_edges;
00617         // Check whether value is still supported
00618         if (s.n_edges == 0) {
00619           layers[i].size--;
00620           GECODE_ME_CHECK(layers[i].x.nq(home,s.val));
00621         } else {
00622           layers[i].support[k++]=s;
00623         }
00624       } while (++j<s);
00625       assert(k > 0);
00626       // Update modification information
00627       if (o_mod && (i > 0))
00628         o_ch.add(i-1);
00629       if (i_mod && (i+1 < n))
00630         i_ch.add(i+1);
00631     }
00632 
00633     // Backward pass
00634     for (int i=o_ch.lst(); i>=o_ch.fst(); i--) {
00635       bool o_mod = false;
00636       ValSize j=0;
00637       ValSize k=0;
00638       ValSize s=layers[i].size;
00639       do {
00640         Support& s=layers[i].support[j];
00641         n_edges -= s.n_edges;
00642         for (Degree d=s.n_edges; d--; )
00643           if (o_state(i,s.edges[d]).o_deg == 0) {
00644             // Adapt states
00645             o_mod |= i_dec(i,s.edges[d]);
00646             (void)   o_dec(i,s.edges[d]);
00647             // Remove edge
00648             s.edges[d] = s.edges[--s.n_edges];
00649           }
00650         n_edges += s.n_edges;
00651         // Check whether value is still supported
00652         if (s.n_edges == 0) {
00653           layers[i].size--;
00654           GECODE_ME_CHECK(layers[i].x.nq(home,s.val));
00655         } else {
00656           layers[i].support[k++]=s;
00657         }
00658       } while (++j<s);
00659       assert(k > 0);
00660       // Update modification information
00661       if (o_mod && (i > 0))
00662         o_ch.add(i-1);
00663     }
00664 
00665     a_ch.add(i_ch); i_ch.reset();
00666     a_ch.add(o_ch); o_ch.reset();
00667 
00668     audit();
00669 
00670     // Check subsumption
00671     if (c.empty())
00672       return home.ES_SUBSUMED(*this);
00673     else
00674       return ES_FIX;
00675   }
00676 
00677 
00678   template<class View, class Val, class Degree, class StateIdx>
00679   template<class Var>
00680   ExecStatus
00681   LayeredGraph<View,Val,Degree,StateIdx>::post(Home home, 
00682                                                const VarArgArray<Var>& x,
00683                                                const DFA& dfa) {
00684     if (x.size() == 0) {
00685       // Check whether the start state 0 is also a final state
00686       if ((dfa.final_fst() <= 0) && (dfa.final_lst() >= 0))
00687         return ES_OK;
00688       return ES_FAILED;
00689     }
00690     assert(x.size() > 0);
00691     for (int i=x.size(); i--; ) {
00692       DFA::Symbols s(dfa);
00693       typename VarTraits<Var>::View xi(x[i]);
00694       GECODE_ME_CHECK(xi.inter_v(home,s,false));
00695     }
00696     LayeredGraph<View,Val,Degree,StateIdx>* p =
00697       new (home) LayeredGraph<View,Val,Degree,StateIdx>(home,x,dfa);
00698     return p->initialize(home,x,dfa);
00699   }
00700 
00701   template<class View, class Val, class Degree, class StateIdx>
00702   forceinline
00703   LayeredGraph<View,Val,Degree,StateIdx>
00704   ::LayeredGraph(Space& home, bool share,
00705                  LayeredGraph<View,Val,Degree,StateIdx>& p)
00706     : Propagator(home,share,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,share,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=n; i--; ) {
00717       layers[i].x.update(home,share,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=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, bool share) {
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(home);
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,share,*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