Generated on Tue Mar 24 2020 14:04:04 for Gecode by doxygen 1.8.17
gcc.hh
Go to the documentation of this file.
1 /* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */
2 /*
3  * Main authors:
4  * Patrick Pekczynski <pekczynski@ps.uni-sb.de>
5  *
6  * Contributing authors:
7  * Christian Schulte <schulte@gecode.org>
8  * Guido Tack <tack@gecode.org>
9  *
10  * Copyright:
11  * Patrick Pekczynski, 2004/2005
12  * Christian Schulte, 2009
13  * Guido Tack, 2009
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_GCC_HH__
41 #define __GECODE_INT_GCC_HH__
42 
43 #include <gecode/int.hh>
44 
50 #include <gecode/int/gcc/view.hpp>
53 
54 namespace Gecode { namespace Int { namespace GCC {
55 
62  template<class Card>
63  class Val : public Propagator {
64  protected:
72  Val(Space& home, Val<Card>& p);
73  public:
75  virtual Actor* copy(Space& home);
77  virtual PropCost cost(const Space& home, const ModEventDelta& med) const;
79  virtual void reschedule(Space& home);
81  virtual ExecStatus propagate(Space& home, const ModEventDelta& med);
83  virtual size_t dispose(Space& home);
85  static ExecStatus post(Home home,
87  };
88 
112  template<class Card>
113  class Bnd : public Propagator {
114  protected:
141  bool skip_lbc;
143  Bnd(Space& home, Bnd<Card>& p);
144 
146  ExecStatus pruneCards(Space& home);
147 
166  ExecStatus lbc(Space& home, int& nb, HallInfo hall[], Rank rank[],
167  int mu[], int nu[]);
168 
187  ExecStatus ubc(Space& home, int& nb, HallInfo hall[], Rank rank[],
188  int mu[], int nu[]);
190  Bnd(Home home, ViewArray<IntView>&, ViewArray<Card>&, bool, bool);
191  public:
193  virtual Actor* copy(Space& home);
195  virtual PropCost cost(const Space& home, const ModEventDelta& med) const;
197  virtual void reschedule(Space& home);
199  virtual ExecStatus propagate(Space& home, const ModEventDelta& med);
201  virtual size_t dispose(Space& home);
203  static ExecStatus post(Home home,
205  };
206 
218  template<class Card>
219  class Dom : public Propagator {
220  protected:
240  Dom(Space& home, Dom<Card>& p);
242  Dom(Home home, ViewArray<IntView>&, ViewArray<Card>&, bool);
243  public:
245  virtual Actor* copy(Space& home);
247  virtual PropCost cost(const Space& home, const ModEventDelta& med) const;
249  virtual void reschedule(Space& home);
251  virtual ExecStatus propagate(Space& home, const ModEventDelta& med);
253  virtual size_t dispose(Space& home);
255  static ExecStatus post(Home home,
257  };
258 
259 }}}
260 
261 #include <gecode/int/gcc/post.hpp>
262 #include <gecode/int/gcc/val.hpp>
263 #include <gecode/int/gcc/bnd.hpp>
264 #include <gecode/int/gcc/dom.hpp>
265 
266 #endif
267 
268 
269 // STATISTICS: int-prop
270 
ViewArray< IntView > x
Views on which to perform value-propagation.
Definition: gcc.hh:66
PartialSum< Card > ups
Data structure storing the sum of the views upper bounds.
Definition: gcc.hh:128
ViewArray< IntView > y
Views used to channel information between x and k ( ).
Definition: gcc.hh:227
Domain consistent global cardinality propagator.
Definition: gcc.hh:219
virtual size_t dispose(Space &home)
Destructor.
Definition: val.hpp:60
Value consistent global cardinality propagator.
Definition: gcc.hh:63
virtual void reschedule(Space &home)
Schedule function.
Definition: dom.hpp:109
virtual size_t dispose(Space &home)
Destructor.
Definition: bnd.hpp:66
virtual PropCost cost(const Space &home, const ModEventDelta &med) const
Cost funtion returning high linear.
Definition: val.hpp:75
bool card_fixed
Stores whether cardinalities are all assigned.
Definition: gcc.hh:238
virtual ExecStatus propagate(Space &home, const ModEventDelta &med)
Perform propagation.
Definition: dom.hpp:116
bool card_fixed
Stores whether cardinalities are all assigned.
Definition: gcc.hh:135
virtual ExecStatus propagate(Space &home, const ModEventDelta &med)
Perform propagation.
Definition: bnd.hpp:596
Computation spaces.
Definition: core.hpp:1742
ExecStatus ubc(Space &home, int &nb, HallInfo hall[], Rank rank[], int mu[], int nu[])
Upper Bounds constraint (UBC) stating Hence the ubc constraints the variables such that no value occ...
Definition: bnd.hpp:404
Base-class for both propagators and branchers.
Definition: core.hpp:628
virtual PropCost cost(const Space &home, const ModEventDelta &med) const
Cost funtion.
Definition: bnd.hpp:81
Val(Home home, ViewArray< IntView > &x, ViewArray< Card > &k)
Constructor for posting.
Definition: val.hpp:43
ViewArray< IntView > y
Views on which to perform value-propagation (subset of x)
Definition: gcc.hh:118
Gecode toplevel namespace
Base-class for propagators.
Definition: core.hpp:1064
static ExecStatus post(Home home, ViewArray< IntView > &x, ViewArray< Card > &k)
Post propagator for views x and cardinalities k.
Definition: val.hpp:287
virtual ExecStatus propagate(Space &home, const ModEventDelta &med)
Perform propagation.
Definition: val.hpp:281
static ExecStatus post(Home home, ViewArray< IntView > &x, ViewArray< Card > &k)
Post propagator for views x and cardinalities k.
Definition: dom.hpp:299
Home class for posting propagators
Definition: core.hpp:856
Variable-value-graph used during propagation.
Definition: dom-sup.hpp:387
virtual void reschedule(Space &home)
Schedule function.
Definition: bnd.hpp:93
ModEventDelta med
A set of modification events (used during propagation)
Definition: core.hpp:1075
virtual size_t dispose(Space &home)
Destructor.
Definition: dom.hpp:88
Maps domain bounds to their position in hall[].bounds.
Definition: bnd-sup.hpp:154
virtual void reschedule(Space &home)
Schedule function.
Definition: val.hpp:85
Dom(Space &home, Dom< Card > &p)
Constructor for cloning p.
Definition: dom.hpp:79
ExecStatus lbc(Space &home, int &nb, HallInfo hall[], Rank rank[], int mu[], int nu[])
Lower Bounds constraint (LBC) stating Hence the lbc constraints the variables such that every value ...
Definition: bnd.hpp:100
Bnd(Space &home, Bnd< Card > &p)
Constructor for cloning p.
Definition: bnd.hpp:56
ViewArray< IntView > x
Views on which to perform domain-propagation.
Definition: gcc.hh:222
Propagation cost.
Definition: core.hpp:486
ExecStatus pruneCards(Space &home)
Prune cardinality variables with 0 maximum occurrence.
Definition: bnd.hpp:562
Container class provding information about the Hall structure of the problem variables.
Definition: bnd-sup.hpp:456
ViewArray< Card > k
Array containing either fixed cardinalities or CardViews.
Definition: gcc.hh:229
ViewArray< Card > k
Array containing either fixed cardinalities or CardViews.
Definition: gcc.hh:120
PartialSum< Card > lps
Data structure storing the sum of the views lower bounds Necessary for reasoning about the interval c...
Definition: gcc.hh:126
ViewArray< IntView > x
Views on which to perform bounds-propagation.
Definition: gcc.hh:116
VarValGraph< Card > * vvg
Propagation is performed on a variable-value graph (used as cache)
Definition: gcc.hh:231
bool skip_lbc
Stores whether the minium required occurences of the cardinalities are all zero. If so,...
Definition: gcc.hh:141
virtual Actor * copy(Space &home)
Copy propagator during cloning.
Definition: bnd.hpp:75
Partial sum structure for constant time computation of the maximal capacity of an interval.
Definition: bnd-sup.hpp:237
virtual Actor * copy(Space &home)
Copy propagator during cloning.
Definition: dom.hpp:97
Bounds consistent global cardinality propagator.
Definition: gcc.hh:113
ViewArray< Card > k
Array containing either fixed cardinalities or CardViews.
Definition: gcc.hh:68
static ExecStatus post(Home home, ViewArray< IntView > &x, ViewArray< Card > &k)
Post propagator for views x and cardinalities k.
Definition: bnd.hpp:808
int ModEventDelta
Modification event deltas.
Definition: core.hpp:89
int p
Number of positive literals for node type.
Definition: bool-expr.cpp:232
virtual PropCost cost(const Space &home, const ModEventDelta &med) const
Cost function.
Definition: dom.hpp:103
virtual Actor * copy(Space &home)
Copy propagator during cloning.
Definition: val.hpp:69
ExecStatus
Definition: core.hpp:472