Generated on Sat Jul 29 2017 12:41:24 for Gecode by doxygen 1.8.13
extensional.hh
Go to the documentation of this file.
1 /* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */
2 /*
3  * Main authors:
4  * Mikael Lagerkvist <lagerkvist@gecode.org>
5  * Christian Schulte <schulte@gecode.org>
6  *
7  * Copyright:
8  * Mikael Lagerkvist, 2007
9  * Christian Schulte, 2004
10  *
11  * Last modified:
12  * $Date: 2016-06-29 17:28:17 +0200 (Wed, 29 Jun 2016) $ by $Author: schulte $
13  * $Revision: 15137 $
14  *
15  * This file is part of Gecode, the generic constraint
16  * development environment:
17  * http://www.gecode.org
18  *
19  * Permission is hereby granted, free of charge, to any person obtaining
20  * a copy of this software and associated documentation files (the
21  * "Software"), to deal in the Software without restriction, including
22  * without limitation the rights to use, copy, modify, merge, publish,
23  * distribute, sublicense, and/or sell copies of the Software, and to
24  * permit persons to whom the Software is furnished to do so, subject to
25  * the following conditions:
26  *
27  * The above copyright notice and this permission notice shall be
28  * included in all copies or substantial portions of the Software.
29  *
30  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
31  * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
32  * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
33  * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
34  * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
35  * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
36  * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
37  *
38  */
39 
40 #ifndef __GECODE_INT_EXTENSIONAL_HH__
41 #define __GECODE_INT_EXTENSIONAL_HH__
42 
43 #include <gecode/int.hh>
44 
45 #include <gecode/int/rel.hh>
46 
52 namespace Gecode { namespace Int { namespace Extensional {
53 
68  template<class View, class Val, class Degree, class StateIdx>
69  class LayeredGraph : public Propagator {
70  protected:
72  class State {
73  public:
74  Degree i_deg;
75  Degree o_deg;
76  void init(void);
78  };
80  class Edge {
81  public:
82  StateIdx i_state;
83  StateIdx o_state;
84  };
86  class Support {
87  public:
88  Val val;
89  Degree n_edges;
91  };
95  class Layer {
96  public:
97  View x;
98  StateIdx n_states;
99  ValSize size;
102  };
104  class LayerValues {
105  private:
106  const Support* s1;
107  const Support* s2;
108  public:
110  LayerValues(void);
112  LayerValues(const Layer& l);
114  void init(const Layer& l);
116  bool operator ()(void) const;
118  void operator ++(void);
120  int val(void) const;
121  };
123  class Index : public Advisor {
124  public:
126  int i;
128  Index(Space& home, Propagator& p, Council<Index>& c, int i);
130  Index(Space& home, bool share, Index& a);
131  };
133  class IndexRange {
134  private:
135  int _fst;
136  int _lst;
137  public:
139  IndexRange(void);
141  void reset(void);
143  void add(int i);
145  void add(const IndexRange& ir);
147  void lshift(int n);
149  bool empty(void) const;
151  int fst(void) const;
153  int lst(void) const;
154  };
158  int n;
162  StateIdx max_states;
164  unsigned int n_states;
166  unsigned int n_edges;
174  State& i_state(int i, StateIdx is);
176  State& i_state(int i, const Edge& e);
178  bool i_dec(int i, const Edge& e);
180  State& o_state(int i, StateIdx os);
182  State& o_state(int i, const Edge& e);
184  bool o_dec(int i, const Edge& e);
186  void audit(void);
188  template<class Var>
190  const VarArgArray<Var>& x, const DFA& dfa);
192  LayeredGraph(Space& home, bool share,
194  public:
196  template<class Var>
197  LayeredGraph(Home home,
198  const VarArgArray<Var>& x, const DFA& dfa);
200  virtual Actor* copy(Space& home, bool share);
202  virtual PropCost cost(const Space& home, const ModEventDelta& med) const;
204  virtual void reschedule(Space& home);
206  virtual ExecStatus advise(Space& home, Advisor& a, const Delta& d);
208  virtual ExecStatus propagate(Space& home, const ModEventDelta& med);
210  virtual size_t dispose(Space& home);
212  template<class Var>
213  static ExecStatus post(Home home,
214  const VarArgArray<Var>& x, const DFA& dfa);
215  };
216 
218  template<class Var>
219  ExecStatus post_lgp(Home home,
220  const VarArgArray<Var>& x, const DFA& dfa);
221 
222 }}}
223 
225 
226 
227 namespace Gecode { namespace Int { namespace Extensional {
228 
232 
243  template<class View, bool subscribe = true>
244  class Base : public Propagator {
245  protected:
248  Tuple** last_data;
249  TupleSet::TupleSetI* ts(void);
251 
253  Base(Space& home, bool share, Base<View,subscribe>& p);
255  Base(Home home, ViewArray<View>& x, const TupleSet& t);
257  void init_last(Space& home, Tuple** source, Tuple* base);
259  Tuple last(int i, int n);
261  Tuple last_next(int i, int n);
263  void init_dom(Space& home, Domain dom);
265  bool valid(Tuple t, Domain dom);
267  Tuple find_support(Domain dom, int i, int n);
268  public:
270  virtual PropCost cost(const Space& home, const ModEventDelta& med) const;
272  virtual void reschedule(Space& home);
274  virtual size_t dispose(Space& home);
275  };
276 
277 }}}
278 
280 
281 
282 namespace Gecode { namespace Int { namespace Extensional {
283 
296  template<class View, bool shared>
297  class Basic : public Base<View> {
298  protected:
299  using Base<View>::x;
300  using Base<View>::tupleSet;
301  using Base<View>::ts;
302  using Base<View>::last;
303  using Base<View>::last_next;
304  using Base<View>::init_last;
305  using Base<View>::init_dom;
307 
309  Basic(Space& home, bool share, Basic<View,shared>& p);
311  Basic(Home home, ViewArray<View>& x, const TupleSet& t);
312 
313  public:
315  virtual ExecStatus propagate(Space& home, const ModEventDelta& med);
322  virtual PropCost cost(const Space& home, const ModEventDelta& med) const;
324  virtual Actor* copy(Space& home, bool share);
326  static ExecStatus post(Home home, ViewArray<View>& x, const TupleSet& t);
327  };
328 
329 }}}
330 
332 
333 
334 namespace Gecode { namespace Int { namespace Extensional {
344  template<class View>
345  class Incremental : public Base<View, false> {
346  protected:
347  using Base<View, false>::x;
349  using Base<View, false>::ts;
355  class SupportEntry : public FreeList {
356  public:
359 
361 
362  SupportEntry* next(void) const;
365  SupportEntry** nextRef(void);
367 
369 
370  SupportEntry(Tuple t);
375 
377 
378  void dispose(Space& home, SupportEntry* l);
381  void dispose(Space& home);
382 
384  static void* operator new(size_t s, Space& home);
386  static void operator delete(void* p);
388  static void operator delete(void* p, Space& home);
390  };
392  class WorkEntry : public FreeList {
393  public:
395  int i;
397  int n;
398 
400 
401  WorkEntry(int i, int n, WorkEntry* ne);
404 
406 
407  WorkEntry* next(void) const;
410  void next(WorkEntry* n);
412 
414 
415  void dispose(Space& home);
417 
419  static void* operator new(size_t s, Space& home);
421  static void operator delete(void* p);
423  static void operator delete(void* p, Space& home);
425  };
427  class Work {
428  private:
430  WorkEntry* we;
431  public:
433  Work(void);
435  bool empty(void) const;
437  void push(Space& home, int i, int n);
439  void pop(Space& home, int& i, int& n);
440  };
445 
450 
452  Incremental(Space& home, bool share, Incremental<View>& p);
454  Incremental(Home home, ViewArray<View>& x, const TupleSet& t);
456  void init_support(Space& home);
458  void find_support(Space& home, Domain dom, int i, int n);
460  void add_support(Space& home, Tuple l);
462  void remove_support(Space& home, Tuple l, int i, int n);
464  SupportEntry* support(int i, int n);
465  public:
472  virtual PropCost cost(const Space& home, const ModEventDelta& med) const;
474  virtual void reschedule(Space& home);
476  virtual ExecStatus propagate(Space& home, const ModEventDelta& med);
478  virtual Actor* copy(Space& home, bool share);
480  static ExecStatus post(Home home, ViewArray<View>& x, const TupleSet& t);
482  size_t dispose(Space& home);
483  private:
485  class SupportAdvisor : public Advisor {
486  public:
488  int i;
490  SupportAdvisor(Space& home, Propagator& p, Council<SupportAdvisor>& c,
491  int i);
493  SupportAdvisor(Space& home, bool share, SupportAdvisor& a);
495  void dispose(Space& home, Council<SupportAdvisor>& c);
496  };
499  public:
501  virtual ExecStatus advise(Space& home, Advisor& a, const Delta& d);
502  };
503 
504 }}}
505 
507 
508 
509 #endif
510 
511 // STATISTICS: int-prop
512 
IndexRange i_ch
Index range with in-degree modifications.
Definition: extensional.hh:168
Council of advisors
Definition: core.hpp:232
TupleSet tupleSet
Definition of constraint.
Definition: extensional.hh:247
NodeType t
Type of node.
Definition: bool-expr.cpp:234
Work w_remove
Work for removing values.
Definition: extensional.hh:444
Description of work to be done.
Definition: extensional.hh:392
NNF * l
Left subtree.
Definition: bool-expr.cpp:244
bool valid(const FloatVal &n)
Return whether float n is a valid number.
Definition: limits.hpp:43
void audit(void)
Perform consistency check on data structures.
Edge defined by in-state and out-state
Definition: extensional.hh:80
Council< Index > c
The advisor council.
Definition: extensional.hh:156
int n
Number of layers (and views)
Definition: extensional.hh:158
Iterator for telling variable domains by scanning support.
Definition: extensional.hh:104
IndexRange a_ch
Index range for any change (for compression)
Definition: extensional.hh:172
StateIdx n_states
Number of states used by outgoing edges.
Definition: extensional.hh:98
unsigned int n_states
Total number of states.
Definition: extensional.hh:164
Basic bitset support.
int * Tuple
Type of a tuple.
Definition: int.hh:2167
void dom(Home home, FloatVar x, FloatVal n)
Propagates .
Definition: dom.cpp:44
StateIdx i_state
Number of in-state.
Definition: extensional.hh:82
Base-class for propagators.
Definition: core.hpp:1092
Base-class for advisors.
Definition: core.hpp:1294
Computation spaces.
Definition: core.hpp:1748
Support information for a value
Definition: extensional.hh:86
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:170
Base-class for both propagators and branchers.
Definition: core.hpp:696
Gecode::IntSet d(v, 7)
SupportEntry ** support_data
Support information.
Definition: extensional.hh:447
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:99
struct Gecode::@579::NNF::@61::@63 a
For atomic nodes.
StateIdx o_state
Number of out-state.
Definition: extensional.hh:83
Deterministic finite automaton (DFA)
Definition: int.hh:2034
int p
Number of positive literals for node type.
Definition: bool-expr.cpp:236
Gecode::IntArgs i(4, 1, 2, 3, 4)
TupleSet::Tuple Tuple
Definition: extensional.hh:229
Domain consistent extensional propagator.
Definition: extensional.hh:297
Range approximation of which positions have changed.
Definition: extensional.hh:133
ViewArray< View > x
Variables.
Definition: extensional.hh:246
Tuple ** last_data
Last tuple looked at Access real tuple-set.
Definition: extensional.hh:248
ModEventDelta med
A set of modification events (used during propagation)
Definition: core.hpp:1103
Layer for a view in the layered graph
Definition: extensional.hh:95
Support::BitSetBase * Domain
Definition: extensional.hh:231
Degree n_edges
Number of supporting edges.
Definition: extensional.hh:89
LayeredGraph(Space &home, bool share, LayeredGraph< View, Val, Degree, StateIdx > &p)
Constructor for cloning p.
Layer * layers
The layers of the graph.
Definition: extensional.hh:160
int i
Position of view in view array.
Definition: extensional.hh:395
StateIdx max_states
Maximal number of states per layer.
Definition: extensional.hh:162
Data stored for a Table.
Definition: int.hh:2173
ExecStatus post_lgp(Home home, const VarArgArray< Var > &x, const DFA &dfa)
Select small types for the layered graph propagator.
View arrays.
Definition: array.hpp:234
Traits to for information about integer types.
Definition: int-type.hpp:56
int unassigned
Number of unassigned views.
Definition: extensional.hh:449
Degree o_deg
The out-degree (number of outgoing edges) Initialize with zeroes.
Definition: extensional.hh:75
State * states
States used by outgoing edges.
Definition: extensional.hh:100
Domain consistent layered graph (regular) propagator.
Definition: extensional.hh:69
Class represeting a set of tuples.
Definition: int.hh:2161
Work w_support
Work for finding support.
Definition: extensional.hh:442
const double base
Base for geometric restart sequence.
Definition: search.hh:122
Domain consistent extensional propagator.
Definition: extensional.hh:345
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:281
Advisors for views (by position in array)
Definition: extensional.hh:123
Propagation cost.
Definition: core.hpp:554
ExecStatus
Definition: core.hpp:540
virtual ExecStatus propagate(Space &home, const ModEventDelta &med)
Perform propagation.
Support::BitSetBase BitSet
Definition: extensional.hh:230
Base-class for freelist-managed objects.
Post propagator for SetVar x
Definition: set.hh:784
Base for domain consistent extensional propagation
Definition: extensional.hh:244
Edge * edges
Supporting edges in layered graph.
Definition: extensional.hh:90
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
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:72
Degree i_deg
The in-degree (number of incoming edges)
Definition: extensional.hh:74
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.
int ModEventDelta
Modification event deltas.
Definition: core.hpp:169
Home class for posting propagators
Definition: core.hpp:922
unsigned int n_edges
Total number of edges.
Definition: extensional.hh:166
virtual Actor * copy(Space &home, bool share)
Copy propagator during cloning.
Gecode::Support::IntTypeTraits< Val >::utype ValSize
Type for support size.
Definition: extensional.hh:93
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:126