Generated on Sat Feb 7 2015 02:01:47 for Gecode by doxygen 1.8.9.1
Gecode::Int::Distinct::Bnd< View > Class Template Reference

Bounds consistent distinct propagator. More...

#include <distinct.hh>

Public Member Functions

virtual ExecStatus propagate (Space &home, const ModEventDelta &med)
 Perform propagation. More...
 
virtual PropCost cost (const Space &home, const ModEventDelta &med) const
 Cost function. More...
 
virtual Actorcopy (Space &home, bool share)
 Copy propagator during cloning. More...
 
virtual size_t dispose (Space &home)
 Destructor. More...
 
- Public Member Functions inherited from Gecode::Propagator
ModEventDelta modeventdelta (void) const
 Return the modification event delta. More...
 
virtual ExecStatus advise (Space &home, Advisor &a, const Delta &d)
 Advise function. More...
 
double afc (const Space &home) const
 Return the accumlated failure count. More...
 
- Public Member Functions inherited from Gecode::Actor

Static Public Member Functions

static ExecStatus post (Home home, ViewArray< View > &x)
 Post propagator for view array x. More...
 
- Static Public Member Functions inherited from Gecode::Actor
static void * operator new (size_t s, Space &home)
 Allocate memory from space. More...
 
static void operator delete (void *p, Space &home)
 No-op for exceptions. More...
 

Protected Member Functions

 Bnd (Home home, ViewArray< View > &x)
 Constructor for posting. More...
 
 Bnd (Space &home, bool share, Bnd< View > &p)
 Constructor for cloning p. More...
 
- Protected Member Functions inherited from Gecode::Propagator
 Propagator (Home home)
 Constructor for posting. More...
 
 Propagator (Space &home, bool share, Propagator &p)
 Constructor for cloning p. More...
 
Propagatorfwd (void) const
 Return forwarding pointer during copying. More...
 

Protected Attributes

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

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

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 
)
inlineprotected

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 
)
inlineprotected

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 
)
static

Post propagator for view array x.

Definition at line 459 of file bnd.hpp.

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

Perform propagation.

Implements Gecode::Propagator.

Definition at line 379 of file bnd.hpp.

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 82 of file bnd.hpp.

template<class View >
Actor * Gecode::Int::Distinct::Bnd< View >::copy ( Space home,
bool  share 
)
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)
inlinevirtual

Destructor.

Reimplemented from Gecode::Actor.

Definition at line 60 of file bnd.hpp.

Member Data Documentation

template<class View>
ViewArray<View> 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<View> 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: