ibex::Adjacency Class Reference
[Contractors]

Adjacency of a contractor list (CSP). More...

#include <IbexAdjacency.h>

List of all members.

Public Member Functions
	Adjacency (const ContractorList &csp, const Space &space)
	Adjacency (const Adjacency &)
	~Adjacency ()
int	nb_ctr () const
int	nb_var () const
int	nb_upr () const
int	nb_epr () const
int	nb_syb () const
int	ctr_nb_vars (int ctr) const
int	ctr_nb_occ_var (int ctr, int var) const
int	ctr_ith_var (int ctr, int i) const
int	var_nb_ctrs (int var) const
int	var_ith_ctr (int var, int i) const
int	ctr_nb_uprs (int ctr) const
int	ctr_nb_occ_upr (int ctr, int upr) const
int	ctr_ith_upr (int ctr, int i) const
int	upr_nb_ctrs (int upr) const
int	upr_ith_ctr (int upr, int i) const
int	ctr_nb_eprs (int ctr) const
int	ctr_nb_occ_epr (int ctr, int epr) const
int	ctr_ith_epr (int ctr, int i) const
int	epr_nb_ctrs (int epr) const
int	epr_ith_ctr (int epr, int i) const
int	ctr_nb_sybs (int ctr) const
int	ctr_nb_occ_syb (int ctr, int syb) const
int	ctr_ith_syb (int ctr, int i) const
int	syb_nb_ctrs (int syb) const
int	syb_ith_ctr (int syb, int i) const
void	init (CoupleQueue &q) const
void	propagate (CoupleQueue &q, int var) const
void	propagate (CoupleQueue &q, int ctr, int var) const
Friends
std::ostream &	operator<< (std::ostream &os, const Adjacency &a)

---

Detailed Description

Adjacency of a contractor list (CSP).

This class contains the adjacency (incidence graph) of contractors (e.g., CSP) typically used by propagation-based algorithms. An Adjacency allows to know whether an entity is impacted by a contractor or not. As an example, it allows to know whether an equation (with any associated contractor) contains a variable.

The space complexity is in O(n*m) where n is the number of entities and m the number of contractors. For efficiency reasons, both an adjacency table and adjacency lists are built.

Since one may rather think in terms of "CSP" and "constraints" rather than "contractors, we shall switch to the former more intuitive terminology in the documentation of this class.

Author:

Gilles Chabert

Date:

March 2007

---

Constructor & Destructor Documentation

ibex::Adjacency::Adjacency	(	const ContractorList &	csp,
		const Space &	space
	)

Build the adjacency of a list of contractors.

In case one of the components of csp has a different space than space: if an entity belongs to the component's space but not to space, it will be ignored. This means that no contractor will be considered to impact this entity (so that, e.g., the value returned by nb_var() will match the number of variables in space).

ibex::Adjacency::Adjacency

(

const Adjacency &

a

)

Duplicate the adjacency.

ibex::Adjacency::~Adjacency

(

)

Delete the adjacency.

---

Member Function Documentation

int ibex::Adjacency::nb_ctr

(

)

const [inline]

Return the number of constraints.

int ibex::Adjacency::nb_var

(

)

const [inline]

Return the number of variables in the CSP.

int ibex::Adjacency::nb_upr

(

)

const [inline]

Return the number of univ-params in the CSP.

int ibex::Adjacency::nb_epr

(

)

const [inline]

Return the number of exist-params in the CSP.

int ibex::Adjacency::nb_syb

(

)

const [inline]

Return the number of symbolic constants in the CSP.

int ibex::Adjacency::ctr_nb_vars

(

int

ctr

)

const [inline]

Return the number of variables in a constraint ctr.

Return values:

n

- a value that satisfies 0 <= n <= nb_var().

Precondition:

0 <= ctr < nb_ctr().

int ibex::Adjacency::ctr_nb_occ_var	(	int	ctr,
		int	var
	)			const [inline]

Return the number of occurrences of a variable var in a constraint ctr.

Return values:

n

- a value that satisfies 0 <= n <= nb_var() (0 if var doest not appear in ctr).

Precondition:

0 <= ctr < nb_ctr().
0 <= var < nb_var().

int ibex::Adjacency::ctr_ith_var	(	int	ctr,
		int	i
	)			const [inline]

Return the i th variable in a constraint ctr.

Return values:

var

- a value that satisfies 0 <= var < nb_var().

Precondition:

0 <= var < nb_var().
0 <= i < ctr_nb_vars (ctr).

int ibex::Adjacency::var_nb_ctrs

(

int

var

)

const [inline]

Return the number of constraints containing a variable var.

Precondition:

0 <= var < nb_var().

Return values:

n

- a value that satisfies 0 <= n <= nb_ctr().

int ibex::Adjacency::var_ith_ctr	(	int	var,
		int	i
	)			const [inline]

Return the i th constraint containing a variable var.

Return values:

ctr

- a value that satisfies 0 <= ctr < nb_ctr().

Precondition:

0 <= var < nb_var().
0 <= i < var_nb_ctrs (var).

int ibex::Adjacency::ctr_nb_uprs

(

int

ctr

)

const [inline]

Return the number of univ parameters in a constraint ctr.

Return values:

n

- a value that satisfies 0 <= n <= nb_upr().

Precondition:

0 <= ctr < nb_ctr().

int ibex::Adjacency::ctr_nb_occ_upr	(	int	ctr,
		int	upr
	)			const [inline]

Return the number of occurrences of a univ parameter upr in a constraint ctr.

Return values:

n

- a value that satisfies 0 <= n <= nb_upr() (0 if upr doest not appear in ctr).

Precondition:

0 <= ctr < nb_ctr().
0 <= upr < nb_upr().

int ibex::Adjacency::ctr_ith_upr	(	int	ctr,
		int	i
	)			const [inline]

Return the i th univ parameter in a constraint ctr.

Return values:

upr

- a value that satisfies 0 <= upr < nb_upr().

Precondition:

0 <= upr < nb_upr().
0 <= i < ctr_nb_uprs (ctr).

int ibex::Adjacency::upr_nb_ctrs

(

int

upr

)

const [inline]

Return the number of constraints containing a univ parameter upr.

Precondition:

0 <= upr < nb_upr().

Return values:

n

- a value that satisfies 0 <= n <= nb_ctr().

int ibex::Adjacency::upr_ith_ctr	(	int	upr,
		int	i
	)			const [inline]

Return the i th constraint containing a univ parameter upr.

Return values:

ctr

- a value that satisfies 0 <= ctr < nb_ctr().

Precondition:

0 <= upr < nb_upr().
0 <= i < upr_nb_ctrs (upr).

int ibex::Adjacency::ctr_nb_eprs

(

int

ctr

)

const [inline]

Return the number of exist parameters in a constraint ctr.

Return values:

n

- a value that satisfies 0 <= n <= nb_epr().

Precondition:

0 <= ctr < nb_ctr().

int ibex::Adjacency::ctr_nb_occ_epr	(	int	ctr,
		int	epr
	)			const [inline]

Return the number of occurrences of an exist parameter epr in a constraint ctr.

Return values:

n

- a value that satisfies 0 <= n <= nb_epr() (0 if epr doest not appear in ctr).

Precondition:

0 <= ctr < nb_ctr().
0 <= epr < nb_epr().

int ibex::Adjacency::ctr_ith_epr	(	int	ctr,
		int	i
	)			const [inline]

Return the i th exist parameter in a constraint ctr.

Return values:

epr

- a value that satisfies 0 <= epr < nb_epr().

Precondition:

0 <= epr < nb_epr().
0 <= i < ctr_nb_eprs (ctr).

int ibex::Adjacency::epr_nb_ctrs

(

int

epr

)

const [inline]

Return the number of constraints containing an exist parameter epr.

Precondition:

0 <= epr < nb_epr().

Return values:

n

- a value that satisfies 0 <= n <= nb_ctr().

int ibex::Adjacency::epr_ith_ctr	(	int	epr,
		int	i
	)			const [inline]

Return the i th constraint containing an exist parameter epr.

Return values:

ctr

- a value that satisfies 0 <= ctr < nb_ctr().

Precondition:

0 <= epr < nb_epr().
0 <= i < epr_nb_ctrs (epr).

int ibex::Adjacency::ctr_nb_sybs

(

int

ctr

)

const [inline]

Return the number of symbolic constants in a constraint ctr.

Return values:

n

- a value that satisfies 0 <= n <= nb_syb().

Precondition:

0 <= ctr < nb_ctr().

int ibex::Adjacency::ctr_nb_occ_syb	(	int	ctr,
		int	syb
	)			const [inline]

Return the number of occurrences of a symbolic constant syb in a constraint ctr.

Return values:

n

- a value that satisfies 0 <= n <= nb_syb() (0 if syb doest not appear in ctr).

Precondition:

0 <= ctr < nb_ctr().
0 <= syb < nb_syb().

int ibex::Adjacency::ctr_ith_syb	(	int	ctr,
		int	i
	)			const [inline]

Return the i th symbolic constant in a constraint ctr.

Return values:

syb

- a value that satisfies 0 <= syb < nb_syb().

Precondition:

0 <= syb < nb_syb().
0 <= i < ctr_nb_sybs (ctr).

int ibex::Adjacency::syb_nb_ctrs

(

int

syb

)

const [inline]

Return the number of constraints containing a symbolic constant syb.

Precondition:

0 <= syb < nb_syb().

Return values:

n

- a value that satisfies 0 <= n <= nb_ctr().

int ibex::Adjacency::syb_ith_ctr	(	int	syb,
		int	i
	)			const [inline]

Return the i th constraint containing a symbolic constant syb.

Return values:

ctr

- a value that satisfies 0 <= ctr < nb_ctr().

Precondition:

0 <= syb < nb_syb().
0 <= i < syb_nb_ctrs (syb).

void ibex::Adjacency::init

(

CoupleQueue &

q

)

const

Initialize a propagation queue by inserting all the possible pairs constraint/variable.

void ibex::Adjacency::propagate	(	CoupleQueue &	q,
		int	var
	)			const [inline]

Push in a propagation queue all the pairs constraint/variable impacted by the reduction of one given variable var.

See also:

ibex::Propagation.

void ibex::Adjacency::propagate	(	CoupleQueue &	q,
		int	ctr,
		int	var
	)			const

Push in a propagation queue all the pairs constraint/variable impacted by the reduction of a variable var by contractor ctr.

Precondition:

The variable var must appear in ctr. Otherwise the behaviour is undefined.

See also:

ibex::Propagation.

---

Friends And Related Function Documentation

std::ostream& operator<<	(	std::ostream &	os,
		const Adjacency &	a
	)			[friend]

Display the internal structure (matrix & tables). For debug purposes only.

---

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

• src/IbexAdjacency.h
• src/IbexAdjacency.cpp