Generated on Thu Jan 16 2025 00:00:00 for Gecode by doxygen 1.14.0
nvalues.hh
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
34#ifndef __GECODE_INT_NVALUES_HH__
35#define __GECODE_INT_NVALUES_HH__
36
37#include <gecode/int.hh>
38#include <gecode/int/val-set.hh>
39
44
45namespace Gecode { namespace Int { namespace NValues {
46
55 };
56
58 class RangeEvent {
59 public:
63 int val;
65 int view;
67 bool operator <(RangeEvent re) const;
68 };
69
71 class SymBitMatrix : public Support::BitSet<Region> {
72 protected:
74 int n;
76 int pos(int x, int y) const;
77 public:
79 SymBitMatrix(Region& r, int n);
81 bool get(int x, int y) const;
83 void set(int x, int y);
84 };
85
86}}}
87
90
92
93namespace Gecode { namespace Int { namespace NValues {
94
96 class Graph : public ViewValGraph::Graph<IntView> {
97 protected:
100 public:
102 Graph(void);
104 int size(void) const;
106 void init(Space& home, const ValSet& vs, const ViewArray<IntView>& x);
108 void sync(void);
109 /*
110 * \brief Mark all edges used that can appear in some maximal matching
111 *
112 * Return true, if any edge can be in fact pruned.
113 */
114 bool mark(void);
116 ExecStatus prune(Space& home);
117 };
118
119}}}
120
122
123namespace Gecode { namespace Int { namespace NValues {
124
131 template<class VY>
133 : public MixNaryOnePropagator<IntView,PC_INT_DOM,VY,PC_INT_BND> {
134 protected:
140 IntBase(Home home, ValSet& vs, ViewArray<IntView>& x, VY y);
142 IntBase(Space& home, IntBase<VY>& p);
144 void add(Space& home);
150 void disjoint(Space& home, Region& r, int*& dis, int& n_dis);
152 void eliminate(Space& home);
163 ExecStatus prune_lower(Space& home, int* dis, int n_dis);
171 public:
173 virtual PropCost cost(const Space&, const ModEventDelta&) const;
175 virtual size_t dispose(Space& home);
176 };
177
184 template<class VY>
185 class EqInt : public IntBase<VY> {
186 protected:
187 using IntBase<VY>::x;
188 using IntBase<VY>::y;
189 using IntBase<VY>::vs;
190 using IntBase<VY>::add;
191 using IntBase<VY>::all_in_valset;
192 using IntBase<VY>::disjoint;
193 using IntBase<VY>::prune_lower;
194 using IntBase<VY>::prune_upper;
198 EqInt(Home home, ValSet& vs, ViewArray<IntView>& x, VY y);
200 EqInt(Space& home, EqInt<VY>& p);
201 public:
203 virtual Propagator* copy(Space& home);
205 virtual ExecStatus propagate(Space& home, const ModEventDelta& med);
207 static ExecStatus post(Home home, ViewArray<IntView>& x, VY y);
209 virtual size_t dispose(Space& home);
210 };
211
218 template<class VY>
219 class LqInt : public IntBase<VY> {
220 protected:
221 using IntBase<VY>::x;
222 using IntBase<VY>::y;
223 using IntBase<VY>::vs;
224 using IntBase<VY>::add;
225 using IntBase<VY>::all_in_valset;
226 using IntBase<VY>::disjoint;
227 using IntBase<VY>::prune_lower;
228 using IntBase<VY>::prune_upper;
230 LqInt(Home home, ValSet& vs, ViewArray<IntView>& x, VY y);
232 LqInt(Space& home, LqInt<VY>& p);
233 public:
235 virtual Propagator* copy(Space& home);
237 virtual ExecStatus propagate(Space& home, const ModEventDelta& med);
239 static ExecStatus post(Home home, ViewArray<IntView>& x, VY y);
241 virtual size_t dispose(Space& home);
242 };
243
250 template<class VY>
251 class GqInt : public IntBase<VY> {
252 protected:
253 using IntBase<VY>::x;
254 using IntBase<VY>::y;
255 using IntBase<VY>::vs;
256 using IntBase<VY>::add;
257 using IntBase<VY>::all_in_valset;
258 using IntBase<VY>::disjoint;
259 using IntBase<VY>::prune_lower;
260 using IntBase<VY>::prune_upper;
261 using IntBase<VY>::eliminate;
265 GqInt(Home home, ValSet& vs, ViewArray<IntView>& x, VY y);
267 GqInt(Space& home, GqInt<VY>& p);
268 public:
270 virtual Propagator* copy(Space& home);
272 virtual ExecStatus propagate(Space& home, const ModEventDelta& med);
274 static ExecStatus post(Home home, ViewArray<IntView>& x, VY y);
275 };
276
277}}}
278
283
284namespace Gecode { namespace Int { namespace NValues {
285
292 template<class VY>
293 class BoolBase : public Propagator {
294 protected:
296 static const int VS_ZERO = 1 << 0;
298 static const int VS_ONE = 1 << 1;
304 VY y;
306 BoolBase(Home home, int status, ViewArray<BoolView>& x, VY y);
308 BoolBase(Space& home, BoolBase<VY>& p);
309 public:
311 virtual ExecStatus advise(Space& home, Advisor& a, const Delta& d);
313 virtual PropCost cost(const Space& home, const ModEventDelta& med) const;
315 virtual void reschedule(Space& home);
317 virtual size_t dispose(Space& home);
318 };
319
326 template<class VY>
327 class EqBool : public BoolBase<VY> {
328 protected:
329 using BoolBase<VY>::VS_ZERO;
330 using BoolBase<VY>::VS_ONE;
331 using BoolBase<VY>::status;
332 using BoolBase<VY>::c;
333 using BoolBase<VY>::y;
335 EqBool(Home home, int status, ViewArray<BoolView>& x, VY y);
337 EqBool(Space& home, EqBool<VY>& p);
338 public:
340 virtual Actor* copy(Space& home);
342 virtual ExecStatus propagate(Space& home, const ModEventDelta& med);
349 static ExecStatus post(Home home, ViewArray<BoolView>& x, VY y);
350 };
351
358 template<class VY>
359 class LqBool : public BoolBase<VY> {
360 protected:
361 using BoolBase<VY>::VS_ZERO;
362 using BoolBase<VY>::VS_ONE;
363 using BoolBase<VY>::status;
364 using BoolBase<VY>::c;
365 using BoolBase<VY>::y;
367 LqBool(Home home, int status, ViewArray<BoolView>& x, VY y);
369 LqBool(Space& home, LqBool<VY>& p);
370 public:
372 virtual Actor* copy(Space& home);
374 virtual ExecStatus propagate(Space& home, const ModEventDelta& med);
381 static ExecStatus post(Home home, ViewArray<BoolView>& x, VY y);
382 };
383
390 template<class VY>
391 class GqBool : public BoolBase<VY> {
392 protected:
393 using BoolBase<VY>::VS_ZERO;
394 using BoolBase<VY>::VS_ONE;
395 using BoolBase<VY>::status;
396 using BoolBase<VY>::c;
397 using BoolBase<VY>::y;
399 GqBool(Home home, int status, ViewArray<BoolView>& x, VY y);
401 GqBool(Space& home, GqBool<VY>& p);
402 public:
404 virtual Actor* copy(Space& home);
406 virtual ExecStatus propagate(Space& home, const ModEventDelta& med);
413 static ExecStatus post(Home home, ViewArray<BoolView>& x, VY y);
414 };
415
416}}}
417
422
423#endif
424
425// STATISTICS: int-prop
Generic domain change information to be supplied to advisors.
Definition core.hpp:204
Home class for posting propagators
Definition core.hpp:856
Integer view for integer variables.
Definition view.hpp:129
virtual size_t dispose(Space &home)
Delete propagator and return its size.
Definition bool-base.hpp:91
Council< ViewAdvisor< BoolView > > c
The advisor council.
Definition nvalues.hh:302
virtual PropCost cost(const Space &home, const ModEventDelta &med) const
Cost function (defined as low unary)
Definition bool-base.hpp:58
BoolBase(Home home, int status, ViewArray< BoolView > &x, VY y)
Constructor for posting.
Definition bool-base.hpp:38
static const int VS_ONE
View status: a one has already been encountered.
Definition nvalues.hh:298
VY y
The view for counting the number of values.
Definition nvalues.hh:304
virtual void reschedule(Space &home)
Schedule function.
Definition bool-base.hpp:64
static const int VS_ZERO
View status: a zero has already been encountered.
Definition nvalues.hh:296
virtual ExecStatus advise(Space &home, Advisor &a, const Delta &d)
Give advice to propagator.
Definition bool-base.hpp:70
int status
Status information about the views.
Definition nvalues.hh:300
EqBool(Home home, int status, ViewArray< BoolView > &x, VY y)
Constructor for posting.
Definition bool-eq.hpp:41
static ExecStatus post(Home home, ViewArray< BoolView > &x, VY y)
Post propagator for .
Definition bool-eq.hpp:57
virtual ExecStatus propagate(Space &home, const ModEventDelta &med)
Perform propagation.
Definition bool-eq.hpp:118
virtual Actor * copy(Space &home)
Copy propagator during cloning.
Definition bool-eq.hpp:51
EqInt(Home home, ValSet &vs, ViewArray< IntView > &x, VY y)
Constructor for posting.
Definition int-eq.hpp:41
virtual Propagator * copy(Space &home)
Copy propagator during cloning.
Definition int-eq.hpp:102
virtual size_t dispose(Space &home)
Delete propagator and return its size.
Definition int-eq.hpp:108
static ExecStatus post(Home home, ViewArray< IntView > &x, VY y)
Post propagator for .
Definition int-eq.hpp:48
virtual ExecStatus propagate(Space &home, const ModEventDelta &med)
Perform propagation.
Definition int-eq.hpp:116
Graph g
View-value graph.
Definition nvalues.hh:196
virtual ExecStatus propagate(Space &home, const ModEventDelta &med)
Perform propagation.
Definition bool-gq.hpp:109
virtual Actor * copy(Space &home)
Copy propagator during cloning.
Definition bool-gq.hpp:50
GqBool(Home home, int status, ViewArray< BoolView > &x, VY y)
Constructor for posting.
Definition bool-gq.hpp:40
static ExecStatus post(Home home, ViewArray< BoolView > &x, VY y)
Post propagator for .
Definition bool-gq.hpp:56
static ExecStatus post(Home home, ViewArray< IntView > &x, VY y)
Post propagator for .
Definition int-gq.hpp:46
virtual Propagator * copy(Space &home)
Copy propagator during cloning.
Definition int-gq.hpp:98
virtual ExecStatus propagate(Space &home, const ModEventDelta &med)
Perform propagation.
Definition int-gq.hpp:104
GqInt(Home home, ValSet &vs, ViewArray< IntView > &x, VY y)
Constructor for posting.
Definition int-gq.hpp:41
Graph g
View-value graph.
Definition nvalues.hh:263
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
Graph(void)
Construct graph as not yet initialized.
Definition graph.hpp:37
int n_matched
Number of matched edges.
Definition nvalues.hh:99
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
virtual Actor * copy(Space &home)
Copy propagator during cloning.
Definition bool-lq.hpp:50
LqBool(Home home, int status, ViewArray< BoolView > &x, VY y)
Constructor for posting.
Definition bool-lq.hpp:40
static ExecStatus post(Home home, ViewArray< BoolView > &x, VY y)
Post propagator for .
Definition bool-lq.hpp:56
virtual ExecStatus propagate(Space &home, const ModEventDelta &med)
Perform propagation.
Definition bool-lq.hpp:111
static ExecStatus post(Home home, ViewArray< IntView > &x, VY y)
Post propagator for .
Definition int-lq.hpp:48
LqInt(Home home, ValSet &vs, ViewArray< IntView > &x, VY y)
Constructor for posting.
Definition int-lq.hpp:41
virtual size_t dispose(Space &home)
Delete propagator and return its size.
Definition int-lq.hpp:104
virtual ExecStatus propagate(Space &home, const ModEventDelta &med)
Perform propagation.
Definition int-lq.hpp:112
virtual Propagator * copy(Space &home)
Copy propagator during cloning.
Definition int-lq.hpp:98
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
bool operator<(RangeEvent re) const
Order events: first by val, then by event type.
bool get(int x, int y) const
Is bit at position x, y set?
int pos(int x, int y) const
Return position in matrix.
void set(int x, int y)
Set bit at position x, y.
SymBitMatrix(Region &r, int n)
Initialize matrix for dimension n by n.
Class for storing values of already assigned views.
Definition val-set.hh:44
View-value graph base class.
Propagation cost.
Definition core.hpp:486
friend class Space
Definition core.hpp:1068
friend class Advisor
Definition core.hpp:1070
friend class Council
Definition core.hpp:1071
ModEventDelta med
A set of modification events (used during propagation)
Definition core.hpp:1077
Propagator(Home home)
Constructor for posting.
Definition core.hpp:3505
Handle to region.
Definition region.hpp:55
Computation spaces.
Definition core.hpp:1744
Simple bitsets.
Definition bitset.hpp:45
View arrays.
Definition array.hpp:253
int ModEventDelta
Modification event deltas.
Definition core.hpp:89
Number of values propagators.
RangeEventType
Event type for range-based overlap analysis.
Definition nvalues.hh:48
@ 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
Gecode toplevel namespace
Post propagator for SetVar SetOpType SetVar SetRelType r
Definition set.hh:773
Post propagator for SetVar SetOpType SetVar y
Definition set.hh:773
ExecStatus
Definition core.hpp:472
Post propagator for SetVar x
Definition set.hh:773