Generated on for Gecode by doxygen 1.17.0
min-distance.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, 2026
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
35
36#include "test/int.hh"
37
38#include <memory>
39
40namespace Test { namespace Int { namespace MinDistance {
41
44 return Gecode::IntArgs({0,0,3,4, 0,0,2,1, 3,2,0,4, 4,1,4,0});
45 }
46
48 class Minimum : public Test {
49 protected:
53 int alias;
55 public:
56 Minimum(int n, bool f, bool r, int a,
58 : Test(TestTags::check(),
59 "MinDistance::"+str(n)+"::"+str(f)+"::"+str(r)+"::"+
60 str(a)+"::"+str(k == Gecode::MDP_SINGLE)+"::"+str(level),
61 n+1,0,4,false,level),
62 positions(n), computed(f), requirements(r), alias(a), kind(k) {
64 }
65 virtual bool solution(const Assignment& a) const {
66 int minimum = 4;
68 for (int i=0; i<positions; i++) {
69 if (a[i] >= 4)
70 return false;
71 for (int j=i+1; j<positions; j++) {
72 if (a[j] >= 4)
73 return false;
74 int first = a[alias == 1 && i == 1 ? 0 : i];
75 int second = a[alias == 1 && j == 1 ? 0 : j];
76 int distance = m[first*4+second];
77 if (requirements && (i == 0) && (j == positions-1) &&
78 (distance < 3))
79 return false;
80 minimum = std::min(minimum,distance);
81 }
82 }
83 return (a[positions] == minimum) &&
84 ((alias != 2) || (a[positions] == a[0]));
85 }
86 virtual void post(Gecode::Space& home, Gecode::IntVarArray& a) {
87 using namespace Gecode;
88 IntArgs m = matrix();
90 IntDistance(4,[m](int i, int j) { return m[i*4+j]; }) :
91 IntDistance(4,m);
93 for (int i=0; i<positions; i++) {
94 Gecode::dom(home,a[i],0,3);
95 x[i] = a[alias == 1 && i == 1 ? 0 : i];
96 }
97 if (alias == 2)
98 rel(home,a[positions],IRT_EQ,a[0]);
99 IntVar z = a[alias == 2 ? 0 : positions];
100 if (requirements) {
102 for (int i=0; i<r.size(); i++)
103 r[i] = 0;
104 r[positions-1] = r[(positions-1)*positions] = 3;
105 minimum_distance(home,x,z,d,r,ipl,kind);
106 } else {
107 minimum_distance(home,x,z,d,ipl,kind);
108 }
109 }
110 };
111
113 class Model : public Gecode::Space {
114 public:
117 Model(int n, int sites, int lower, int upper,
119 std::function<int(int,int)> distance)
120 : x(*this,n,0,sites-1), z(*this,lower,upper) {
122 Gecode::IntDistance(sites,distance),level,kind);
123 }
125 x.update(*this,s.x); z.update(*this,s.z);
126 }
127 virtual Gecode::Space* copy(void) { return new Model(*this); }
128 };
129
131 // Check domain bounds before assignment and ownership across Space clones.
132 class Propagation : public Base {
133 public:
134 Propagation(void) : Base("Int::MinDistance::Propagation",
135 TestTags::check()) {}
136 virtual bool run(void) {
137 using namespace Gecode;
138 const MinDistancePropKind kinds[] = {MDP_DECOMPOSED,MDP_SINGLE};
139 const IntPropLevel levels[] = {IPL_BASIC,IPL_ADVANCED};
140 for (MinDistancePropKind kind : kinds)
141 for (IntPropLevel level : levels) {
142 // Forward filtering includes equality at the threshold.
143 Model forward(2,4,2,4,kind,level,
144 [](int a, int b) { return std::abs(a-b); });
145 rel(forward,forward.x[0],IRT_EQ,0);
146 if ((forward.status() == SS_FAILED) ||
147 (forward.x[1].min() != 2) || (forward.z.max() != 3))
148 return false;
149 std::unique_ptr<Model> clone(static_cast<Model*>(forward.clone()));
150 rel(*clone,clone->x[1],IRT_EQ,2);
151 if ((clone->status() == SS_FAILED) || !clone->z.assigned() ||
152 (clone->z.val() != 2) || forward.z.assigned())
153 return false;
154 }
155
156 // A perfect conflict matching rules out selecting three sites at 3.
157 auto conflicts = [](int a, int b) {
158 return a == b ? 0 : (a/2 == b/2 ? 1 : 3);
159 };
160 for (MinDistancePropKind kind : kinds) {
161 Model basic(3,4,1,3,kind,IPL_BASIC,conflicts);
162 Model matching(3,4,1,3,kind,IPL_ADVANCED,conflicts);
163 if ((basic.status() == SS_FAILED) || (basic.z.max() != 3) ||
164 (matching.status() == SS_FAILED) || (matching.z.max() != 1))
165 return false;
166 }
167
168 // Share a captured object across stable clones and release it with
169 // the last Space. Computed distances must not build an n*n matrix.
170 std::weak_ptr<int> lifetime;
171 std::unique_ptr<Model> clone;
172 {
173 auto data = std::make_shared<int>(1);
174 lifetime = data;
175 Model original(2,1000000,1,3,MDP_SINGLE,IPL_BASIC,
176 [data](int a, int b) { return a == b ? 0 : *data; });
177 // Restrict domains before propagation to avoid enumerating the
178 // million-site universe; construction itself makes no distance calls.
179 dom(original,original.x,0,2);
180 if (original.status() == SS_FAILED)
181 return false;
182 clone.reset(static_cast<Model*>(original.clone()));
183 }
184 if (lifetime.expired() || (clone->status() == SS_FAILED))
185 return false;
186 clone.reset();
187 if (!lifetime.expired())
188 return false;
189 return true;
190 }
191 };
192
194 class Arguments : public Base {
195 public:
196 Arguments(void) : Base("Int::MinDistance::Arguments",
197 TestTags::check()) {}
198 virtual bool run(void) {
199 using namespace Gecode;
200 try {
201 IntDistance invalid(2,IntArgs({0,1,2,0}));
202 return false;
203 } catch (const Gecode::Int::IllegalOperation&) {}
204 try {
205 IntDistance invalid(2,IntArgs({0,-1,-1,0}));
206 return false;
207 } catch (const Gecode::Int::OutOfLimits&) {}
208 try {
209 IntDistance invalid(2,std::function<int(int,int)>());
210 return false;
211 } catch (const InvalidFunction&) {}
212 try {
213 IntDistance invalid(2,[](int, int) { return -1; });
214 (void) invalid(0,1);
215 return false;
216 } catch (const Gecode::Int::OutOfLimits&) {}
217 try {
218 Model space(2,4,0,4,MDP_DECOMPOSED,IPL_BASIC,
219 [](int a, int b) { return std::abs(a-b); });
220 IntVarArgs x;
221 IntVar z(space,0,4);
222 minimum_distance(space,x,z,IntDistance(4,matrix()));
223 return false;
224 } catch (const Gecode::Int::TooFewArguments&) {}
225 return true;
226 }
227 };
228
230 class Create {
231 public:
232 Create(void) {
233 const Gecode::MinDistancePropKind kinds[] =
234 {Gecode::MDP_DECOMPOSED,Gecode::MDP_SINGLE};
235 const Gecode::IntPropLevel levels[] =
237 for (int n : {2,3})
238 for (bool computed : {false,true})
239 for (bool requirements : {false,true})
240 for (Gecode::MinDistancePropKind kind : kinds)
241 for (Gecode::IntPropLevel level : levels)
242 (void) new Minimum(n,computed,requirements,0,kind,level);
243 for (Gecode::MinDistancePropKind kind : kinds)
244 for (Gecode::IntPropLevel level : levels)
245 (void) new Minimum(3,true,true,1,kind,level);
246 for (Gecode::MinDistancePropKind kind : kinds)
247 for (Gecode::IntPropLevel level : levels)
248 (void) new Minimum(3,true,false,2,kind,level);
249 (void) new Propagation;
250 (void) new Arguments;
251 }
252 };
254
255}}}
256
257// STATISTICS: test-int
Passing integer arguments.
Definition int.hh:653
Shared distances between indexed sites.
Definition int.hh:3356
Passing integer variables.
Definition int.hh:681
Integer variable array.
Definition int.hh:792
Integer variables.
Definition int.hh:390
int max(void) const
Return maximum of domain.
Definition int.hpp:70
Exception: Illegal operation passed as argument
Exception: Value out of limits
Definition exception.hpp:44
Exception: Too few arguments available in argument array
Definition exception.hpp:66
Exception: invalid function
Computation spaces.
Definition core.hpp:1787
Base(std::string s)
Create and register a standard test with name s.
Definition test.cpp:125
Base class for assignments
Definition int.hh:73
Matrix and callback validation.
virtual bool run(void)
Run test.
Register the compact semantic matrix.
Exhaustive assignments and incremental clone/prune checks.
virtual void post(Gecode::Space &home, Gecode::IntVarArray &a)
Post constraint.
virtual bool solution(const Assignment &a) const
Check for solution.
Gecode::MinDistancePropKind kind
Minimum(int n, bool f, bool r, int a, Gecode::MinDistancePropKind k, Gecode::IntPropLevel level)
Small space for direct propagation checks.
virtual Gecode::Space * copy(void)
Copying member function.
Model(int n, int sites, int lower, int upper, Gecode::MinDistancePropKind kind, Gecode::IntPropLevel level, std::function< int(int, int)> distance)
Domain filtering, matching strength, and callback lifetime.
virtual bool run(void)
Run test.
static std::string str(bool b)
Map bool to string.
Definition int.hpp:278
Gecode::IntPropLevel ipl
Propagation level.
Definition int.hh:281
ConTestLevel contest
Whether to test for certain consistency.
Definition int.hh:283
Set of test tags.
Definition test.hh:105
void rel(Home home, FloatVar x0, FloatRelType frt, FloatVar x1)
Post propagator for .
Definition rel.cpp:68
IntPropLevel
Propagation levels for integer propagators.
Definition int.hh:1274
@ IRT_EQ
Equality ( ).
Definition int.hh:1226
@ IPL_BASIC
Use basic propagation algorithm.
Definition int.hh:1281
@ IPL_ADVANCED
Use advanced propagation algorithm.
Definition int.hh:1282
Space(void)
Default constructor.
Definition core.cpp:121
SpaceStatus status(StatusStatistics &stat)
Query space status.
Definition core.cpp:281
@ SS_FAILED
Space is failed
Definition core.hpp:1727
Gecode toplevel namespace
void dom(Home home, FloatVar x, FloatVal n)
Propagates .
Definition dom.cpp:40
void minimum_distance(Home home, const IntVarArgs &x, IntVar z, const IntDistance &d, IntPropLevel ipl=IPL_DEF, MinDistancePropKind kind=MDP_SINGLE)
Post .
MinDistancePropKind
Organization of forward-bound minimum-distance propagation.
Definition int.hh:3395
Gecode::IntArgs matrix(void)
Distances with both a zero off-diagonal pair and threshold boundaries.
Testing finite domain integers.
Definition int.cpp:41
@ CTL_NONE
No consistency-test.
Definition int.hh:154
General test support.
Definition afc.cpp:41
Region r
Definition region.cpp:65
@ check
Basic integrity tests.
Definition test.hh:99