this repo has no description
dekker.one
1/* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */
2/*
3 * Main authors:
4 * Denys Duchier <denys.duchier@univ-orleans.fr>
5 * Guido Tack <tack@gecode.org>
6 * Christian Schulte <schulte@gecode.org>
7 *
8 * Copyright:
9 * Denys Duchier, 2011
10 * Guido Tack, 2011
11 * Christian Schulte, 2004
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#ifndef GECODE_SET_CHANNEL_HH
39#define GECODE_SET_CHANNEL_HH
40
41#include <gecode/set.hh>
42
43namespace Gecode { namespace Set { namespace Channel {
44
45 /**
46 * \namespace Gecode::Set::Channel
47 * \brief Channeling propagators for set variables
48 */
49
50
51
52
53 /**
54 * \brief %Propagator for the sorted channel constraint
55 *
56 * Requires \code #include <gecode/set/int.hh> \endcode
57 * \ingroup FuncSetProp
58 */
59 template<class View>
60 class ChannelSorted : public Propagator {
61 protected:
62 /// SetView for the match
63 View x0;
64 /// IntViews that together form the set \a x0
65 ViewArray<Gecode::Int::IntView> xs;
66
67 /// Constructor for cloning \a p
68 ChannelSorted(Space& home, ChannelSorted& p);
69 /// Constructor for posting
70 ChannelSorted(Home home, View, ViewArray<Gecode::Int::IntView>&);
71 public:
72 /// Copy propagator during cloning
73 virtual Actor* copy(Space& home);
74 /// Cost function (defined as PC_LINEAR_LO)
75 virtual PropCost cost(const Space& home, const ModEventDelta& med) const;
76 /// Schedule function
77 virtual void reschedule(Space& home);
78 /// Delete Propagator
79 virtual size_t dispose(Space& home);
80 /// Perform propagation
81 virtual ExecStatus propagate(Space& home, const ModEventDelta& med);
82 /// Post propagator that propagates that \a s contains the \f$x_i\f$, which are sorted in non-descending order
83 static ExecStatus post(Home home, View s,
84 ViewArray<Gecode::Int::IntView>& x);
85 };
86
87 /**
88 * \brief %Propagator for channelling between variable-value-dual models
89 *
90 * Implements channelling constraints between IntVars and SetVars.
91 * For IntVars \f$x_0,\dots,x_n\f$ and SetVars \f$y_0,\dots,y_m\f$ it
92 * propagates the constraint \f$x_i=j \Leftrightarrow i\in y_j\f$.
93 *
94 * Can be used to implement the "channelling constraints" for disjoint with
95 * cardinalities from
96 * "Disjoint, Partition and Intersection Constraints for
97 * Set and Multiset Variables"
98 * Christian Bessiere, Emmanuel Hebrard, Brahim Hnich, Toby Walsh
99 * CP 2004
100 *
101 * Requires \code #include <gecode/set/int.hh> \endcode
102 * \ingroup FuncSetProp
103 */
104 template<class View>
105 class ChannelInt : public Propagator {
106 protected:
107 /// IntViews, \f$x_i\f$ reflects which set contains element \f$i\f$
108 ViewArray<Gecode::Int::CachedView<Gecode::Int::IntView> > xs;
109 /// SetViews that are constrained to be disjoint
110 ViewArray<CachedView<View> > ys;
111
112 /// Constructor for cloning \a p
113 ChannelInt(Space& home, ChannelInt& p);
114 /// Constructor for posting
115 ChannelInt(Home home,
116 ViewArray<Gecode::Int::CachedView<Gecode::Int::IntView> >&,
117 ViewArray<CachedView<View> >&);
118 public:
119 /// Copy propagator during cloning
120 virtual Actor* copy(Space& home);
121 /// Cost function (defined as PC_QUADRATIC_LO)
122 virtual PropCost cost(const Space& home, const ModEventDelta& med) const;
123 /// Schedule function
124 virtual void reschedule(Space& home);
125 /// Delete propagator and return its size
126 virtual size_t dispose(Space& home);
127 /// Perform propagation
128 virtual ExecStatus propagate(Space& home, const ModEventDelta& med);
129 /// Post propagator for \f$x_i=j \Leftrightarrow i\in y_j\f$
130 static ExecStatus post(Home home,
131 ViewArray<Gecode::Int::CachedView<
132 Gecode::Int::IntView> >& x,
133 ViewArray<CachedView<View> >& y);
134 };
135
136 /**
137 * \brief %Propagator for channelling between set variable and its
138 * characteristic function
139 *
140 * Implements channelling constraints between BoolVar and a SetVar.
141 * For BoolVars \f$x_0,\dots,x_n\f$ and SetVar \f$y\f$ it
142 * propagates the constraint \f$x_i=1 \Leftrightarrow i\in y\f$.
143 *
144 * Requires \code #include <gecode/set/int.hh> \endcode
145 * \ingroup FuncSetProp
146 */
147 template<class View>
148 class ChannelBool
149 : public MixNaryOnePropagator<Gecode::Int::BoolView,
150 Gecode::Int::PC_BOOL_VAL,
151 View,PC_GEN_NONE> {
152 protected:
153 typedef MixNaryOnePropagator<Gecode::Int::BoolView,
154 Gecode::Int::PC_BOOL_VAL,
155 View,PC_GEN_NONE> Super;
156 using Super::x;
157 using Super::y;
158
159 /// Constructor for cloning \a p
160 ChannelBool(Space& home, ChannelBool& p);
161 /// Constructor for posting
162 ChannelBool(Home home,ViewArray<Gecode::Int::BoolView>&,
163 View);
164
165 /// %Advisor storing a single index
166 class IndexAdvisor : public Advisor {
167 protected:
168 /// The single index
169 int idx;
170 public:
171 /// Constructor for creation
172 template<class A>
173 IndexAdvisor(Space& home, ChannelBool<View>& p, Council<A>& c,
174 int index);
175 /// Constructor for cloning \a a
176 IndexAdvisor(Space& home, IndexAdvisor& a);
177 /// Access index
178 int index(void) const;
179 /// Delete advisor
180 template<class A>
181 void dispose(Space& home, Council<A>& c);
182 };
183
184 /// Council for managing advisors
185 Council<IndexAdvisor> co;
186 /// Accumulated delta information
187 SetDelta delta;
188 /// Accumulated zero Booleans
189 GLBndSet zeros;
190 /// Accumulated one Booleans
191 GLBndSet ones;
192 /// Flag whether propagation is currently running
193 bool running;
194 public:
195 /// Copy propagator during cloning
196 virtual Actor* copy(Space& home);
197 /// Cost function (defined as PC_QUADRATIC_LO)
198 virtual PropCost cost(const Space& home, const ModEventDelta& med) const;
199 /// Schedule function
200 virtual void reschedule(Space& home);
201 /// Delete propagator and return its size
202 virtual size_t dispose(Space& home);
203 /// Perform propagation
204 virtual ExecStatus propagate(Space& home, const ModEventDelta& med);
205 /// Give advice to propagator
206 virtual ExecStatus advise(Space& home, Advisor& a, const Delta& d);
207 /// Post propagator for \f$x_i=j \Leftrightarrow i\in y_j\f$
208 static ExecStatus post(Home home,ViewArray<Gecode::Int::BoolView>& x,
209 View y);
210 };
211
212 /**
213 * \brief %Propagator for successors/predecessors channelling
214 *
215 * Implements channelling constraints between 2 sequences of SetVars.
216 * For SetVars \f$x_0,\dots,x_n\f$ and SetVars \f$y_0,\dots,y_m\f$ it
217 * propagates the constraint \f$j\in x_i \Leftrightarrow i\in y_i\f$.
218 * \f$x_i\f$ is the set of successors of \f$i\f$, and \f$y_j\f$ is the
219 * set of predecessors of \f$j\f$.
220 *
221 * Requires \code #include <gecode/set/int.hh> \endcode
222 * \ingroup FuncSetProp
223 */
224
225 template<typename View>
226 class ChannelSet: public Propagator {
227 protected:
228 /// SetViews, \f$x_i\f$ reflects the successors of \f$i\f$
229 ViewArray<CachedView<View> > xs;
230 /// SetViews, \f$y_j\f$ reflects the predecessors of \f$j\f$
231 ViewArray<CachedView<View> > ys;
232
233 /// Constructor for cloning \a p
234 ChannelSet(Space& home, ChannelSet& p);
235 /// Constructor for posting
236 ChannelSet(Home home,
237 ViewArray<CachedView<View> >&,
238 ViewArray<CachedView<View> >&);
239 public:
240 /// Copy propagator during cloning
241 virtual Actor* copy(Space& home);
242 /// Cost function (defined as PC_QUADRATIC_HI)
243 virtual PropCost cost(const Space& home, const ModEventDelta& med) const;
244 /// Schedule function
245 virtual void reschedule(Space& home);
246 /// Delete propagator and return its size
247 virtual size_t dispose(Space& home);
248 /// Perform propagation
249 virtual ExecStatus propagate(Space& home, const ModEventDelta& med);
250 /// Post propagator for \f$j\in x_i \Leftrightarrow i\in y_j\f$
251 static ExecStatus post(Home home,
252 ViewArray<CachedView<View> >& x,
253 ViewArray<CachedView<View> >& y);
254 };
255
256}}}
257
258#include <gecode/set/channel/sorted.hpp>
259#include <gecode/set/channel/int.hpp>
260#include <gecode/set/channel/bool.hpp>
261#include <gecode/set/channel/set.hpp>
262
263#endif
264
265// STATISTICS: set-prop