Generated on Thu Mar 22 10:39:56 2012 for Gecode by doxygen 1.6.3

Gecode::Int::Distinct::Bnd< View > Class Template Reference [Integer propagators]

Bounds consistent distinct propagator. More...

`#include <distinct.hh>`

List of all members.

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 Actorcopy (Space &home, bool share)
Copy propagator during cloning.
virtual size_t dispose (Space &home)
Destructor.

Static Public Member Functions

static ExecStatus post (Home home, ViewArray< View > &x)
Post propagator for view array x.

Protected Member Functions

Bnd (Home home, ViewArray< View > &x)
Constructor for posting.
Bnd (Space &home, bool share, Bnd< View > &p)
Constructor for cloning p.

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>
```

Definition at line 129 of file distinct.hh.

Constructor & Destructor Documentation

template<class View >
 Gecode::Int::Distinct::Bnd< View >::Bnd ( Home home, ViewArray< View > & x ) ` [inline, protected]`

Constructor for posting.

Definition at line 42 of file bnd.hpp.

template<class View >
 Gecode::Int::Distinct::Bnd< View >::Bnd ( Space & home, bool share, Bnd< View > & p ) ` [inline, protected]`

Constructor for cloning p.

Definition at line 68 of file bnd.hpp.

Member Function Documentation

template<class View >
 ExecStatus Gecode::Int::Distinct::Bnd< View >::post ( Home home, ViewArray< View > & x ) ` [inline, static]`

Post propagator for view array x.

Definition at line 433 of file bnd.hpp.

template<class View >
 ExecStatus Gecode::Int::Distinct::Bnd< View >::propagate ( Space & home, const ModEventDelta & med ) ` [inline, virtual]`

Perform propagation.

Implements Gecode::Propagator.

Definition at line 355 of file bnd.hpp.

template<class View >
 PropCost Gecode::Int::Distinct::Bnd< View >::cost ( const Space & home, const ModEventDelta & med ) const` [inline, 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 82 of file bnd.hpp.

template<class View >
 Actor * Gecode::Int::Distinct::Bnd< View >::copy ( Space & home, bool share ) ` [inline, virtual]`

Copy propagator during cloning.

Implements Gecode::Actor.

Definition at line 76 of file bnd.hpp.

template<class View >
 size_t Gecode::Int::Distinct::Bnd< View >::dispose ( Space & home ) ` [inline, virtual]`

Destructor.

Reimplemented from Gecode::Actor.

Definition at line 60 of file bnd.hpp.

Member Data Documentation

template<class View>
 ViewArray Gecode::Int::Distinct::Bnd< View >::x` [protected]`

Views on which to perform bounds-propagation.

Definition at line 132 of file distinct.hh.

template<class View>
 ViewArray Gecode::Int::Distinct::Bnd< View >::y` [protected]`

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

Definition at line 134 of file distinct.hh.

template<class View>
 int Gecode::Int::Distinct::Bnd< View >::min_x` [protected]`

Minimum (approximation) of view in x.

Definition at line 136 of file distinct.hh.

template<class View>
 int Gecode::Int::Distinct::Bnd< View >::max_x` [protected]`

Maximum (approximation) of view in x.

Definition at line 138 of file distinct.hh.

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