Generated on Tue Feb 11 2025 17:33:26 for Gecode by doxygen 1.12.0
ldsb.hh
Go to the documentation of this file.
1/* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */
2/*
3 * Main authors:
4 * Christopher Mears <chris.mears@monash.edu>
5 *
6 * Copyright:
7 * Christopher Mears, 2012
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_LDSB_HH__
35#define __GECODE_INT_LDSB_HH__
36
37#include <gecode/int.hh>
38
43namespace Gecode { namespace Int { namespace LDSB {
44
46 class Literal {
47 public:
49 Literal(void);
51 Literal(int _var, int _val);
52
59 int _value;
60
63 bool operator <(const Literal &rhs) const;
64 };
65
78 std::pair<int,int>
79 findVar(int *indices, unsigned int n_values, unsigned int seq_size, int index);
80}}}
81
82namespace Gecode {
84 template<>
91
95 template<>
102}
103
104namespace Gecode { namespace Int { namespace LDSB {
107 public:
109 int nrefs;
111 SymmetryObject(void);
113 virtual ~SymmetryObject(void);
114 };
159
161 template<class View>
163 public:
167 virtual void update(Literal) = 0;
169 virtual SymmetryImp<View>* copy(Space& home) const = 0;
171 virtual size_t dispose(Space& home) = 0;
173 virtual ~SymmetryImp(void);
175 static void* operator new(size_t s, Space& home);
177 static void operator delete(void*,Space&);
179 static void operator delete(void*);
180 };
182 template <class View>
183 class VariableSymmetryImp : public SymmetryImp<View> {
184 protected:
187 public:
189 VariableSymmetryImp<View>(Space& home, int* vs, unsigned int n);
193 virtual size_t dispose(Space& home);
195 void update(Literal);
199 SymmetryImp<View>* copy(Space& home) const;
200 };
202 template <class View>
203 class ValueSymmetryImp : public SymmetryImp<View>
204 {
205 public:
209 ValueSymmetryImp<View>(Space& home, int* vs, unsigned int n);
213 virtual size_t dispose(Space& home);
215 void update(Literal);
219 SymmetryImp<View>* copy(Space& home) const;
220 };
222 template <class View>
224 {
225 protected:
227 unsigned int *indices;
229 unsigned int n_indices;
231 unsigned int seq_size;
233 unsigned int n_seqs;
234
236 // e.g. lookup[2] == 10 indicates that the variable with index 2
237 // occurs at position 10 in the "indices" array.
238 // If a variable occurs more than once, only the first occurrence
239 // is recorded.
240 // A value of -1 indicates that the variable does not occur in
241 // "indices".
242 int *lookup;
244 unsigned int lookup_size;
245
248 int getVal(unsigned int sequence, unsigned int position) const;
249 public:
251 VariableSequenceSymmetryImp<View>(Space& home, int *_indices, unsigned int n, unsigned int seqsize);
255 virtual size_t dispose(Space& home);
257 void update(Literal);
259 virtual ArgArray<Literal> symmetric(Literal, const ViewArray<View>&) const;
261 SymmetryImp<View>* copy(Space& home) const;
262 };
264 template <class View>
266 {
267 protected:
269 int *values;
271 unsigned int n_values;
273 unsigned int seq_size;
275 unsigned int n_seqs;
280 int getVal(unsigned int sequence, unsigned int position) const;
281 private:
283 public:
285 ValueSequenceSymmetryImp<View>(Space& home, int* _values, unsigned int n, unsigned int seqsize);
289 virtual size_t dispose(Space& home);
291 void update(Literal);
295 SymmetryImp<View>* copy(Space& home) const;
296 };
297
300 template<class Val>
302 private:
304 const Literal * const _literals;
306 const int _nliterals;
307 public:
310 LDSBChoice(const Brancher& b, unsigned int a, const Pos& p, const Val& n,
311 const Literal* literals, int nliterals);
313 ~LDSBChoice(void);
315 const Literal* literals(void) const;
317 int nliterals(void) const;
319 virtual void archive(Archive& e) const;
320 };
321
330 template<class View, int n, class Val, unsigned int a,
331 class Filter, class Print>
332 class LDSBBrancher : public ViewValBrancher<View,n,Val,a,Filter,Print> {
333 public:
339 // Position of variable that last choice was created for
341 protected:
349 SymmetryImp<View>** syms, int nsyms,
352 public:
354 virtual const Choice* choice(Space& home);
356 virtual const Choice* choice(const Space& home, Archive& e);
358 virtual ExecStatus commit(Space& home, const Choice& c, unsigned int b);
360 virtual Actor* copy(Space& home);
362 virtual size_t dispose(Space& home);
364 static void post(Home home,
368 SymmetryImp<View>** syms,
369 int nsyms,
372 };
373
375 template<class View, int n, class Val, unsigned int a>
376 void postldsbbrancher(Home home,
378 ViewSel<View>* vs[n],
380 SymmetryImp<View>** syms, int nsyms,
383
385 template<class View>
386 ModEvent prune(Space& home, View x, int v);
387
388}}}
389
392
393#endif
394
395// STATISTICS: int-branch
396
struct Gecode::@603::NNF::@65::@66 b
For binary nodes (and, or, eqv)
int p
Number of positive literals for node type.
int n
Number of negative 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
Archive representation
Definition archive.hpp:42
Argument array for non-primitive types.
Definition array.hpp:691
ArgArray< VarImpBase * > StorageType
Definition ldsb.hh:87
Int::LDSB::Literal ValueType
Definition ldsb.hh:99
Traits of arrays in Gecode.
Definition array.hpp:94
Base-class for branchers.
Definition core.hpp:1442
Choice for performing commit
Definition core.hpp:1412
Home class for posting propagators
Definition core.hpp:856
Passing integer arguments.
Definition int.hh:628
Integer sets.
Definition int.hh:174
Symmetry-breaking brancher with generic view and value selection.
Definition ldsb.hh:332
static void post(Home home, ViewArray< View > &x, ViewSel< View > *vs[n], ValSelCommitBase< View, Val > *vsc, SymmetryImp< View > **syms, int nsyms, BranchFilter< Var > bf, VarValPrint< Var, Val > vvp)
Brancher post function.
Definition brancher.hpp:112
virtual ExecStatus commit(Space &home, const Choice &c, unsigned int b)
Perform commit for choice c and alternative b.
Definition brancher.hpp:232
int _nsyms
Number of symmetry implementations.
Definition ldsb.hh:338
SymmetryImp< View > ** _syms
Array of symmetry implementations.
Definition ldsb.hh:336
virtual const Choice * choice(Space &home)
Return choice.
Definition brancher.hpp:148
virtual Actor * copy(Space &home)
Perform cloning.
Definition brancher.hpp:138
LDSBBrancher(Space &home, LDSBBrancher &b)
Constructor for cloning b.
Definition brancher.hpp:125
virtual size_t dispose(Space &home)
Delete brancher and return its size.
Definition brancher.hpp:267
LDSBBrancher(Home home, ViewArray< View > &x, ViewSel< View > *vs[n], ValSelCommitBase< View, Val > *vsc, SymmetryImp< View > **syms, int nsyms, BranchFilter< Var > bf, VarValPrint< Var, Val > vvp)
Constructor for creation.
Choice storing position and value, and symmetric literals to be excluded on the right branch.
Definition ldsb.hh:301
A Literal is a pair of variable index and value.
Definition ldsb.hh:46
bool operator<(const Literal &rhs) const
Less than. The ordering is the lexicographical order on the (variable,value) pair.
Definition brancher.hpp:49
Literal(void)
Constructor for an empty literal.
Definition brancher.hpp:40
int _variable
Variable index. The ViewArray that the index is meant for is assumed to be known by context.
Definition ldsb.hh:55
int _value
The value of the literal. For int and bool variables, this is the value itself; for set variables,...
Definition ldsb.hh:59
Implementation of a single symmetry.
Definition ldsb.hh:162
virtual ArgArray< Literal > symmetric(Literal, const ViewArray< View > &) const =0
Compute symmetric literals.
virtual size_t dispose(Space &home)=0
Disposal.
virtual void update(Literal)=0
Left-branch update.
virtual ~SymmetryImp(void)
Unused destructor.
Definition sym-imp.hpp:48
virtual SymmetryImp< View > * copy(Space &home) const =0
Copy function.
Implementation of a symmetry at the modelling level.
Definition ldsb.hh:106
int nrefs
Number of references that point to this symmetry object.
Definition ldsb.hh:109
Implementation of a value sequence symmetry.
Definition ldsb.hh:266
virtual ArgArray< Literal > symmetric(Literal, const ViewArray< View > &) const
Compute symmetric literals.
unsigned int n_seqs
Number of sequences in symmetry.
Definition ldsb.hh:275
int getVal(unsigned int sequence, unsigned int position) const
Get the value in the specified sequence at the specified position. (Both are zero-based....
Definition sym-imp.hpp:287
SymmetryImp< View > * copy(Space &home) const
Copy function.
Definition sym-imp.hpp:349
unsigned int seq_size
Size of each sequence in symmetry.
Definition ldsb.hh:273
void update(Literal)
Left-branch update.
Definition sym-imp.hpp:326
virtual size_t dispose(Space &home)
Disposal.
Definition sym-imp.hpp:318
Support::BitSet< Space > dead_sequences
Which sequences are dead.
Definition ldsb.hh:277
unsigned int n_values
Total number of values (n_seqs * seq_size)
Definition ldsb.hh:271
Implementation of a value sequence symmetry at the modelling level.
Definition ldsb.hh:150
IntArgs values
Array of values in symmetry.
Definition ldsb.hh:153
int seq_size
Size of each sequence in symmetry.
Definition ldsb.hh:155
Implementation of a value symmetry.
Definition ldsb.hh:204
virtual size_t dispose(Space &home)
Disposal.
Definition sym-imp.hpp:150
SymmetryImp< View > * copy(Space &home) const
Copy function.
Definition sym-imp.hpp:165
ValueSymmetryImp(Space &home, int *vs, unsigned int n)
Constructor for creation.
Definition sym-imp.hpp:122
Support::BitSetOffset< Space > values
Symmetric values.
Definition ldsb.hh:207
void update(Literal)
Left-branch update.
Definition sym-imp.hpp:158
virtual ArgArray< Literal > symmetric(Literal, const ViewArray< View > &) const
Compute symmetric literals.
Implementation of a value symmetry at the modelling level.
Definition ldsb.hh:128
IntSet values
Set of symmetric values.
Definition ldsb.hh:131
Implementation of a variable sequence symmetry.
Definition ldsb.hh:224
VariableSequenceSymmetryImp(Space &home, int *_indices, unsigned int n, unsigned int seqsize)
Constructor for creation.
Definition sym-imp.hpp:180
unsigned int * indices
Array of variable indices.
Definition ldsb.hh:227
int getVal(unsigned int sequence, unsigned int position) const
Get the value in the specified sequence at the specified position. (Both are zero-based....
Definition sym-imp.hpp:174
virtual size_t dispose(Space &home)
Disposal.
Definition sym-imp.hpp:216
SymmetryImp< View > * copy(Space &home) const
Copy function.
Definition sym-imp.hpp:278
unsigned int seq_size
Size of each sequence in symmetry.
Definition ldsb.hh:231
int * lookup
Map from variable's index to its sequence and position.
Definition ldsb.hh:242
void update(Literal)
Search left-branch update.
Definition sym-imp.hpp:270
unsigned int lookup_size
Size of lookup.
Definition ldsb.hh:244
unsigned int n_indices
Total number of indices (n_seqs * seq_size)
Definition ldsb.hh:229
virtual ArgArray< Literal > symmetric(Literal, const ViewArray< View > &) const
Compute symmetric literals.
Definition sym-imp.hpp:226
unsigned int n_seqs
Number of sequences in symmetry.
Definition ldsb.hh:233
Implementation of a variable sequence symmetry at the modelling level.
Definition ldsb.hh:136
int seq_size
Size of each sequence in symmetry.
Definition ldsb.hh:143
int nxs
Number of variables in symmetry.
Definition ldsb.hh:141
VarImpBase ** xs
Array of variables in symmetry.
Definition ldsb.hh:139
Implementation of a variable symmetry.
Definition ldsb.hh:183
VariableSymmetryImp(Space &home, int *vs, unsigned int n)
Constructor for creation.
Definition sym-imp.hpp:66
void update(Literal)
Left-branch update.
Definition sym-imp.hpp:104
SymmetryImp< View > * copy(Space &home) const
Copy function.
Definition sym-imp.hpp:112
Support::BitSetOffset< Space > indices
Symmetric variable indices.
Definition ldsb.hh:186
virtual size_t dispose(Space &home)
Disposal.
Definition sym-imp.hpp:96
virtual ArgArray< Literal > symmetric(Literal, const ViewArray< View > &) const
Compute symmetric literals.
Implementation of a variable symmetry at the modelling level.
Definition ldsb.hh:116
int nxs
Number of variables in symmetry.
Definition ldsb.hh:121
VarImpBase ** xs
Array of variables in symmetry.
Definition ldsb.hh:119
Choice storing position and value
Definition view-val.hpp:46
Position information.
Definition view.hpp:44
Computation spaces.
Definition core.hpp:1742
Bitsets with index offset.
Simple bitsets.
Definition bitset.hpp:45
Base class for value selection and commit.
Base-class for variable implementations.
Definition core.hpp:172
View arrays.
Definition array.hpp:253
ViewArray< View > x
Views to branch on.
Definition view.hpp:83
ViewSel< View > * vs[n]
View selection objects.
Definition view.hpp:87
Abstract class for view selection.
Definition view-sel.hpp:44
Generic brancher by view and value selection.
Definition view-val.hpp:91
View::VarType Var
The corresponding variable.
Definition view-val.hpp:97
ValSelCommitBase< View, Val > * vsc
Value selection and commit object.
Definition view-val.hpp:99
#define GECODE_INT_EXPORT
Definition int.hh:81
std::pair< int, int > findVar(int *indices, unsigned int n_values, unsigned int seq_size, int index)
Find the location of an integer in a collection of sequences.
Definition ldsb.cpp:42
ModEvent prune(Space &home, View x, int v)
Exclude value \v from variable view \x.
void postldsbbrancher(Home home, ViewArray< View > &x, ViewSel< View > *vs[n], ValSelCommitBase< View, Val > *vsc, SymmetryImp< View > **syms, int nsyms, BranchFilter< typename View::VarType > bf, VarValPrint< typename View::VarType, Val > vvp)
Post LDSB brancher.
Definition brancher.hpp:275
Gecode toplevel namespace
std::function< void(const Space &home, const Brancher &b, unsigned int a, Var x, int i, const Val &m, std::ostream &o)> VarValPrint
Function type for printing variable and value selection.
Definition print.hpp:40
void sequence(Home home, const IntVarArgs &x, const IntSet &s, int q, int l, int u, IntPropLevel ipl=IPL_DEF)
Post propagator for .
Definition sequence.cpp:47
ExecStatus
Definition core.hpp:472
ArgArray< Int::LDSB::Literal > LiteralArgs
An array of literals.
Definition ldsb.hh:93
Post propagator for SetVar x
Definition set.hh:767
std::function< bool(const Space &home, Var x, int i)> BranchFilter
Function type for branch filter functions.
Definition filter.hpp:40
int ModEvent
Type for modification events.
Definition core.hpp:62
#define GECODE_VTABLE_EXPORT
Definition support.hh:72