Generated on for Gecode by doxygen 1.17.0
int.cpp
Go to the documentation of this file.
1/* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */
2/*
3 * Main authors:
4 * Mikael Zayenz Lagerkvist <lagerkvist@gecode.dev>
5 *
6 * Copyright:
7 * Mikael Zayenz Lagerkvist, 2006
8 *
9 * This file is part of Gecode, the generic constraint
10 * development environment:
11 * http://www.gecode.dev
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#include "test/branch.hh"
35
36#include <gecode/int/branch.hh>
37#include <gecode/search.hh>
38
39#include <memory>
40
41namespace Test { namespace Branch {
42
45 public:
48
51 : x(*this, 4, 0, 1) {
57 };
58 // Post directly so the random selector remains first in the tie chain.
60 *this, xv, vs,
62 [](const Gecode::Space&, Gecode::IntVar, int i) {
63 return (i == 0) || (i == 2);
64 }, nullptr);
65 }
66
69 : Gecode::Space(s) {
70 x.update(*this, s.x);
71 }
72
74 virtual Gecode::Space* copy(void) {
75 return new FilteredRndTiesSpace(*this);
76 }
77 };
78
80 class FilteredRndTies : public Base {
81 public:
84 : Base("Int::Branch::FilteredRndTies") {}
85
87 virtual bool run(void) {
88 bool selected[2] = {false, false};
89
90 for (unsigned int seed = 1; seed <= 16; seed++) {
93 if (probe->status() != Gecode::SS_BRANCH) {
94 delete probe;
95 return false;
96 }
97 const Gecode::Choice* c = probe->choice();
98 const Gecode::PosChoice& pc
99 = static_cast<const Gecode::PosChoice&>(*c);
100 const int p = pc.pos().pos;
101 delete c;
102 delete probe;
103 if ((p != 0) && (p != 2))
104 return false;
105 selected[p == 2] = true;
106
110 o.c_d = 2;
111 o.a_d = 1;
113 delete root;
114
115 int n = 0;
116 while (Gecode::Space* s = e.next()) {
117 FilteredRndTiesSpace* solution =
118 static_cast<FilteredRndTiesSpace*>(s);
119 if (solution->x[1].assigned() || solution->x[3].assigned()) {
120 delete solution;
121 return false;
122 }
123 delete solution;
124 n++;
125 }
126 if (n != 4)
127 return false;
128 }
129
130 return selected[0] && selected[1];
131 }
132 };
133
135
136#ifdef GECODE_HAS_CBS
138 class CBSSpace : public Gecode::Space {
139 public:
141 CBSSpace(bool local) : x(*this,8,0,3) {
142 if (local) {
143 NoGPI suppress(*this);
144 post();
145 } else {
146 post();
147 }
148 Gecode::cbsbranch(*this,x);
149 }
150 void post(void) {
151 using namespace Gecode;
152 distinct(*this,IntVarArgs() << x[0] << x[1] << x[2] << x[3],IPL_VAL);
153 distinct(*this,IntVarArgs() << x[4] << x[5] << x[6] << x[7],IPL_VAL);
154 }
155 CBSSpace(CBSSpace& s) : Space(s) {
156 x.update(*this,s.x);
157 }
158 virtual Space* copy(void) {
159 return new CBSSpace(*this);
160 }
161 };
162
164 class CBS : public Base {
165 public:
166 CBS(void) : Base("Int::Branch::CBS",TestTags::check()) {}
167 virtual bool run(void) {
168 using namespace Gecode;
169 for (bool local : {false,true}) {
170 CBSSpace root(local);
171 Search::Options o;
172 o.c_d = 2;
173 o.a_d = 1;
174 DFS<CBSSpace> engine(&root,o);
175 int n = 0;
176 while (std::unique_ptr<CBSSpace> s{engine.next()}) {
177 for (int i=0; i<s->x.size(); i++)
178 if (!s->x[i].assigned())
179 return false;
180 n++;
181 }
182 if (n != 24*24)
183 return false;
184 }
185 return true;
186 }
187 };
188
189 CBS cbs;
190#endif
191
193 class Int : public IntTest {
194 public:
196 Int(const std::string& s, const Gecode::IntSet& d, int n)
197 : IntTest(s,n,d) {}
198
199 virtual void post(Gecode::Space& home, Gecode::IntVarArray& x) {
200 Gecode::distinct(home, x);
201 }
202 };
203
205 const int v_sparse[5] = {-100,-10,0,10,100};
207
209
210 Int d_3("Dense::3",d_dense,3);
211 Int d_5("Dense::5",d_dense,5);
212 Int s_3("Sparse::3",d_sparse,3);
213 Int s_5("Sparse::5",d_sparse,5);
214 Int l_2("Large::2",d_large,2);
215 Int l_3("Large::3",d_large,3);
216
217}}
218
219// STATISTICS: test-branch
int size(void) const
Return size of array (number of elements).
Definition array.hpp:1606
Choice for performing commit
Definition core.hpp:1430
Depth-first search engine.
Definition search.hh:1211
Integer sets.
Definition int.hh:179
Passing integer variables.
Definition int.hh:681
Integer variable array.
Definition int.hh:792
Integer variables.
Definition int.hh:390
Choices storing position
Definition view.hpp:55
const Pos & pos(void) const
Return position in array.
Definition view.hpp:126
const int pos
Position of view.
Definition view.hpp:47
Random number generator.
Definition rnd.hpp:42
virtual T * next(void)
Return next solution (nullptr, if none exists or search has been stopped).
Definition base.hpp:46
Search engine options
Definition search.hh:848
unsigned int c_d
Create a clone after every c_d commits (commit distance).
Definition search.hh:863
unsigned int a_d
Create a clone during recomputation if distance is greater than a_d (adaptive distance).
Definition search.hh:865
Computation spaces.
Definition core.hpp:1787
bool assigned(void) const
Test if all variables are assigned.
Definition array.hpp:1045
void update(Space &home, VarArray< Var > &a)
Update array to be a clone of array a.
Definition array.hpp:1032
View arrays.
Definition array.hpp:255
Abstract class for view selection.
Definition view-sel.hpp:44
Base class for all tests to be run
Definition test.hh:186
Base(std::string s)
Create and register a standard test with name s.
Definition test.cpp:125
Space for testing filtered random tie selection.
Definition int.cpp:44
virtual Gecode::Space * copy(void)
Copy space during cloning.
Definition int.cpp:74
FilteredRndTiesSpace(FilteredRndTiesSpace &s)
Constructor for cloning.
Definition int.cpp:68
FilteredRndTiesSpace(Gecode::Rnd r)
Initialize space.
Definition int.cpp:50
Gecode::IntVarArray x
Variables to branch on.
Definition int.cpp:47
Test filtered random tie selection with accepted and rejected views.
Definition int.cpp:80
virtual bool run(void)
Run test.
Definition int.cpp:87
FilteredRndTies(void)
Create and register test.
Definition int.cpp:83
IntTest(const std::string &s, int a, const Gecode::IntSet &d)
Construct and register test.
Definition branch.cpp:430
Test brancher with distinct propagator
Definition int.cpp:193
virtual void post(Gecode::Space &home, Gecode::IntVarArray &x)
Post propagators on variables x.
Definition int.cpp:199
Int(const std::string &s, const Gecode::IntSet &d, int n)
Create and register test.
Definition int.cpp:196
Scoped suppression of global propagator information.
Definition afc.cpp:138
Set of test tags.
Definition test.hh:105
@ IPL_VAL
Value propagation.
Definition int.hh:1277
Space(void)
Default constructor.
Definition core.cpp:121
const Choice * choice(void)
Create new choice for current brancher.
Definition core.cpp:568
SpaceStatus status(StatusStatistics &stat)
Query space status.
Definition core.cpp:281
@ SS_BRANCH
Space must be branched (at least one brancher left)
Definition core.hpp:1729
ViewSel< IntView > * viewsel(Space &home, const IntVarBranch &ivb)
Return view selectors for integer views.
Definition view-sel.cpp:39
ValSelCommitBase< IntView, int > * valselcommit(Space &home, const IntValBranch &ivb)
Return value and commit for integer views.
Gecode toplevel namespace
void distinct(Home home, const IntVarArgs &x, IntPropLevel ipl=IPL_DEF)
Post propagator for for all .
Definition distinct.cpp:46
void postviewvalbrancher(Home home, ViewArray< View > &x, ViewSel< View > *vs[n], ValSelCommitBase< View, Val > *vsc, BranchFilter< typename View::VarType > bf, VarValPrint< typename View::VarType, Val > vvp)
Post view value brancher.
Definition view-val.hpp:342
IntValBranch INT_VAL_MIN(void)
Select smallest value.
Definition val.hpp:55
IntVarBranch INT_VAR_RND(Rnd r)
Select random variable (uniform distribution, for tie breaking).
Definition var.hpp:101
IntVarBranch INT_VAR_SIZE_MIN(BranchTbl tbl=nullptr)
Select variable with smallest domain size.
Definition var.hpp:206
Tests for branchings.
Definition branch.cpp:58
Int d_5("Dense::5", d_dense, 5)
Gecode::IntSet d_sparse(v_sparse, 5)
Int s_3("Sparse::3", d_sparse, 3)
Gecode::IntSet d_large(-2, 10)
FilteredRndTies filtered_rnd_ties
Definition int.cpp:134
Int s_5("Sparse::5", d_sparse, 5)
const int v_sparse[5]
Definition int.cpp:205
Int l_3("Large::3", d_large, 3)
Int d_3("Dense::3", d_dense, 3)
Gecode::IntSet d_dense(-2, 2)
Int l_2("Large::2", d_large, 2)
Gecode::IntArgs i({1, 2, 3, 4})
General test support.
Definition afc.cpp:41
Region r
Definition region.cpp:65