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 void	reschedule (Space &home)
	Schedule function.
virtual Actor *	copy (Space &home)
	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, 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 125 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 38 of file bnd.hpp.

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

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 461 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 381 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 78 of file bnd.hpp.

template<class View >

void Gecode::Int::Distinct::Bnd< View >::reschedule

(

Space &

home

)

[inline, virtual]

Schedule function.

Implements Gecode::Propagator.

Definition at line 87 of file bnd.hpp.

template<class View >

Actor * Gecode::Int::Distinct::Bnd< View >::copy

(

Space &

home

)

[inline, virtual]

Copy propagator during cloning.

Implements Gecode::Actor.

Definition at line 72 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 56 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 128 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 130 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 132 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 134 of file distinct.hh.

---

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

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