ibex::Propagation Class Reference
[Contractors]

Propagation contractor. More...

#include <IbexPropagation.h>

Inheritance diagram for ibex::Propagation:

List of all members.

Public Member Functions
	Propagation (const vector< const Contractor * > &vec, Space &space, REAL ratio=default_ratio, bool incremental=false)
	Propagation (const Propagation &p)
virtual Propagation *	copy () const
bool	contract (int start)
virtual void	contract ()
Public Attributes
const REAL	ratio
const bool	incremental
Static Public Attributes
static const REAL	default_ratio = __IBEX_DEFAULT_RATIO_PROPAG

---

Detailed Description

Propagation contractor.

This class is an implementation of the classical interval variant of the AC3 constraint propagation algorithm.

• Space complexity (constructor) : O(n*m), where n is the number of variables, m the number of constraints.
• Time complexity (contraction) : O(m*d²), where d is 1/ratio .

Author:

Gilles Chabert, Bertrand Neveu

Date:

March 2007

---

Constructor & Destructor Documentation

ibex::Propagation::Propagation	(	const vector< const Contractor * > &	vec,
		Space &	space,
		REAL	ratio = default_ratio,
		bool	incremental = false
	)

Create a AC3-like propagation with a list of contractors.

Parameters:

	vec	- The list of contractors.
	space	- the space for this contractor
	ratio	(optional) - Criterion for stopping propagation. If a projection does not remove more that ratio times the diameter of a variable domain, then this reduction is not propagated. The default value is default_ratio.
	incremental	(optional) - This parameter is only used when contraction is called with a Indicators structure. If set to true, only the pairs (var,ctr) where var is the impacted variable are pushed in the queue. If set to false, all the pairs are pushed in the queue. Default value is false.

See also:

ibex::Contractor::contract(Cell& cell, const Contractor::Indicators& p) { ibex::Contractor::contract(Space& space, const Contractor::Indicators& p), ibex::Contractor::contract(const Contractor::Indicators& p)

ibex::Propagation::Propagation

(

const Propagation &

p

)

Duplicate this instance (space are all passed by reference).

---

Member Function Documentation

virtual Propagation* ibex::Propagation::copy

(

)

const [inline, virtual]

Implement the contractor abstract copy.

Implements ibex::Contractor.

Reimplemented in ibex::Box, and ibex::HC4.

bool ibex::Propagation::contract

(

int

start

)

Enforces propagation (e.g.: HC4 or BOX) fitering.

Parameters:

start

- The variable to start propagation with. Set this parameter to ALL_VARS if all the variables must be considered.

Returns:

true if the box was significantly reduced, i.e., if at least one domain reduction has triggered propagation (i.e., has pushed some pair (var,ctr) back into the queue).

Exceptions:

ibex::UnfeasibilityException

- if inconsistency is detected.

void ibex::Propagation::contract

(

)

[virtual]

Applies contraction (taking into account indicators, if any). If incremental is true and the impact field of p is a specific variable, then propagation will start from this variable only (instead of from all the variables).

See also:

contract(int).

Implements ibex::Contractor.

---

Member Data Documentation

const REAL ibex::Propagation::ratio

Ratio (see constructor for details).

const bool ibex::Propagation::incremental

Queue initialization mode (see constructor for details).

const REAL ibex::Propagation::default_ratio = __IBEX_DEFAULT_RATIO_PROPAG [static]

Default ratio used by propagation, set to 0.1.

---

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

• src/IbexPropagation.h
• src/IbexPropagation.cpp