Gecode::Int::Distinct::Bnd< View > Class Template Reference
Other available functionality » Integer propagators

Bounds consistent distinct propagator. More...

`#include <distinct.hh>`

## Public Member Functions

virtual ExecStatus | propagate (Space &home, const ModEventDelta &med)
| Perform propagation.
virtual PropCost | cost (const Space &home, const ModEventDelta &med) const
| Cost function.
virtual void | reschedule (Space &home)
| Schedule function.
virtual Actor * | copy (Space &home)
| Copy propagator during cloning.
virtual size_t | dispose (Space &home)
| Destructor.
ModEventDelta | modeventdelta (void) const
| Return the modification event delta.
virtual ExecStatus | advise (Space &home, Advisor &a, const Delta &d)
| Advise function.
virtual void | advise (Space &home, Advisor &a)
| Run advisor a to be run on failure in failed space.
double | afc (void) const
| Return the accumlated failure count.
unsigned int | id (void) const
| Return propagator id.
PropagatorGroup | group (void) const
| Return group propagator belongs to.
void | group (PropagatorGroup g)
| Add propagator to group g.
bool | disabled (void) const
| Whether propagator is currently disabled.
virtual | ~Actor (void)
| To avoid warnings.

## Static Public Member Functions

static ExecStatus | post (Home home, ViewArray< View > &x)
| Post propagator for view array x.
static void * | operator new (size_t s, Space &home)
| Allocate memory from space.
static void | operator delete (void *p, Space &home)
| No-op for exceptions.
static void * | operator new (size_t s)
| Not used.
static void | operator delete (void *p)
| Not used.

## Protected Member Functions

| Bnd (Home home, ViewArray< View > &x)
| Constructor for posting.
| Bnd (Space &home, Bnd< View > &p)
| Constructor for cloning p.
Protected Member Functions inherited from Gecode::Propagator
| Propagator (Home home)
| Constructor for posting.
| Propagator (Space &home, Propagator &p)
| Constructor for cloning p.
Propagator * | fwd (void) const
| Return forwarding pointer during copying.
Kernel::GPI::Info & | gpi (void)
| Provide access to global propagator information.

## Protected Attributes

ViewArray< View > | x
| Views on which to perform bounds-propagation.
ViewArray< View > | y
| Views on which to perform value-propagation (subset of `x`).
int | min_x
| Minimum (approximation) of view in x.
int | max_x
| Maximum (approximation) of view in x.

## Detailed Description

template<class View>
class Gecode::Int::Distinct::Bnd< View >

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

#include <gecode/int/distinct.hh>
distinct.hh

Definition at line 152 of file distinct.hh.

## Constructor & Destructor Documentation

## Bnd() [1/2]

template<class View>

Gecode::Int::Distinct::Bnd< View >::Bnd | ( | Home | home,
|  | ViewArray< View > & | x )

inline protected

Constructor for posting.

Definition at line 38 of file bnd.hpp.

## Bnd() [2/2]

template<class View>

Gecode::Int::Distinct::Bnd< View >::Bnd | ( | Space & | home,
|  | Bnd< View > & | p )

inline protected

Constructor for cloning p.

Definition at line 64 of file bnd.hpp.

## Member Function Documentation

## post()

template<class View>

ExecStatus Gecode::Int::Distinct::Bnd< View >::post | ( | Home | home,
|  | ViewArray< View > & | x )

static

Post propagator for view array x.

Definition at line 476 of file bnd.hpp.

## propagate()

template<class View>

ExecStatus Gecode::Int::Distinct::Bnd< View >::propagate | ( | Space & | home,
|  | const ModEventDelta & | med )

virtual

Perform propagation.

Implements Gecode::Propagator.

Definition at line 381 of file bnd.hpp.

## cost()

template<class View>

PropCost Gecode::Int::Distinct::Bnd< View >::cost | ( | const Space & | home,
|  | const ModEventDelta & | med ) const

virtual

Cost function.

If in stage for naive value propagation, the cost is low linear. Otherwise it is low quadratic.

Implements Gecode::Propagator.

Definition at line 78 of file bnd.hpp.

## reschedule()

template<class View>

void Gecode::Int::Distinct::Bnd< View >::reschedule | ( | Space & | home | ) |

virtual

Schedule function.

Implements Gecode::Propagator.

Definition at line 87 of file bnd.hpp.

## copy()

template<class View>

Actor * Gecode::Int::Distinct::Bnd< View >::copy | ( | Space & | home | ) |

virtual

Copy propagator during cloning.

Implements Gecode::Actor.

Definition at line 72 of file bnd.hpp.

## dispose()

template<class View>

size_t Gecode::Int::Distinct::Bnd< View >::dispose | ( | Space & | home | ) |

inline virtual

Destructor.

Reimplemented from Gecode::Actor.

Definition at line 56 of file bnd.hpp.

## Member Data Documentation

## x

template<class View>

ViewArray<View> Gecode::Int::Distinct::Bnd< View >::x

protected

Views on which to perform bounds-propagation.

Definition at line 155 of file distinct.hh.

## y

template<class View>

ViewArray<View> Gecode::Int::Distinct::Bnd< View >::y

protected

Views on which to perform value-propagation (subset of `x`).

Definition at line 157 of file distinct.hh.

## min_x

template<class View>

int Gecode::Int::Distinct::Bnd< View >::min_x

protected

Minimum (approximation) of view in x.

Definition at line 159 of file distinct.hh.

## max_x

template<class View>

int Gecode::Int::Distinct::Bnd< View >::max_x

protected

Maximum (approximation) of view in x.

Definition at line 161 of file distinct.hh.

The documentation for this class was generated from the following files:

- gecode/int/distinct.hh
- gecode/int/distinct/bnd.hpp