Generated on Thu Jan 16 2025 00:00:00 for Gecode by doxygen 1.14.0
int-base.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, 2011
8 *
9 * This file is part of Gecode, the generic constraint
10 * development environment:
11 * http://www.gecode.org
12 *
13 * Permission is hereby granted, free of charge, to any person obtaining
14 * a copy of this software and associated documentation files (the
15 * "Software"), to deal in the Software without restriction, including
16 * without limitation the rights to use, copy, modify, merge, publish,
17 * distribute, sublicense, and/or sell copies of the Software, and to
18 * permit persons to whom the Software is furnished to do so, subject to
19 * the following conditions:
20 *
21 * The above copyright notice and this permission notice shall be
22 * included in all copies or substantial portions of the Software.
23 *
24 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
25 * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
26 * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
27 * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
28 * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
29 * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
30 * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
31 *
32 */
33
35
36namespace Gecode { namespace Int { namespace NValues {
37
38 template<class VY>
43
44 template<class VY>
48 vs.update(home, p.vs);
49 }
50
51 template<class VY>
52 forceinline size_t
54 vs.dispose(home);
56 ::dispose(home);
57 return sizeof(*this);
58 }
59
60 template<class VY>
62 IntBase<VY>::cost(const Space&, const ModEventDelta&) const {
63 return PropCost::quadratic(PropCost::HI, x.size());
64 }
65
66 template<class VY>
67 void
69 int n=x.size();
70 for (int i=n; i--; )
71 if (x[i].assigned()) {
72 vs.add(home, x[i].val());
73 x[i] = x[--n];
74 }
75 x.size(n);
76 }
77
78 template<class VY>
79 void
80 IntBase<VY>::disjoint(Space& home, Region& r, int*& dis, int& n_dis) {
81 // Compute positions of disjoint views
82 int n=x.size();
83 dis = r.alloc<int>(n); n_dis = 0;
84
85 int i=0;
86 while (i < n)
87 switch (vs.compare(x[i])) {
89 // All values are already contained in vs, eliminate x[i]
90 x[i].cancel(home, *this, PC_INT_DOM);
91 x[i] = x[--n];
92 break;
94 dis[n_dis++] = i++;
95 break;
97 i++;
98 break;
99 default:
101 }
102 x.size(n);
103 }
104
105 template<class VY>
106 void
108 int n=x.size();
109 for (int i=n; i--; )
110 if (vs.subset(x[i])) {
111 // All values are already contained in vs, eliminate x[i]
112 x[i].cancel(home, *this, PC_INT_DOM);
113 x[i] = x[--n];
114 }
115 x.size(n);
116 }
117
118 template<class VY>
121 for (int i=x.size(); i--; ) {
122 ValSet::Ranges vsr(vs);
123 GECODE_ME_CHECK(x[i].inter_r(home, vsr, false));
124 }
125 return home.ES_SUBSUMED(*this);
126 }
127
128 template<class VY>
130 IntBase<VY>::prune_lower(Space& home, int* dis, int n_dis) {
131 assert(n_dis > 0);
132
133 // At least one more value will be needed
134 GECODE_ME_CHECK(y.gq(home,vs.size() + 1));
135
136 Region r;
137
138 // Only one additional value is allowed
139 if (y.max() == vs.size() + 1) {
140 // Compute possible values
141 ViewRanges<IntView>* r_dis = r.alloc<ViewRanges<IntView> >(n_dis);
142 for (int i=n_dis; i--; )
143 r_dis[i] = ViewRanges<IntView>(x[dis[i]]);
144 Iter::Ranges::NaryInter iv(r, r_dis, n_dis);
145 // Is there a common value at all?
146 if (!iv())
147 return ES_FAILED;
148 ValSet::Ranges vsr(vs);
149 Iter::Ranges::NaryUnion pv(r,iv,vsr);
150 // Enforce common values
151 for (int i=x.size(); i--; ) {
152 pv.reset();
153 GECODE_ME_CHECK(x[i].inter_r(home, pv, false));
154 }
155 return ES_OK;
156 }
157
158 // Compute independent set for lower bound
159 // ovl is a bit-matrix defining whether two views overlap
160 SymBitMatrix ovl(r,x.size());
161 // deg[i] is the degree of x[i]
162 int* deg = r.alloc<int>(x.size());
163 // ovl_i[i] is an array of indices j such that x[j] overlaps with x[i]
164 int** ovl_i = r.alloc<int*>(x.size());
165 // n_ovl_i[i] defines how many integers are stored for ovl_i[i]
166 int* n_ovl_i = r.alloc<int>(x.size());
167 {
168#ifndef NDEBUG
169 // Initialize all to null pointers so that things crash ;-)
170 for (int i=x.size(); i--; )
171 ovl_i[i] = NULL;
172#endif
173 // For each i there can be at most n_dis-1 entries in ovl_i[i]
174 int* m = r.alloc<int>(n_dis*(n_dis-1));
175 for (int i=n_dis; i--; ) {
176 deg[dis[i]] = 0;
177 ovl_i[dis[i]] = m; m += n_dis-1;
178 }
179 }
180
181 // Initialize overlap matrix by analyzing the view ranges
182 {
183 // Compute how many events are needed
184 // One event for the end marker
185 int n_re = 1;
186 // Two events for each range
187 for (int i=n_dis; i--; )
188 for (ViewRanges<IntView> rx(x[dis[i]]); rx(); ++rx)
189 n_re += 2;
190
191 // Allocate and initialize events
192 RangeEvent* re = r.alloc<RangeEvent>(n_re);
193 {
194 int j=0;
195 for (int i=n_dis; i--; )
196 for (ViewRanges<IntView> rx(x[dis[i]]); rx(); ++rx) {
197 // Event when a range starts
198 re[j].ret=RET_FST; re[j].val=rx.min(); re[j].view=dis[i]; j++;
199 // Event when a range ends
200 re[j].ret=RET_LST; re[j].val=rx.max(); re[j].view=dis[i]; j++;
201 }
202 // Make this the last event
204 assert(j+1 == n_re);
205 }
206 // Sort and process events
207 Support::quicksort(re,n_re);
208
209 // Current views with a range being active
210 Support::BitSet<Region> cur(r,static_cast<unsigned int>(x.size()));
211 // Process all events
212 for (int i=0; true; i++)
213 switch (re[i].ret) {
214 case RET_FST:
215 // Process all overlapping views
217 j(); ++j) {
218 int di = re[i].view, dj = j.val();
219 if (!ovl.get(di,dj)) {
220 ovl.set(di,dj);
221 ovl_i[di][deg[di]++] = dj;
222 ovl_i[dj][deg[dj]++] = di;
223 }
224 }
225 cur.set(static_cast<unsigned int>(re[i].view));
226 break;
227 case RET_LST:
228 cur.clear(static_cast<unsigned int>(re[i].view));
229 break;
230 case RET_END:
231 goto done;
232 default:
234 }
235 done:
236 r.free<RangeEvent>(re,n_re);
237 }
238
239 // While deg changes, n_ovl_i remains unchanged and is needed, so copy it
240 for (int i=n_dis; i--; ) {
241 assert(deg[dis[i]] < n_dis);
242 n_ovl_i[dis[i]] = deg[dis[i]];
243 }
244
245 // Views in the independent set
246 int* ind = r.alloc<int>(n_dis);
247 int n_ind = 0;
248
249 while (n_dis > 0) {
250 int i_min = n_dis-1;
251 int d_min = deg[dis[i_min]];
252 unsigned int s_min = x[dis[i_min]].size();
253
254 // Find view with smallest (degree,size)
255 for (int i=n_dis-1; i--; )
256 if ((d_min > deg[dis[i]]) ||
257 ((d_min == deg[dis[i]]) && (s_min > x[dis[i]].size()))) {
258 i_min = i;
259 d_min = deg[dis[i]];
260 s_min = x[dis[i]].size();
261 }
262
263 // i_min refers to view with smallest (degree,size)
264 ind[n_ind++] = dis[i_min]; dis[i_min] = dis[--n_dis];
265
266 // Filter out non disjoint views
267 for (int i=n_dis; i--; )
268 if (ovl.get(dis[i],ind[n_ind-1])) {
269 // Update degree information
270 for (int j=n_ovl_i[dis[i]]; j--; )
271 deg[ovl_i[dis[i]][j]]--;
272 // Eliminate view
273 dis[i] = dis[--n_dis];
274 }
275 }
276 // Enforce lower bound
277 GECODE_ME_CHECK(y.gq(home,vs.size() + n_ind));
278
279 // Prune, if possible
280 if (vs.size() + n_ind == y.max()) {
281 // Only values from the indepent set a can be taken
282 ViewRanges<IntView>* r_ind = r.alloc<ViewRanges<IntView> >(n_ind);
283 for (int i=n_ind; i--; )
284 r_ind[i] = ViewRanges<IntView>(x[ind[i]]);
285 Iter::Ranges::NaryUnion v_ind(r, r_ind, n_ind);
286 ValSet::Ranges vsr(vs);
287 v_ind |= vsr;
288 for (int i=x.size(); i--; ) {
289 v_ind.reset();
290 GECODE_ME_CHECK(x[i].inter_r(home,v_ind,false));
291 }
292 }
293 return ES_OK;
294 }
295
296 template<class VY>
299 if (!g) {
300 g.init(home,vs,x);
301 } else {
302 g.purge();
303 g.sync();
304 }
305 GECODE_ME_CHECK(y.lq(home, g.size()));
306 if (y.min() == g.size()) {
307 // All values must be taken on
308 if (vs.size() + x.size() == g.size()) {
309 // This is in fact a distinct, simplify and rewrite
310 for (int i=x.size(); i--; ) {
311 ValSet::Ranges vsr(vs);
312 GECODE_ME_CHECK(x[i].minus_r(home, vsr, false));
313 }
315 }
316 if (g.mark())
317 GECODE_ES_CHECK(g.prune(home));
318 }
319 return ES_OK;
320 }
321
322}}}
323
324// STATISTICS: int-prop
Home class for posting propagators
Definition core.hpp:856
static ExecStatus post(Home home, ViewArray< View > &x)
Post propagator for views x.
Definition dom.hpp:45
Integer view for integer variables.
Definition view.hpp:129
View-value graph for propagation of upper bound.
Definition nvalues.hh:96
void init(Space &home, const ValSet &vs, const ViewArray< IntView > &x)
Initialize graph including values in vs.
Definition graph.hpp:46
void sync(void)
Synchronize graph with new view domains.
Definition graph.hpp:90
ExecStatus prune(Space &home)
Prune all values corresponding to unused edges.
Definition graph.hpp:255
int size(void) const
Return size of maximal matching (excluding assigned views)
Definition graph.hpp:41
virtual size_t dispose(Space &home)
Delete propagator and return its size.
Definition int-base.hpp:53
ValSet vs
Value set storing the values of already assigned views.
Definition nvalues.hh:138
ExecStatus prune_lower(Space &home, int *dis, int n_dis)
Definition int-base.hpp:130
void disjoint(Space &home, Region &r, int *&dis, int &n_dis)
Definition int-base.hpp:80
virtual PropCost cost(const Space &, const ModEventDelta &) const
Cost function.
Definition int-base.hpp:62
void add(Space &home)
Add values of assigned views to value set.
Definition int-base.hpp:68
void eliminate(Space &home)
Eliminate subsumed views (all values included in the value set vs)
Definition int-base.hpp:107
ExecStatus all_in_valset(Space &home)
Propagate that all views must take values from value set.
Definition int-base.hpp:120
ExecStatus prune_upper(Space &home, Graph &g)
Definition int-base.hpp:298
IntBase(Home home, ValSet &vs, ViewArray< IntView > &x, VY y)
Constructor for posting.
Definition int-base.hpp:40
Event for range-based overlap analysis.
Definition nvalues.hh:58
RangeEventType ret
The event type.
Definition nvalues.hh:61
int view
Which view does this range belong to.
Definition nvalues.hh:65
int val
The value for the range (first or last value, depending on type)
Definition nvalues.hh:63
Symmetric diagonal bit matrix.
Definition nvalues.hh:71
bool get(int x, int y) const
Is bit at position x, y set?
void set(int x, int y)
Set bit at position x, y.
Iterator over ranges.
Definition val-set.hh:78
Class for storing values of already assigned views.
Definition val-set.hh:44
Range iterator for integer views.
Definition view.hpp:54
void purge(void)
Purge graph if necessary (reset information to avoid overflow)
Definition graph.hpp:130
Range iterator for intersection of iterators.
Range iterator for union of iterators.
void reset(void)
Reset iterator to start.
Value iterator for values in a bitset.
Propagation cost.
Definition core.hpp:486
static PropCost quadratic(PropCost::Mod m, unsigned int n)
Quadratic complexity for modifier m and size measure n.
Definition core.hpp:4794
@ HI
Expensive.
Definition core.hpp:514
size_t size
The size of the propagator (used during subsumption)
Definition core.hpp:1079
friend class Space
Definition core.hpp:1068
Handle to region.
Definition region.hpp:55
void clear(unsigned int i)
Clear bit i.
void set(unsigned int i)
Set bit i.
Simple bitsets.
Definition bitset.hpp:45
View arrays.
Definition array.hpp:253
ExecStatus ES_SUBSUMED(Propagator &p)
Propagator p is subsumed
Definition core.hpp:3570
int ModEventDelta
Modification event deltas.
Definition core.hpp:89
#define GECODE_ME_CHECK(me)
Check whether modification event me is failed, and forward failure.
Definition macros.hpp:52
#define GECODE_REWRITE(prop, post)
Rewrite propagator by executing post function.
Definition macros.hpp:116
#define GECODE_ES_CHECK(es)
Check whether execution status es is failed or subsumed, and forward failure or subsumption.
Definition macros.hpp:91
const int infinity
Infinity for integers.
Definition int.hh:120
Number of values propagators.
@ RET_FST
A range starts.
Definition nvalues.hh:50
@ RET_LST
A range ends.
Definition nvalues.hh:52
@ RET_END
No further events.
Definition nvalues.hh:54
Finite domain integers.
const Gecode::PropCond PC_INT_BND
Propagate when minimum or maximum of a view changes.
Definition var-type.hpp:91
const Gecode::PropCond PC_INT_DOM
Propagate when domain changes.
Definition var-type.hpp:100
@ CS_NONE
Neither of the above.
@ CS_SUBSET
First is subset of second iterator.
@ CS_DISJOINT
Intersection is empty.
void quicksort(Type *l, Type *r, Less &less)
Standard quick sort.
Definition sort.hpp:130
Gecode toplevel namespace
Post propagator for SetVar SetOpType SetVar SetRelType r
Definition set.hh:773
ExecStatus
Definition core.hpp:472
@ ES_OK
Execution is okay.
Definition core.hpp:476
@ ES_FAILED
Execution has resulted in failure.
Definition core.hpp:474
#define forceinline
Definition config.hpp:194
#define GECODE_NEVER
Assert that this command is never executed.
Definition macros.hpp:56