#include <Constraint.defs.hh>
Public Types | |
enum | Type { EQUALITY, NONSTRICT_INEQUALITY, STRICT_INEQUALITY } |
The constraint type. More... | |
Public Member Functions | |
Constraint (const Constraint &c) | |
Ordinary copy-constructor. | |
~Constraint () | |
Destructor. | |
Constraint & | operator= (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) 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 const Constraint & | zero_dim_false () |
The unsatisfiable (zero-dimension space) constraint ![]() | |
static const Constraint & | zero_dim_positivity () |
The true (zero-dimension space) constraint ![]() | |
Private Member Functions | |
friend | Parma_Polyhedra_Library::Linear_Expression::Linear_Expression (const Constraint &c) |
Constraint () | |
Default constructor: private and not implemented. | |
Constraint (Linear_Expression &e, Type type, Topology topology) | |
Builds a constraint of type type and topology topology , stealing the coefficients from e . | |
void | throw_dimension_incompatible (const char *method, const char *name_var, Variable v) const |
Throws a std::invalid_argument exception containing the appropriate error message. | |
Constraint (const Constraint &c, dimension_type sz) | |
Copy-constructor with given size. | |
void | set_is_equality () |
Sets the constraint type to EQUALITY . | |
void | set_is_inequality () |
Sets the constraint to be an inequality. | |
Static Private Member Functions | |
static Constraint | construct_epsilon_geq_zero () |
Builds a new copy of the zero-dimension space constraint ![]() | |
static const Constraint & | epsilon_geq_zero () |
Returns the zero-dimension space constraint ![]() | |
static const Constraint & | epsilon_leq_one () |
The zero-dimension space constraint ![]() | |
Friends | |
class | Parma_Polyhedra_Library::Congruence |
class | Parma_Polyhedra_Library::Scalar_Products |
class | Parma_Polyhedra_Library::Topology_Adjusted_Scalar_Product_Sign |
class | Parma_Polyhedra_Library::Constraint_System |
class | Parma_Polyhedra_Library::Constraint_System::const_iterator |
class | Parma_Polyhedra_Library::Polyhedron |
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>= (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> (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 . | |
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. |
An object of the class Constraint is either:
where is the dimension of the space,
is the integer coefficient of variable
and
is the integer inhomogeneous term.
==
), 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.x
, y
and z
are defined as follows: Variable x(0); Variable y(1); Variable z(2);
Constraint eq_c(3*x + 5*y - z == 0);
Constraint ineq_c(4*x >= 2*y - 13);
Constraint strict_ineq_c(4*x > 2*y - 13);
Constraint false_c = Constraint::zero_dim_false();
Constraint false_c1(Linear_Expression::zero() == 1); Constraint false_c2(Linear_Expression::zero() >= 1); Constraint false_c3(Linear_Expression::zero() > 0);
Constraint false_c(0*z == 1);
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 (int i = c1.space_dimension() - 1; i >= 0; i--) 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; }
Constraint c1: -A + 5*B - 3*C >= -4 Complement c2: A - 5*B + 3*C > 4
Definition at line 224 of file Constraint.defs.hh.
The constraint type.
EQUALITY | The constraint is an equality. |
NONSTRICT_INEQUALITY | The constraint is a non-strict inequality. |
STRICT_INEQUALITY | The constraint is a strict inequality. |
Definition at line 242 of file Constraint.defs.hh.
00242 { 00244 EQUALITY, 00246 NONSTRICT_INEQUALITY, 00248 STRICT_INEQUALITY 00249 };
Parma_Polyhedra_Library::Constraint::Constraint | ( | const Constraint & | c | ) | [inline] |
Ordinary copy-constructor.
Definition at line 40 of file Constraint.inlines.hh.
00041 : Linear_Row(c) { 00042 }
Parma_Polyhedra_Library::Constraint::~Constraint | ( | ) | [inline] |
Parma_Polyhedra_Library::Constraint::Constraint | ( | ) | [private] |
Default constructor: private and not implemented.
Parma_Polyhedra_Library::Constraint::Constraint | ( | Linear_Expression & | e, | |
Type | type, | |||
Topology | topology | |||
) | [inline, private] |
Builds a constraint of type type
and topology topology
, stealing the coefficients from e
.
Definition at line 31 of file Constraint.inlines.hh.
References EQUALITY, Parma_Polyhedra_Library::Linear_Row::flags(), Parma_Polyhedra_Library::Linear_Row::LINE_OR_EQUALITY, Parma_Polyhedra_Library::NOT_NECESSARILY_CLOSED, Parma_Polyhedra_Library::Linear_Row::RAY_OR_POINT_OR_INEQUALITY, STRICT_INEQUALITY, and Parma_Polyhedra_Library::Linear_Row::swap().
00031 { 00032 assert(type != STRICT_INEQUALITY || topology == NOT_NECESSARILY_CLOSED); 00033 Linear_Row::swap(e); 00034 flags() = Flags(topology, (type == EQUALITY 00035 ? LINE_OR_EQUALITY 00036 : RAY_OR_POINT_OR_INEQUALITY)); 00037 }
Parma_Polyhedra_Library::Constraint::Constraint | ( | const Constraint & | c, | |
dimension_type | sz | |||
) | [inline, private] |
Copy-constructor with given size.
Definition at line 45 of file Constraint.inlines.hh.
00046 : Linear_Row(c, sz, sz) { 00047 }
Constraint & Parma_Polyhedra_Library::Constraint::operator= | ( | const Constraint & | c | ) | [inline] |
Assignment operator.
Definition at line 54 of file Constraint.inlines.hh.
References Parma_Polyhedra_Library::Row::operator=().
00054 { 00055 Linear_Row::operator=(c); 00056 return *this; 00057 }
dimension_type Parma_Polyhedra_Library::Constraint::max_space_dimension | ( | ) | [inline, static] |
Returns the maximum space dimension a Constraint can handle.
Reimplemented from Parma_Polyhedra_Library::Linear_Row.
Definition at line 60 of file Constraint.inlines.hh.
References Parma_Polyhedra_Library::Linear_Row::max_space_dimension().
00060 { 00061 return Linear_Row::max_space_dimension(); 00062 }
dimension_type Parma_Polyhedra_Library::Constraint::space_dimension | ( | ) | const [inline] |
Returns the dimension of the vector space enclosing *this
.
Reimplemented from Parma_Polyhedra_Library::Linear_Row.
Definition at line 65 of file Constraint.inlines.hh.
References Parma_Polyhedra_Library::Linear_Row::space_dimension().
Referenced by Parma_Polyhedra_Library::Polyhedron::add_constraint(), Parma_Polyhedra_Library::Grid::add_constraint(), Parma_Polyhedra_Library::BD_Shape< T >::add_constraint(), Parma_Polyhedra_Library::Grid::add_constraint_and_minimize(), coefficient(), Parma_Polyhedra_Library::BD_Shape< T >::extract_bounded_difference(), Parma_Polyhedra_Library::Constraint_System::insert(), Parma_Polyhedra_Library::Congruence_System::insert(), Parma_Polyhedra_Library::Constraint_System::insert_pending(), is_equivalent_to(), Parma_Polyhedra_Library::Topology_Adjusted_Scalar_Product_Sign::operator()(), operator<<(), Parma_Polyhedra_Library::Polyhedron::relation_with(), Parma_Polyhedra_Library::Generator_System::relation_with(), Parma_Polyhedra_Library::BD_Shape< T >::relation_with(), Parma_Polyhedra_Library::Generator_System::satisfied_by_all_generators(), Parma_Polyhedra_Library::Polyhedron::throw_dimension_incompatible(), Parma_Polyhedra_Library::Grid::throw_dimension_incompatible(), throw_dimension_incompatible(), and Parma_Polyhedra_Library::BD_Shape< T >::throw_dimension_incompatible().
00065 { 00066 return Linear_Row::space_dimension(); 00067 }
Constraint::Type Parma_Polyhedra_Library::Constraint::type | ( | ) | const [inline] |
Returns the constraint type of *this
.
Definition at line 80 of file Constraint.inlines.hh.
References EQUALITY, is_equality(), Parma_Polyhedra_Library::Linear_Row::is_necessarily_closed(), NONSTRICT_INEQUALITY, Parma_Polyhedra_Library::Row::size(), and STRICT_INEQUALITY.
Referenced by Parma_Polyhedra_Library::Constraint_System::ascii_dump(), constraint_term(), is_equivalent_to(), Parma_Polyhedra_Library::Polyhedron::is_included_in(), is_nonstrict_inequality(), is_strict_inequality(), operator<<(), Parma_Polyhedra_Library::Polyhedron::poly_difference_assign(), Parma_Polyhedra_Library::Generator_System::relation_with(), Parma_Polyhedra_Library::BD_Shape< T >::relation_with(), Parma_Polyhedra_Library::Generator_System::satisfied_by_all_generators(), Parma_Polyhedra_Library::Constraint_System::satisfies_all_constraints(), and Parma_Polyhedra_Library::Polyhedron::shrink_bounding_box().
00080 { 00081 if (is_equality()) 00082 return EQUALITY; 00083 if (is_necessarily_closed()) 00084 return NONSTRICT_INEQUALITY; 00085 else 00086 return ((*this)[size() - 1] < 0) 00087 ? STRICT_INEQUALITY 00088 : NONSTRICT_INEQUALITY; 00089 }
bool Parma_Polyhedra_Library::Constraint::is_equality | ( | ) | const [inline] |
Returns true
if and only if *this
is an equality constraint.
Definition at line 70 of file Constraint.inlines.hh.
References Parma_Polyhedra_Library::Linear_Row::is_line_or_equality().
Referenced by Parma_Polyhedra_Library::Grid::add_congruence(), Parma_Polyhedra_Library::Grid::add_congruence_and_minimize(), Parma_Polyhedra_Library::Polyhedron::add_constraint(), Parma_Polyhedra_Library::Grid::add_constraint(), Parma_Polyhedra_Library::BD_Shape< T >::add_constraint(), Parma_Polyhedra_Library::Grid::add_constraint_and_minimize(), Parma_Polyhedra_Library::Polyhedron::add_recycled_constraints(), Parma_Polyhedra_Library::BD_Shape< T >::BD_Shape(), Parma_Polyhedra_Library::BD_Shape< T >::bds_difference_assign(), Parma_Polyhedra_Library::Polyhedron::concatenate_assign(), Parma_Polyhedra_Library::Polyhedron::expand_space_dimension(), is_inconsistent(), is_tautological(), Parma_Polyhedra_Library::Polyhedra_Powerset< PH >::linear_partition(), Parma_Polyhedra_Library::Polyhedron::relation_with(), Parma_Polyhedra_Library::BD_Shape< T >::relation_with(), and type().
00070 { 00071 return is_line_or_equality(); 00072 }
bool Parma_Polyhedra_Library::Constraint::is_inequality | ( | ) | const [inline] |
Returns true
if and only if *this
is an inequality constraint (either strict or non-strict).
Definition at line 75 of file Constraint.inlines.hh.
References Parma_Polyhedra_Library::Linear_Row::is_ray_or_point_or_inequality().
Referenced by Parma_Polyhedra_Library::Polyhedron::BHRZ03_combining_constraints(), Parma_Polyhedra_Library::BD_Shape< T >::get_limiting_shape(), Parma_Polyhedra_Library::Polyhedron::is_included_in(), Parma_Polyhedra_Library::BD_Shape< T >::relation_with(), and Parma_Polyhedra_Library::Constraint_System::satisfies_all_constraints().
00075 { 00076 return is_ray_or_point_or_inequality(); 00077 }
bool Parma_Polyhedra_Library::Constraint::is_nonstrict_inequality | ( | ) | const [inline] |
Returns true
if and only if *this
is a non-strict inequality constraint.
Definition at line 92 of file Constraint.inlines.hh.
References NONSTRICT_INEQUALITY, and type().
Referenced by Parma_Polyhedra_Library::BD_Shape< T >::bds_difference_assign(), and Parma_Polyhedra_Library::Polyhedron::expand_space_dimension().
00092 { 00093 return type() == NONSTRICT_INEQUALITY; 00094 }
bool Parma_Polyhedra_Library::Constraint::is_strict_inequality | ( | ) | const [inline] |
Returns true
if and only if *this
is a strict inequality constraint.
Definition at line 97 of file Constraint.inlines.hh.
References STRICT_INEQUALITY, and type().
Referenced by Parma_Polyhedra_Library::Polyhedron::add_constraint(), Parma_Polyhedra_Library::LP_Problem::add_constraint(), Parma_Polyhedra_Library::BD_Shape< T >::add_constraint(), Parma_Polyhedra_Library::C_Polyhedron::C_Polyhedron(), Parma_Polyhedra_Library::Polyhedra_Powerset< PH >::linear_partition_aux(), Parma_Polyhedra_Library::Polyhedron::relation_with(), and Parma_Polyhedra_Library::BD_Shape< T >::relation_with().
00097 { 00098 return type() == STRICT_INEQUALITY; 00099 }
Coefficient_traits::const_reference Parma_Polyhedra_Library::Constraint::coefficient | ( | Variable | v | ) | const [inline] |
Returns the coefficient of v
in *this
.
std::invalid_argument | thrown if the index of v is greater than or equal to the space dimension of *this . |
Definition at line 112 of file Constraint.inlines.hh.
References Parma_Polyhedra_Library::Linear_Row::coefficient(), Parma_Polyhedra_Library::Variable::id(), space_dimension(), Parma_Polyhedra_Library::Variable::space_dimension(), and throw_dimension_incompatible().
Referenced by Parma_Polyhedra_Library::Polyhedron::expand_space_dimension(), Parma_Polyhedra_Library::BD_Shape< T >::extract_bounded_difference(), operator<<(), ppl_Constraint_coefficient(), and Parma_Polyhedra_Library::Polyhedron::shrink_bounding_box().
00112 { 00113 if (v.space_dimension() > space_dimension()) 00114 throw_dimension_incompatible("coefficient(v)", "v", v); 00115 return Linear_Row::coefficient(v.id()); 00116 }
Coefficient_traits::const_reference Parma_Polyhedra_Library::Constraint::inhomogeneous_term | ( | ) | const [inline] |
Returns the inhomogeneous term of *this
.
Reimplemented from Parma_Polyhedra_Library::Linear_Row.
Definition at line 119 of file Constraint.inlines.hh.
References Parma_Polyhedra_Library::Linear_Row::inhomogeneous_term().
Referenced by Parma_Polyhedra_Library::BD_Shape< T >::add_constraint(), constraint_term(), Parma_Polyhedra_Library::Polyhedron::expand_space_dimension(), Parma_Polyhedra_Library::BD_Shape< T >::get_limiting_shape(), operator<<(), ppl_Constraint_inhomogeneous_term(), Parma_Polyhedra_Library::Polyhedron::relation_with(), Parma_Polyhedra_Library::BD_Shape< T >::relation_with(), and Parma_Polyhedra_Library::Polyhedron::shrink_bounding_box().
00119 { 00120 return Linear_Row::inhomogeneous_term(); 00121 }
const Constraint & Parma_Polyhedra_Library::Constraint::zero_dim_false | ( | ) | [inline, static] |
The unsatisfiable (zero-dimension space) constraint .
Definition at line 291 of file Constraint.inlines.hh.
References Parma_Polyhedra_Library::Coefficient_one(), and Parma_Polyhedra_Library::Linear_Expression::zero().
Referenced by Parma_Polyhedra_Library::Constraint_System::zero_dim_empty().
00291 { 00292 static const Constraint zdf(Linear_Expression::zero() == Coefficient_one()); 00293 return zdf; 00294 }
const Constraint & Parma_Polyhedra_Library::Constraint::zero_dim_positivity | ( | ) | [inline, static] |
The true (zero-dimension space) constraint , also known as positivity constraint.
Definition at line 297 of file Constraint.inlines.hh.
References Parma_Polyhedra_Library::Coefficient_one(), and Parma_Polyhedra_Library::Linear_Expression::zero().
Referenced by Parma_Polyhedra_Library::Constraint_System::add_low_level_constraints().
00297 { 00298 static const Constraint zdp(Linear_Expression::zero() <= Coefficient_one()); 00299 return zdp; 00300 }
memory_size_type Parma_Polyhedra_Library::Constraint::total_memory_in_bytes | ( | ) | const [inline] |
Returns a lower bound to the total size in bytes of the memory occupied by *this
.
Reimplemented from Parma_Polyhedra_Library::Row.
Definition at line 129 of file Constraint.inlines.hh.
References Parma_Polyhedra_Library::Checked::total_memory_in_bytes().
00129 { 00130 return Linear_Row::total_memory_in_bytes(); 00131 }
memory_size_type Parma_Polyhedra_Library::Constraint::external_memory_in_bytes | ( | ) | const [inline] |
Returns the size in bytes of the memory managed by *this
.
Reimplemented from Parma_Polyhedra_Library::Row.
Definition at line 124 of file Constraint.inlines.hh.
References Parma_Polyhedra_Library::Checked::external_memory_in_bytes().
00124 { 00125 return Linear_Row::external_memory_in_bytes(); 00126 }
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:
Definition at line 53 of file Constraint.cc.
References Parma_Polyhedra_Library::Linear_Row::all_homogeneous_terms_are_zero(), is_equality(), Parma_Polyhedra_Library::Linear_Row::is_necessarily_closed(), and Parma_Polyhedra_Library::Row::size().
Referenced by Parma_Polyhedra_Library::Polyhedron::add_constraint(), Parma_Polyhedra_Library::Constraint_System::has_strict_inequalities(), is_equivalent_to(), Parma_Polyhedra_Library::Polyhedron::poly_difference_assign(), and Parma_Polyhedra_Library::Polyhedron::topological_closure_assign().
00053 { 00054 assert(size() > 0); 00055 const Constraint& x = *this; 00056 if (x.all_homogeneous_terms_are_zero()) 00057 if (is_equality()) 00058 return x[0] == 0; 00059 else 00060 // Non-strict inequality constraint. 00061 return x[0] >= 0; 00062 else 00063 // There is a non-zero homogeneous coefficient. 00064 if (is_necessarily_closed()) 00065 return false; 00066 else { 00067 // The constraint is NOT necessarily closed. 00068 const dimension_type eps_index = size() - 1; 00069 const int eps_sign = sgn(x[eps_index]); 00070 if (eps_sign > 0) 00071 // We have found the constraint epsilon >= 0. 00072 return true; 00073 if (eps_sign == 0) 00074 // One of the `true' dimensions has a non-zero coefficient. 00075 return false; 00076 else { 00077 // Here the epsilon coefficient is negative: strict inequality. 00078 if (x[0] <= 0) 00079 // A strict inequality such as `lhs - k > 0', 00080 // where k is a non negative integer, cannot be trivially true. 00081 return false; 00082 // Checking for another non-zero coefficient. 00083 for (dimension_type i = eps_index; --i > 0; ) 00084 if (x[i] != 0) 00085 return false; 00086 // We have the inequality `k > 0', 00087 // where k is a positive integer. 00088 return true; 00089 } 00090 } 00091 }
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:
Definition at line 94 of file Constraint.cc.
References Parma_Polyhedra_Library::Linear_Row::all_homogeneous_terms_are_zero(), is_equality(), Parma_Polyhedra_Library::Linear_Row::is_necessarily_closed(), and Parma_Polyhedra_Library::Row::size().
Referenced by is_equivalent_to(), Parma_Polyhedra_Library::Polyhedron::poly_difference_assign(), Parma_Polyhedra_Library::Polyhedron::relation_with(), and Parma_Polyhedra_Library::Polyhedron::shrink_bounding_box().
00094 { 00095 assert(size() > 0); 00096 const Constraint& x = *this; 00097 if (x.all_homogeneous_terms_are_zero()) 00098 // The inhomogeneous term is the only non-zero coefficient. 00099 if (is_equality()) 00100 return x[0] != 0; 00101 else 00102 // Non-strict inequality constraint. 00103 return x[0] < 0; 00104 else 00105 // There is a non-zero homogeneous coefficient. 00106 if (is_necessarily_closed()) 00107 return false; 00108 else { 00109 // The constraint is NOT necessarily closed. 00110 const dimension_type eps_index = size() - 1; 00111 if (x[eps_index] >= 0) 00112 // If positive, we have found the constraint epsilon >= 0. 00113 // If zero, one of the `true' dimensions has a non-zero coefficient. 00114 // In both cases, it is not trivially false. 00115 return false; 00116 else { 00117 // Here the epsilon coefficient is negative: strict inequality. 00118 if (x[0] > 0) 00119 // A strict inequality such as `lhs + k > 0', 00120 // where k is a positive integer, cannot be trivially false. 00121 return false; 00122 // Checking for another non-zero coefficient. 00123 for (dimension_type i = eps_index; --i > 0; ) 00124 if (x[i] != 0) 00125 return false; 00126 // We have the inequality `k > 0', 00127 // where k is zero or a negative integer. 00128 return true; 00129 } 00130 } 00131 }
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.
Definition at line 134 of file Constraint.cc.
References is_inconsistent(), is_tautological(), Parma_Polyhedra_Library::Row::normalize(), space_dimension(), STRICT_INEQUALITY, and type().
Referenced by operator!=(), and operator==().
00134 { 00135 const Constraint& x = *this; 00136 const dimension_type x_space_dim = x.space_dimension(); 00137 if (x_space_dim != y.space_dimension()) 00138 return false; 00139 00140 const Type x_type = x.type(); 00141 if (x_type != y.type()) { 00142 // Check for special cases. 00143 if (x.is_tautological()) 00144 return y.is_tautological(); 00145 else 00146 return x.is_inconsistent() && y.is_inconsistent(); 00147 } 00148 00149 if (x_type == STRICT_INEQUALITY) { 00150 // Due to the presence of epsilon-coefficients, syntactically 00151 // different strict inequalities may actually encode the same 00152 // topologically open half-space. 00153 // First, drop the epsilon-coefficient ... 00154 Linear_Expression x_expr(x); 00155 Linear_Expression y_expr(y); 00156 // ... then, re-normalize ... 00157 x_expr.normalize(); 00158 y_expr.normalize(); 00159 // ... and finally check for syntactic equality. 00160 for (dimension_type i = x_space_dim + 1; i-- > 0; ) 00161 if (x_expr[i] != y_expr[i]) 00162 return false; 00163 return true; 00164 } 00165 00166 // `x' and 'y' are of the same type and they are not strict inequalities; 00167 // thus, the epsilon-coefficient, if present, is zero. 00168 // It is sufficient to check for syntactic equality. 00169 for (dimension_type i = x_space_dim + 1; i-- > 0; ) 00170 if (x[i] != y[i]) 00171 return false; 00172 return true; 00173 }
void Parma_Polyhedra_Library::Constraint::ascii_dump | ( | ) | const |
Writes to std::cerr
an ASCII representation of *this
.
Reimplemented from Parma_Polyhedra_Library::Linear_Row.
void Parma_Polyhedra_Library::Constraint::ascii_dump | ( | std::ostream & | s | ) | const [inline] |
Writes to s
an ASCII representation of *this
.
Reimplemented from Parma_Polyhedra_Library::Linear_Row.
Definition at line 316 of file Constraint.inlines.hh.
References Parma_Polyhedra_Library::Linear_Row::ascii_dump().
00316 { 00317 Linear_Row::ascii_dump(s); 00318 }
void Parma_Polyhedra_Library::Constraint::print | ( | ) | const |
bool Parma_Polyhedra_Library::Constraint::ascii_load | ( | std::istream & | s | ) | [inline] |
Loads from s
an ASCII representation (as produced by ascii_dump) and sets *this
accordingly. Returns true
if successful, false
otherwise.
Reimplemented from Parma_Polyhedra_Library::Linear_Row.
Definition at line 321 of file Constraint.inlines.hh.
References Parma_Polyhedra_Library::Linear_Row::ascii_load().
00321 { 00322 return Linear_Row::ascii_load(s); 00323 }
bool Parma_Polyhedra_Library::Constraint::OK | ( | ) | const |
Checks if all the invariants are satisfied.
Definition at line 240 of file Constraint.cc.
References Parma_Polyhedra_Library::Linear_Row::is_necessarily_closed(), Parma_Polyhedra_Library::Row::size(), and Parma_Polyhedra_Library::Linear_Row::strong_normalize().
00240 { 00241 // Topology consistency check. 00242 const dimension_type min_size = is_necessarily_closed() ? 1 : 2; 00243 if (size() < min_size) { 00244 #ifndef NDEBUG 00245 std::cerr << "Constraint has fewer coefficients than the minimum " 00246 << "allowed by its topology:" 00247 << std::endl 00248 << "size is " << size() 00249 << ", minimum is " << min_size << "." 00250 << std::endl; 00251 #endif 00252 return false; 00253 } 00254 00255 // Normalization check. 00256 Constraint tmp = *this; 00257 tmp.strong_normalize(); 00258 if (tmp != *this) { 00259 #ifndef NDEBUG 00260 std::cerr << "Constraint is not strongly normalized as it should be." 00261 << std::endl; 00262 #endif 00263 return false; 00264 } 00265 00266 // All tests passed. 00267 return true; 00268 }
void Parma_Polyhedra_Library::Constraint::swap | ( | Constraint & | y | ) | [inline] |
Swaps *this
with y
.
Definition at line 326 of file Constraint.inlines.hh.
References Parma_Polyhedra_Library::Linear_Row::swap().
Referenced by swap().
00326 { 00327 Linear_Row::swap(y); 00328 }
Parma_Polyhedra_Library::Constraint::Parma_Polyhedra_Library::Linear_Expression::Linear_Expression | ( | const Constraint & | c | ) | [private] |
void Parma_Polyhedra_Library::Constraint::throw_dimension_incompatible | ( | const char * | method, | |
const char * | name_var, | |||
Variable | v | |||
) | const [private] |
Throws a std::invalid_argument
exception containing the appropriate error message.
Definition at line 35 of file Constraint.cc.
References Parma_Polyhedra_Library::Variable::space_dimension(), and space_dimension().
Referenced by coefficient().
00037 { 00038 std::ostringstream s; 00039 s << "PPL::Constraint::" << method << ":" << std::endl 00040 << "this->space_dimension() == " << space_dimension() << ", " 00041 << name_var << ".space_dimension() == " << v.space_dimension() << "."; 00042 throw std::invalid_argument(s.str()); 00043 }
PPL::Constraint Parma_Polyhedra_Library::Constraint::construct_epsilon_geq_zero | ( | ) | [static, private] |
Builds a new copy of the zero-dimension space constraint (used to implement NNC polyhedra).
Definition at line 46 of file Constraint.cc.
References NONSTRICT_INEQUALITY, and Parma_Polyhedra_Library::NOT_NECESSARILY_CLOSED.
Referenced by epsilon_geq_zero().
00046 { 00047 Linear_Expression e = Variable(0); 00048 Constraint c(e, NONSTRICT_INEQUALITY, NOT_NECESSARILY_CLOSED); 00049 return c; 00050 }
const Constraint & Parma_Polyhedra_Library::Constraint::epsilon_geq_zero | ( | ) | [inline, static, private] |
Returns the zero-dimension space constraint .
Definition at line 303 of file Constraint.inlines.hh.
References construct_epsilon_geq_zero().
Referenced by Parma_Polyhedra_Library::Constraint_System::add_low_level_constraints().
00303 { 00304 static const Constraint eps_geq_zero = construct_epsilon_geq_zero(); 00305 return eps_geq_zero; 00306 }
const Constraint & Parma_Polyhedra_Library::Constraint::epsilon_leq_one | ( | ) | [inline, static, private] |
The zero-dimension space constraint (used to implement NNC polyhedra).
Definition at line 309 of file Constraint.inlines.hh.
References Parma_Polyhedra_Library::Coefficient_one(), and Parma_Polyhedra_Library::Linear_Expression::zero().
Referenced by Parma_Polyhedra_Library::Constraint_System::add_low_level_constraints(), Parma_Polyhedra_Library::Polyhedron::strongly_minimize_constraints(), and Parma_Polyhedra_Library::Polyhedron::topological_closure_assign().
00309 { 00310 static const Constraint 00311 eps_leq_one(Linear_Expression::zero() < Coefficient_one()); 00312 return eps_leq_one; 00313 }
void Parma_Polyhedra_Library::Constraint::set_is_equality | ( | ) | [inline, private] |
Sets the constraint type to EQUALITY
.
Definition at line 102 of file Constraint.inlines.hh.
References Parma_Polyhedra_Library::Linear_Row::set_is_line_or_equality().
Referenced by Parma_Polyhedra_Library::Polyhedron::add_recycled_constraints(), and Parma_Polyhedra_Library::Polyhedron::concatenate_assign().
00102 { 00103 set_is_line_or_equality(); 00104 }
void Parma_Polyhedra_Library::Constraint::set_is_inequality | ( | ) | [inline, private] |
Sets the constraint to be an inequality.
Whether the constraint type will become NONSTRICT_INEQUALITY
or STRICT_INEQUALITY
depends on the topology and the value of the low-level coefficients of the constraint.
Definition at line 107 of file Constraint.inlines.hh.
References Parma_Polyhedra_Library::Linear_Row::set_is_ray_or_point_or_inequality().
00107 { 00108 set_is_ray_or_point_or_inequality(); 00109 }
friend class Parma_Polyhedra_Library::Congruence [friend] |
Definition at line 361 of file Constraint.defs.hh.
friend class Parma_Polyhedra_Library::Scalar_Products [friend] |
Definition at line 362 of file Constraint.defs.hh.
friend class Parma_Polyhedra_Library::Topology_Adjusted_Scalar_Product_Sign [friend] |
Definition at line 363 of file Constraint.defs.hh.
friend class Parma_Polyhedra_Library::Constraint_System [friend] |
Definition at line 364 of file Constraint.defs.hh.
friend class Parma_Polyhedra_Library::Constraint_System::const_iterator [friend] |
Definition at line 365 of file Constraint.defs.hh.
friend class Parma_Polyhedra_Library::Polyhedron [friend] |
Definition at line 367 of file Constraint.defs.hh.
Constraint operator== | ( | const Linear_Expression & | e1, | |
const Linear_Expression & | e2 | |||
) | [friend] |
Returns the constraint e1
= e2
.
Definition at line 147 of file Constraint.inlines.hh.
00147 { 00148 Linear_Expression diff = e1 - e2; 00149 Constraint c(diff, Constraint::EQUALITY, NECESSARILY_CLOSED); 00150 // Enforce normalization. 00151 c.strong_normalize(); 00152 return c; 00153 }
Constraint operator== | ( | const Linear_Expression & | e, | |
Coefficient_traits::const_reference | n | |||
) | [friend] |
Returns the constraint e
= n
.
Definition at line 220 of file Constraint.inlines.hh.
00220 { 00221 Linear_Expression diff = e - n; 00222 Constraint c(diff, Constraint::EQUALITY, NECESSARILY_CLOSED); 00223 // Enforce normalization. 00224 c.strong_normalize(); 00225 return c; 00226 }
Constraint operator== | ( | Coefficient_traits::const_reference | n, | |
const Linear_Expression & | e | |||
) | [friend] |
Returns the constraint n
= e
.
Definition at line 186 of file Constraint.inlines.hh.
00186 { 00187 Linear_Expression diff = n - e; 00188 Constraint c(diff, Constraint::EQUALITY, NECESSARILY_CLOSED); 00189 // Enforce normalization. 00190 c.strong_normalize(); 00191 return c; 00192 }
Constraint operator>= | ( | const Linear_Expression & | e1, | |
const Linear_Expression & | e2 | |||
) | [friend] |
Returns the constraint e1
>= e2
.
Definition at line 157 of file Constraint.inlines.hh.
00157 { 00158 Linear_Expression diff = e1 - e2; 00159 Constraint c(diff, Constraint::NONSTRICT_INEQUALITY, NECESSARILY_CLOSED); 00160 // Enforce normalization. 00161 c.normalize(); 00162 return c; 00163 }
Constraint operator>= | ( | const Linear_Expression & | e, | |
Coefficient_traits::const_reference | n | |||
) | [friend] |
Returns the constraint e
>= n
.
Definition at line 230 of file Constraint.inlines.hh.
00230 { 00231 Linear_Expression diff = e - n; 00232 Constraint c(diff, Constraint::NONSTRICT_INEQUALITY, NECESSARILY_CLOSED); 00233 // Enforce normalization. 00234 c.normalize(); 00235 return c; 00236 }
Constraint operator>= | ( | Coefficient_traits::const_reference | n, | |
const Linear_Expression & | e | |||
) | [friend] |
Returns the constraint n
>= e
.
Definition at line 196 of file Constraint.inlines.hh.
00196 { 00197 Linear_Expression diff = n - e; 00198 Constraint c(diff, Constraint::NONSTRICT_INEQUALITY, NECESSARILY_CLOSED); 00199 // Enforce normalization. 00200 c.normalize(); 00201 return c; 00202 }
Constraint operator<= | ( | const Linear_Expression & | e1, | |
const Linear_Expression & | e2 | |||
) | [friend] |
Constraint operator<= | ( | const Linear_Expression & | e, | |
Coefficient_traits::const_reference | n | |||
) | [friend] |
Constraint operator<= | ( | Coefficient_traits::const_reference | n, | |
const Linear_Expression & | e | |||
) | [friend] |
Constraint operator> | ( | const Linear_Expression & | e1, | |
const Linear_Expression & | e2 | |||
) | [friend] |
Returns the constraint e1
> e2
.
Definition at line 167 of file Constraint.inlines.hh.
00167 { 00168 Linear_Expression diff; 00169 // Setting the epsilon coefficient to -1. 00170 // NOTE: this also enforces normalization. 00171 const dimension_type e1_dim = e1.space_dimension(); 00172 const dimension_type e2_dim = e2.space_dimension(); 00173 if (e1_dim > e2_dim) 00174 diff -= Variable(e1_dim); 00175 else 00176 diff -= Variable(e2_dim); 00177 diff += e1; 00178 diff -= e2; 00179 00180 Constraint c(diff, Constraint::STRICT_INEQUALITY, NOT_NECESSARILY_CLOSED); 00181 return c; 00182 }
Constraint operator> | ( | const Linear_Expression & | e, | |
Coefficient_traits::const_reference | n | |||
) | [friend] |
Returns the constraint e
> n
.
Definition at line 240 of file Constraint.inlines.hh.
00240 { 00241 Linear_Expression diff; 00242 // Setting the epsilon coefficient to -1. 00243 // NOTE: this also enforces normalization. 00244 diff -= Variable(e.space_dimension()); 00245 diff += e; 00246 diff -= n; 00247 00248 Constraint c(diff, Constraint::STRICT_INEQUALITY, NOT_NECESSARILY_CLOSED); 00249 c.set_not_necessarily_closed(); 00250 c.set_is_inequality(); 00251 return c; 00252 }
Constraint operator> | ( | Coefficient_traits::const_reference | n, | |
const Linear_Expression & | e | |||
) | [friend] |
Returns the constraint n
> e
.
Definition at line 206 of file Constraint.inlines.hh.
00206 { 00207 Linear_Expression diff; 00208 // Setting the epsilon coefficient to -1. 00209 // NOTE: this also enforces normalization. 00210 diff -= Variable(e.space_dimension()); 00211 diff += n; 00212 diff -= e; 00213 00214 Constraint c(diff, Constraint::STRICT_INEQUALITY, NOT_NECESSARILY_CLOSED); 00215 return c; 00216 }
Constraint operator< | ( | const Linear_Expression & | e1, | |
const Linear_Expression & | e2 | |||
) | [friend] |
Constraint operator< | ( | const Linear_Expression & | e, | |
Coefficient_traits::const_reference | n | |||
) | [friend] |
Constraint operator< | ( | Coefficient_traits::const_reference | n, | |
const Linear_Expression & | e | |||
) | [friend] |
bool operator== | ( | const Constraint & | x, | |
const Constraint & | y | |||
) | [related] |
Returns true
if and only if x
is equivalent to y
.
Definition at line 135 of file Constraint.inlines.hh.
References is_equivalent_to().
bool operator!= | ( | const Constraint & | x, | |
const Constraint & | y | |||
) | [related] |
Returns true
if and only if x
is not equivalent to y
.
Definition at line 141 of file Constraint.inlines.hh.
References is_equivalent_to().
void swap | ( | Parma_Polyhedra_Library::Constraint & | x, | |
Parma_Polyhedra_Library::Constraint & | y | |||
) | [related] |
Specializes std::swap
.
Definition at line 336 of file Constraint.inlines.hh.
References swap().
00337 { 00338 x.swap(y); 00339 }
std::ostream & operator<< | ( | std::ostream & | s, | |
const Constraint & | c | |||
) | [related] |
Output operator.
Definition at line 177 of file Constraint.cc.
References coefficient(), Parma_Polyhedra_Library::Coefficient_zero(), EQUALITY, inhomogeneous_term(), Parma_Polyhedra_Library::neg_assign(), NONSTRICT_INEQUALITY, relation_symbol(), space_dimension(), STRICT_INEQUALITY, and type().
00177 { 00178 const int num_variables = c.space_dimension(); 00179 bool first = true; 00180 for (int v = 0; v < num_variables; ++v) { 00181 Coefficient cv = c.coefficient(Variable(v)); 00182 if (cv != 0) { 00183 if (!first) { 00184 if (cv > 0) 00185 s << " + "; 00186 else { 00187 s << " - "; 00188 neg_assign(cv); 00189 } 00190 } 00191 else 00192 first = false; 00193 if (cv == -1) 00194 s << "-"; 00195 else if (cv != 1) 00196 s << cv << "*"; 00197 s << PPL::Variable(v); 00198 } 00199 } 00200 if (first) 00201 s << Coefficient_zero(); 00202 const char* relation_symbol = 0; 00203 switch (c.type()) { 00204 case Constraint::EQUALITY: 00205 relation_symbol = " = "; 00206 break; 00207 case Constraint::NONSTRICT_INEQUALITY: 00208 relation_symbol = " >= "; 00209 break; 00210 case Constraint::STRICT_INEQUALITY: 00211 relation_symbol = " > "; 00212 break; 00213 } 00214 s << relation_symbol << -c.inhomogeneous_term(); 00215 return s; 00216 }
std::ostream & operator<< | ( | std::ostream & | s, | |
const Constraint::Type & | t | |||
) | [related] |
Output operator.
Definition at line 220 of file Constraint.cc.
References EQUALITY, NONSTRICT_INEQUALITY, and STRICT_INEQUALITY.
00220 { 00221 const char* n = 0; 00222 switch (t) { 00223 case Constraint::EQUALITY: 00224 n = "EQUALITY"; 00225 break; 00226 case Constraint::NONSTRICT_INEQUALITY: 00227 n = "NONSTRICT_INEQUALITY"; 00228 break; 00229 case Constraint::STRICT_INEQUALITY: 00230 n = "STRICT_INEQUALITY"; 00231 break; 00232 } 00233 s << n; 00234 return s; 00235 }