Generated on Tue Jan 28 2020 00:00:00 for Gecode by doxygen 1.8.17
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: 2016-06-29 17:28:17 +0200 (Wed, 29 Jun 2016) $ by $Author: schulte $
11  * $Revision: 15137 $
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
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
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  Index& a)
172  : Advisor(home,share,a), i(a.i) {}
173 
174 
175  /*
176  * Index ranges
177  *
178  */
179  template<class View, class Val, class Degree, class StateIdx>
182  : _fst(INT_MAX), _lst(INT_MIN) {}
183  template<class View, class Val, class Degree, class StateIdx>
184  forceinline void
186  _fst=INT_MAX; _lst=INT_MIN;
187  }
188  template<class View, class Val, class Degree, class StateIdx>
189  forceinline void
191  _fst=std::min(_fst,i); _lst=std::max(_lst,i);
192  }
193  template<class View, class Val, class Degree, class StateIdx>
194  forceinline void
197  _fst=std::min(_fst,ir._fst); _lst=std::max(_lst,ir._lst);
198  }
199  template<class View, class Val, class Degree, class StateIdx>
200  forceinline bool
202  return _fst>_lst;
203  }
204  template<class View, class Val, class Degree, class StateIdx>
205  forceinline void
207  if (empty())
208  return;
209  if (n > _lst) {
210  reset();
211  } else {
212  _fst = std::max(0,_fst-n);
213  _lst -= n;
214  }
215  }
216  template<class View, class Val, class Degree, class StateIdx>
217  forceinline int
219  return _fst;
220  }
221  template<class View, class Val, class Degree, class StateIdx>
222  forceinline int
224  return _lst;
225  }
226 
227 
228 
229  /*
230  * The layered graph
231  *
232  */
233 
234  template<class View, class Val, class Degree, class StateIdx>
235  template<class Var>
238  const VarArgArray<Var>& x,
239  const DFA& dfa)
240  : Propagator(home), c(home), n(x.size()),
241  max_states(static_cast<StateIdx>(dfa.n_states())) {
242  assert(n > 0);
243  }
244 
245  template<class View, class Val, class Degree, class StateIdx>
246  forceinline void
248 #ifdef GECODE_AUDIT
249  // Check states and edge information to be consistent
250  unsigned int n_e = 0; // Number of edges
251  unsigned int n_s = 0; // Number of states
252  StateIdx m_s = 0; // Maximal number of states per layer
253  for (int i=n; i--; ) {
254  n_s += layers[i].n_states;
255  m_s = std::max(m_s,layers[i].n_states);
256  for (ValSize j=layers[i].size; j--; )
257  n_e += layers[i].support[j].n_edges;
258  }
259  n_s += layers[n].n_states;
260  m_s = std::max(m_s,layers[n].n_states);
261  assert(n_e == n_edges);
262  assert(n_s <= n_states);
263  assert(m_s <= max_states);
264 #endif
265  }
266 
267  template<class View, class Val, class Degree, class StateIdx>
268  template<class Var>
271  const VarArgArray<Var>& x,
272  const DFA& dfa) {
273 
274  Region r(home);
275 
276  // Allocate memory for layers
277  layers = home.alloc<Layer>(n+1);
278 
279  // Allocate temporary memory for all possible states
280  State* states = r.alloc<State>(max_states*(n+1));
281  for (int i=static_cast<int>(max_states)*(n+1); i--; )
282  states[i].init();
283  for (int i=n+1; i--; )
284  layers[i].states = states + i*max_states;
285 
286  // Allocate temporary memory for edges
287  Edge* edges = r.alloc<Edge>(dfa.max_degree());
288 
289  // Mark initial state as being reachable
290  i_state(0,0).i_deg = 1;
291 
292  // Forward pass: add transitions
293  for (int i=0; i<n; i++) {
294  layers[i].x = x[i];
295  layers[i].support = home.alloc<Support>(layers[i].x.size());
296  ValSize j=0;
297  // Enter links leaving reachable states (indegree != 0)
298  for (ViewValues<View> nx(layers[i].x); nx(); ++nx) {
299  Degree n_edges=0;
300  for (DFA::Transitions t(dfa,nx.val()); t(); ++t)
301  if (i_state(i,static_cast<StateIdx>(t.i_state())).i_deg != 0) {
302  i_state(i,static_cast<StateIdx>(t.i_state())).o_deg++;
303  o_state(i,static_cast<StateIdx>(t.o_state())).i_deg++;
304  edges[n_edges].i_state = static_cast<StateIdx>(t.i_state());
305  edges[n_edges].o_state = static_cast<StateIdx>(t.o_state());
306  n_edges++;
307  }
308  assert(n_edges <= dfa.max_degree());
309  // Found support for value
310  if (n_edges > 0) {
311  Support& s = layers[i].support[j];
312  s.val = static_cast<Val>(nx.val());
313  s.n_edges = n_edges;
314  s.edges = Heap::copy(home.alloc<Edge>(n_edges),edges,n_edges);
315  j++;
316  }
317  }
318  if ((layers[i].size = j) == 0)
319  return ES_FAILED;
320  }
321 
322  // Mark final states as reachable
323  for (int s=dfa.final_fst(); s<dfa.final_lst(); s++)
324  if (o_state(n-1,static_cast<StateIdx>(s)).i_deg != 0)
325  o_state(n-1,static_cast<StateIdx>(s)).o_deg = 1;
326 
327  // Backward pass: prune all transitions that do not lead to final state
328  for (int i=n; i--; ) {
329  ValSize k=0;
330  for (ValSize j=0; j<layers[i].size; j++) {
331  Support& s = layers[i].support[j];
332  for (Degree d=s.n_edges; d--; )
333  if (o_state(i,s.edges[d]).o_deg == 0) {
334  // Adapt states
335  i_dec(i,s.edges[d]); o_dec(i,s.edges[d]);
336  // Prune edge
337  s.edges[d] = s.edges[--s.n_edges];
338  }
339  // Value has support, copy the support information
340  if (s.n_edges > 0)
341  layers[i].support[k++]=s;
342  }
343  if ((layers[i].size = k) == 0)
344  return ES_FAILED;
345  LayerValues lv(layers[i]);
346  GECODE_ME_CHECK(layers[i].x.narrow_v(home,lv,false));
347  if (!layers[i].x.assigned())
348  layers[i].x.subscribe(home, *new (home) Index(home,*this,c,i));
349  }
350 
351  // Copy and compress states, setup other information
352  {
353  // State map for in-states
354  StateIdx* i_map = r.alloc<StateIdx>(max_states);
355  // State map for out-states
356  StateIdx* o_map = r.alloc<StateIdx>(max_states);
357  // Number of in-states
358  StateIdx i_n = 0;
359 
360  // Initialize map for in-states (special for last layer)
361  // Degree for single final state
362  unsigned int d = 0;
363  for (StateIdx j=max_states; j--; )
364  d += static_cast<unsigned int>(layers[n].states[j].i_deg);
365  // Check whether all final states can be joined to a single state
366  if (d >
367  static_cast<unsigned int>
369  // Initialize map for in-states
370  for (StateIdx j=max_states; j--; )
371  if ((layers[n].states[j].o_deg != 0) ||
372  (layers[n].states[j].i_deg != 0))
373  i_map[j]=i_n++;
374  } else {
375  i_n = 1;
376  for (StateIdx j=max_states; j--; ) {
377  layers[n].states[j].init();
378  i_map[j] = 0;
379  }
380  layers[n].states[0].i_deg = static_cast<Degree>(d);
381  layers[n].states[0].o_deg = 1;
382  }
383  layers[n].n_states = i_n;
384 
385  // Total number of states
386  n_states = i_n;
387  // Total number of edges
388  n_edges = 0;
389  // New maximal number of states
390  StateIdx max_s = i_n;
391 
392  for (int i=n; i--; ) {
393  // In-states become out-states
394  std::swap(o_map,i_map); i_n=0;
395  // Initialize map for in-states
396  for (StateIdx j=max_states; j--; )
397  if ((layers[i].states[j].o_deg != 0) ||
398  (layers[i].states[j].i_deg != 0))
399  i_map[j]=i_n++;
400  layers[i].n_states = i_n;
401  n_states += i_n;
402  max_s = std::max(max_s,i_n);
403 
404  // Update states in edges
405  for (ValSize j=layers[i].size; j--; ) {
406  Support& ls = layers[i].support[j];
407  n_edges += ls.n_edges;
408  for (Degree deg=ls.n_edges; deg--; ) {
409  ls.edges[deg].i_state = i_map[ls.edges[deg].i_state];
410  ls.edges[deg].o_state = o_map[ls.edges[deg].o_state];
411  }
412  }
413  }
414 
415  // Allocate and copy states
416  State* a_states = home.alloc<State>(n_states);
417  for (int i=n+1; i--; ) {
418  StateIdx k=0;
419  for (StateIdx j=max_states; j--; )
420  if ((layers[i].states[j].o_deg != 0) ||
421  (layers[i].states[j].i_deg != 0))
422  a_states[k++] = layers[i].states[j];
423  assert(k == layers[i].n_states);
424  layers[i].states = a_states;
425  a_states += layers[i].n_states;
426  }
427 
428  // Update maximal number of states
429  max_states = max_s;
430  }
431 
432  // Schedule if subsumption is needed
433  if (c.empty())
434  View::schedule(home,*this,ME_INT_VAL);
435 
436  audit();
437  return ES_OK;
438  }
439 
440  template<class View, class Val, class Degree, class StateIdx>
441  ExecStatus
443  Advisor& _a, const Delta& d) {
444  // Check whether state information has already been created
445  if (layers[0].states == NULL) {
446  State* states = home.alloc<State>(n_states);
447  for (unsigned int i=n_states; i--; )
448  states[i].init();
449  layers[n].states = states;
450  states += layers[n].n_states;
451  for (int i=n; i--; ) {
452  layers[i].states = states;
453  states += layers[i].n_states;
454  for (ValSize j=layers[i].size; j--; ) {
455  Support& s = layers[i].support[j];
456  for (Degree deg=s.n_edges; deg--; ) {
457  i_state(i,s.edges[deg]).o_deg++;
458  o_state(i,s.edges[deg]).i_deg++;
459  }
460  }
461  }
462  }
463 
464  Index& a = static_cast<Index&>(_a);
465  const int i = a.i;
466 
467  if (layers[i].size <= layers[i].x.size()) {
468  // Propagator has already done everything
469  if (View::modevent(d) == ME_INT_VAL) {
470  a.dispose(home,c);
471  return c.empty() ? ES_NOFIX : ES_FIX;
472  } else {
473  return ES_FIX;
474  }
475  }
476 
477  bool i_mod = false;
478  bool o_mod = false;
479 
480  if (View::modevent(d) == ME_INT_VAL) {
481  Val n = static_cast<Val>(layers[i].x.val());
482  ValSize j=0;
483  for (; layers[i].support[j].val < n; j++) {
484  Support& s = layers[i].support[j];
485  n_edges -= s.n_edges;
486  // Supported value not any longer in view
487  for (Degree deg=s.n_edges; deg--; ) {
488  // Adapt states
489  o_mod |= i_dec(i,s.edges[deg]);
490  i_mod |= o_dec(i,s.edges[deg]);
491  }
492  }
493  assert(layers[i].support[j].val == n);
494  layers[i].support[0] = layers[i].support[j++];
495  ValSize s=layers[i].size;
496  layers[i].size = 1;
497  for (; j<s; j++) {
498  Support& ls = layers[i].support[j];
499  n_edges -= ls.n_edges;
500  for (Degree deg=ls.n_edges; deg--; ) {
501  // Adapt states
502  o_mod |= i_dec(i,ls.edges[deg]);
503  i_mod |= o_dec(i,ls.edges[deg]);
504  }
505  }
506  } else if (layers[i].x.any(d)) {
507  ValSize j=0;
508  ValSize k=0;
509  ValSize s=layers[i].size;
510  for (ViewRanges<View> rx(layers[i].x); rx() && (j<s);) {
511  Support& ls = layers[i].support[j];
512  if (ls.val < static_cast<Val>(rx.min())) {
513  // Supported value not any longer in view
514  n_edges -= ls.n_edges;
515  for (Degree deg=ls.n_edges; deg--; ) {
516  // Adapt states
517  o_mod |= i_dec(i,ls.edges[deg]);
518  i_mod |= o_dec(i,ls.edges[deg]);
519  }
520  ++j;
521  } else if (ls.val > static_cast<Val>(rx.max())) {
522  ++rx;
523  } else {
524  layers[i].support[k++]=ls;
525  ++j;
526  }
527  }
528  assert(k > 0);
529  layers[i].size = k;
530  // Remove remaining values
531  for (; j<s; j++) {
532  Support& ls=layers[i].support[j];
533  n_edges -= ls.n_edges;
534  for (Degree deg=ls.n_edges; deg--; ) {
535  // Adapt states
536  o_mod |= i_dec(i,ls.edges[deg]);
537  i_mod |= o_dec(i,ls.edges[deg]);
538  }
539  }
540  } else {
541  Val min = static_cast<Val>(layers[i].x.min(d));
542  ValSize j=0;
543  // Skip values smaller than min (to keep)
544  for (; layers[i].support[j].val < min; j++) {}
545  Val max = static_cast<Val>(layers[i].x.max(d));
546  ValSize k=j;
547  ValSize s=layers[i].size;
548  // Remove pruned values
549  for (; (j<s) && (layers[i].support[j].val <= max); j++) {
550  Support& ls=layers[i].support[j];
551  n_edges -= ls.n_edges;
552  for (Degree deg=ls.n_edges; deg--; ) {
553  // Adapt states
554  o_mod |= i_dec(i,ls.edges[deg]);
555  i_mod |= o_dec(i,ls.edges[deg]);
556  }
557  }
558  // Keep remaining values
559  while (j<s)
560  layers[i].support[k++]=layers[i].support[j++];
561  layers[i].size=k;
562  assert(k > 0);
563  }
564 
565  audit();
566 
567  bool fix = true;
568  if (o_mod && (i > 0)) {
569  o_ch.add(i-1); fix = false;
570  }
571  if (i_mod && (i+1 < n)) {
572  i_ch.add(i+1); fix = false;
573  }
574  if (fix) {
575  if (View::modevent(d) == ME_INT_VAL) {
576  a.dispose(home,c);
577  return c.empty() ? ES_NOFIX : ES_FIX;
578  }
579  return ES_FIX;
580  } else {
581  return (View::modevent(d) == ME_INT_VAL)
582  ? home.ES_NOFIX_DISPOSE(c,a) : ES_NOFIX;
583  }
584  }
585 
586  template<class View, class Val, class Degree, class StateIdx>
587  forceinline size_t
589  c.dispose(home);
590  (void) Propagator::dispose(home);
591  return sizeof(*this);
592  }
593 
594  template<class View, class Val, class Degree, class StateIdx>
595  void
597  View::schedule(home,*this,c.empty() ? ME_INT_VAL : ME_INT_DOM);
598  }
599 
600  template<class View, class Val, class Degree, class StateIdx>
601  ExecStatus
603  const ModEventDelta&) {
604  // Forward pass
605  for (int i=i_ch.fst(); i<=i_ch.lst(); i++) {
606  bool i_mod = false;
607  bool o_mod = false;
608  ValSize j=0;
609  ValSize k=0;
610  ValSize ls=layers[i].size;
611  do {
612  Support& s=layers[i].support[j];
613  n_edges -= s.n_edges;
614  for (Degree d=s.n_edges; d--; )
615  if (i_state(i,s.edges[d]).i_deg == 0) {
616  // Adapt states
617  o_mod |= i_dec(i,s.edges[d]);
618  i_mod |= o_dec(i,s.edges[d]);
619  // Remove edge
620  s.edges[d] = s.edges[--s.n_edges];
621  }
622  n_edges += s.n_edges;
623  // Check whether value is still supported
624  if (s.n_edges == 0) {
625  layers[i].size--;
626  GECODE_ME_CHECK(layers[i].x.nq(home,s.val));
627  } else {
628  layers[i].support[k++]=s;
629  }
630  } while (++j<ls);
631  assert(k > 0);
632  // Update modification information
633  if (o_mod && (i > 0))
634  o_ch.add(i-1);
635  if (i_mod && (i+1 < n))
636  i_ch.add(i+1);
637  }
638 
639  // Backward pass
640  for (int i=o_ch.lst(); i>=o_ch.fst(); i--) {
641  bool o_mod = false;
642  ValSize j=0;
643  ValSize k=0;
644  ValSize ls=layers[i].size;
645  do {
646  Support& s=layers[i].support[j];
647  n_edges -= s.n_edges;
648  for (Degree d=s.n_edges; d--; )
649  if (o_state(i,s.edges[d]).o_deg == 0) {
650  // Adapt states
651  o_mod |= i_dec(i,s.edges[d]);
652  (void) o_dec(i,s.edges[d]);
653  // Remove edge
654  s.edges[d] = s.edges[--s.n_edges];
655  }
656  n_edges += s.n_edges;
657  // Check whether value is still supported
658  if (s.n_edges == 0) {
659  layers[i].size--;
660  GECODE_ME_CHECK(layers[i].x.nq(home,s.val));
661  } else {
662  layers[i].support[k++]=s;
663  }
664  } while (++j<ls);
665  assert(k > 0);
666  // Update modification information
667  if (o_mod && (i > 0))
668  o_ch.add(i-1);
669  }
670 
671  a_ch.add(i_ch); i_ch.reset();
672  a_ch.add(o_ch); o_ch.reset();
673 
674  audit();
675 
676  // Check subsumption
677  if (c.empty())
678  return home.ES_SUBSUMED(*this);
679  else
680  return ES_FIX;
681  }
682 
683 
684  template<class View, class Val, class Degree, class StateIdx>
685  template<class Var>
686  ExecStatus
688  const VarArgArray<Var>& x,
689  const DFA& dfa) {
690  if (x.size() == 0) {
691  // Check whether the start state 0 is also a final state
692  if ((dfa.final_fst() <= 0) && (dfa.final_lst() >= 0))
693  return ES_OK;
694  return ES_FAILED;
695  }
696  assert(x.size() > 0);
697  for (int i=x.size(); i--; ) {
698  DFA::Symbols s(dfa);
699  typename VarTraits<Var>::View xi(x[i]);
700  GECODE_ME_CHECK(xi.inter_v(home,s,false));
701  }
703  new (home) LayeredGraph<View,Val,Degree,StateIdx>(home,x,dfa);
704  return p->initialize(home,x,dfa);
705  }
706 
707  template<class View, class Val, class Degree, class StateIdx>
710  ::LayeredGraph(Space& home, bool share,
712  : Propagator(home,share,p),
713  n(p.n), layers(home.alloc<Layer>(n+1)),
714  max_states(p.max_states), n_states(p.n_states), n_edges(p.n_edges) {
715  c.update(home,share,p.c);
716  // Do not allocate states, postpone to advise!
717  layers[n].n_states = p.layers[n].n_states;
718  layers[n].states = NULL;
719  // Allocate memory for edges
720  Edge* edges = home.alloc<Edge>(n_edges);
721  // Copy layers
722  for (int i=n; i--; ) {
723  layers[i].x.update(home,share,p.layers[i].x);
724  assert(layers[i].x.size() == p.layers[i].size);
725  layers[i].size = p.layers[i].size;
726  layers[i].support = home.alloc<Support>(layers[i].size);
727  for (ValSize j=layers[i].size; j--; ) {
728  layers[i].support[j].val = p.layers[i].support[j].val;
729  layers[i].support[j].n_edges = p.layers[i].support[j].n_edges;
730  assert(layers[i].support[j].n_edges > 0);
731  layers[i].support[j].edges =
732  Heap::copy(edges,p.layers[i].support[j].edges,
733  layers[i].support[j].n_edges);
734  edges += layers[i].support[j].n_edges;
735  }
736  layers[i].n_states = p.layers[i].n_states;
737  layers[i].states = NULL;
738  }
739  audit();
740  }
741 
742  template<class View, class Val, class Degree, class StateIdx>
743  PropCost
745  const ModEventDelta&) const {
747  }
748 
749  template<class View, class Val, class Degree, class StateIdx>
750  Actor*
752  // Eliminate an assigned prefix
753  {
754  int k=0;
755  while (layers[k].size == 1) {
756  assert(layers[k].support[0].n_edges == 1);
757  n_states -= layers[k].n_states;
758  k++;
759  }
760  if (k > 0) {
761  /*
762  * The state information is always available: either the propagator
763  * has been created (hence, also the state information has been
764  * created), or the first variable become assigned and hence
765  * an advisor must have been run (which then has created the state
766  * information).
767  */
768  // Eliminate assigned layers
769  n -= k; layers += k;
770  // Eliminate edges
771  n_edges -= static_cast<unsigned int>(k);
772  // Update advisor indices
773  for (Advisors<Index> as(c); as(); ++as)
774  as.advisor().i -= k;
775  // Update all change information
776  a_ch.lshift(k);
777  }
778  }
779  audit();
780 
781  // Compress states
782  if (!a_ch.empty()) {
783  int f = a_ch.fst();
784  int l = a_ch.lst();
785  assert((f >= 0) && (l <= n));
786  Region r(home);
787  // State map for in-states
788  StateIdx* i_map = r.alloc<StateIdx>(max_states);
789  // State map for out-states
790  StateIdx* o_map = r.alloc<StateIdx>(max_states);
791  // Number of in-states
792  StateIdx i_n = 0;
793 
794  n_states -= layers[l].n_states;
795  // Initialize map for in-states and compress
796  for (StateIdx j=0; j<layers[l].n_states; j++)
797  if ((layers[l].states[j].i_deg != 0) ||
798  (layers[l].states[j].o_deg != 0)) {
799  layers[l].states[i_n]=layers[l].states[j];
800  i_map[j]=i_n++;
801  }
802  layers[l].n_states = i_n;
803  n_states += layers[l].n_states;
804  assert(i_n > 0);
805 
806  // Update in-states in edges for last layer, if any
807  if (l < n)
808  for (ValSize j=layers[l].size; j--; ) {
809  Support& s = layers[l].support[j];
810  for (Degree d=s.n_edges; d--; )
811  s.edges[d].i_state = i_map[s.edges[d].i_state];
812  }
813 
814  // Update all changed layers
815  for (int i=l-1; i>=f; i--) {
816  // In-states become out-states
817  std::swap(o_map,i_map); i_n=0;
818  // Initialize map for in-states and compress
819  n_states -= layers[i].n_states;
820  for (StateIdx j=0; j<layers[i].n_states; j++)
821  if ((layers[i].states[j].o_deg != 0) ||
822  (layers[i].states[j].i_deg != 0)) {
823  layers[i].states[i_n]=layers[i].states[j];
824  i_map[j]=i_n++;
825  }
826  layers[i].n_states = i_n;
827  n_states += layers[i].n_states;
828  assert(i_n > 0);
829 
830  // Update states in edges
831  for (ValSize j=layers[i].size; j--; ) {
832  Support& s = layers[i].support[j];
833  for (Degree d=s.n_edges; d--; ) {
834  s.edges[d].i_state = i_map[s.edges[d].i_state];
835  s.edges[d].o_state = o_map[s.edges[d].o_state];
836  }
837  }
838  }
839 
840  // Update out-states in edges for previous layer, if any
841  if (f > 0)
842  for (ValSize j=layers[f-1].size; j--; ) {
843  Support& s = layers[f-1].support[j];
844  for (Degree d=s.n_edges; d--; )
845  s.edges[d].o_state = i_map[s.edges[d].o_state];
846  }
847 
848  a_ch.reset();
849  }
850  audit();
851 
852  return new (home) LayeredGraph<View,Val,Degree,StateIdx>(home,share,*this);
853  }
854 
856  template<class Var>
858  post_lgp(Home home, const VarArgArray<Var>& x, const DFA& dfa) {
859  Gecode::Support::IntType t_state_idx =
860  Gecode::Support::u_type(static_cast<unsigned int>(dfa.n_states()));
861  Gecode::Support::IntType t_degree =
865  Support::s_type(dfa.symbol_max()));
866  switch (t_val) {
869  switch (t_state_idx) {
871  switch (t_degree) {
874  <typename VarTraits<Var>::View,short int,unsigned char,unsigned char>
875  ::post(home,x,dfa);
878  <typename VarTraits<Var>::View,short int,unsigned short int,unsigned char>
879  ::post(home,x,dfa);
882  <typename VarTraits<Var>::View,short int,unsigned int,unsigned char>
883  ::post(home,x,dfa);
884  default: GECODE_NEVER;
885  }
886  break;
888  switch (t_degree) {
891  <typename VarTraits<Var>::View,short int,unsigned char,unsigned short int>
892  ::post(home,x,dfa);
895  <typename VarTraits<Var>::View,short int,unsigned short int,unsigned short int>
896  ::post(home,x,dfa);
899  <typename VarTraits<Var>::View,short int,unsigned int,unsigned short int>
900  ::post(home,x,dfa);
901  default: GECODE_NEVER;
902  }
903  break;
905  switch (t_degree) {
908  <typename VarTraits<Var>::View,short int,unsigned char,unsigned int>
909  ::post(home,x,dfa);
912  <typename VarTraits<Var>::View,short int,unsigned short int,unsigned int>
913  ::post(home,x,dfa);
916  <typename VarTraits<Var>::View,short int,unsigned int,unsigned int>
917  ::post(home,x,dfa);
918  default: GECODE_NEVER;
919  }
920  break;
921  default: GECODE_NEVER;
922  }
923 
925  switch (t_state_idx) {
927  switch (t_degree) {
930  <typename VarTraits<Var>::View,int,unsigned char,unsigned char>
931  ::post(home,x,dfa);
934  <typename VarTraits<Var>::View,int,unsigned short int,unsigned char>
935  ::post(home,x,dfa);
938  <typename VarTraits<Var>::View,int,unsigned int,unsigned char>
939  ::post(home,x,dfa);
940  default: GECODE_NEVER;
941  }
942  break;
944  switch (t_degree) {
947  <typename VarTraits<Var>::View,int,unsigned char,unsigned short int>
948  ::post(home,x,dfa);
951  <typename VarTraits<Var>::View,int,unsigned short int,unsigned short int>
952  ::post(home,x,dfa);
955  <typename VarTraits<Var>::View,int,unsigned int,unsigned short int>
956  ::post(home,x,dfa);
957  default: GECODE_NEVER;
958  }
959  break;
961  switch (t_degree) {
964  <typename VarTraits<Var>::View,int,unsigned char,unsigned int>
965  ::post(home,x,dfa);
968  <typename VarTraits<Var>::View,int,unsigned short int,unsigned int>
969  ::post(home,x,dfa);
972  <typename VarTraits<Var>::View,int,unsigned int,unsigned int>
973  ::post(home,x,dfa);
974  default: GECODE_NEVER;
975  }
976  break;
977  default: GECODE_NEVER;
978  }
979 
980  default: GECODE_NEVER;
981  }
982  return ES_OK;
983  }
984 
985 }}}
986 
987 // STATISTICS: int-prop
988 
void audit(void)
Perform consistency check on data structures.
Degree o_deg
The out-degree (number of outgoing edges) Initialize with zeroes.
Definition: extensional.hh:75
Post propagator for SetVar x
Definition: set.hh:784
static T * copy(T *d, const T *s, long unsigned int n)
Copy n objects starting at s to d.
Definition: heap.hpp:587
void lshift(int n)
Shift index range by n elements to the left.
#define forceinline
Definition: config.hpp:173
Index(Space &home, Propagator &p, Council< Index > &c, int i)
Create index advisor.
Advisors for views (by position in array)
Definition: extensional.hh:123
size_t size
The size of the propagator (used during subsumption)
Definition: core.hpp:1105
@ IT_SHRT
short integer type
Definition: int-type.hpp:45
bool i_dec(int i, const Edge &e)
Decrement out degree for in state of edge e for layer i.
int val(void) const
Return supported value.
void max(Home home, FloatVar x0, FloatVar x1, FloatVar x2)
Post propagator for .
Definition: arithmetic.cpp:53
ExecStatus ES_NOFIX_DISPOSE(Council< A > &c, A &a)
Advisor a must be disposed and its propagator must be run
Definition: core.hpp:3938
ExecStatus ES_SUBSUMED(Propagator &p)
Definition: core.hpp:3614
virtual Actor * copy(Space &home, bool share)
Copy propagator during cloning.
Single _a(2, 3)
int fst(void) const
Return first position.
unsigned int size(I &i)
Size of all ranges of range iterator i.
Council< Index > c
The advisor council.
Definition: extensional.hh:156
static ExecStatus post(Home home, const VarArgArray< Var > &x, const DFA &dfa)
Post propagator on views x and DFA dfa.
virtual ExecStatus propagate(Space &home, const ModEventDelta &med)
Perform propagation.
Class to iterate over advisors of a council.
Definition: core.hpp:233
Gecode::IntArgs i(4, 1, 2, 3, 4)
NodeType t
Type of node.
Definition: bool-expr.cpp:234
Value iterator for integer views.
Definition: view.hpp:94
const FloatNum min
Smallest allowed float value.
Definition: float.hh:850
int final_fst(void) const
Return the number of the first final state.
Definition: dfa.hpp:129
ExecStatus post_lgp(Home home, const VarArgArray< Var > &x, const DFA &dfa)
Select small types for the layered graph propagator.
Computation spaces.
Definition: core.hpp:1748
static PropCost linear(PropCost::Mod m, unsigned int n)
Linear complexity for modifier pcm and size measure n.
Definition: core.hpp:4841
Edge * edges
Supporting edges in layered graph.
Definition: extensional.hh:90
Base-class for both propagators and branchers.
Definition: core.hpp:696
bool assigned(void) const
Test whether view is assigned.
Definition: var.hpp:123
State & i_state(int i, StateIdx is)
Return in state for layer i and state index is.
Layer * layers
The layers of the graph.
Definition: extensional.hh:160
int symbol_max(void) const
Return largest symbol in DFA.
Definition: dfa.hpp:148
void init(const Layer &l)
Initialize for support of layer l.
const Gecode::ModEvent ME_INT_VAL
Domain operation has resulted in a value (assigned variable)
Definition: var-type.hpp:56
Range approximation of which positions have changed.
Definition: extensional.hh:133
Boolean view for Boolean variables.
Definition: view.hpp:1315
Gecode toplevel namespace
Int::IntView View
The variable type of an IntView.
Support information for a value
Definition: extensional.hh:86
Base-class for propagators.
Definition: core.hpp:1092
Range iterator for integer views.
Definition: view.hpp:54
virtual ExecStatus advise(Space &home, Advisor &a, const Delta &d)
Give advice to propagator.
LayerValues(void)
Default constructor.
Val val
Supported value.
Definition: extensional.hh:88
Domain consistent layered graph (regular) propagator.
Definition: extensional.hh:69
int lst(void) const
Return last position.
IntType u_type(unsigned int n)
Return type required to represent n.
Definition: int-type.hpp:151
Generic domain change information to be supplied to advisors.
Definition: core.hpp:281
Home class for posting propagators
Definition: core.hpp:922
struct Gecode::@579::NNF::@61::@63 a
For atomic nodes.
Traits class for variables.
Handle to region.
Definition: region.hpp:61
int n
Number of layers (and views)
Definition: extensional.hh:158
Gecode::Support::IntTypeTraits< Val >::utype ValSize
Type for support size.
Definition: extensional.hh:93
Iterator for telling variable domains by scanning support.
Definition: extensional.hh:104
Post propagator for SetVar SetOpType SetVar SetRelType r
Definition: set.hh:784
Boolean integer variables.
Definition: int.hh:494
T * alloc(long unsigned int n)
Allocate block of n objects of type T from space heap.
Definition: core.hpp:2868
TFE post(PropagatorGroup g)
Only post functions (but not propagators) from g are considered.
void operator++(void)
Move to next supported value.
void reset(void)
Reset range to be empty.
IntRelType swap(IntRelType irt)
Return swapped relation type of irt.
Definition: irt.hpp:41
unsigned int n_states
Total number of states.
Definition: extensional.hh:164
StateIdx o_state
Number of out-state.
Definition: extensional.hh:83
Iterator for DFA transitions (sorted by symbols)
Definition: int.hh:2051
LayeredGraph(Space &home, bool share, LayeredGraph< View, Val, Degree, StateIdx > &p)
Constructor for cloning p.
Int::BoolView View
The variable type of an IntView.
Integer variables.
Definition: int.hh:353
unsigned int max_degree(void) const
Return maximal degree (in-degree and out-degree) of any state.
Definition: dfa.hpp:123
Degree i_deg
The in-degree (number of incoming edges)
Definition: extensional.hh:74
#define GECODE_NEVER
Assert that this command is never executed.
Definition: macros.hpp:60
virtual PropCost cost(const Space &home, const ModEventDelta &med) const
Cost function (defined as high linear)
int n_states(void) const
Return the number of states.
Definition: dfa.hpp:105
StateIdx i_state
Number of in-state.
Definition: extensional.hh:82
StateIdx max_states
Maximal number of states per layer.
Definition: extensional.hh:162
Propagation cost.
Definition: core.hpp:554
Deterministic finite automaton (DFA)
Definition: int.hh:2034
Traits to for information about integer types.
Definition: int-type.hpp:56
bool empty(void) const
Test whether range is empty.
States are described by number of incoming and outgoing edges.
Definition: extensional.hh:72
NNF * l
Left subtree.
Definition: bool-expr.cpp:244
Council of advisors
Definition: core.hpp:232
@ IT_CHAR
char integer type
Definition: int-type.hpp:44
int final_lst(void) const
Return the number of the last final state.
Definition: dfa.hpp:135
State * states
States used by outgoing edges.
Definition: extensional.hh:100
Gecode::IntSet d(v, 7)
Base-class for advisors.
Definition: core.hpp:1294
IntType
Description of integer types.
Definition: int-type.hpp:43
@ ES_FIX
Propagation has computed fixpoint.
Definition: core.hpp:545
Layer for a view in the layered graph
Definition: extensional.hh:95
Integer view for integer variables.
Definition: view.hpp:129
virtual void reschedule(Space &home)
Schedule function.
ExecStatus initialize(Space &home, const VarArgArray< Var > &x, const DFA &dfa)
Initialize layered graph.
IndexRange(void)
Initialize range as empty.
#define GECODE_ME_CHECK(me)
Check whether modification event me is failed, and forward failure.
Definition: macros.hpp:56
virtual size_t dispose(Space &home)
Delete actor and return its size.
Definition: core.hpp:3354
Degree n_edges
Number of supporting edges.
Definition: extensional.hh:89
void min(Home home, FloatVar x0, FloatVar x1, FloatVar x2)
Post propagator for .
Definition: arithmetic.cpp:71
@ HI
Expensive.
Definition: core.hpp:582
Post propagator for f(x \diamond_{\mathit{op}} y) \sim_r z \f$ void rel(Home home
Gecode::FloatVal c(-8, 8)
State & o_state(int i, StateIdx os)
Return out state for layer i and state index os.
IntType s_type(signed int n)
Return type required to represent n.
Edge defined by in-state and out-state
Definition: extensional.hh:80
int n
Number of negative literals for node type.
Definition: bool-expr.cpp:238
void init(void)
@ ES_FAILED
Execution has resulted in failure.
Definition: core.hpp:542
Argument array for variables.
Definition: array.hpp:53
int ModEventDelta
Modification event deltas.
Definition: core.hpp:169
@ ES_NOFIX
Propagation has not computed fixpoint.
Definition: core.hpp:543
bool o_dec(int i, const Edge &e)
Decrement in degree for out state of edge e for layer i.
const Gecode::ModEvent ME_INT_DOM
Domain operation has changed the domain.
Definition: var-type.hpp:72
@ ES_OK
Execution is okay.
Definition: core.hpp:544
int p
Number of positive literals for node type.
Definition: bool-expr.cpp:236
int symbol_min(void) const
Return smallest symbol in DFA.
Definition: dfa.hpp:141
bool operator()(void) const
Test whether more values supported.
const FloatNum max
Largest allowed float value.
Definition: float.hh:848
Iterator for DFA symbols.
Definition: int.hh:2074
void add(int i)
Add index i to range.
ExecStatus
Definition: core.hpp:540
virtual size_t dispose(Space &home)
Delete propagator and return its size.
@ IT_INT
integer type
Definition: int-type.hpp:46