Generated on for Gecode by doxygen 1.18.0
min-distance.hh
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#ifndef GECODE_INT_MIN_DISTANCE_HH
35#define GECODE_INT_MIN_DISTANCE_HH
36
37#include <gecode/int.hh>
38
39#include <algorithm>
40
51namespace Gecode { namespace Int { namespace MinDistance {
52
54 struct PairCache {
55 int a;
56 int b;
57 int upper;
58 };
59
66 class Pair
67 : public MixTernaryPropagator<IntView,PC_INT_DOM,IntView,PC_INT_DOM,
68 IntView,PC_INT_BND> {
69 protected:
73 int r;
75 Pair(Home home, IntView x0, IntView y0, IntView z0,
76 const IntDistance& d0, int r0);
78 Pair(Space& home, Pair& p);
79 public:
82 const IntDistance& d, int r);
84 virtual Actor* copy(Space& home);
86 virtual PropCost cost(const Space&, const ModEventDelta&) const;
88 virtual ExecStatus propagate(Space& home, const ModEventDelta&);
90 virtual size_t dispose(Space& home);
91 };
92
100 : public MixNaryOnePropagator<IntView,PC_INT_DOM,IntView,PC_INT_BND> {
101 protected:
108 const IntDistance& d0, const IntSharedArray& r0);
110 Finalize(Space& home, Finalize& p);
111 public:
114 const IntDistance& d, const IntSharedArray& r);
116 virtual Actor* copy(Space& home);
118 virtual PropCost cost(const Space&, const ModEventDelta&) const;
120 virtual ExecStatus propagate(Space& home, const ModEventDelta&);
122 virtual size_t dispose(Space& home);
123 };
124
131 class AdvisorForward : public Propagator {
132 protected:
134 class XAdvisor : public Advisor {
135 public:
137 int index;
139 XAdvisor(Space& home, Propagator& p, Council<XAdvisor>& c, int i);
141 XAdvisor(Space& home, XAdvisor& a);
142 };
143
163 const IntDistance& d0, const IntSharedArray& r0);
166 public:
169 const IntDistance& d, const IntSharedArray& r);
171 virtual Actor* copy(Space& home);
173 virtual PropCost cost(const Space&, const ModEventDelta&) const;
175 virtual void reschedule(Space& home);
177 virtual ExecStatus advise(Space&, Advisor& a, const Delta&);
179 virtual ExecStatus propagate(Space& home, const ModEventDelta&);
181 virtual size_t dispose(Space& home);
182 };
183
191 : public MixNaryOnePropagator<IntView,PC_INT_DOM,IntView,PC_INT_BND> {
192 protected:
197 const IntDistance& d0);
199 Matching(Space& home, Matching& p);
201 bool refuted(int* sites, int n, bool* matched, int threshold) const;
202 public:
205 const IntDistance& d);
207 virtual Actor* copy(Space& home);
209 virtual PropCost cost(const Space&, const ModEventDelta&) const;
211 virtual ExecStatus propagate(Space& home, const ModEventDelta&);
213 virtual size_t dispose(Space& home);
214 };
215
216}}}
217
219
220#endif
221
222// STATISTICS: int-prop
Advisor(Space &home, Propagator &p, Council< A > &c)
Constructor for creation.
Definition core.hpp:4060
friend class Council
Definition core.hpp:1310
Generic domain change information to be supplied to advisors.
Definition core.hpp:209
Home class for posting propagators
Definition core.hpp:863
Shared distances between indexed sites.
Definition int.hh:3356
Integer view for integer variables.
Definition view.hpp:129
XAdvisor(Space &home, Propagator &p, Council< XAdvisor > &c, int i)
Constructor for creation.
Definition prop.hpp:277
IntSharedArray r
Shared pair requirements.
Council< XAdvisor > council
Domain advisors.
Support::BitSetBase dirty
Positions changed since the last fixpoint.
AdvisorForward(Home home, ViewArray< IntView > &x0, IntView z0, const IntDistance &d0, const IntSharedArray &r0)
Constructor for posting.
Definition prop.hpp:286
int last_min
Objective lower bound at the last fixpoint.
virtual ExecStatus advise(Space &, Advisor &a, const Delta &)
Record a changed selected-site domain.
Definition prop.hpp:341
static ExecStatus post(Home home, ViewArray< IntView > &x, IntView z, const IntDistance &d, const IntSharedArray &r)
Post propagator.
Definition prop.hpp:315
virtual Actor * copy(Space &home)
Copy propagator during cloning.
Definition prop.hpp:322
ViewArray< IntView > x
Selected sites.
bool z_shared
Whether the objective shares a selected-site variable.
virtual size_t dispose(Space &home)
Cancel subscriptions and dispose stored data.
Definition prop.hpp:407
PairCache * cache
Pair maxima and witnesses.
virtual PropCost cost(const Space &, const ModEventDelta &) const
Cost function.
Definition prop.hpp:327
virtual void reschedule(Space &home)
Reschedule propagation.
Definition prop.hpp:333
virtual ExecStatus propagate(Space &home, const ModEventDelta &)
Perform propagation.
Definition prop.hpp:347
static ExecStatus post(Home home, ViewArray< IntView > &x, IntView z, const IntDistance &d, const IntSharedArray &r)
Post propagator.
Definition prop.hpp:236
virtual ExecStatus propagate(Space &home, const ModEventDelta &)
Perform propagation.
Definition prop.hpp:253
IntSharedArray r
Shared pair requirements.
virtual size_t dispose(Space &home)
Cancel subscriptions and dispose shared data.
Definition prop.hpp:269
virtual PropCost cost(const Space &, const ModEventDelta &) const
Cost function.
Definition prop.hpp:248
virtual Actor * copy(Space &home)
Copy propagator during cloning.
Definition prop.hpp:243
Finalize(Home home, ViewArray< IntView > &x, IntView z, const IntDistance &d0, const IntSharedArray &r0)
Constructor for posting.
Definition prop.hpp:223
IntDistance d
Shared distances.
virtual size_t dispose(Space &home)
Cancel subscriptions and dispose shared data.
Definition prop.hpp:509
IntDistance d
Shared distances.
virtual PropCost cost(const Space &, const ModEventDelta &) const
Cost function.
Definition prop.hpp:467
bool refuted(int *sites, int n, bool *matched, int threshold) const
Whether a greedy conflict matching refutes the threshold.
Definition prop.hpp:435
Matching(Home home, ViewArray< IntView > &x, IntView z, const IntDistance &d0)
Constructor for posting.
Definition prop.hpp:423
virtual Actor * copy(Space &home)
Copy propagator during cloning.
Definition prop.hpp:462
virtual ExecStatus propagate(Space &home, const ModEventDelta &)
Perform propagation.
Definition prop.hpp:472
static ExecStatus post(Home home, ViewArray< IntView > &x, IntView z, const IntDistance &d)
Post propagator.
Definition prop.hpp:454
IntDistance d
Shared distances.
virtual Actor * copy(Space &home)
Copy propagator during cloning.
Definition prop.hpp:179
virtual PropCost cost(const Space &, const ModEventDelta &) const
Cost function.
Definition prop.hpp:184
virtual ExecStatus propagate(Space &home, const ModEventDelta &)
Perform propagation.
Definition prop.hpp:189
static ExecStatus post(Home home, IntView x0, IntView x1, IntView x2, const IntDistance &d, int r)
Post propagator.
Definition prop.hpp:165
virtual size_t dispose(Space &home)
Cancel subscriptions and dispose shared data.
Definition prop.hpp:214
Pair(Home home, IntView x0, IntView y0, IntView z0, const IntDistance &d0, int r0)
Constructor for posting.
Definition prop.hpp:150
int r
Inclusive pair requirement.
Propagation cost.
Definition core.hpp:493
friend class Space
Definition core.hpp:1075
friend class Advisor
Definition core.hpp:1077
friend class Council
Definition core.hpp:1078
Propagator(Home home)
Constructor for posting.
Definition core.hpp:3707
Basic bitset support.
View arrays.
Definition array.hpp:255
int ModEventDelta
Modification event deltas.
Definition core.hpp:94
Minimum-distance propagators over indexed sites.
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
ExecStatus
Definition core.hpp:479
Pair maximum and its witness.
int b
Site at the second endpoint.
int a
Site at the first endpoint.
int upper
Maximum distance between the endpoint domains.