A linear equality or inequality. More...

#include <ppl.hh>

Public Types
enum	Type { EQUALITY, NONSTRICT_INEQUALITY, STRICT_INEQUALITY }
	The constraint type. More...

typedef Expression_Hide_Last< Linear_Expression >	expr_type
	The type of the (adapted) internal expression.

Public Member Functions
	Constraint (Representation r=default_representation)
	Constructs the constraint.

	Constraint (const Constraint &c)
	Ordinary copy constructor. More...

	Constraint (const Constraint &c, dimension_type space_dim)
	Copy constructor with given size. More...

	Constraint (const Constraint &c, Representation r)
	Copy constructor with given representation.

	Constraint (const Constraint &c, dimension_type space_dim, Representation r)
	Copy constructor with given size and representation.

	Constraint (const Congruence &cg, Representation r=default_representation)
	Copy-constructs from equality congruence `cg`. More...

	~Constraint ()
	Destructor.

Representation	representation () const
	Returns the current representation of *this.

void	set_representation (Representation r)
	Converts *this to the specified representation.

Constraint &	operator= (const Constraint &c)
	Assignment operator.

dimension_type	space_dimension () const
	Returns the dimension of the vector space enclosing `*this`.

void	set_space_dimension (dimension_type space_dim)

void	swap_space_dimensions (Variable v1, Variable v2)
	Swaps the coefficients of the variables `v1` and `v2` .

bool	remove_space_dimensions (const Variables_Set &vars)
	Removes all the specified dimensions from the constraint. More...

void	permute_space_dimensions (const std::vector< Variable > &cycle)
	Permutes the space dimensions of the constraint.

void	shift_space_dimensions (Variable v, dimension_type n)

Type	type () const
	Returns the constraint type of `*this`.

bool	is_equality () const
	Returns `true` if and only if `*this` is an equality constraint.

bool	is_inequality () const
	Returns `true` if and only if `*this` is an inequality constraint (either strict or non-strict).

bool	is_nonstrict_inequality () const
	Returns `true` if and only if `*this` is a non-strict inequality constraint.

bool	is_strict_inequality () const
	Returns `true` if and only if `*this` is a strict inequality constraint.

Coefficient_traits::const_reference	coefficient (Variable v) const
	Returns the coefficient of `v` in `*this`. More...

Coefficient_traits::const_reference	inhomogeneous_term () const
	Returns the inhomogeneous term of `*this`.

memory_size_type	total_memory_in_bytes () const
	Returns a lower bound to the total size in bytes of the memory occupied by `*this`.

memory_size_type	external_memory_in_bytes () const
	Returns the size in bytes of the memory managed by `*this`.

bool	is_tautological () const
	Returns `true` if and only if `*this` is a tautology (i.e., an always true constraint). More...

bool	is_inconsistent () const
	Returns `true` if and only if `*this` is inconsistent (i.e., an always false constraint). More...

bool	is_equivalent_to (const Constraint &y) const
	Returns `true` if and only if `*this` and `y` are equivalent constraints. More...

bool	is_equal_to (const Constraint &y) const
	Returns `true` if `*this` is identical to `y`. More...

bool	OK () const
	Checks if all the invariants are satisfied.

void	ascii_dump () const
	Writes to `std::cerr` an ASCII representation of `*this`.

void	ascii_dump (std::ostream &s) const
	Writes to `s` an ASCII representation of `*this`.

void	print () const
	Prints `*this` to `std::cerr` using `operator<<`.

bool	ascii_load (std::istream &s)
	Loads from `s` an ASCII representation (as produced by ascii_dump(std::ostream&) const) and sets `*this` accordingly. Returns `true` if successful, `false` otherwise.

void	m_swap (Constraint &y)
	Swaps `*this` with `y`.

expr_type	expression () const
	Partial read access to the (adapted) internal expression.

Static Public Member Functions
static dimension_type	max_space_dimension ()
	Returns the maximum space dimension a Constraint can handle.

static void	initialize ()
	Initializes the class.

static void	finalize ()
	Finalizes the class.

static const Constraint &	zero_dim_false ()
	The unsatisfiable (zero-dimension space) constraint .

static const Constraint &	zero_dim_positivity ()
	The true (zero-dimension space) constraint $0 \leq 1$ , also known as positivity constraint.

static const Constraint &	epsilon_geq_zero ()
	Returns the zero-dimension space constraint $\epsilon \geq 0$ .

static const Constraint &	epsilon_leq_one ()
	The zero-dimension space constraint $\epsilon \leq 1$ (used to implement NNC polyhedra).

Static Public Attributes
static const Representation	default_representation = SPARSE
	The representation used for new Constraints. More...

Related Functions
(Note that these are not member functions.)
Constraint	operator< (const Linear_Expression &e1, const Linear_Expression &e2)
	Returns the constraint `e1` < `e2`. More...

Constraint	operator< (Variable v1, Variable v2)
	Returns the constraint `v1` < `v2`. More...

Constraint	operator< (const Linear_Expression &e, Coefficient_traits::const_reference n)
	Returns the constraint `e` < `n`. More...

Constraint	operator< (Coefficient_traits::const_reference n, const Linear_Expression &e)
	Returns the constraint `n` < `e`. More...

Constraint	operator> (const Linear_Expression &e1, const Linear_Expression &e2)
	Returns the constraint `e1` > `e2`. More...

Constraint	operator> (Variable v1, Variable v2)
	Returns the constraint `v1` > `v2`. More...

Constraint	operator> (const Linear_Expression &e, Coefficient_traits::const_reference n)
	Returns the constraint `e` > `n`. More...

Constraint	operator> (Coefficient_traits::const_reference n, const Linear_Expression &e)
	Returns the constraint `n` > `e`. More...

Constraint	operator== (const Linear_Expression &e1, const Linear_Expression &e2)
	Returns the constraint `e1` = `e2`. More...

Constraint	operator== (Variable v1, Variable v2)
	Returns the constraint `v1` = `v2`. More...

Constraint	operator== (const Linear_Expression &e, Coefficient_traits::const_reference n)
	Returns the constraint `e` = `n`. More...

Constraint	operator== (Coefficient_traits::const_reference n, const Linear_Expression &e)
	Returns the constraint `n` = `e`. More...

Constraint	operator<= (const Linear_Expression &e1, const Linear_Expression &e2)
	Returns the constraint `e1` <= `e2`. More...

Constraint	operator<= (Variable v1, Variable v2)
	Returns the constraint `v1` <= `v2`. More...

Constraint	operator<= (const Linear_Expression &e, Coefficient_traits::const_reference n)
	Returns the constraint `e` <= `n`. More...

Constraint	operator<= (Coefficient_traits::const_reference n, const Linear_Expression &e)
	Returns the constraint `n` <= `e`. More...

Constraint	operator>= (const Linear_Expression &e1, const Linear_Expression &e2)
	Returns the constraint `e1` >= `e2`. More...

Constraint	operator>= (Variable v1, Variable v2)
	Returns the constraint `v1` >= `v2`. More...

Constraint	operator>= (const Linear_Expression &e, Coefficient_traits::const_reference n)
	Returns the constraint `e` >= `n`. More...

Constraint	operator>= (Coefficient_traits::const_reference n, const Linear_Expression &e)
	Returns the constraint `n` >= `e`. More...

std::ostream &	operator<< (std::ostream &s, const Constraint &c)
	Output operator. More...

std::ostream &	operator<< (std::ostream &s, const Constraint::Type &t)
	Output operator. More...

bool	operator== (const Constraint &x, const Constraint &y)
	Returns `true` if and only if `x` is equivalent to `y`. More...

bool	operator!= (const Constraint &x, const Constraint &y)
	Returns `true` if and only if `x` is not equivalent to `y`. More...

void	swap (Constraint &x, Constraint &y)

bool	operator== (const Constraint &x, const Constraint &y)

bool	operator!= (const Constraint &x, const Constraint &y)

Constraint	operator== (const Linear_Expression &e1, const Linear_Expression &e2)

Constraint	operator== (Variable v1, Variable v2)

Constraint	operator>= (const Linear_Expression &e1, const Linear_Expression &e2)

Constraint	operator>= (const Variable v1, const Variable v2)

Constraint	operator> (const Linear_Expression &e1, const Linear_Expression &e2)

Constraint	operator> (const Variable v1, const Variable v2)

Constraint	operator== (Coefficient_traits::const_reference n, const Linear_Expression &e)

Constraint	operator>= (Coefficient_traits::const_reference n, const Linear_Expression &e)

Constraint	operator> (Coefficient_traits::const_reference n, const Linear_Expression &e)

Constraint	operator== (const Linear_Expression &e, Coefficient_traits::const_reference n)

Constraint	operator>= (const Linear_Expression &e, Coefficient_traits::const_reference n)

Constraint	operator> (const Linear_Expression &e, Coefficient_traits::const_reference n)

Constraint	operator<= (const Linear_Expression &e1, const Linear_Expression &e2)

Constraint	operator<= (const Variable v1, const Variable v2)

Constraint	operator<= (Coefficient_traits::const_reference n, const Linear_Expression &e)

Constraint	operator<= (const Linear_Expression &e, Coefficient_traits::const_reference n)

Constraint	operator< (const Linear_Expression &e1, const Linear_Expression &e2)

Constraint	operator< (const Variable v1, const Variable v2)

Constraint	operator< (Coefficient_traits::const_reference n, const Linear_Expression &e)

Constraint	operator< (const Linear_Expression &e, Coefficient_traits::const_reference n)

void	swap (Constraint &x, Constraint &y)

Detailed Description

A linear equality or inequality.

An object of the class Constraint is either:

an equality: $\sum_{i=0}^{n-1} a_i x_i + b = 0$ ;
a non-strict inequality: $\sum_{i=0}^{n-1} a_i x_i + b \geq 0$ ; or
a strict inequality: $\sum_{i=0}^{n-1} a_i x_i + b > 0$ ;

where $n$ is the dimension of the space, $a_i$ is the integer coefficient of variable $x_i$ and $b$ is the integer inhomogeneous term.

How to build a constraint: Constraints are typically built by applying a relation symbol to a pair of linear expressions. Available relation symbols are equality (==), non-strict inequalities (>= and <=) and strict inequalities (< and >). The space dimension of a constraint is defined as the maximum space dimension of the arguments of its constructor.

: In the following examples it is assumed that variables x, y and z are defined as follows:
Variable x(0);

Variable y(1);

Variable z(2);

Example 1: The following code builds the equality constraint , having space dimension :
Constraint eq_c(3*x + 5*y - z == 0);

The following code builds the (non-strict) inequality constraint $4x \geq 2y - 13$ , having space dimension :
Constraint ineq_c(4*x >= 2*y - 13);

The corresponding strict inequality constraint is obtained as follows:
Constraint strict_ineq_c(4*x > 2*y - 13);

An unsatisfiable constraint on the zero-dimension space $\Rset^0$ can be specified as follows:
Constraint false_c = Constraint::zero_dim_false();

Equivalent, but more involved ways are the following:
Constraint false_c1(Linear_Expression::zero() == 1);

Constraint false_c2(Linear_Expression::zero() >= 1);

Constraint false_c3(Linear_Expression::zero() > 0);

In contrast, the following code defines an unsatisfiable constraint having space dimension :
Constraint false_c(0*z == 1);

How to inspect a constraint: Several methods are provided to examine a constraint and extract all the encoded information: its space dimension, its type (equality, non-strict inequality, strict inequality) and the value of its integer coefficients.

Example 2: The following code shows how it is possible to access each single coefficient of a constraint. Given an inequality constraint (in this case $x - 5y + 3z \leq 4$ ), we construct a new constraint corresponding to its complement (thus, in this case we want to obtain the strict inequality constraint ).
Constraint c1(x - 5*y + 3*z <= 4);

cout << "Constraint c1: " << c1 << endl;

if (c1.is_equality())

cout << "Constraint c1 is not an inequality." << endl;

else {

Linear_Expression e;

for (dimension_type i = c1.space_dimension(); i-- > 0; )

e += c1.coefficient(Variable(i)) * Variable(i);

e += c1.inhomogeneous_term();

Constraint c2 = c1.is_strict_inequality() ? (e <= 0) : (e < 0);

cout << "Complement c2: " << c2 << endl;

}

The actual output is the following:
Constraint c1: -A + 5*B - 3*C >= -4

Complement c2: A - 5*B + 3*C > 4

Note that, in general, the particular output obtained can be syntactically different from the (semantically equivalent) constraint considered.

Constructor & Destructor Documentation

Parma_Polyhedra_Library::Constraint::Constraint ( const Constraint & c )

inline

Ordinary copy constructor.

Note: The new Constraint will have the same representation as `c', not default_representation, so that they are indistinguishable.

Parma_Polyhedra_Library::Constraint::Constraint	(	const Constraint &	c,
		dimension_type	space_dim
	)

inline

Copy constructor with given size.

Note: The new Constraint will have the same representation as `c', not default_representation, so that they are indistinguishable.

Parma_Polyhedra_Library::Constraint::Constraint	(	const Congruence &	cg,
		Representation	r = `default_representation`
	)

explicit

Copy-constructs from equality congruence cg.

Exceptions

std::invalid_argument Thrown if cg is a proper congruence.

Member Function Documentation

void Parma_Polyhedra_Library::Constraint::set_space_dimension ( dimension_type space_dim )

inline

Sets the dimension of the vector space enclosing *this to space_dim .

bool Parma_Polyhedra_Library::Constraint::remove_space_dimensions ( const Variables_Set & vars )

inline

Removes all the specified dimensions from the constraint.

The space dimension of the variable with the highest space dimension in vars must be at most the space dimension of this.

Always returns true. The return value is needed for compatibility with the Generator class.

void Parma_Polyhedra_Library::Constraint::shift_space_dimensions	(	Variable	v,
		dimension_type	n
	)

inline

Shift by n positions the coefficients of variables, starting from the coefficient of v. This increases the space dimension by n.

Coefficient_traits::const_reference Parma_Polyhedra_Library::Constraint::coefficient ( Variable v ) const

inline

Returns the coefficient of v in *this.

Exceptions

std::invalid_argument thrown if the index of v is greater than or equal to the space dimension of *this.

bool Parma_Polyhedra_Library::Constraint::is_tautological ( ) const

Returns true if and only if *this is a tautology (i.e., an always true constraint).

A tautology can have either one of the following forms:

an equality: $\sum_{i=0}^{n-1} 0 x_i + 0 = 0$ ; or
a non-strict inequality: $\sum_{i=0}^{n-1} 0 x_i + b \geq 0$ , where $b \geq 0$ ; or
a strict inequality: $\sum_{i=0}^{n-1} 0 x_i + b > 0$ , where .

bool Parma_Polyhedra_Library::Constraint::is_inconsistent ( ) const

Returns true if and only if *this is inconsistent (i.e., an always false constraint).

An inconsistent constraint can have either one of the following forms:

an equality: $\sum_{i=0}^{n-1} 0 x_i + b = 0$ , where $b \neq 0$ ; or
a non-strict inequality: $\sum_{i=0}^{n-1} 0 x_i + b \geq 0$ , where ; or
a strict inequality: $\sum_{i=0}^{n-1} 0 x_i + b > 0$ , where $b \leq 0$ .

bool Parma_Polyhedra_Library::Constraint::is_equivalent_to ( const Constraint & y ) const

Returns true if and only if *this and y are equivalent constraints.

Constraints having different space dimensions are not equivalent. Note that constraints having different types may nonetheless be equivalent, if they both are tautologies or inconsistent.

bool Parma_Polyhedra_Library::Constraint::is_equal_to ( const Constraint & y ) const

Returns true if *this is identical to y.

This is faster than is_equivalent_to(), but it may return `false' even for equivalent constraints.

Friends And Related Function Documentation

Constraint operator<	(	const Linear_Expression &	e1,
		const Linear_Expression &	e2
	)

Constraint operator<	(	Variable	v1,
		Variable	v2
	)

Constraint operator<	(	const Linear_Expression &	e,
		Coefficient_traits::const_reference	n
	)

Constraint operator<	(	Coefficient_traits::const_reference	n,
		const Linear_Expression &	e
	)

Constraint operator>	(	const Linear_Expression &	e1,
		const Linear_Expression &	e2
	)

Constraint operator>	(	Variable	v1,
		Variable	v2
	)

Constraint operator>	(	const Linear_Expression &	e,
		Coefficient_traits::const_reference	n
	)

Constraint operator>	(	Coefficient_traits::const_reference	n,
		const Linear_Expression &	e
	)

Constraint operator==	(	const Linear_Expression &	e1,
		const Linear_Expression &	e2
	)

Constraint operator==	(	Variable	v1,
		Variable	v2
	)

Constraint operator==	(	const Linear_Expression &	e,
		Coefficient_traits::const_reference	n
	)

Constraint operator==	(	Coefficient_traits::const_reference	n,
		const Linear_Expression &	e
	)

Constraint operator<=	(	const Linear_Expression &	e1,
		const Linear_Expression &	e2
	)

Constraint operator<=	(	Variable	v1,
		Variable	v2
	)

Constraint operator<=	(	const Linear_Expression &	e,
		Coefficient_traits::const_reference	n
	)

Constraint operator<=	(	Coefficient_traits::const_reference	n,
		const Linear_Expression &	e
	)

Constraint operator>=	(	const Linear_Expression &	e1,
		const Linear_Expression &	e2
	)

Constraint operator>=	(	Variable	v1,
		Variable	v2
	)

Constraint operator>=	(	const Linear_Expression &	e,
		Coefficient_traits::const_reference	n
	)

Constraint operator>=	(	Coefficient_traits::const_reference	n,
		const Linear_Expression &	e
	)

std::ostream & operator<<	(	std::ostream &	s,
		const Constraint &	c
	)

std::ostream & operator<<	(	std::ostream &	s,
		const Constraint::Type &	t
	)

bool operator==	(	const Constraint &	x,
		const Constraint &	y
	)

bool operator!=	(	const Constraint &	x,
		const Constraint &	y
	)

void swap	(	Constraint &	x,
		Constraint &	y
	)

bool operator==	(	const Constraint &	x,
		const Constraint &	y
	)

bool operator!=	(	const Constraint &	x,
		const Constraint &	y
	)

Constraint operator==	(	const Linear_Expression &	e1,
		const Linear_Expression &	e2
	)

Constraint operator==	(	Variable	v1,
		Variable	v2
	)

Constraint operator>=	(	const Linear_Expression &	e1,
		const Linear_Expression &	e2
	)

Constraint operator>=	(	const Variable	v1,
		const Variable	v2
	)

Constraint operator>	(	const Linear_Expression &	e1,
		const Linear_Expression &	e2
	)

Constraint operator>	(	const Variable	v1,
		const Variable	v2
	)

Constraint operator==	(	Coefficient_traits::const_reference	n,
		const Linear_Expression &	e
	)

Constraint operator>=	(	Coefficient_traits::const_reference	n,
		const Linear_Expression &	e
	)

Constraint operator>	(	Coefficient_traits::const_reference	n,
		const Linear_Expression &	e
	)

Constraint operator==	(	const Linear_Expression &	e,
		Coefficient_traits::const_reference	n
	)

Constraint operator>=	(	const Linear_Expression &	e,
		Coefficient_traits::const_reference	n
	)

Constraint operator>	(	const Linear_Expression &	e,
		Coefficient_traits::const_reference	n
	)

Constraint operator<=	(	const Linear_Expression &	e1,
		const Linear_Expression &	e2
	)

Constraint operator<=	(	const Variable	v1,
		const Variable	v2
	)

Constraint operator<=	(	Coefficient_traits::const_reference	n,
		const Linear_Expression &	e
	)

Constraint operator<=	(	const Linear_Expression &	e,
		Coefficient_traits::const_reference	n
	)

Constraint operator<	(	const Linear_Expression &	e1,
		const Linear_Expression &	e2
	)

Constraint operator<	(	const Variable	v1,
		const Variable	v2
	)

Constraint operator<	(	Coefficient_traits::const_reference	n,
		const Linear_Expression &	e
	)

Constraint operator<	(	const Linear_Expression &	e,
		Coefficient_traits::const_reference	n
	)

void swap	(	Constraint &	x,
		Constraint &	y
	)

const Representation Parma_Polyhedra_Library::Constraint::default_representation = SPARSE

static

The representation used for new Constraints.

Note: The copy constructor and the copy constructor with specified size use the representation of the original object, so that it is indistinguishable from the original object.

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

ppl.hh

Public Types

Public Member Functions

Static Public Member Functions

Static Public Attributes

Related Functions

Detailed Description

Constructor & Destructor Documentation

Member Function Documentation

Friends And Related Function Documentation

Member Data Documentation