Generated on Tue Feb 11 2025 17:33:26 for Gecode by doxygen 1.12.0

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 Actorcopy (Space &home)
 Copy propagator during cloning.
 
virtual size_t dispose (Space &home)
 Destructor.
 
- Public Member Functions inherited from Gecode::Propagator
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.
 
- Public Member Functions inherited from Gecode::Actor
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 Public Member Functions inherited from Gecode::Actor
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.
 
Propagatorfwd (void) const
 Return forwarding pointer during copying.
 
Kernel::GPI::Infogpi (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

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

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

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

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: