Generated on Thu Apr 5 2018 19:44:19 for Gecode by doxygen 1.8.13
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.org>
5  *
6  * Copyright:
7  * Christian Schulte, 2004
8  *
9  * Last modified:
10  * $Date$ by $Author$
11  * $Revision$
12  *
13  * This file is part of Gecode, the generic constraint
14  * development environment:
15  * http://www.gecode.org
16  *
17  * Permission is hereby granted, free of charge, to any person obtaining
18  * a copy of this software and associated documentation files (the
19  * "Software"), to deal in the Software without restriction, including
20  * without limitation the rights to use, copy, modify, merge, publish,
21  * distribute, sublicense, and/or sell copies of the Software, and to
22  * permit persons to whom the Software is furnished to do so, subject to
23  * the following conditions:
24  *
25  * The above copyright notice and this permission notice shall be
26  * included in all copies or substantial portions of the Software.
27  *
28  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
29  * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
30  * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
31  * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
32  * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
33  * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
34  * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
35  *
36  */
37 
38 #include <climits>
39 #include <algorithm>
40 
41 namespace Gecode { namespace Int { namespace Extensional {
42 
49  template<class Var>
50  class VarTraits {};
51 
57  template<>
58  class VarTraits<IntVar> {
59  public:
61  typedef Int::IntView View;
62  };
63 
69  template<>
70  class VarTraits<BoolVar> {
71  public:
74  };
75 
76 
77  /*
78  * States
79  */
80  template<class View, class Val, class Degree, class StateIdx>
81  forceinline void
83  i_deg=o_deg=0;
84  }
85 
86 
87  template<class View, class Val, class Degree, class StateIdx>
90  return layers[i].states[is];
91  }
92  template<class View, class Val, class Degree, class StateIdx>
95  (int i, const typename LayeredGraph<View,Val,Degree,StateIdx>::Edge& e) {
96  return i_state(i,e.i_state);
97  }
98  template<class View, class Val, class Degree, class StateIdx>
99  forceinline bool
101  (int i, const typename LayeredGraph<View,Val,Degree,StateIdx>::Edge& e) {
102  return --i_state(i,e).o_deg == 0;
103  }
104  template<class View, class Val, class Degree, class StateIdx>
107  return layers[i+1].states[os];
108  }
109  template<class View, class Val, class Degree, class StateIdx>
112  (int i, const typename LayeredGraph<View,Val,Degree,StateIdx>::Edge& e) {
113  return o_state(i,e.o_state);
114  }
115  template<class View, class Val, class Degree, class StateIdx>
116  forceinline bool
118  (int i, const typename LayeredGraph<View,Val,Degree,StateIdx>::Edge& e) {
119  return --o_state(i,e).i_deg == 0;
120  }
121 
122 
123  /*
124  * Value iterator
125  */
126  template<class View, class Val, class Degree, class StateIdx>
129  template<class View, class Val, class Degree, class StateIdx>
133  : s1(l.support), s2(l.support+l.size) {}
134  template<class View, class Val, class Degree, class StateIdx>
135  forceinline void
137  s1=l.support; s2=l.support+l.size;
138  }
139  template<class View, class Val, class Degree, class StateIdx>
140  forceinline bool
142  ::operator ()(void) const {
143  return s1<s2;
144  }
145  template<class View, class Val, class Degree, class StateIdx>
146  forceinline void
148  s1++;
149  }
150  template<class View, class Val, class Degree, class StateIdx>
151  forceinline int
153  return s1->val;
154  }
155 
156 
157  /*
158  * Index advisors
159  *
160  */
161  template<class View, class Val, class Degree, class StateIdx>
164  Council<Index>& c,
165  int i0)
166  : Advisor(home,p,c), i(i0) {}
167 
168  template<class View, class Val, class Degree, class StateIdx>
171  : Advisor(home,a), i(a.i) {}
172 
173 
174  /*
175  * Index ranges
176  *
177  */
178  template<class View, class Val, class Degree, class StateIdx>
181  : _fst(INT_MAX), _lst(INT_MIN) {}
182  template<class View, class Val, class Degree, class StateIdx>
183  forceinline void
185  _fst=INT_MAX; _lst=INT_MIN;
186  }
187  template<class View, class Val, class Degree, class StateIdx>
188  forceinline void
190  _fst=std::min(_fst,i); _lst=std::max(_lst,i);
191  }
192  template<class View, class Val, class Degree, class StateIdx>
193  forceinline void
196  _fst=std::min(_fst,ir._fst); _lst=std::max(_lst,ir._lst);
197  }
198  template<class View, class Val, class Degree, class StateIdx>
199  forceinline bool
201  return _fst>_lst;
202  }
203  template<class View, class Val, class Degree, class StateIdx>
204  forceinline void
206  if (empty())
207  return;
208  if (n > _lst) {
209  reset();
210  } else {
211  _fst = std::max(0,_fst-n);
212  _lst -= n;
213  }
214  }
215  template<class View, class Val, class Degree, class StateIdx>
216  forceinline int
218  return _fst;
219  }
220  template<class View, class Val, class Degree, class StateIdx>
221  forceinline int
223  return _lst;
224  }
225 
226 
227 
228  /*
229  * The layered graph
230  *
231  */
232 
233  template<class View, class Val, class Degree, class StateIdx>
234  template<class Var>
237  const VarArgArray<Var>& x,
238  const DFA& dfa)
239  : Propagator(home), c(home), n(x.size()),
240  max_states(static_cast<StateIdx>(dfa.n_states())) {
241  assert(n > 0);
242  }
243 
244  template<class View, class Val, class Degree, class StateIdx>
245  forceinline void
247 #ifdef GECODE_AUDIT
248  // Check states and edge information to be consistent
249  unsigned int n_e = 0; // Number of edges
250  unsigned int n_s = 0; // Number of states
251  StateIdx m_s = 0; // Maximal number of states per layer
252  for (int i=n; i--; ) {
253  n_s += layers[i].n_states;
254  m_s = std::max(m_s,layers[i].n_states);
255  for (ValSize j=layers[i].size; j--; )
256  n_e += layers[i].support[j].n_edges;
257  }
258  n_s += layers[n].n_states;
259  m_s = std::max(m_s,layers[n].n_states);
260  assert(n_e == n_edges);
261  assert(n_s <= n_states);
262  assert(m_s <= max_states);
263 #endif
264  }
265 
266  template<class View, class Val, class Degree, class StateIdx>
267  template<class Var>
270  const VarArgArray<Var>& x,
271  const DFA& dfa) {
272 
273  Region r;
274 
275  // Allocate memory for layers
276  layers = home.alloc<Layer>(n+1);
277 
278  // Allocate temporary memory for all possible states
279  State* states = r.alloc<State>(max_states*(n+1));
280  for (int i=static_cast<int>(max_states)*(n+1); i--; )
281  states[i].init();
282  for (int i=n+1; i--; )
283  layers[i].states = states + i*max_states;
284 
285  // Allocate temporary memory for edges
286  Edge* edges = r.alloc<Edge>(dfa.max_degree());
287 
288  // Mark initial state as being reachable
289  i_state(0,0).i_deg = 1;
290 
291  // Forward pass: add transitions
292  for (int i=0; i<n; i++) {
293  layers[i].x = x[i];
294  layers[i].support = home.alloc<Support>(layers[i].x.size());
295  ValSize j=0;
296  // Enter links leaving reachable states (indegree != 0)
297  for (ViewValues<View> nx(layers[i].x); nx(); ++nx) {
298  Degree n_edges=0;
299  for (DFA::Transitions t(dfa,nx.val()); t(); ++t)
300  if (i_state(i,static_cast<StateIdx>(t.i_state())).i_deg != 0) {
301  i_state(i,static_cast<StateIdx>(t.i_state())).o_deg++;
302  o_state(i,static_cast<StateIdx>(t.o_state())).i_deg++;
303  edges[n_edges].i_state = static_cast<StateIdx>(t.i_state());
304  edges[n_edges].o_state = static_cast<StateIdx>(t.o_state());
305  n_edges++;
306  }
307  assert(n_edges <= dfa.max_degree());
308  // Found support for value
309  if (n_edges > 0) {
310  Support& s = layers[i].support[j];
311  s.val = static_cast<Val>(nx.val());
312  s.n_edges = n_edges;
313  s.edges = Heap::copy(home.alloc<Edge>(n_edges),edges,n_edges);
314  j++;
315  }
316  }
317  if ((layers[i].size = j) == 0)
318  return ES_FAILED;
319  }
320 
321  // Mark final states as reachable
322  for (int s=dfa.final_fst(); s<dfa.final_lst(); s++)
323  if (o_state(n-1,static_cast<StateIdx>(s)).i_deg != 0)
324  o_state(n-1,static_cast<StateIdx>(s)).o_deg = 1;
325 
326  // Backward pass: prune all transitions that do not lead to final state
327  for (int i=n; i--; ) {
328  ValSize k=0;
329  for (ValSize j=0; j<layers[i].size; j++) {
330  Support& s = layers[i].support[j];
331  for (Degree d=s.n_edges; d--; )
332  if (o_state(i,s.edges[d]).o_deg == 0) {
333  // Adapt states
334  i_dec(i,s.edges[d]); o_dec(i,s.edges[d]);
335  // Prune edge
336  s.edges[d] = s.edges[--s.n_edges];
337  }
338  // Value has support, copy the support information
339  if (s.n_edges > 0)
340  layers[i].support[k++]=s;
341  }
342  if ((layers[i].size = k) == 0)
343  return ES_FAILED;
344  LayerValues lv(layers[i]);
345  GECODE_ME_CHECK(layers[i].x.narrow_v(home,lv,false));
346  if (!layers[i].x.assigned())
347  layers[i].x.subscribe(home, *new (home) Index(home,*this,c,i));
348  }
349 
350  // Copy and compress states, setup other information
351  {
352  // State map for in-states
353  StateIdx* i_map = r.alloc<StateIdx>(max_states);
354  // State map for out-states
355  StateIdx* o_map = r.alloc<StateIdx>(max_states);
356  // Number of in-states
357  StateIdx i_n = 0;
358 
359  // Initialize map for in-states (special for last layer)
360  // Degree for single final state
361  unsigned int d = 0;
362  for (StateIdx j=max_states; j--; )
363  d += static_cast<unsigned int>(layers[n].states[j].i_deg);
364  // Check whether all final states can be joined to a single state
365  if (d >
366  static_cast<unsigned int>
368  // Initialize map for in-states
369  for (StateIdx j=max_states; j--; )
370  if ((layers[n].states[j].o_deg != 0) ||
371  (layers[n].states[j].i_deg != 0))
372  i_map[j]=i_n++;
373  } else {
374  i_n = 1;
375  for (StateIdx j=max_states; j--; ) {
376  layers[n].states[j].init();
377  i_map[j] = 0;
378  }
379  layers[n].states[0].i_deg = static_cast<Degree>(d);
380  layers[n].states[0].o_deg = 1;
381  }
382  layers[n].n_states = i_n;
383 
384  // Total number of states
385  n_states = i_n;
386  // Total number of edges
387  n_edges = 0;
388  // New maximal number of states
389  StateIdx max_s = i_n;
390 
391  for (int i=n; i--; ) {
392  // In-states become out-states
393  std::swap(o_map,i_map); i_n=0;
394  // Initialize map for in-states
395  for (StateIdx j=max_states; j--; )
396  if ((layers[i].states[j].o_deg != 0) ||
397  (layers[i].states[j].i_deg != 0))
398  i_map[j]=i_n++;
399  layers[i].n_states = i_n;
400  n_states += i_n;
401  max_s = std::max(max_s,i_n);
402 
403  // Update states in edges
404  for (ValSize j=layers[i].size; j--; ) {
405  Support& ls = layers[i].support[j];
406  n_edges += ls.n_edges;
407  for (Degree deg=ls.n_edges; deg--; ) {
408  ls.edges[deg].i_state = i_map[ls.edges[deg].i_state];
409  ls.edges[deg].o_state = o_map[ls.edges[deg].o_state];
410  }
411  }
412  }
413 
414  // Allocate and copy states
415  State* a_states = home.alloc<State>(n_states);
416  for (int i=n+1; i--; ) {
417  StateIdx k=0;
418  for (StateIdx j=max_states; j--; )
419  if ((layers[i].states[j].o_deg != 0) ||
420  (layers[i].states[j].i_deg != 0))
421  a_states[k++] = layers[i].states[j];
422  assert(k == layers[i].n_states);
423  layers[i].states = a_states;
424  a_states += layers[i].n_states;
425  }
426 
427  // Update maximal number of states
428  max_states = max_s;
429  }
430 
431  // Schedule if subsumption is needed
432  if (c.empty())
433  View::schedule(home,*this,ME_INT_VAL);
434 
435  audit();
436  return ES_OK;
437  }
438 
439  template<class View, class Val, class Degree, class StateIdx>
440  ExecStatus
442  Advisor& _a, const Delta& d) {
443  // Check whether state information has already been created
444  if (layers[0].states == NULL) {
445  State* states = home.alloc<State>(n_states);
446  for (unsigned int i=n_states; i--; )
447  states[i].init();
448  layers[n].states = states;
449  states += layers[n].n_states;
450  for (int i=n; i--; ) {
451  layers[i].states = states;
452  states += layers[i].n_states;
453  for (ValSize j=layers[i].size; j--; ) {
454  Support& s = layers[i].support[j];
455  for (Degree deg=s.n_edges; deg--; ) {
456  i_state(i,s.edges[deg]).o_deg++;
457  o_state(i,s.edges[deg]).i_deg++;
458  }
459  }
460  }
461  }
462 
463  Index& a = static_cast<Index&>(_a);
464  const int i = a.i;
465 
466  if (layers[i].size <= layers[i].x.size()) {
467  // Propagator has already done everything
468  if (View::modevent(d) == ME_INT_VAL) {
469  a.dispose(home,c);
470  return c.empty() ? ES_NOFIX : ES_FIX;
471  } else {
472  return ES_FIX;
473  }
474  }
475 
476  bool i_mod = false;
477  bool o_mod = false;
478 
479  if (View::modevent(d) == ME_INT_VAL) {
480  Val n = static_cast<Val>(layers[i].x.val());
481  ValSize j=0;
482  for (; layers[i].support[j].val < n; j++) {
483  Support& s = layers[i].support[j];
484  n_edges -= s.n_edges;
485  // Supported value not any longer in view
486  for (Degree deg=s.n_edges; deg--; ) {
487  // Adapt states
488  o_mod |= i_dec(i,s.edges[deg]);
489  i_mod |= o_dec(i,s.edges[deg]);
490  }
491  }
492  assert(layers[i].support[j].val == n);
493  layers[i].support[0] = layers[i].support[j++];
494  ValSize s=layers[i].size;
495  layers[i].size = 1;
496  for (; j<s; j++) {
497  Support& ls = layers[i].support[j];
498  n_edges -= ls.n_edges;
499  for (Degree deg=ls.n_edges; deg--; ) {
500  // Adapt states
501  o_mod |= i_dec(i,ls.edges[deg]);
502  i_mod |= o_dec(i,ls.edges[deg]);
503  }
504  }
505  } else if (layers[i].x.any(d)) {
506  ValSize j=0;
507  ValSize k=0;
508  ValSize s=layers[i].size;
509  for (ViewRanges<View> rx(layers[i].x); rx() && (j<s);) {
510  Support& ls = layers[i].support[j];
511  if (ls.val < static_cast<Val>(rx.min())) {
512  // Supported value not any longer in view
513  n_edges -= ls.n_edges;
514  for (Degree deg=ls.n_edges; deg--; ) {
515  // Adapt states
516  o_mod |= i_dec(i,ls.edges[deg]);
517  i_mod |= o_dec(i,ls.edges[deg]);
518  }
519  ++j;
520  } else if (ls.val > static_cast<Val>(rx.max())) {
521  ++rx;
522  } else {
523  layers[i].support[k++]=ls;
524  ++j;
525  }
526  }
527  assert(k > 0);
528  layers[i].size = k;
529  // Remove remaining values
530  for (; j<s; j++) {
531  Support& ls=layers[i].support[j];
532  n_edges -= ls.n_edges;
533  for (Degree deg=ls.n_edges; deg--; ) {
534  // Adapt states
535  o_mod |= i_dec(i,ls.edges[deg]);
536  i_mod |= o_dec(i,ls.edges[deg]);
537  }
538  }
539  } else {
540  Val min = static_cast<Val>(layers[i].x.min(d));
541  ValSize j=0;
542  // Skip values smaller than min (to keep)
543  for (; layers[i].support[j].val < min; j++) {}
544  Val max = static_cast<Val>(layers[i].x.max(d));
545  ValSize k=j;
546  ValSize s=layers[i].size;
547  // Remove pruned values
548  for (; (j<s) && (layers[i].support[j].val <= max); j++) {
549  Support& ls=layers[i].support[j];
550  n_edges -= ls.n_edges;
551  for (Degree deg=ls.n_edges; deg--; ) {
552  // Adapt states
553  o_mod |= i_dec(i,ls.edges[deg]);
554  i_mod |= o_dec(i,ls.edges[deg]);
555  }
556  }
557  // Keep remaining values
558  while (j<s)
559  layers[i].support[k++]=layers[i].support[j++];
560  layers[i].size=k;
561  assert(k > 0);
562  }
563 
564  audit();
565 
566  bool fix = true;
567  if (o_mod && (i > 0)) {
568  o_ch.add(i-1); fix = false;
569  }
570  if (i_mod && (i+1 < n)) {
571  i_ch.add(i+1); fix = false;
572  }
573  if (fix) {
574  if (View::modevent(d) == ME_INT_VAL) {
575  a.dispose(home,c);
576  return c.empty() ? ES_NOFIX : ES_FIX;
577  }
578  return ES_FIX;
579  } else {
580  return (View::modevent(d) == ME_INT_VAL)
581  ? home.ES_NOFIX_DISPOSE(c,a) : ES_NOFIX;
582  }
583  }
584 
585  template<class View, class Val, class Degree, class StateIdx>
586  forceinline size_t
588  c.dispose(home);
589  (void) Propagator::dispose(home);
590  return sizeof(*this);
591  }
592 
593  template<class View, class Val, class Degree, class StateIdx>
594  void
596  View::schedule(home,*this,c.empty() ? ME_INT_VAL : ME_INT_DOM);
597  }
598 
599  template<class View, class Val, class Degree, class StateIdx>
600  ExecStatus
602  const ModEventDelta&) {
603  // Forward pass
604  for (int i=i_ch.fst(); i<=i_ch.lst(); i++) {
605  bool i_mod = false;
606  bool o_mod = false;
607  ValSize j=0;
608  ValSize k=0;
609  ValSize ls=layers[i].size;
610  do {
611  Support& s=layers[i].support[j];
612  n_edges -= s.n_edges;
613  for (Degree d=s.n_edges; d--; )
614  if (i_state(i,s.edges[d]).i_deg == 0) {
615  // Adapt states
616  o_mod |= i_dec(i,s.edges[d]);
617  i_mod |= o_dec(i,s.edges[d]);
618  // Remove edge
619  s.edges[d] = s.edges[--s.n_edges];
620  }
621  n_edges += s.n_edges;
622  // Check whether value is still supported
623  if (s.n_edges == 0) {
624  layers[i].size--;
625  GECODE_ME_CHECK(layers[i].x.nq(home,s.val));
626  } else {
627  layers[i].support[k++]=s;
628  }
629  } while (++j<ls);
630  assert(k > 0);
631  // Update modification information
632  if (o_mod && (i > 0))
633  o_ch.add(i-1);
634  if (i_mod && (i+1 < n))
635  i_ch.add(i+1);
636  }
637 
638  // Backward pass
639  for (int i=o_ch.lst(); i>=o_ch.fst(); i--) {
640  bool o_mod = false;
641  ValSize j=0;
642  ValSize k=0;
643  ValSize ls=layers[i].size;
644  do {
645  Support& s=layers[i].support[j];
646  n_edges -= s.n_edges;
647  for (Degree d=s.n_edges; d--; )
648  if (o_state(i,s.edges[d]).o_deg == 0) {
649  // Adapt states
650  o_mod |= i_dec(i,s.edges[d]);
651  (void) o_dec(i,s.edges[d]);
652  // Remove edge
653  s.edges[d] = s.edges[--s.n_edges];
654  }
655  n_edges += s.n_edges;
656  // Check whether value is still supported
657  if (s.n_edges == 0) {
658  layers[i].size--;
659  GECODE_ME_CHECK(layers[i].x.nq(home,s.val));
660  } else {
661  layers[i].support[k++]=s;
662  }
663  } while (++j<ls);
664  assert(k > 0);
665  // Update modification information
666  if (o_mod && (i > 0))
667  o_ch.add(i-1);
668  }
669 
670  a_ch.add(i_ch); i_ch.reset();
671  a_ch.add(o_ch); o_ch.reset();
672 
673  audit();
674 
675  // Check subsumption
676  if (c.empty())
677  return home.ES_SUBSUMED(*this);
678  else
679  return ES_FIX;
680  }
681 
682 
683  template<class View, class Val, class Degree, class StateIdx>
684  template<class Var>
685  ExecStatus
687  const VarArgArray<Var>& x,
688  const DFA& dfa) {
689  if (x.size() == 0) {
690  // Check whether the start state 0 is also a final state
691  if ((dfa.final_fst() <= 0) && (dfa.final_lst() >= 0))
692  return ES_OK;
693  return ES_FAILED;
694  }
695  assert(x.size() > 0);
696  for (int i=x.size(); i--; ) {
697  DFA::Symbols s(dfa);
698  typename VarTraits<Var>::View xi(x[i]);
699  GECODE_ME_CHECK(xi.inter_v(home,s,false));
700  }
702  new (home) LayeredGraph<View,Val,Degree,StateIdx>(home,x,dfa);
703  return p->initialize(home,x,dfa);
704  }
705 
706  template<class View, class Val, class Degree, class StateIdx>
710  : Propagator(home,p),
711  n(p.n), layers(home.alloc<Layer>(n+1)),
713  c.update(home,p.c);
714  // Do not allocate states, postpone to advise!
716  layers[n].states = NULL;
717  // Allocate memory for edges
718  Edge* edges = home.alloc<Edge>(n_edges);
719  // Copy layers
720  for (int i=n; i--; ) {
721  layers[i].x.update(home,p.layers[i].x);
722  assert(layers[i].x.size() == p.layers[i].size);
723  layers[i].size = p.layers[i].size;
724  layers[i].support = home.alloc<Support>(layers[i].size);
725  for (ValSize j=layers[i].size; j--; ) {
726  layers[i].support[j].val = p.layers[i].support[j].val;
728  assert(layers[i].support[j].n_edges > 0);
729  layers[i].support[j].edges =
730  Heap::copy(edges,p.layers[i].support[j].edges,
731  layers[i].support[j].n_edges);
732  edges += layers[i].support[j].n_edges;
733  }
735  layers[i].states = NULL;
736  }
737  audit();
738  }
739 
740  template<class View, class Val, class Degree, class StateIdx>
741  PropCost
743  const ModEventDelta&) const {
745  }
746 
747  template<class View, class Val, class Degree, class StateIdx>
748  Actor*
750  // Eliminate an assigned prefix
751  {
752  int k=0;
753  while (layers[k].size == 1) {
754  assert(layers[k].support[0].n_edges == 1);
755  n_states -= layers[k].n_states;
756  k++;
757  }
758  if (k > 0) {
759  /*
760  * The state information is always available: either the propagator
761  * has been created (hence, also the state information has been
762  * created), or the first variable become assigned and hence
763  * an advisor must have been run (which then has created the state
764  * information).
765  */
766  // Eliminate assigned layers
767  n -= k; layers += k;
768  // Eliminate edges
769  n_edges -= static_cast<unsigned int>(k);
770  // Update advisor indices
771  for (Advisors<Index> as(c); as(); ++as)
772  as.advisor().i -= k;
773  // Update all change information
774  a_ch.lshift(k);
775  }
776  }
777  audit();
778 
779  // Compress states
780  if (!a_ch.empty()) {
781  int f = a_ch.fst();
782  int l = a_ch.lst();
783  assert((f >= 0) && (l <= n));
784  Region r;
785  // State map for in-states
786  StateIdx* i_map = r.alloc<StateIdx>(max_states);
787  // State map for out-states
788  StateIdx* o_map = r.alloc<StateIdx>(max_states);
789  // Number of in-states
790  StateIdx i_n = 0;
791 
793  // Initialize map for in-states and compress
794  for (StateIdx j=0; j<layers[l].n_states; j++)
795  if ((layers[l].states[j].i_deg != 0) ||
796  (layers[l].states[j].o_deg != 0)) {
797  layers[l].states[i_n]=layers[l].states[j];
798  i_map[j]=i_n++;
799  }
800  layers[l].n_states = i_n;
802  assert(i_n > 0);
803 
804  // Update in-states in edges for last layer, if any
805  if (l < n)
806  for (ValSize j=layers[l].size; j--; ) {
807  Support& s = layers[l].support[j];
808  for (Degree d=s.n_edges; d--; )
809  s.edges[d].i_state = i_map[s.edges[d].i_state];
810  }
811 
812  // Update all changed layers
813  for (int i=l-1; i>=f; i--) {
814  // In-states become out-states
815  std::swap(o_map,i_map); i_n=0;
816  // Initialize map for in-states and compress
818  for (StateIdx j=0; j<layers[i].n_states; j++)
819  if ((layers[i].states[j].o_deg != 0) ||
820  (layers[i].states[j].i_deg != 0)) {
821  layers[i].states[i_n]=layers[i].states[j];
822  i_map[j]=i_n++;
823  }
824  layers[i].n_states = i_n;
826  assert(i_n > 0);
827 
828  // Update states in edges
829  for (ValSize j=layers[i].size; j--; ) {
830  Support& s = layers[i].support[j];
831  for (Degree d=s.n_edges; d--; ) {
832  s.edges[d].i_state = i_map[s.edges[d].i_state];
833  s.edges[d].o_state = o_map[s.edges[d].o_state];
834  }
835  }
836  }
837 
838  // Update out-states in edges for previous layer, if any
839  if (f > 0)
840  for (ValSize j=layers[f-1].size; j--; ) {
841  Support& s = layers[f-1].support[j];
842  for (Degree d=s.n_edges; d--; )
843  s.edges[d].o_state = i_map[s.edges[d].o_state];
844  }
845 
846  a_ch.reset();
847  }
848  audit();
849 
850  return new (home) LayeredGraph<View,Val,Degree,StateIdx>(home,*this);
851  }
852 
854  template<class Var>
856  post_lgp(Home home, const VarArgArray<Var>& x, const DFA& dfa) {
857  Gecode::Support::IntType t_state_idx =
858  Gecode::Support::u_type(static_cast<unsigned int>(dfa.n_states()));
859  Gecode::Support::IntType t_degree =
863  Support::s_type(dfa.symbol_max()));
864  switch (t_val) {
867  switch (t_state_idx) {
869  switch (t_degree) {
872  <typename VarTraits<Var>::View,short int,unsigned char,unsigned char>
873  ::post(home,x,dfa);
876  <typename VarTraits<Var>::View,short int,unsigned short int,unsigned char>
877  ::post(home,x,dfa);
880  <typename VarTraits<Var>::View,short int,unsigned int,unsigned char>
881  ::post(home,x,dfa);
882  default: GECODE_NEVER;
883  }
884  break;
886  switch (t_degree) {
889  <typename VarTraits<Var>::View,short int,unsigned char,unsigned short int>
890  ::post(home,x,dfa);
893  <typename VarTraits<Var>::View,short int,unsigned short int,unsigned short int>
894  ::post(home,x,dfa);
897  <typename VarTraits<Var>::View,short int,unsigned int,unsigned short int>
898  ::post(home,x,dfa);
899  default: GECODE_NEVER;
900  }
901  break;
903  switch (t_degree) {
906  <typename VarTraits<Var>::View,short int,unsigned char,unsigned int>
907  ::post(home,x,dfa);
910  <typename VarTraits<Var>::View,short int,unsigned short int,unsigned int>
911  ::post(home,x,dfa);
914  <typename VarTraits<Var>::View,short int,unsigned int,unsigned int>
915  ::post(home,x,dfa);
916  default: GECODE_NEVER;
917  }
918  break;
919  default: GECODE_NEVER;
920  }
921 
923  switch (t_state_idx) {
925  switch (t_degree) {
928  <typename VarTraits<Var>::View,int,unsigned char,unsigned char>
929  ::post(home,x,dfa);
932  <typename VarTraits<Var>::View,int,unsigned short int,unsigned char>
933  ::post(home,x,dfa);
936  <typename VarTraits<Var>::View,int,unsigned int,unsigned char>
937  ::post(home,x,dfa);
938  default: GECODE_NEVER;
939  }
940  break;
942  switch (t_degree) {
945  <typename VarTraits<Var>::View,int,unsigned char,unsigned short int>
946  ::post(home,x,dfa);
949  <typename VarTraits<Var>::View,int,unsigned short int,unsigned short int>
950  ::post(home,x,dfa);
953  <typename VarTraits<Var>::View,int,unsigned int,unsigned short int>
954  ::post(home,x,dfa);
955  default: GECODE_NEVER;
956  }
957  break;
959  switch (t_degree) {
962  <typename VarTraits<Var>::View,int,unsigned char,unsigned int>
963  ::post(home,x,dfa);
966  <typename VarTraits<Var>::View,int,unsigned short int,unsigned int>
967  ::post(home,x,dfa);
970  <typename VarTraits<Var>::View,int,unsigned int,unsigned int>
971  ::post(home,x,dfa);
972  default: GECODE_NEVER;
973  }
974  break;
975  default: GECODE_NEVER;
976  }
977 
978  default: GECODE_NEVER;
979  }
980  return ES_OK;
981  }
982 
983 }}}
984 
985 // STATISTICS: int-prop
986 
IndexRange i_ch
Index range with in-degree modifications.
Definition: extensional.hh:170
int fst(void) const
Return first position.
Council of advisors
Definition: core.hpp:156
static T * copy(T *d, const T *s, long unsigned int n)
Copy n objects starting at s to d.
Definition: heap.hpp:587
NodeType t
Type of node.
Definition: bool-expr.cpp:234
int final_fst(void) const
Return the number of the first final state.
Definition: dfa.hpp:167
NNF * l
Left subtree.
Definition: bool-expr.cpp:244
int size(void) const
Return size of array (number of elements)
Definition: array.hpp:1657
void audit(void)
Perform consistency check on data structures.
Edge defined by in-state and out-state
Definition: extensional.hh:82
static PropCost linear(PropCost::Mod m, unsigned int n)
Linear complexity for modifier pcm and size measure n.
Definition: core.hpp:4643
Council< Index > c
The advisor council.
Definition: extensional.hh:158
Iterator for DFA symbols.
Definition: int.hh:2070
ExecStatus ES_SUBSUMED(Propagator &p)
Definition: core.hpp:3433
const FloatNum max
Largest allowed float value.
Definition: float.hh:848
int n
Number of layers (and views)
Definition: extensional.hh:160
Iterator for telling variable domains by scanning support.
Definition: extensional.hh:106
IndexRange a_ch
Index range for any change (for compression)
Definition: extensional.hh:174
StateIdx n_states
Number of states used by outgoing edges.
Definition: extensional.hh:100
T * alloc(long unsigned int n)
Allocate block of n objects of type T from region.
Definition: region.hpp:384
Traits class for variables.
void max(Home home, FloatVar x0, FloatVar x1, FloatVar x2)
Post propagator for .
Definition: arithmetic.cpp:53
unsigned int n_states
Total number of states.
Definition: extensional.hh:166
Index(Space &home, Propagator &p, Council< Index > &c, int i)
Create index advisor.
IntType u_type(unsigned int n)
Return type required to represent n.
Definition: int-type.hpp:151
void init(const Layer &l)
Initialize for support of layer l.
StateIdx i_state
Number of in-state.
Definition: extensional.hh:84
Base-class for propagators.
Definition: core.hpp:1016
Base-class for advisors.
Definition: core.hpp:1218
ExecStatus ES_NOFIX_DISPOSE(Council< A > &c, A &a)
Advisor a must be disposed and its propagator must be run
Definition: core.hpp:3757
Class to iterate over advisors of a council.
Definition: core.hpp:157
Handle to region.
Definition: region.hpp:57
Value iterator for integer views.
Definition: view.hpp:94
void lshift(int n)
Shift index range by n elements to the left.
#define forceinline
Definition: config.hpp:182
Propagation has computed fixpoint.
Definition: core.hpp:469
Int::IntView View
The variable type of an IntView.
Computation spaces.
Definition: core.hpp:1668
Support information for a value
Definition: extensional.hh:88
bool i_dec(int i, const Edge &e)
Decrement out degree for in state of edge e for layer i.
IndexRange o_ch
Index range with out-degree modifications.
Definition: extensional.hh:172
LayeredGraph(Space &home, LayeredGraph< View, Val, Degree, StateIdx > &p)
Constructor for cloning p.
Base-class for both propagators and branchers.
Definition: core.hpp:620
Range iterator for integer views.
Definition: view.hpp:54
IntType s_type(signed int n)
Return type required to represent n.
Gecode::IntSet d(v, 7)
T * alloc(long unsigned int n)
Allocate block of n objects of type T from space heap.
Definition: core.hpp:2757
State & o_state(int i, StateIdx os)
Return out state for layer i and state index os.
ValSize size
Number of supported values.
Definition: extensional.hh:101
char integer type
Definition: int-type.hpp:44
Single _a(2, 3)
StateIdx o_state
Number of out-state.
Definition: extensional.hh:85
Deterministic finite automaton (DFA)
Definition: int.hh:2027
int p
Number of positive literals for node type.
Definition: bool-expr.cpp:236
const FloatNum min
Smallest allowed float value.
Definition: float.hh:850
Gecode::IntArgs i(4, 1, 2, 3, 4)
void operator++(void)
Move to next supported value.
Execution has resulted in failure.
Definition: core.hpp:466
Range approximation of which positions have changed.
Definition: extensional.hh:135
const Gecode::ModEvent ME_INT_VAL
Domain operation has resulted in a value (assigned variable)
Definition: var-type.hpp:56
bool assigned(void) const
Test if all variables are assigned.
Definition: array.hpp:2060
int lst(void) const
Return last position.
Layer for a view in the layered graph
Definition: extensional.hh:97
Degree n_edges
Number of supporting edges.
Definition: extensional.hh:91
int symbol_max(void) const
Return largest symbol in DFA.
Definition: dfa.hpp:186
unsigned int size(I &i)
Size of all ranges of range iterator i.
size_t size
The size of the propagator (used during subsumption)
Definition: core.hpp:1029
Layer * layers
The layers of the graph.
Definition: extensional.hh:162
StateIdx max_states
Maximal number of states per layer.
Definition: extensional.hh:164
Expensive.
Definition: core.hpp:506
ExecStatus post_lgp(Home home, const VarArgArray< Var > &x, const DFA &dfa)
Select small types for the layered graph propagator.
void reset(void)
Reset range to be empty.
#define GECODE_ME_CHECK(me)
Check whether modification event me is failed, and forward failure.
Definition: macros.hpp:56
Traits to for information about integer types.
Definition: int-type.hpp:56
Degree o_deg
The out-degree (number of outgoing edges) Initialize with zeroes.
Definition: extensional.hh:77
State * states
States used by outgoing edges.
Definition: extensional.hh:102
Boolean integer variables.
Definition: int.hh:492
Domain consistent layered graph (regular) propagator.
Definition: extensional.hh:71
Post propagator for SetVar SetOpType SetVar SetRelType r
Definition: set.hh:769
void min(Home home, FloatVar x0, FloatVar x1, FloatVar x2)
Post propagator for .
Definition: arithmetic.cpp:71
Post propagator for f(x \diamond_{\mathit{op}} y) \sim_r z \f$ void rel(Home home
Integer view for integer variables.
Definition: view.hpp:129
static ExecStatus post(Home home, const VarArgArray< Var > &x, const DFA &dfa)
Post propagator on views x and DFA dfa.
Generic domain change information to be supplied to advisors.
Definition: core.hpp:205
struct Gecode::@585::NNF::@62::@64 a
For atomic nodes.
bool empty(void) const
Test whether range is empty.
Advisors for views (by position in array)
Definition: extensional.hh:125
unsigned int max_degree(void) const
Return maximal degree (in-degree and out-degree) of any state.
Definition: dfa.hpp:161
virtual size_t dispose(Space &home)
Delete actor and return its size.
Definition: core.hpp:3172
void dispose(Space &home, Council< A > &c)
Dispose the advisor.
Definition: core.hpp:3734
Propagation cost.
Definition: core.hpp:478
const Gecode::ModEvent ME_INT_DOM
Domain operation has changed the domain.
Definition: var-type.hpp:72
ExecStatus
Definition: core.hpp:464
Integer variables.
Definition: int.hh:351
virtual ExecStatus propagate(Space &home, const ModEventDelta &med)
Perform propagation.
Iterator for DFA transitions (sorted by symbols)
Definition: int.hh:2047
Post propagator for SetVar x
Definition: set.hh:769
Execution is okay.
Definition: core.hpp:468
Propagation has not computed fixpoint.
Definition: core.hpp:467
virtual Actor * copy(Space &home)
Copy propagator during cloning.
int n_states(void) const
Return the number of states.
Definition: dfa.hpp:143
bool operator()(void) const
Test whether more values supported.
Edge * edges
Supporting edges in layered graph.
Definition: extensional.hh:92
Int::BoolView View
The variable type of an IntView.
virtual PropCost cost(const Space &home, const ModEventDelta &med) const
Cost function (defined as high linear)
State & i_state(int i, StateIdx is)
Return in state for layer i and state index is.
Gecode toplevel namespace
Argument array for variables.
Definition: array.hpp:53
int symbol_min(void) const
Return smallest symbol in DFA.
Definition: dfa.hpp:179
ExecStatus initialize(Space &home, const VarArgArray< Var > &x, const DFA &dfa)
Initialize layered graph.
States are described by number of incoming and outgoing edges.
Definition: extensional.hh:74
Degree i_deg
The in-degree (number of incoming edges)
Definition: extensional.hh:76
virtual void reschedule(Space &home)
Schedule function.
bool o_dec(int i, const Edge &e)
Decrement in degree for out state of edge e for layer i.
virtual size_t dispose(Space &home)
Delete propagator and return its size.
IntType
Description of integer types.
Definition: int-type.hpp:43
int final_lst(void) const
Return the number of the last final state.
Definition: dfa.hpp:173
int ModEventDelta
Modification event deltas.
Definition: core.hpp:91
short integer type
Definition: int-type.hpp:45
Home class for posting propagators
Definition: core.hpp:846
#define GECODE_NEVER
Assert that this command is never executed.
Definition: macros.hpp:60
int val(void) const
Return supported value.
unsigned int n_edges
Total number of edges.
Definition: extensional.hh:168
Gecode::Support::IntTypeTraits< Val >::utype ValSize
Type for support size.
Definition: extensional.hh:95
virtual ExecStatus advise(Space &home, Advisor &a, const Delta &d)
Give advice to propagator.
int i
The position of the view in the view array.
Definition: extensional.hh:128
IntRelType swap(IntRelType irt)
Return swapped relation type of irt.
Definition: irt.hpp:41
Boolean view for Boolean variables.
Definition: view.hpp:1329