/usr/include/gecode/int/distinct.hh is in libgecode-dev 4.4.0-5.
This file is owned by root:root, with mode 0o644.
The actual contents of the file can be viewed below.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256 257 258 259 260 261 262 263 264 265 266 267 268 269 270 271 272 273 274 275 276 277 278 279 280 281 282 283 284 285 286 287 288 289 290 291 292 293 294 295 296 297 298 299 300 301 302 303 304 305 306 307 308 309 310 311 312 313 | /* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */
/*
* Main authors:
* Christian Schulte <schulte@gecode.org>
* Guido Tack <tack@gecode.org>
*
* Contributing authors:
* Gabor Szokoli <szokoli@gecode.org>
*
* Copyright:
* Christian Schulte, 2002
* Guido Tack, 2004
* Gabor Szokoli, 2003
*
* Last modified:
* $Date: 2011-10-06 17:27:42 +0200 (Thu, 06 Oct 2011) $ by $Author: schulte $
* $Revision: 12423 $
*
* This file is part of Gecode, the generic constraint
* development environment:
* http://www.gecode.org
*
* Permission is hereby granted, free of charge, to any person obtaining
* a copy of this software and associated documentation files (the
* "Software"), to deal in the Software without restriction, including
* without limitation the rights to use, copy, modify, merge, publish,
* distribute, sublicense, and/or sell copies of the Software, and to
* permit persons to whom the Software is furnished to do so, subject to
* the following conditions:
*
* The above copyright notice and this permission notice shall be
* included in all copies or substantial portions of the Software.
*
* THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
* EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
* MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
* NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
* LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
* OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
* WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
*
*/
#ifndef __GECODE_INT_DISTINCT_HH__
#define __GECODE_INT_DISTINCT_HH__
#include <gecode/int.hh>
#include <gecode/int/view-val-graph.hh>
#include <gecode/int/rel.hh>
/**
* \namespace Gecode::Int::Distinct
* \brief %Distinct propagators
*/
namespace Gecode { namespace Int { namespace Distinct {
/**
* \brief Naive value distinct propagator
*
* Eliminates values of assigned views of type \a View.
*
* Requires \code #include <gecode/int/distinct.hh> \endcode
* \ingroup FuncIntProp
*/
template<class View>
class Val : public NaryPropagator<View,PC_INT_VAL> {
protected:
using NaryPropagator<View,PC_INT_VAL>::x;
/// Constructor for posting
Val(Home home, ViewArray<View>& x);
/// Constructor for cloning \a p
Val(Space& home, bool share, Val<View>& p);
public:
/// Copy propagator during cloning
virtual Actor* copy(Space& home, bool share);
/// Perform propagation
virtual ExecStatus propagate(Space& home, const ModEventDelta& med);
/// Post propagator for view array \a x
static ExecStatus post(Home home, ViewArray<View>& x);
};
/**
* \brief Eliminate singletons by naive value propagation
*
* This is actually the propagation algorithm for Distinct::Val.
* It is available as separate function as it is reused for
* both bounds consistent and domain consistent distinct
* propagators.
*
* If \a complete is true, computes fixpoint, otherwise might not
* compute fixpoint. This can be helpful when used together with
* bounds or domain propagation to protect from pathological cases
* which can be handled more efficiently with bounds propagation.
*/
template<class View, bool complete>
ExecStatus prop_val(Space& home, ViewArray<View>&);
/**
* \brief Bounds consistent distinct propagator
*
* The propagator uses staging: first it uses naive value-based
* propagation and only then uses bounds consistent propagation.
* Due to using naive value-based propagation, the propagator
* might actually achieve stronger consistency than just
* bounds consistency.
*
* The algorithm is taken from:
* A. Lopez-Ortiz, C.-G. Quimper, J. Tromp, and P. van Beek.
* A fast and simple algorithm for bounds consistency of the
* alldifferent constraint. IJCAI-2003.
*
* This implementation uses the code that is provided by
* Peter Van Beek:
* http://ai.uwaterloo.ca/~vanbeek/software/software.html
* The code (originally by John Tromp) here has only been slightly modified
* to fit %Gecode (taking idempotent/non-idempotent propagation into account)
* and uses a more efficient layout of datastructures (keeping the number
* of different arrays small).
*
* Requires \code #include <gecode/int/distinct.hh> \endcode
* \ingroup FuncIntProp
*/
template<class View>
class Bnd : public Propagator {
protected:
/// Views on which to perform bounds-propagation
ViewArray<View> x;
/// Views on which to perform value-propagation (subset of \c x)
ViewArray<View> y;
/// Minimum (approximation) of view in \a x
int min_x;
/// Maximum (approximation) of view in \a x
int max_x;
/// Constructor for posting
Bnd(Home home, ViewArray<View>& x);
/// Constructor for cloning \a p
Bnd(Space& home, bool share, Bnd<View>& p);
public:
/// Post propagator for view array \a x
static ExecStatus post(Home home, ViewArray<View>& x);
/// Perform propagation
virtual ExecStatus propagate(Space& home, const ModEventDelta& med);
/**
* \brief Cost function
*
* If in stage for naive value propagation, the cost is
* low linear. Otherwise it is low quadratic.
*/
virtual PropCost cost(const Space& home, const ModEventDelta& med) const;
/// Copy propagator during cloning
virtual Actor* copy(Space& home, bool share);
/// Destructor
virtual size_t dispose(Space& home);
};
/**
* \brief Perform bounds consistent distinct propagation
*
* This is actually the propagation algorithm for Distinct::Bnd.
* It is available as separate function as it is reused for
* both bounds consistent and domain consistent distinct
* propagators.
*/
template<class View>
ExecStatus prop_bnd(Space& home, ViewArray<View>& x, int& min_x, int& max_x);
/**
* \brief Perform bounds consistent distinct propagation
*
* This is actually the propagation algorithm for Distinct::Bnd.
* It is available as separate function as it is reused for
* both bounds consistent and domain consistent distinct
* propagators.
*/
template<class View>
ExecStatus prop_bnd(Space& home, ViewArray<View>& x);
/// View-value graph for propagation
template<class View>
class Graph : public ViewValGraph::Graph<View> {
public:
using ViewValGraph::Graph<View>::view;
using ViewValGraph::Graph<View>::n_view;
using ViewValGraph::Graph<View>::val;
using ViewValGraph::Graph<View>::n_val;
using ViewValGraph::Graph<View>::count;
using ViewValGraph::Graph<View>::scc;
using ViewValGraph::Graph<View>::match;
/// Construct graph as not yet initialized
Graph(void);
/// Initialize graph
ExecStatus init(Space& home, ViewArray<View>& x);
/// Mark edges in graph, return true if pruning is at all possible
bool mark(Space& home);
/// Prune unmarked edges, \a assigned is true if a view got assigned
ExecStatus prune(Space& home, bool& assigned);
/// Synchronize graph with new view domains
bool sync(Space& home);
};
/**
* \brief Propagation controller for domain consistent distinct
*
* The propagation controller provides convenient access to
* performing incremental domain consistent distinct propagation
* so that the routines can be reused easily.
*
* Requires \code #include <gecode/int/distinct.hh> \endcode
* \ingroup FuncIntProp
*/
template<class View>
class DomCtrl {
protected:
/// Propagation is performed on a view-value graph
Graph<View> g;
public:
/// Initialize with non-initialized view-value graph
DomCtrl(void);
/// Check whether a view-value graph is available
bool available(void);
/// Initialize view-value graph for views \a x
ExecStatus init(Space& home, ViewArray<View>& x);
/// Synchronize available view-value graph
ExecStatus sync(Space& home);
/// Perform propagation, \a assigned is true if a view gets assigned
ExecStatus propagate(Space& home, bool& assigned);
};
/**
* \brief Domain consistent distinct propagator
*
* The propagator uses staging: first it uses naive value-based
* propagation and only then uses domain consistent propagation.
*
* The algorithm is taken from:
* Jean-Charles RĂ©gin, A filtering algorithm for constraints
* of difference in CSPs, Proceedings of the Twelfth National
* Conference on Artificial Intelligence, pages 362--367.
* Seattle, WA, USA, 1994.
*
* Requires \code #include <gecode/int/distinct.hh> \endcode
* \ingroup FuncIntProp
*/
template<class View>
class Dom : public NaryPropagator<View,PC_INT_DOM> {
protected:
using NaryPropagator<View,PC_INT_DOM>::x;
/// Propagation controller
DomCtrl<View> dc;
/// Constructor for cloning \a p
Dom(Space& home, bool share, Dom<View>& p);
/// Constructor for posting
Dom(Home home, ViewArray<View>& x);
public:
/// Perform propagation
virtual ExecStatus propagate(Space& home, const ModEventDelta& med);
/**
* \brief Cost function
*
* If in stage for naive value propagation, the cost is
* low linear. Otherwise it is high quadratic.
*/
virtual PropCost cost(const Space& home, const ModEventDelta& med) const;
/// Copy propagator during cloning
virtual Actor* copy(Space& home, bool share);
/// Post propagator for views \a x
static ExecStatus post(Home home, ViewArray<View>& x);
};
/**
* \brief Ternary domain consistent distinct propagator
*
* Requires \code #include <gecode/int/distinct.hh> \endcode
* \ingroup FuncIntProp
*/
template<class View>
class TerDom : public TernaryPropagator<View,PC_INT_DOM> {
protected:
using TernaryPropagator<View,PC_INT_DOM>::x0;
using TernaryPropagator<View,PC_INT_DOM>::x1;
using TernaryPropagator<View,PC_INT_DOM>::x2;
/// Constructor for cloning \a p
TerDom(Space& home, bool share, TerDom<View>& p);
/// Constructor for posting
TerDom(Home home, View x0, View x1, View x2);
public:
/// Perform propagation
virtual ExecStatus propagate(Space& home, const ModEventDelta& med);
/// Copy propagator during cloning
virtual Actor* copy(Space& home, bool share);
/// Post propagator for views \a x
static ExecStatus post(Home home, View x0, View x1, View x2);
};
}}}
#include <gecode/int/distinct/val.hpp>
#include <gecode/int/distinct/bnd.hpp>
#include <gecode/int/distinct/ter-dom.hpp>
#include <gecode/int/distinct/graph.hpp>
#include <gecode/int/distinct/dom-ctrl.hpp>
#include <gecode/int/distinct/dom.hpp>
#endif
// STATISTICS: int-prop
|