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
36
37#include <utility>
38
39namespace Gecode {
40
42 : n(n0), matrix(m) {}
43
44 IntDistance::Data::Data(int n0, std::function<int(int,int)> f)
45 : n(n0), function(std::move(f)) {}
46
48
49 IntDistance::IntDistance(int n, const IntArgs& matrix) {
50 Int::Limits::positive(n,"IntDistance");
51 if (static_cast<long long int>(n)*n != matrix.size())
52 throw Int::ArgumentSizeMismatch("IntDistance");
53 for (int a=0; a<n; a++)
54 for (int b=0; b<n; b++) {
55 Int::Limits::nonnegative(matrix[a*n+b],"IntDistance");
56 if (((a == b) && (matrix[a*n+b] != 0)) ||
57 (matrix[a*n+b] != matrix[b*n+a]))
58 throw Int::IllegalOperation("IntDistance");
59 }
60 object(new Data(n,matrix));
61 }
62
63 IntDistance::IntDistance(int n, std::function<int(int,int)> f) {
64 Int::Limits::positive(n,"IntDistance");
65 if (!f)
66 throw InvalidFunction("IntDistance");
67 object(new Data(n,std::move(f)));
68 }
69
70}
71
72namespace Gecode { namespace Int { namespace MinDistance {
73
75 void check(const IntVarArgs& x, MinDistancePropKind kind) {
76 if (x.size() < 2)
77 throw TooFewArguments("Int::minimum_distance");
78 if ((kind != MDP_DECOMPOSED) && (kind != MDP_SINGLE))
79 throw IllegalOperation("Int::minimum_distance");
80 Limits::nonnegative(static_cast<long long int>(x.size())*(x.size()-1)/2,
81 "Int::minimum_distance");
82 }
83
86 const IntDistance& d, const IntSharedArray& r,
88 ViewArray<IntView> views(home,x);
89 for (int i=0; i<views.size(); i++) {
90 GECODE_ME_CHECK(views[i].gq(home,0));
91 GECODE_ME_CHECK(views[i].le(home,d.size()));
92 }
93 GECODE_ME_CHECK(z.gq(home,0));
94 if (views.assigned())
95 return assigned(home,views,z,d,r);
96 if (kind == MDP_DECOMPOSED) {
97 for (int i=0; i<views.size(); i++)
98 for (int j=i+1; j<views.size(); j++)
99 GECODE_ES_CHECK(Pair::post(home,views[i],views[j],z,d,
100 requirement(r,views.size(),i,j)));
101 GECODE_ES_CHECK(Finalize::post(home,views,z,d,r));
102 } else {
103 GECODE_ES_CHECK(AdvisorForward::post(home,views,z,d,r));
104 }
105 if (ba(ipl) != IPL_BASIC)
106 GECODE_ES_CHECK(Matching::post(home,views,z,d));
107 return ES_OK;
108 }
109
110}}}
111
112namespace Gecode {
113
114 void minimum_distance(Home home, const IntVarArgs& x, IntVar z,
115 const IntDistance& d, IntPropLevel ipl,
116 MinDistancePropKind kind) {
120 GECODE_ES_FAIL(Int::MinDistance::post(home,x,z,d,r,kind,ipl));
121 }
122
123 void minimum_distance(Home home, const IntVarArgs& x, IntVar z,
124 const IntDistance& d, const IntArgs& r,
127 if (static_cast<long long int>(x.size())*x.size() != r.size())
128 throw Int::ArgumentSizeMismatch("Int::minimum_distance");
129 for (int i=0; i<x.size(); i++)
130 for (int j=0; j<x.size(); j++) {
131 Int::Limits::nonnegative(r[i*x.size()+j],"Int::minimum_distance");
132 if (((i == j) && (r[i*x.size()+j] != 0)) ||
133 (r[i*x.size()+j] != r[j*x.size()+i]))
134 throw Int::IllegalOperation("Int::minimum_distance");
135 }
137 IntSharedArray requirements(r);
138 GECODE_ES_FAIL(Int::MinDistance::post(home,x,z,d,requirements,kind,ipl));
139 }
140
141}
142
143// STATISTICS: int-post
int size(void) const
Return size of array (number of elements).
Definition array.hpp:1606
Home class for posting propagators
Definition core.hpp:863
Passing integer arguments.
Definition int.hh:653
Shared matrix or callable.
Definition int.hh:3359
Data(int n, const IntArgs &matrix)
const int n
Number of sites.
Definition int.hh:3361
const IntSharedArray matrix
Row-major matrix, empty for a callable.
Definition int.hh:3362
const std::function< int(int, int)> function
Computed distance.
Definition int.hh:3363
Shared distances between indexed sites.
Definition int.hh:3356
IntDistance(int n, const IntArgs &matrix)
Copy and validate an n by n row-major distance matrix.
unsigned int size(void) const
Return size (cardinality) of set.
Passing integer variables.
Definition int.hh:681
Integer variables.
Definition int.hh:390
Exception: Arguments are of different size
Definition exception.hpp:73
Exception: Illegal operation passed as argument
Integer view for integer variables.
Definition view.hpp:129
ModEvent gq(Space &home, int n)
Restrict domain values to be greater or equal than n.
Definition int.hpp:139
static ExecStatus post(Home home, ViewArray< IntView > &x, IntView z, const IntDistance &d, const IntSharedArray &r)
Post propagator.
Definition prop.hpp:315
static ExecStatus post(Home home, ViewArray< IntView > &x, IntView z, const IntDistance &d, const IntSharedArray &r)
Post propagator.
Definition prop.hpp:236
static ExecStatus post(Home home, ViewArray< IntView > &x, IntView z, const IntDistance &d)
Post propagator.
Definition prop.hpp:454
static ExecStatus post(Home home, IntView x0, IntView x1, IntView x2, const IntDistance &d, int r)
Post propagator.
Definition prop.hpp:165
Exception: Too few arguments available in argument array
Definition exception.hpp:66
Exception: invalid function
SharedHandle::Object * object(void) const
Access to the shared object.
View arrays.
Definition array.hpp:255
#define GECODE_POST
Check for failure in a constraint post function.
Definition macros.hpp:40
#define GECODE_ME_CHECK(me)
Check whether modification event me is failed, and forward failure.
Definition macros.hpp:52
#define GECODE_ES_FAIL(es)
Check whether execution status es is failed, and fail space home.
Definition macros.hpp:103
#define GECODE_ES_CHECK(es)
Check whether execution status es is failed or subsumed, and forward failure or subsumption.
Definition macros.hpp:91
IntPropLevel
Propagation levels for integer propagators.
Definition int.hh:1274
@ IPL_BASIC
Use basic propagation algorithm.
Definition int.hh:1281
void positive(int n, const char *l)
Check whether n is in range and strictly positive, otherwise throw out of limits with information l.
Definition limits.hpp:57
void nonnegative(int n, const char *l)
Check whether n is in range and nonnegative, otherwise throw out of limits with information l.
Definition limits.hpp:68
Minimum-distance propagators over indexed sites.
void check(const IntVarArgs &x, MinDistancePropKind kind)
Validate the organization and number of positions.
ExecStatus assigned(Space &home, const ViewArray< IntView > &x, IntView z, const IntDistance &d, const IntSharedArray &r)
Validate and bind a complete assignment.
Definition prop.hpp:77
ExecStatus post(Home home, const IntVarArgs &x, IntView z, const IntDistance &d, const IntSharedArray &r, MinDistancePropKind kind, IntPropLevel ipl)
Shared posting for the two public overloads.
int requirement(const IntSharedArray &r, int n, int i, int j)
Inclusive requirement, with an empty matrix denoting all zeroes.
Definition prop.hpp:39
Finite domain integers.
Definition lastval.hh:52
Gecode toplevel namespace
SharedArray< int > IntSharedArray
Arrays of integers that can be shared among several element constraints.
Definition int.hh:1813
IntPropLevel ba(IntPropLevel ipl)
Extract basic or advanced from propagation level.
Definition ipl.hpp:43
void minimum_distance(Home home, const IntVarArgs &x, IntVar z, const IntDistance &d, IntPropLevel ipl=IPL_DEF, MinDistancePropKind kind=MDP_SINGLE)
Post .
ExecStatus
Definition core.hpp:479
@ ES_OK
Execution is okay.
Definition core.hpp:483
MinDistancePropKind
Organization of forward-bound minimum-distance propagation.
Definition int.hh:3395