Generated on Tue Mar 26 2024 01:51:50 for Gecode by doxygen 1.9.8
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
45namespace Gecode { namespace Int { namespace NValues {
46
54 RET_END = 2
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
int p
Number of positive literals for node type.
struct Gecode::@603::NNF::@65::@67 a
For atomic nodes.
Base-class for both propagators and branchers.
Definition core.hpp:628
Base-class for advisors.
Definition core.hpp:1292
Council of advisors
Definition core.hpp:1241
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
Number of values propagator for Boolean views base class.
Definition nvalues.hh:293
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
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
Equal to number of values propagator for Boolean views.
Definition nvalues.hh:327
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
Equal to number of values propagator for integer views.
Definition nvalues.hh:185
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
Greater or equal to number of values propagator for Boolean views.
Definition nvalues.hh:391
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
static ExecStatus post(Home home, ViewArray< BoolView > &x, VY y)
Post propagator for .
Definition bool-gq.hpp:56
Greater or equal to number of values propagator for integer views.
Definition nvalues.hh:251
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
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
Number of values propagator for integer views base class.
Definition nvalues.hh:133
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
Less or equal to number of values propagator for Boolean views.
Definition nvalues.hh:359
virtual Actor * copy(Space &home)
Copy propagator during cloning.
Definition bool-lq.hpp:50
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
Less or equal to number of values propagator for integer views.
Definition nvalues.hh:219
static ExecStatus post(Home home, ViewArray< IntView > &x, VY y)
Post propagator for .
Definition int-lq.hpp:48
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.
Symmetric diagonal bit matrix.
Definition nvalues.hh:71
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.
Class for storing values of already assigned views.
Definition val-set.hh:44
View-value graph base class.
Mixed (n+1)-ary propagator.
Definition pattern.hpp:272
Propagation cost.
Definition core.hpp:486
Base-class for propagators.
Definition core.hpp:1064
ModEventDelta med
A set of modification events (used during propagation)
Definition core.hpp:1075
Handle to region.
Definition region.hpp:55
Computation spaces.
Definition core.hpp:1742
Simple bitsets.
Definition bitset.hpp:45
View arrays.
Definition array.hpp:253
int ModEventDelta
Modification event deltas.
Definition core.hpp:89
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
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:767
Post propagator for SetVar SetOpType SetVar y
Definition set.hh:767
ExecStatus
Definition core.hpp:472
Post propagator for SetVar x
Definition set.hh:767