Parma_Polyhedra_Library::Constraint Class Reference
[C++ Language Interface]

A linear equality or inequality. More...

#include <ppl.hh>

Inherits Parma_Polyhedra_Library::Linear_Row.

List of all members.

Public Types

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

Public Member Functions

 Constraint (const Constraint &c)
 Ordinary copy-constructor.
 Constraint (const Congruence &cg)
 Copy-constructs from equality congruence cg.
 ~Constraint ()
 Destructor.
Constraintoperator= (const Constraint &c)
 Assignment operator.
dimension_type space_dimension () const
 Returns the dimension of the vector space enclosing *this.
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.
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).
bool is_inconsistent () const
 Returns true if and only if *this is inconsistent (i.e., an always false constraint).
bool is_equivalent_to (const Constraint &y) const
 Returns true if and only if *this and y are equivalent constraints.
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.
bool OK () const
 Checks if all the invariants are satisfied.
void swap (Constraint &y)
 Swaps *this with y.

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 Constraintzero_dim_false ()
 The unsatisfiable (zero-dimension space) constraint $0 = 1$.
static const Constraintzero_dim_positivity ()
 The true (zero-dimension space) constraint $0 \leq 1$, also known as positivity constraint.

Friends

Constraint operator== (const Linear_Expression &e1, const Linear_Expression &e2)
 Returns the constraint e1 = e2.
Constraint operator== (Variable v1, Variable v2)
 Returns the constraint v1 = v2.
Constraint operator== (const Linear_Expression &e, Coefficient_traits::const_reference n)
 Returns the constraint e = n.
Constraint operator== (Coefficient_traits::const_reference n, const Linear_Expression &e)
 Returns the constraint n = e.
Constraint operator>= (const Linear_Expression &e1, const Linear_Expression &e2)
 Returns the constraint e1 >= e2.
Constraint operator>= (Variable v1, Variable v2)
 Returns the constraint v1 >= v2.
Constraint operator>= (const Linear_Expression &e, Coefficient_traits::const_reference n)
 Returns the constraint e >= n.
Constraint operator>= (Coefficient_traits::const_reference n, const Linear_Expression &e)
 Returns the constraint n >= e.
Constraint operator<= (const Linear_Expression &e1, const Linear_Expression &e2)
 Returns the constraint e1 <= e2.
Constraint operator<= (const Linear_Expression &e, Coefficient_traits::const_reference n)
 Returns the constraint e <= n.
Constraint operator<= (Coefficient_traits::const_reference n, const Linear_Expression &e)
 Returns the constraint n <= e.
Constraint operator> (const Linear_Expression &e1, const Linear_Expression &e2)
 Returns the constraint e1 > e2.
Constraint operator> (Variable v1, Variable v2)
 Returns the constraint v1 > v2.
Constraint operator> (const Linear_Expression &e, Coefficient_traits::const_reference n)
 Returns the constraint e > n.
Constraint operator> (Coefficient_traits::const_reference n, const Linear_Expression &e)
 Returns the constraint n > e.
Constraint operator< (const Linear_Expression &e1, const Linear_Expression &e2)
 Returns the constraint e1 < e2.
Constraint operator< (const Linear_Expression &e, Coefficient_traits::const_reference n)
 Returns the constraint e < n.
Constraint operator< (Coefficient_traits::const_reference n, const Linear_Expression &e)
 Returns the constraint n < e.

Related Functions

(Note that these are not member functions.)

bool operator== (const Constraint &x, const Constraint &y)
 Returns true if and only if x is equivalent to y.
bool operator!= (const Constraint &x, const Constraint &y)
 Returns true if and only if x is not equivalent to y.
Constraint operator<= (Variable v1, Variable v2)
 Returns the constraint v1 <= v2.
Constraint operator< (Variable v1, Variable v2)
 Returns the constraint v1 < v2.
void swap (Parma_Polyhedra_Library::Constraint &x, Parma_Polyhedra_Library::Constraint &y)
 Specializes std::swap.
std::ostream & operator<< (std::ostream &s, const Constraint &c)
 Output operator.
std::ostream & operator<< (std::ostream &s, const Constraint::Type &t)
 Output operator.


Detailed Description

A linear equality or inequality.

An object of the class Constraint is either:

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 $3x + 5y - z = 0$, having space dimension $3$:
  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 $2$:
  Constraint ineq_c(4*x >= 2*y - 13);
The corresponding strict inequality constraint $4x > 2y - 13$ 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: Equivalent, but more involved ways are the following: In contrast, the following code defines an unsatisfiable constraint having space dimension $3$:
  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 $x - 5y + 3z > 4$).
  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.

Member Enumeration Documentation

The constraint type.

Enumerator:
EQUALITY  The constraint is an equality.
NONSTRICT_INEQUALITY  The constraint is a non-strict inequality.
STRICT_INEQUALITY  The constraint is a strict inequality.


Constructor & Destructor Documentation

Parma_Polyhedra_Library::Constraint::Constraint ( const Congruence cg  )  [explicit]

Copy-constructs from equality congruence cg.

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


Member Function Documentation

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 $b > 0$.

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 $b < 0$; 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.


Friends And Related Function Documentation

Constraint operator== ( const Linear_Expression e1,
const Linear_Expression e2 
) [friend]

Returns the constraint e1 = e2.

Constraint operator== ( Variable  v1,
Variable  v2 
) [friend]

Returns the constraint v1 = v2.

Constraint operator== ( const Linear_Expression e,
Coefficient_traits::const_reference  n 
) [friend]

Returns the constraint e = n.

Constraint operator== ( Coefficient_traits::const_reference  n,
const Linear_Expression e 
) [friend]

Returns the constraint n = e.

Constraint operator>= ( const Linear_Expression e1,
const Linear_Expression e2 
) [friend]

Returns the constraint e1 >= e2.

Constraint operator>= ( Variable  v1,
Variable  v2 
) [friend]

Returns the constraint v1 >= v2.

Constraint operator>= ( const Linear_Expression e,
Coefficient_traits::const_reference  n 
) [friend]

Returns the constraint e >= n.

Constraint operator>= ( Coefficient_traits::const_reference  n,
const Linear_Expression e 
) [friend]

Returns the constraint n >= e.

Constraint operator<= ( const Linear_Expression e1,
const Linear_Expression e2 
) [friend]

Returns the constraint e1 <= e2.

Constraint operator<= ( const Linear_Expression e,
Coefficient_traits::const_reference  n 
) [friend]

Returns the constraint e <= n.

Constraint operator<= ( Coefficient_traits::const_reference  n,
const Linear_Expression e 
) [friend]

Returns the constraint n <= e.

Constraint operator> ( const Linear_Expression e1,
const Linear_Expression e2 
) [friend]

Returns the constraint e1 > e2.

Constraint operator> ( Variable  v1,
Variable  v2 
) [friend]

Returns the constraint v1 > v2.

Constraint operator> ( const Linear_Expression e,
Coefficient_traits::const_reference  n 
) [friend]

Returns the constraint e > n.

Constraint operator> ( Coefficient_traits::const_reference  n,
const Linear_Expression e 
) [friend]

Returns the constraint n > e.

Constraint operator< ( const Linear_Expression e1,
const Linear_Expression e2 
) [friend]

Returns the constraint e1 < e2.

Constraint operator< ( const Linear_Expression e,
Coefficient_traits::const_reference  n 
) [friend]

Returns the constraint e < n.

Constraint operator< ( Coefficient_traits::const_reference  n,
const Linear_Expression e 
) [friend]

Returns the constraint n < e.

bool operator== ( const Constraint x,
const Constraint y 
) [related]

Returns true if and only if x is equivalent to y.

bool operator!= ( const Constraint x,
const Constraint y 
) [related]

Returns true if and only if x is not equivalent to y.

Constraint operator<= ( Variable  v1,
Variable  v2 
) [related]

Returns the constraint v1 <= v2.

Constraint operator< ( Variable  v1,
Variable  v2 
) [related]

Returns the constraint v1 < v2.

Specializes std::swap.

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

Output operator.

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

Output operator.


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

Generated on Tue Nov 4 10:38:37 2008 for PPL by  doxygen 1.5.7.1-20081012