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