Generated on for Gecode by doxygen 1.17.0
layered-graph.hpp
Go to the documentation of this file.
1/* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */
2/*
3 * Main authors:
4 * Christian Schulte <schulte@gecode.dev>
5 *
6 * Copyright:
7 * Christian Schulte, 2004
8 *
9 * This file is part of Gecode, the generic constraint
10 * development environment:
11 * http://www.gecode.dev
12 *
13 * Permission is hereby granted, free of charge, to any person obtaining
14 * a copy of this software and associated documentation files (the
15 * "Software"), to deal in the Software without restriction, including
16 * without limitation the rights to use, copy, modify, merge, publish,
17 * distribute, sublicense, and/or sell copies of the Software, and to
18 * permit persons to whom the Software is furnished to do so, subject to
19 * the following conditions:
20 *
21 * The above copyright notice and this permission notice shall be
22 * included in all copies or substantial portions of the Software.
23 *
24 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
25 * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
26 * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
27 * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
28 * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
29 * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
30 * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
31 *
32 */
33
34#include <climits>
35#include <algorithm>
36#include <limits>
37
38namespace Gecode { namespace Int { namespace Extensional {
39
46 template<class Var>
47 class VarTraits {};
48
54 template<>
56 public:
59 };
60
66 template<>
68 public:
71 };
72
73
74 /*
75 * States
76 */
77 template<class View, class Val, class Degree, class StateIdx>
78 forceinline void
82
83
84 template<class View, class Val, class Degree, class StateIdx>
87 return layers[i].states[is];
88 }
89 template<class View, class Val, class Degree, class StateIdx>
92 (int i, const typename LayeredGraph<View,Val,Degree,StateIdx>::Edge& e) {
93 return i_state(i,e.i_state);
94 }
95 template<class View, class Val, class Degree, class StateIdx>
96 forceinline bool
101 template<class View, class Val, class Degree, class StateIdx>
104 return layers[i+1].states[os];
105 }
106 template<class View, class Val, class Degree, class StateIdx>
109 (int i, const typename LayeredGraph<View,Val,Degree,StateIdx>::Edge& e) {
110 return o_state(i,e.o_state);
111 }
112 template<class View, class Val, class Degree, class StateIdx>
113 forceinline bool
118
119
120 /*
121 * Value iterator
122 */
123 template<class View, class Val, class Degree, class StateIdx>
126 template<class View, class Val, class Degree, class StateIdx>
129 ::LayerValues(const Layer& l)
130 : s1(l.support), s2(l.support+l.size) {}
131 template<class View, class Val, class Degree, class StateIdx>
132 forceinline void
136 template<class View, class Val, class Degree, class StateIdx>
137 forceinline bool
142 template<class View, class Val, class Degree, class StateIdx>
143 forceinline void
147 template<class View, class Val, class Degree, class StateIdx>
148 forceinline int
150 return s1->val;
151 }
152
153
154 /*
155 * Index advisors
156 *
157 */
158 template<class View, class Val, class Degree, class StateIdx>
164
165 template<class View, class Val, class Degree, class StateIdx>
169
170
171 /*
172 * Index ranges
173 *
174 */
175 template<class View, class Val, class Degree, class StateIdx>
178 : _fst(INT_MAX), _lst(INT_MIN) {}
179 template<class View, class Val, class Degree, class StateIdx>
180 forceinline void
182 _fst=INT_MAX; _lst=INT_MIN;
183 }
184 template<class View, class Val, class Degree, class StateIdx>
185 forceinline void
187 _fst=std::min(_fst,i); _lst=std::max(_lst,i);
188 }
189 template<class View, class Val, class Degree, class StateIdx>
190 forceinline void
193 _fst=std::min(_fst,ir._fst); _lst=std::max(_lst,ir._lst);
194 }
195 template<class View, class Val, class Degree, class StateIdx>
196 forceinline bool
198 return _fst>_lst;
199 }
200 template<class View, class Val, class Degree, class StateIdx>
201 forceinline void
203 if (empty())
204 return;
205 if (n > _lst) {
206 reset();
207 } else {
208 _fst = std::max(0,_fst-n);
209 _lst -= n;
210 }
211 }
212 template<class View, class Val, class Degree, class StateIdx>
213 forceinline int
217 template<class View, class Val, class Degree, class StateIdx>
218 forceinline int
222
223
224
225 /*
226 * The layered graph
227 *
228 */
229
230 template<class View, class Val, class Degree, class StateIdx>
231 template<class Var>
234 const VarArgArray<Var>& x,
235 const DFA& dfa)
236 : Propagator(home), c(home), n(x.size()),
237 max_states(static_cast<StateIdx>(dfa.n_states())) {
238 assert(n > 0);
239 }
240
241 template<class View, class Val, class Degree, class StateIdx>
242 forceinline void
244#ifdef GECODE_AUDIT
245 // Check states and edge information to be consistent
246 unsigned int n_e = 0; // Number of edges
247 unsigned int n_s = 0; // Number of states
248 StateIdx m_s = 0; // Maximal number of states per layer
249 for (int i=n; i--; ) {
250 n_s += layers[i].n_states;
251 m_s = std::max(m_s,layers[i].n_states);
252 for (ValSize j=layers[i].size; j--; )
253 n_e += layers[i].support[j].n_edges;
254 }
255 n_s += layers[n].n_states;
256 m_s = std::max(m_s,layers[n].n_states);
257 assert(n_e == n_edges);
258 assert(n_s <= n_states);
259 assert(m_s <= max_states);
260#endif
261 }
262
263 template<class View, class Val, class Degree, class StateIdx>
264 template<class Var>
267 const VarArgArray<Var>& x,
268 const DFA& dfa) {
269
270 // Allocate memory for layers
271 layers = home.alloc<Layer>(n+1);
272
273 const int n_dfa_states = dfa.n_states();
274
275 {
276 Region r;
277
278 // Allocate temporary memory for edges
279 Edge* edges = r.alloc<Edge>(dfa.max_degree());
280
281 // Reachability sets and touched states
282 unsigned char* i_reachable = r.alloc<unsigned char>(n_dfa_states);
283 unsigned char* o_reachable = r.alloc<unsigned char>(n_dfa_states);
284 StateIdx* i_reached = r.alloc<StateIdx>(n_dfa_states);
285 StateIdx* o_reached = r.alloc<StateIdx>(n_dfa_states);
286 for (int i=0; i<n_dfa_states; i++)
287 i_reachable[i] = o_reachable[i] = 0;
288 unsigned int n_i_reached = 1;
289 unsigned int n_o_reached = 0;
290 i_reachable[0] = 1;
291 i_reached[0] = 0;
292
293 // Forward pass: add transitions
294 for (int i=0; i<n; i++) {
295 layers[i].x = x[i];
296 layers[i].support = home.alloc<Support>(layers[i].x.size());
297 ValSize j=0;
298 // Clear the next frontier
299 for (unsigned int k=0; k<n_o_reached; k++)
300 o_reachable[o_reached[k]] = 0;
301 n_o_reached = 0;
302 // Enter links leaving reachable states
303 for (ViewValues<View> nx(layers[i].x); nx(); ++nx) {
304 unsigned int n_support_edges=0;
305 for (DFA::Transitions t(dfa,nx.val()); t(); ++t)
306 if (i_reachable[t.i_state()] != 0) {
307 edges[n_support_edges].i_state =
308 static_cast<StateIdx>(t.i_state());
309 edges[n_support_edges].o_state =
310 static_cast<StateIdx>(t.o_state());
311 n_support_edges++;
312 if (o_reachable[t.o_state()] == 0) {
313 o_reachable[t.o_state()] = 1;
314 o_reached[n_o_reached++] =
315 static_cast<StateIdx>(t.o_state());
316 }
317 }
318 assert(n_support_edges <= dfa.max_degree());
319 // Found support for value
320 if (n_support_edges > 0) {
321 Support& s = layers[i].support[j];
322 s.val = static_cast<Val>(nx.val());
323 s.n_edges = static_cast<Degree>(n_support_edges);
324 s.edges = Heap::copy(home.alloc<Edge>(n_support_edges),edges,
325 n_support_edges);
326 j++;
327 }
328 }
329 if ((layers[i].size = j) == 0)
330 return ES_FAILED;
331 std::swap(i_reachable,o_reachable);
332 std::swap(i_reached,o_reached);
333 std::swap(n_i_reached,n_o_reached);
334 }
335 }
336
337 Region r;
338
339 // Maps from DFA state IDs to layer-local state indices
340 StateIdx* i_map = r.alloc<StateIdx>(n_dfa_states);
341 StateIdx* o_map = r.alloc<StateIdx>(n_dfa_states);
342 unsigned char* i_mapped = r.alloc<unsigned char>(n_dfa_states);
343 unsigned char* o_mapped = r.alloc<unsigned char>(n_dfa_states);
344 StateIdx* i_touched = r.alloc<StateIdx>(n_dfa_states);
345 StateIdx* o_touched = r.alloc<StateIdx>(n_dfa_states);
346 for (int i=0; i<n_dfa_states; i++)
347 i_mapped[i] = o_mapped[i] = 0;
348 unsigned int n_i_mapped = 0;
349 unsigned int n_o_mapped = 0;
350
351 // Count and map reachable edges entering final states
352 unsigned long long int final_degree = 0;
353 for (ValSize j=0; j<layers[n-1].size; j++) {
354 Support& s = layers[n-1].support[j];
355 for (unsigned int d=0; d<static_cast<unsigned int>(s.n_edges); d++) {
356 const int os = static_cast<int>(s.edges[d].o_state);
357 if ((os >= dfa.final_fst()) && (os < dfa.final_lst())) {
358 final_degree++;
359 if (o_mapped[os] == 0) {
360 o_mapped[os] = 1;
361 o_map[os] = static_cast<StateIdx>(n_o_mapped);
362 o_touched[n_o_mapped++] = static_cast<StateIdx>(os);
363 }
364 }
365 }
366 }
367 if (final_degree == 0)
368 return ES_FAILED;
369
370 // Initialize the map for the terminal layer
371 if (final_degree <= static_cast<unsigned long long int>
373 // Merge all terminal states
374 for (unsigned int i=0; i<n_o_mapped; i++)
375 o_map[o_touched[i]] = 0;
376 layers[n].n_states = 1;
377 } else {
378 // Keep terminal states separate
379 layers[n].n_states = static_cast<StateIdx>(n_o_mapped);
380 }
381
382 unsigned long long int total_states = layers[n].n_states;
383 unsigned long long int total_edges = 0;
384 unsigned int max_s = layers[n].n_states;
385
386 // Backward pass: prune and translate endpoints to layer-local indices
387 for (int i=n; i--; ) {
388 for (unsigned int j=0; j<n_i_mapped; j++)
389 i_mapped[i_touched[j]] = 0;
390 n_i_mapped = 0;
391 ValSize n_supports=0;
392 for (ValSize j=0; j<layers[i].size; j++) {
393 Support& s = layers[i].support[j];
394 unsigned int n_support_edges=0;
395 for (unsigned int d=0; d<static_cast<unsigned int>(s.n_edges); d++) {
396 Edge e = s.edges[d];
397 const int is = static_cast<int>(e.i_state);
398 const int os = static_cast<int>(e.o_state);
399 if (o_mapped[os] != 0) {
400 e.o_state = o_map[os];
401 if (i_mapped[is] == 0) {
402 i_mapped[is] = 1;
403 i_map[is] = static_cast<StateIdx>(n_i_mapped);
404 i_touched[n_i_mapped++] = static_cast<StateIdx>(is);
405 }
406 e.i_state = i_map[is];
407 s.edges[n_support_edges++] = e;
408 }
409 }
410 s.n_edges = static_cast<Degree>(n_support_edges);
411 if (n_support_edges > 0) {
412 layers[i].support[n_supports++] = s;
413 total_edges += n_support_edges;
414 }
415 }
416 if ((layers[i].size = n_supports) == 0)
417 return ES_FAILED;
418 layers[i].n_states = static_cast<StateIdx>(n_i_mapped);
419 total_states += n_i_mapped;
420 max_s = std::max(max_s,n_i_mapped);
421 LayerValues lv(layers[i]);
422 GECODE_ME_CHECK(layers[i].x.narrow_v(home,lv,false));
423 if (!layers[i].x.assigned())
424 layers[i].x.subscribe(home, *new (home) Index(home,*this,c,i));
425
426 std::swap(i_map,o_map);
427 std::swap(i_mapped,o_mapped);
428 std::swap(i_touched,o_touched);
429 std::swap(n_i_mapped,n_o_mapped);
430 }
431
432 if ((total_states >
433 static_cast<unsigned long long int>
434 ((std::numeric_limits<unsigned int>::max)())) ||
435 (total_edges >
436 static_cast<unsigned long long int>
437 ((std::numeric_limits<unsigned int>::max)())))
438 throw OutOfLimits("Int::regular");
439 n_states = static_cast<unsigned int>(total_states);
440 n_edges = static_cast<unsigned int>(total_edges);
441 max_states = static_cast<StateIdx>(max_s);
442
443 // Allocate persistent states in terminal-first, descending-layer order
444 State* states = home.alloc<State>(n_states);
445 for (unsigned int i=0; i<n_states; i++)
446 states[i].init();
447 for (int i=n+1; i--; ) {
448 layers[i].states = states;
449 states += layers[i].n_states;
450 }
451
452 // Reconstruct state degrees from the surviving edges
453 for (int i=0; i<n; i++)
454 for (ValSize j=0; j<layers[i].size; j++) {
455 Support& s = layers[i].support[j];
456 for (Degree d=s.n_edges; d--; ) {
457 i_state(i,s.edges[d]).o_deg++;
458 o_state(i,s.edges[d]).i_deg++;
459 }
460 }
461
462 // Restore artificial boundary degrees
463 layers[0].states[0].i_deg = 1;
464 for (StateIdx i=0; i<layers[n].n_states; i++)
465 layers[n].states[i].o_deg = 1;
466
467 // Schedule if subsumption is needed
468 if (c.empty())
469 View::schedule(home,*this,ME_INT_VAL);
470
471 audit();
472 return ES_OK;
473 }
474
475 template<class View, class Val, class Degree, class StateIdx>
478 Advisor& _a, const Delta& d) {
479 // Check whether state information has already been created
480 if (layers[0].states == nullptr) {
481 State* states = home.alloc<State>(n_states);
482 for (unsigned int i=0; i<n_states; i++)
483 states[i].init();
484 layers[n].states = states;
485 states += layers[n].n_states;
486 for (int i=n; i--; ) {
487 layers[i].states = states;
488 states += layers[i].n_states;
489 for (ValSize j=layers[i].size; j--; ) {
490 Support& s = layers[i].support[j];
491 for (Degree deg=s.n_edges; deg--; ) {
492 i_state(i,s.edges[deg]).o_deg++;
493 o_state(i,s.edges[deg]).i_deg++;
494 }
495 }
496 }
497 }
498
499 Index& a = static_cast<Index&>(_a);
500 const int i = a.i;
501
502 if (layers[i].size <= layers[i].x.size()) {
503 // Propagator has already done everything
504 if (View::modevent(d) == ME_INT_VAL) {
505 a.dispose(home,c);
506 return c.empty() ? ES_NOFIX : ES_FIX;
507 } else {
508 return ES_FIX;
509 }
510 }
511
512 bool i_mod = false;
513 bool o_mod = false;
514
515 if (View::modevent(d) == ME_INT_VAL) {
516 Val n = static_cast<Val>(layers[i].x.val());
517 ValSize j=0;
518 for (; layers[i].support[j].val < n; j++) {
519 Support& s = layers[i].support[j];
520 n_edges -= s.n_edges;
521 // Supported value not any longer in view
522 for (Degree deg=s.n_edges; deg--; ) {
523 // Adapt states
524 o_mod |= i_dec(i,s.edges[deg]);
525 i_mod |= o_dec(i,s.edges[deg]);
526 }
527 }
528 assert(layers[i].support[j].val == n);
529 layers[i].support[0] = layers[i].support[j++];
530 ValSize s=layers[i].size;
531 layers[i].size = 1;
532 for (; j<s; j++) {
533 Support& ls = layers[i].support[j];
534 n_edges -= ls.n_edges;
535 for (Degree deg=ls.n_edges; deg--; ) {
536 // Adapt states
537 o_mod |= i_dec(i,ls.edges[deg]);
538 i_mod |= o_dec(i,ls.edges[deg]);
539 }
540 }
541 } else if (layers[i].x.any(d)) {
542 ValSize j=0;
543 ValSize k=0;
544 ValSize s=layers[i].size;
545 for (ViewRanges<View> rx(layers[i].x); rx() && (j<s);) {
546 Support& ls = layers[i].support[j];
547 if (ls.val < static_cast<Val>(rx.min())) {
548 // Supported value not any longer in view
549 n_edges -= ls.n_edges;
550 for (Degree deg=ls.n_edges; deg--; ) {
551 // Adapt states
552 o_mod |= i_dec(i,ls.edges[deg]);
553 i_mod |= o_dec(i,ls.edges[deg]);
554 }
555 ++j;
556 } else if (ls.val > static_cast<Val>(rx.max())) {
557 ++rx;
558 } else {
559 layers[i].support[k++]=ls;
560 ++j;
561 }
562 }
563 assert(k > 0);
564 layers[i].size = k;
565 // Remove remaining values
566 for (; j<s; j++) {
567 Support& ls=layers[i].support[j];
568 n_edges -= ls.n_edges;
569 for (Degree deg=ls.n_edges; deg--; ) {
570 // Adapt states
571 o_mod |= i_dec(i,ls.edges[deg]);
572 i_mod |= o_dec(i,ls.edges[deg]);
573 }
574 }
575 } else {
576 Val min = static_cast<Val>(layers[i].x.min(d));
577 ValSize j=0;
578 // Skip values smaller than min (to keep)
579 for (; layers[i].support[j].val < min; j++) {}
580 Val max = static_cast<Val>(layers[i].x.max(d));
581 ValSize k=j;
582 ValSize s=layers[i].size;
583 // Remove pruned values
584 for (; (j<s) && (layers[i].support[j].val <= max); j++) {
585 Support& ls=layers[i].support[j];
586 n_edges -= ls.n_edges;
587 for (Degree deg=ls.n_edges; deg--; ) {
588 // Adapt states
589 o_mod |= i_dec(i,ls.edges[deg]);
590 i_mod |= o_dec(i,ls.edges[deg]);
591 }
592 }
593 // Keep remaining values
594 while (j<s)
595 layers[i].support[k++]=layers[i].support[j++];
596 layers[i].size=k;
597 assert(k > 0);
598 }
599
600 audit();
601
602 bool fix = true;
603 if (o_mod && (i > 0)) {
604 o_ch.add(i-1); fix = false;
605 }
606 if (i_mod && (i+1 < n)) {
607 i_ch.add(i+1); fix = false;
608 }
609 if (fix) {
610 if (View::modevent(d) == ME_INT_VAL) {
611 a.dispose(home,c);
612 return c.empty() ? ES_NOFIX : ES_FIX;
613 }
614 return ES_FIX;
615 } else {
616 return (View::modevent(d) == ME_INT_VAL)
617 ? home.ES_NOFIX_DISPOSE(c,a) : ES_NOFIX;
618 }
619 }
620
621 template<class View, class Val, class Degree, class StateIdx>
622 forceinline size_t
624 c.dispose(home);
625 (void) Propagator::dispose(home);
626 return sizeof(*this);
627 }
628
629 template<class View, class Val, class Degree, class StateIdx>
630 void
632 View::schedule(home,*this,c.empty() ? ME_INT_VAL : ME_INT_DOM);
633 }
634
635 template<class View, class Val, class Degree, class StateIdx>
638 const ModEventDelta&) {
639 // Forward pass
640 for (int i=i_ch.fst(); i<=i_ch.lst(); i++) {
641 bool i_mod = false;
642 bool o_mod = false;
643 ValSize j=0;
644 ValSize k=0;
645 ValSize ls=layers[i].size;
646 do {
647 Support& s=layers[i].support[j];
648 n_edges -= s.n_edges;
649 for (Degree d=s.n_edges; d--; )
650 if (i_state(i,s.edges[d]).i_deg == 0) {
651 // Adapt states
652 o_mod |= i_dec(i,s.edges[d]);
653 i_mod |= o_dec(i,s.edges[d]);
654 // Remove edge
655 s.edges[d] = s.edges[--s.n_edges];
656 }
657 n_edges += s.n_edges;
658 // Check whether value is still supported
659 if (s.n_edges == 0) {
660 layers[i].size--;
661 GECODE_ME_CHECK(layers[i].x.nq(home,s.val));
662 } else {
663 layers[i].support[k++]=s;
664 }
665 } while (++j<ls);
666 assert(k > 0);
667 // Update modification information
668 if (o_mod && (i > 0))
669 o_ch.add(i-1);
670 if (i_mod && (i+1 < n))
671 i_ch.add(i+1);
672 }
673
674 // Backward pass
675 for (int i=o_ch.lst(); i>=o_ch.fst(); i--) {
676 bool o_mod = false;
677 ValSize j=0;
678 ValSize k=0;
679 ValSize ls=layers[i].size;
680 do {
681 Support& s=layers[i].support[j];
682 n_edges -= s.n_edges;
683 for (Degree d=s.n_edges; d--; )
684 if (o_state(i,s.edges[d]).o_deg == 0) {
685 // Adapt states
686 o_mod |= i_dec(i,s.edges[d]);
687 (void) o_dec(i,s.edges[d]);
688 // Remove edge
689 s.edges[d] = s.edges[--s.n_edges];
690 }
691 n_edges += s.n_edges;
692 // Check whether value is still supported
693 if (s.n_edges == 0) {
694 layers[i].size--;
695 GECODE_ME_CHECK(layers[i].x.nq(home,s.val));
696 } else {
697 layers[i].support[k++]=s;
698 }
699 } while (++j<ls);
700 assert(k > 0);
701 // Update modification information
702 if (o_mod && (i > 0))
703 o_ch.add(i-1);
704 }
705
706 a_ch.add(i_ch); i_ch.reset();
707 a_ch.add(o_ch); o_ch.reset();
708
709 audit();
710
711 // Check subsumption
712 if (c.empty())
713 return home.ES_SUBSUMED(*this);
714 else
715 return ES_FIX;
716 }
717
718
719 template<class View, class Val, class Degree, class StateIdx>
720 template<class Var>
723 const VarArgArray<Var>& x,
724 const DFA& dfa) {
725 if (x.size() == 0) {
726 // Check whether the start state 0 is also a final state
727 if ((dfa.final_fst() <= 0) && (dfa.final_lst() >= 0))
728 return ES_OK;
729 return ES_FAILED;
730 }
731 assert(x.size() > 0);
732 for (int i=0; i<x.size(); i++) {
733 DFA::Symbols s(dfa);
734 typename VarTraits<Var>::View xi(x[i]);
735 GECODE_ME_CHECK(xi.inter_v(home,s,false));
736 }
738 new (home) LayeredGraph<View,Val,Degree,StateIdx>(home,x,dfa);
739 return p->initialize(home,x,dfa);
740 }
741
742 template<class View, class Val, class Degree, class StateIdx>
746 : Propagator(home,p),
747 n(p.n), layers(home.alloc<Layer>(n+1)),
749 c.update(home,p.c);
750 // Do not allocate states, postpone to advise!
751 layers[n].n_states = p.layers[n].n_states;
752 layers[n].states = nullptr;
753 // Allocate memory for edges
754 Edge* edges = home.alloc<Edge>(n_edges);
755 // Copy layers
756 for (int i=0; i<n; i++) {
757 layers[i].x.update(home,p.layers[i].x);
758 assert(layers[i].x.size() == p.layers[i].size);
759 layers[i].size = p.layers[i].size;
760 layers[i].support = home.alloc<Support>(layers[i].size);
761 for (ValSize j=0; j<layers[i].size; j++) {
762 layers[i].support[j].val = p.layers[i].support[j].val;
763 layers[i].support[j].n_edges = p.layers[i].support[j].n_edges;
764 assert(layers[i].support[j].n_edges > 0);
765 layers[i].support[j].edges =
766 Heap::copy(edges,p.layers[i].support[j].edges,
767 layers[i].support[j].n_edges);
768 edges += layers[i].support[j].n_edges;
769 }
770 layers[i].n_states = p.layers[i].n_states;
771 layers[i].states = nullptr;
772 }
773 audit();
774 }
775
776 template<class View, class Val, class Degree, class StateIdx>
782
783 template<class View, class Val, class Degree, class StateIdx>
784 Actor*
786 // Eliminate an assigned prefix with a single path. Keep branching
787 // NFA layers so their reachable states and edge counts remain intact.
788 {
789 int k=0;
790 while ((layers[k].size == 1) &&
791 (layers[k].support[0].n_edges == 1)) {
792 n_states -= layers[k].n_states;
793 k++;
794 }
795 if (k > 0) {
796 /*
797 * The state information is always available: either the propagator
798 * has been created (hence, also the state information has been
799 * created), or the first variable become assigned and hence
800 * an advisor must have been run (which then has created the state
801 * information).
802 */
803 // Eliminate assigned layers
804 n -= k; layers += k;
805 // Eliminate edges
806 n_edges -= static_cast<unsigned int>(k);
807 // Update advisor indices
808 for (Advisors<Index> as(c); as(); ++as)
809 as.advisor().i -= k;
810 // Update all change information
811 a_ch.lshift(k);
812 }
813 }
814 audit();
815
816 // Compress states
817 if (!a_ch.empty()) {
818 int f = a_ch.fst();
819 int l = a_ch.lst();
820 assert((f >= 0) && (l <= n));
821 Region r;
822 // State map for in-states
823 StateIdx* i_map = r.alloc<StateIdx>(max_states);
824 // State map for out-states
825 StateIdx* o_map = r.alloc<StateIdx>(max_states);
826 // Number of in-states
827 StateIdx i_n = 0;
828
829 n_states -= layers[l].n_states;
830 // Initialize map for in-states and compress
831 for (StateIdx j=0; j<layers[l].n_states; j++)
832 if ((layers[l].states[j].i_deg != 0) ||
833 (layers[l].states[j].o_deg != 0)) {
834 layers[l].states[i_n]=layers[l].states[j];
835 i_map[j]=i_n++;
836 }
837 layers[l].n_states = i_n;
838 n_states += layers[l].n_states;
839 assert(i_n > 0);
840
841 // Update in-states in edges for last layer, if any
842 if (l < n)
843 for (ValSize j=layers[l].size; j--; ) {
844 Support& s = layers[l].support[j];
845 for (Degree d=s.n_edges; d--; )
846 s.edges[d].i_state = i_map[s.edges[d].i_state];
847 }
848
849 // Update all changed layers
850 for (int i=l-1; i>=f; i--) {
851 // In-states become out-states
852 std::swap(o_map,i_map); i_n=0;
853 // Initialize map for in-states and compress
854 n_states -= layers[i].n_states;
855 for (StateIdx j=0; j<layers[i].n_states; j++)
856 if ((layers[i].states[j].o_deg != 0) ||
857 (layers[i].states[j].i_deg != 0)) {
858 layers[i].states[i_n]=layers[i].states[j];
859 i_map[j]=i_n++;
860 }
861 layers[i].n_states = i_n;
862 n_states += layers[i].n_states;
863 assert(i_n > 0);
864
865 // Update states in edges
866 for (ValSize j=layers[i].size; j--; ) {
867 Support& s = layers[i].support[j];
868 for (Degree d=s.n_edges; d--; ) {
869 s.edges[d].i_state = i_map[s.edges[d].i_state];
870 s.edges[d].o_state = o_map[s.edges[d].o_state];
871 }
872 }
873 }
874
875 // Update out-states in edges for previous layer, if any
876 if (f > 0)
877 for (ValSize j=layers[f-1].size; j--; ) {
878 Support& s = layers[f-1].support[j];
879 for (Degree d=s.n_edges; d--; )
880 s.edges[d].o_state = i_map[s.edges[d].o_state];
881 }
882
883 a_ch.reset();
884 }
885 audit();
886
887 return new (home) LayeredGraph<View,Val,Degree,StateIdx>(home,*this);
888 }
889
891 template<class Var>
893 post_lgp(Home home, const VarArgArray<Var>& x, const DFA& dfa) {
894 Gecode::Support::IntType t_state_idx =
895 Gecode::Support::u_type(static_cast<unsigned int>(dfa.n_states()));
896 Gecode::Support::IntType t_degree =
899 std::max(Support::s_type(dfa.symbol_min()),
901 switch (t_val) {
903 // fall through
905 switch (t_state_idx) {
907 switch (t_degree) {
910 <typename VarTraits<Var>::View,short int,unsigned char,unsigned char>
911 ::post(home,x,dfa);
914 <typename VarTraits<Var>::View,short int,unsigned short int,unsigned char>
915 ::post(home,x,dfa);
918 <typename VarTraits<Var>::View,short int,unsigned int,unsigned char>
919 ::post(home,x,dfa);
920 default: GECODE_NEVER;
921 }
922 break;
924 switch (t_degree) {
927 <typename VarTraits<Var>::View,short int,unsigned char,unsigned short int>
928 ::post(home,x,dfa);
931 <typename VarTraits<Var>::View,short int,unsigned short int,unsigned short int>
932 ::post(home,x,dfa);
935 <typename VarTraits<Var>::View,short int,unsigned int,unsigned short int>
936 ::post(home,x,dfa);
937 default: GECODE_NEVER;
938 }
939 break;
941 switch (t_degree) {
944 <typename VarTraits<Var>::View,short int,unsigned char,unsigned int>
945 ::post(home,x,dfa);
948 <typename VarTraits<Var>::View,short int,unsigned short int,unsigned int>
949 ::post(home,x,dfa);
952 <typename VarTraits<Var>::View,short int,unsigned int,unsigned int>
953 ::post(home,x,dfa);
954 default: GECODE_NEVER;
955 }
956 break;
957 default: GECODE_NEVER;
958 }
959 break;
961 switch (t_state_idx) {
963 switch (t_degree) {
966 <typename VarTraits<Var>::View,int,unsigned char,unsigned char>
967 ::post(home,x,dfa);
970 <typename VarTraits<Var>::View,int,unsigned short int,unsigned char>
971 ::post(home,x,dfa);
974 <typename VarTraits<Var>::View,int,unsigned int,unsigned char>
975 ::post(home,x,dfa);
976 default: GECODE_NEVER;
977 }
978 break;
980 switch (t_degree) {
983 <typename VarTraits<Var>::View,int,unsigned char,unsigned short int>
984 ::post(home,x,dfa);
987 <typename VarTraits<Var>::View,int,unsigned short int,unsigned short int>
988 ::post(home,x,dfa);
991 <typename VarTraits<Var>::View,int,unsigned int,unsigned short int>
992 ::post(home,x,dfa);
993 default: GECODE_NEVER;
994 }
995 break;
997 switch (t_degree) {
1000 <typename VarTraits<Var>::View,int,unsigned char,unsigned int>
1001 ::post(home,x,dfa);
1004 <typename VarTraits<Var>::View,int,unsigned short int,unsigned int>
1005 ::post(home,x,dfa);
1008 <typename VarTraits<Var>::View,int,unsigned int,unsigned int>
1009 ::post(home,x,dfa);
1010 default: GECODE_NEVER;
1011 }
1012 break;
1013 default: GECODE_NEVER;
1014 }
1015
1016 default: GECODE_NEVER;
1017 }
1018 return ES_OK;
1019 }
1020
1021}}}
1022
1023// STATISTICS: int-prop
Base-class for both propagators and branchers.
Definition core.hpp:635
virtual size_t dispose(Space &home)
Delete actor and return its size.
Definition core.hpp:3430
Advisor(Space &home, Propagator &p, Council< A > &c)
Constructor for creation.
Definition core.hpp:4060
friend class Council
Definition core.hpp:1310
Class to iterate over advisors of a council.
Definition core.hpp:1282
int size(void) const
Return size of array (number of elements).
Definition array.hpp:1606
Boolean integer variables.
Definition int.hh:534
Iterator for DFA symbols.
Definition int.hh:2663
Iterator for DFA transitions (sorted by symbols).
Definition int.hh:2640
Finite automaton with deterministic construction by default.
Definition int.hh:2620
int symbol_max(void) const
Return largest symbol in DFA.
Definition dfa.hpp:182
unsigned int max_degree(void) const
Return maximal degree (in-degree and out-degree) of any state.
Definition dfa.hpp:157
int n_states(void) const
Return the number of states.
Definition dfa.hpp:139
int symbol_min(void) const
Return smallest symbol in DFA.
Definition dfa.hpp:175
int final_lst(void) const
Return the number of the last final state.
Definition dfa.hpp:169
int final_fst(void) const
Return the number of the first final state.
Definition dfa.hpp:163
Generic domain change information to be supplied to advisors.
Definition core.hpp:209
static T * copy(T *d, const T *s, long unsigned int n)
Copy n objects starting at s to d.
Definition heap.hpp:593
Home class for posting propagators
Definition core.hpp:863
Integer variables.
Definition int.hh:390
Boolean view for Boolean variables.
Definition view.hpp:1378
Edge defined by in-state and out-state
Range approximation of which positions have changed.
int fst(void) const
Return first position.
void lshift(int n)
Shift index range by n elements to the left.
int lst(void) const
Return last position.
bool empty(void) const
Test whether range is empty.
Advisors for views (by position in array)
Index(Space &home, Propagator &p, Council< Index > &c, int i)
Create index advisor.
int i
The position of the view in the view array.
Iterator for telling variable domains by scanning support.
void init(const Layer &l)
Initialize for support of layer l.
void operator++(void)
Move to next supported value.
int val(void) const
Return supported value.
Layer for a view in the layered graph
ValSize size
Number of supported values.
StateIdx n_states
Number of states used by outgoing edges.
States are described by number of incoming and outgoing edges.
Degree o_deg
The out-degree (number of outgoing edges) Initialize with zeroes.
Degree i_deg
The in-degree (number of incoming edges).
Edge * edges
Supporting edges in layered graph.
Degree n_edges
Number of supporting edges.
Domain consistent layered graph (regular) propagator.
ExecStatus initialize(Space &home, const VarArgArray< Var > &x, const DFA &dfa)
Initialize layered graph.
virtual ExecStatus advise(Space &home, Advisor &a, const Delta &d)
Give advice to propagator.
unsigned int n_edges
Total number of edges.
virtual ExecStatus propagate(Space &home, const ModEventDelta &med)
Perform propagation.
Gecode::Support::IntTypeTraits< Val >::utype ValSize
Type for support size.
virtual Actor * copy(Space &home)
Copy propagator during cloning.
virtual PropCost cost(const Space &home, const ModEventDelta &med) const
Cost function (defined as high linear).
StateIdx max_states
Maximal number of states per layer.
unsigned int n_states
Total number of states.
bool i_dec(int i, const Edge &e)
Decrement out degree for in state of edge e for layer i.
int n
Number of layers (and views).
IndexRange o_ch
Index range with out-degree modifications.
IndexRange a_ch
Index range for any change (for compression).
virtual size_t dispose(Space &home)
Delete propagator and return its size.
LayeredGraph(Space &home, LayeredGraph< View, Val, Degree, StateIdx > &p)
Constructor for cloning p.
void audit(void)
Perform consistency check on data structures.
IndexRange i_ch
Index range with in-degree modifications.
Council< Index > c
The advisor council.
static ExecStatus post(Home home, const VarArgArray< Var > &x, const DFA &dfa)
Post propagator on views x and DFA dfa.
State & o_state(int i, StateIdx os)
Return out state for layer i and state index os.
bool o_dec(int i, const Edge &e)
Decrement in degree for out state of edge e for layer i.
State & i_state(int i, StateIdx is)
Return in state for layer i and state index is.
virtual void reschedule(Space &home)
Schedule function.
Layer * layers
The layers of the graph.
Int::BoolView View
The variable type of an IntView.
Int::IntView View
The variable type of an IntView.
Traits class for variables.
Integer view for integer variables.
Definition view.hpp:129
Exception: Value out of limits
Definition exception.hpp:44
Range iterator for integer views.
Definition view.hpp:54
Value iterator for integer views.
Definition view.hpp:94
Propagation cost.
Definition core.hpp:493
static PropCost linear(PropCost::Mod m, unsigned int n)
Linear complexity for modifier pcm and size measure n.
Definition core.hpp:5080
@ HI
Expensive.
Definition core.hpp:521
size_t size
The size of the propagator (used during subsumption).
Definition core.hpp:1086
friend class Space
Definition core.hpp:1075
friend class Advisor
Definition core.hpp:1077
Propagator(Home home)
Constructor for posting.
Definition core.hpp:3707
Handle to region.
Definition region.hpp:55
T * alloc(long unsigned int n)
Allocate block of n objects of type T from space heap.
Definition core.hpp:2973
Traits to for information about integer types.
Definition int-type.hpp:72
Argument array for variables.
Definition array.hpp:790
bool assigned(void) const
Test if all variables are assigned.
Definition array.hpp:1922
ExecStatus ES_NOFIX_DISPOSE(Council< A > &c, A &a)
Advisor a must be disposed and its propagator must be run
Definition core.hpp:4121
ExecStatus ES_SUBSUMED(Propagator &p)
Propagator p is subsumed
Definition core.hpp:3780
int ModEventDelta
Modification event deltas.
Definition core.hpp:94
#define GECODE_ME_CHECK(me)
Check whether modification event me is failed, and forward failure.
Definition macros.hpp:52
Extensional propagators
Definition int.hh:2774
ExecStatus post_lgp(Home home, const VarArgArray< Var > &x, const DFA &dfa)
Select small types for the layered graph propagator.
Finite domain integers.
Definition lastval.hh:52
const Gecode::ModEvent ME_INT_VAL
Domain operation has resulted in a value (assigned variable).
Definition var-type.hpp:64
const Gecode::ModEvent ME_INT_DOM
Domain operation has changed the domain.
Definition var-type.hpp:80
IntType u_type(unsigned int n)
Return type required to represent n.
Definition int-type.hpp:167
IntType s_type(signed int n)
Return type required to represent n.
IntType
Description of integer types.
Definition int-type.hpp:59
@ IT_CHAR
char integer type
Definition int-type.hpp:60
@ IT_INT
integer type
Definition int-type.hpp:62
@ IT_SHRT
short integer type
Definition int-type.hpp:61
Gecode toplevel namespace
void min(Home home, FloatVar x0, FloatVar x1, FloatVar x2)
Post propagator for .
TFE post(PropagatorGroup g)
Only post functions (but not propagators) from g are considered.
Definition filter.cpp:138
ExecStatus
Definition core.hpp:479
@ ES_OK
Execution is okay.
Definition core.hpp:483
@ ES_FIX
Propagation has computed fixpoint.
Definition core.hpp:484
@ ES_FAILED
Execution has resulted in failure.
Definition core.hpp:481
@ ES_NOFIX
Propagation has not computed fixpoint.
Definition core.hpp:482
void max(Home home, FloatVar x0, FloatVar x1, FloatVar x2)
Post propagator for .
#define forceinline
Definition config.hpp:144
#define GECODE_NEVER
Assert that this command is never executed.
Definition macros.hpp:56