#include <Constraint_System.defs.hh>
Public Member Functions | |
Constraint_System () | |
Default constructor: builds an empty system of constraints. | |
Constraint_System (const Constraint &c) | |
Builds the singleton system containing only constraint c . | |
Constraint_System (const Constraint_System &cs) | |
Ordinary copy-constructor. | |
~Constraint_System () | |
Destructor. | |
Constraint_System & | operator= (const Constraint_System &y) |
Assignment operator. | |
dimension_type | space_dimension () const |
Returns the dimension of the vector space enclosing *this . | |
bool | has_strict_inequalities () const |
Returns true if and only if *this contains one or more strict inequality constraints. | |
void | clear () |
Removes all the constraints from the constraint system and sets its space dimension to 0. | |
void | insert (const Constraint &c) |
Inserts in *this a copy of the constraint c , increasing the number of space dimensions if needed. | |
const_iterator | begin () const |
Returns the const_iterator pointing to the first constraint, if *this is not empty; otherwise, returns the past-the-end const_iterator. | |
const_iterator | end () const |
Returns the past-the-end const_iterator. | |
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) and sets *this accordingly. Returns true if successful, false otherwise. | |
memory_size_type | total_memory_in_bytes () const |
Returns 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 . | |
void | swap (Constraint_System &y) |
Swaps *this with y . | |
Static Public Member Functions | |
static dimension_type | max_space_dimension () |
Returns the maximum space dimension a Constraint_System can handle. | |
static const Constraint_System & | zero_dim_empty () |
Returns the singleton system containing only Constraint::zero_dim_false(). | |
Private Member Functions | |
Constraint_System (Topology topol) | |
Builds an empty system of constraints having the specified topology. | |
Constraint_System (Topology topol, dimension_type n_rows, dimension_type n_columns) | |
Builds a system of n_rows constraints on a n_columns - 1 dimensional space (including the ![]() topol is NOT_NECESSARILY_CLOSED ). | |
bool | adjust_topology_and_space_dimension (Topology topol, dimension_type num_dimensions) |
Adjusts *this so that it matches the topology and the number of space dimensions given as parameters (adding or removing columns if needed). Returns false if and only if topol is equal to NECESSARILY_CLOSED and *this contains strict inequalities. | |
Constraint & | operator[] (dimension_type k) |
Returns the k- th constraint of the system. | |
const Constraint & | operator[] (dimension_type k) const |
Returns a constant reference to the k- th constraint of the system. | |
bool | satisfies_all_constraints (const Generator &g) const |
Returns true if g satisfies all the constraints. | |
void | affine_preimage (dimension_type v, const Linear_Expression &expr, Coefficient_traits::const_reference denominator) |
Substitutes a given column of coefficients by a given affine expression. | |
dimension_type | num_equalities () const |
Returns the number of equality constraints. | |
dimension_type | num_inequalities () const |
Returns the number of inequality constraints. | |
void | simplify () |
Applies Gaussian's elimination and back-substitution so as to provide a partial simplification of the system of constraints. | |
void | insert_pending (const Constraint &c) |
Inserts in *this a copy of the constraint c , increasing the number of space dimensions if needed. It is a pending constraint. | |
void | add_low_level_constraints () |
Adds low-level constraints to the constraint system. | |
Friends | |
class | const_iterator |
class | Parma_Polyhedra_Library::Polyhedron |
class | Parma_Polyhedra_Library::LP_Problem |
bool | operator== (const Polyhedron &x, const Polyhedron &y) |
Returns true if and only if x and y are the same polyhedron. | |
Related Functions | |
(Note that these are not member functions.) | |
std::ostream & | operator<< (std::ostream &s, const Constraint_System &cs) |
Output operator. | |
void | swap (Parma_Polyhedra_Library::Constraint_System &x, Parma_Polyhedra_Library::Constraint_System &y) |
Specializes std::swap . | |
Classes | |
class | const_iterator |
An iterator over a system of constraints. More... |
An object of the class Constraint_System is a system of constraints, i.e., a multiset of objects of the class Constraint. When inserting constraints in a system, space dimensions are automatically adjusted so that all the constraints in the system are defined on the same vector space.
x
and y
are defined as follows: Variable x(0); Variable y(1);
Constraint_System cs; cs.insert(x >= 0); cs.insert(x <= 3); cs.insert(y >= 0); cs.insert(y <= 3);
cs.insert(x + y > 0); cs.insert(x + y < 6); cs.insert(x - y < 3); cs.insert(y - x < 3);
Constraint_System cs; cs.insert(x >= 0); cs.insert(x - y <= 0); cs.insert(x - y + 1 >= 0);
Definition at line 127 of file Constraint_System.defs.hh.
Parma_Polyhedra_Library::Constraint_System::Constraint_System | ( | ) | [inline] |
Default constructor: builds an empty system of constraints.
Definition at line 31 of file Constraint_System.inlines.hh.
00032 : Linear_System(NECESSARILY_CLOSED) { 00033 }
Parma_Polyhedra_Library::Constraint_System::Constraint_System | ( | const Constraint & | c | ) | [inline, explicit] |
Builds the singleton system containing only constraint c
.
Definition at line 36 of file Constraint_System.inlines.hh.
References Parma_Polyhedra_Library::Linear_System::insert().
00037 : Linear_System(c.topology()) { 00038 Linear_System::insert(c); 00039 }
Parma_Polyhedra_Library::Constraint_System::Constraint_System | ( | const Constraint_System & | cs | ) | [inline] |
Ordinary copy-constructor.
Definition at line 42 of file Constraint_System.inlines.hh.
00043 : Linear_System(cs) { 00044 }
Parma_Polyhedra_Library::Constraint_System::~Constraint_System | ( | ) | [inline] |
Parma_Polyhedra_Library::Constraint_System::Constraint_System | ( | Topology | topol | ) | [inline, explicit, private] |
Builds an empty system of constraints having the specified topology.
Definition at line 47 of file Constraint_System.inlines.hh.
00048 : Linear_System(topol) { 00049 }
Parma_Polyhedra_Library::Constraint_System::Constraint_System | ( | Topology | topol, | |
dimension_type | n_rows, | |||
dimension_type | n_columns | |||
) | [inline, private] |
Builds a system of n_rows
constraints on a n_columns
- 1 dimensional space (including the dimension, if
topol
is NOT_NECESSARILY_CLOSED
).
Definition at line 52 of file Constraint_System.inlines.hh.
00055 : Linear_System(topol, n_rows, n_columns) { 00056 }
Constraint_System & Parma_Polyhedra_Library::Constraint_System::operator= | ( | const Constraint_System & | y | ) | [inline] |
Assignment operator.
Definition at line 63 of file Constraint_System.inlines.hh.
References Parma_Polyhedra_Library::Linear_System::operator=().
00063 { 00064 Linear_System::operator=(y); 00065 return *this; 00066 }
dimension_type Parma_Polyhedra_Library::Constraint_System::max_space_dimension | ( | ) | [inline, static] |
Returns the maximum space dimension a Constraint_System can handle.
Reimplemented from Parma_Polyhedra_Library::Linear_System.
Definition at line 79 of file Constraint_System.inlines.hh.
References Parma_Polyhedra_Library::Linear_System::max_space_dimension().
Referenced by Parma_Polyhedra_Library::Polyhedron::max_space_dimension(), and Parma_Polyhedra_Library::LP_Problem::max_space_dimension().
00079 { 00080 return Linear_System::max_space_dimension(); 00081 }
dimension_type Parma_Polyhedra_Library::Constraint_System::space_dimension | ( | ) | const [inline] |
Returns the dimension of the vector space enclosing *this
.
Reimplemented from Parma_Polyhedra_Library::Linear_System.
Definition at line 84 of file Constraint_System.inlines.hh.
References Parma_Polyhedra_Library::Linear_System::space_dimension().
Referenced by Parma_Polyhedra_Library::Grid::add_congruences(), Parma_Polyhedra_Library::Grid::add_congruences_and_minimize(), Parma_Polyhedra_Library::Grid::add_constraints(), Parma_Polyhedra_Library::Grid::add_constraints_and_minimize(), Parma_Polyhedra_Library::Grid::add_recycled_congruences(), Parma_Polyhedra_Library::Grid::add_recycled_congruences_and_minimize(), Parma_Polyhedra_Library::Polyhedron::add_recycled_constraints(), Parma_Polyhedra_Library::Grid::add_recycled_constraints(), Parma_Polyhedra_Library::Polyhedron::add_recycled_constraints_and_minimize(), Parma_Polyhedra_Library::Grid::add_recycled_constraints_and_minimize(), adjust_topology_and_space_dimension(), affine_preimage(), Parma_Polyhedra_Library::BD_Shape< T >::BD_Shape(), Parma_Polyhedra_Library::Polyhedron::BHRZ03_combining_constraints(), Parma_Polyhedra_Library::LP_Problem::compute_generator(), Parma_Polyhedra_Library::Polyhedron::constraints(), Parma_Polyhedra_Library::BD_Shape< T >::get_limiting_shape(), Parma_Polyhedra_Library::Grid::Grid(), insert(), insert_pending(), Parma_Polyhedra_Library::BD_Shape< T >::limited_BHMZ05_extrapolation_assign(), Parma_Polyhedra_Library::Polyhedron::limited_BHRZ03_extrapolation_assign(), Parma_Polyhedra_Library::BD_Shape< T >::limited_CC76_extrapolation_assign(), Parma_Polyhedra_Library::Polyhedron::limited_H79_extrapolation_assign(), Parma_Polyhedra_Library::Polyhedron::OK(), Parma_Polyhedra_Library::LP_Problem::OK(), Parma_Polyhedra_Library::Polyhedron::Polyhedron(), satisfies_all_constraints(), Parma_Polyhedra_Library::LP_Problem::space_dimension(), Parma_Polyhedra_Library::Polyhedron::throw_dimension_incompatible(), and Parma_Polyhedra_Library::Grid::throw_dimension_incompatible().
00084 { 00085 return Linear_System::space_dimension(); 00086 }
bool Parma_Polyhedra_Library::Constraint_System::has_strict_inequalities | ( | ) | const |
Returns true
if and only if *this
contains one or more strict inequality constraints.
Definition at line 197 of file Constraint_System.cc.
References Parma_Polyhedra_Library::Linear_System::is_necessarily_closed(), Parma_Polyhedra_Library::Constraint::is_tautological(), Parma_Polyhedra_Library::Matrix::num_columns(), and Parma_Polyhedra_Library::Matrix::num_rows().
Referenced by Parma_Polyhedra_Library::LP_Problem::add_constraints(), Parma_Polyhedra_Library::Polyhedron::add_recycled_constraints(), Parma_Polyhedra_Library::Polyhedron::add_recycled_constraints_and_minimize(), adjust_topology_and_space_dimension(), Parma_Polyhedra_Library::BD_Shape< T >::BD_Shape(), Parma_Polyhedra_Library::Polyhedron::is_topologically_closed(), Parma_Polyhedra_Library::BD_Shape< T >::limited_BHMZ05_extrapolation_assign(), Parma_Polyhedra_Library::Polyhedron::limited_BHRZ03_extrapolation_assign(), Parma_Polyhedra_Library::BD_Shape< T >::limited_CC76_extrapolation_assign(), Parma_Polyhedra_Library::Polyhedron::limited_H79_extrapolation_assign(), Parma_Polyhedra_Library::LP_Problem::OK(), and ppl_Constraint_System_has_strict_inequalities().
00197 { 00198 if (is_necessarily_closed()) 00199 return false; 00200 const Constraint_System& cs = *this; 00201 const dimension_type eps_index = cs.num_columns() - 1; 00202 // We verify if the system has strict inequalities 00203 // also in the pending part. 00204 for (dimension_type i = cs.num_rows(); i-- > 0; ) { 00205 const Constraint& c = cs[i]; 00206 // Optimized type checking: we already know the topology; 00207 // also, equalities have the epsilon coefficient equal to zero. 00208 // NOTE: the constraint eps_leq_one should not be considered 00209 // a strict inequality. 00210 if (c[eps_index] < 0 && !c.is_tautological()) 00211 return true; 00212 } 00213 return false; 00214 }
void Parma_Polyhedra_Library::Constraint_System::clear | ( | ) | [inline] |
Removes all the constraints from the constraint system and sets its space dimension to 0.
Reimplemented from Parma_Polyhedra_Library::Linear_System.
Definition at line 89 of file Constraint_System.inlines.hh.
References Parma_Polyhedra_Library::Linear_System::clear().
Referenced by Parma_Polyhedra_Library::Polyhedron::add_space_dimensions_and_embed(), Parma_Polyhedra_Library::Polyhedron::add_space_dimensions_and_project(), Parma_Polyhedra_Library::Polyhedron::BHRZ03_combining_constraints(), Parma_Polyhedra_Library::Polyhedron::map_space_dimensions(), Parma_Polyhedra_Library::Polyhedron::remove_higher_space_dimensions(), Parma_Polyhedra_Library::Polyhedron::remove_space_dimensions(), Parma_Polyhedra_Library::Polyhedron::set_empty(), and Parma_Polyhedra_Library::Polyhedron::set_zero_dim_univ().
00089 { 00090 Linear_System::clear(); 00091 }
void Parma_Polyhedra_Library::Constraint_System::insert | ( | const Constraint & | c | ) |
Inserts in *this
a copy of the constraint c
, increasing the number of space dimensions if needed.
Definition at line 217 of file Constraint_System.cc.
References Parma_Polyhedra_Library::Matrix::add_zero_columns(), Parma_Polyhedra_Library::Linear_System::insert(), Parma_Polyhedra_Library::Linear_System::is_necessarily_closed(), Parma_Polyhedra_Library::Linear_System::num_pending_rows(), OK(), Parma_Polyhedra_Library::Linear_System::set_not_necessarily_closed(), space_dimension(), Parma_Polyhedra_Library::Constraint::space_dimension(), Parma_Polyhedra_Library::Linear_Row::topology(), and Parma_Polyhedra_Library::Linear_System::topology().
Referenced by Parma_Polyhedra_Library::Polyhedron::add_congruences(), Parma_Polyhedra_Library::Polyhedron::add_constraint(), Parma_Polyhedra_Library::LP_Problem::add_constraint(), Parma_Polyhedra_Library::LP_Problem::add_constraints(), add_low_level_constraints(), Parma_Polyhedra_Library::Polyhedron::BHRZ03_combining_constraints(), Parma_Polyhedra_Library::Bounding_Box::constraints(), Parma_Polyhedra_Library::BD_Shape< T >::constraints(), Parma_Polyhedra_Library::Polyhedron::expand_space_dimension(), Parma_Polyhedra_Library::Polyhedron::limited_BHRZ03_extrapolation_assign(), limited_extrapolation_assign(), limited_extrapolation_assign_with_tokens(), Parma_Polyhedra_Library::Polyhedron::limited_H79_extrapolation_assign(), Parma_Polyhedra_Library::BD_Shape< T >::minimized_constraints(), Parma_Polyhedra_Library::Polyhedron::Polyhedron(), ppl_Constraint_System_insert_Constraint(), ppl_LP_Problem_add_constraints(), ppl_new_C_Polyhedron_from_constraints(), ppl_new_LP_Problem(), ppl_new_NNC_Polyhedron_from_constraints(), ppl_Polyhedron_add_constraints(), ppl_Polyhedron_add_constraints_and_minimize(), Parma_Polyhedra_Library::Polyhedron::select_CH78_constraints(), Parma_Polyhedra_Library::Polyhedron::select_H79_constraints(), Parma_Polyhedra_Library::Polyhedron::strongly_minimize_constraints(), and Parma_Polyhedra_Library::Polyhedron::topological_closure_assign().
00217 { 00218 // We are sure that the matrix has no pending rows 00219 // and that the new row is not a pending constraint. 00220 assert(num_pending_rows() == 0); 00221 if (topology() == c.topology()) 00222 Linear_System::insert(c); 00223 else 00224 // `*this' and `c' have different topologies. 00225 if (is_necessarily_closed()) { 00226 // Padding the matrix with a columns of zeroes 00227 // corresponding to the epsilon coefficients. 00228 add_zero_columns(1); 00229 set_not_necessarily_closed(); 00230 Linear_System::insert(c); 00231 } 00232 else { 00233 // Here `*this' is NNC and `c' is necessarily closed. 00234 // Copying the constraint adding the epsilon coefficient 00235 // and the missing space dimensions, if any. 00236 // FIXME: provide a resizing copy-constructor taking 00237 // topology and the space dimension. 00238 const dimension_type new_size = 2 + std::max(c.space_dimension(), 00239 space_dimension()); 00240 Constraint tmp_c(c, new_size); 00241 tmp_c.set_not_necessarily_closed(); 00242 Linear_System::insert(tmp_c); 00243 } 00244 assert(OK()); 00245 }
const Constraint_System & Parma_Polyhedra_Library::Constraint_System::zero_dim_empty | ( | ) | [inline, static] |
Returns the singleton system containing only Constraint::zero_dim_false().
Definition at line 94 of file Constraint_System.inlines.hh.
References Parma_Polyhedra_Library::Constraint::zero_dim_false().
Referenced by Parma_Polyhedra_Library::Polyhedron::constraints(), Parma_Polyhedra_Library::Bounding_Box::constraints(), Parma_Polyhedra_Library::BD_Shape< T >::constraints(), and Parma_Polyhedra_Library::BD_Shape< T >::minimized_constraints().
00094 { 00095 static const Constraint_System zdf(Constraint::zero_dim_false()); 00096 return zdf; 00097 }
Constraint_System::const_iterator Parma_Polyhedra_Library::Constraint_System::begin | ( | ) | const [inline] |
Returns the const_iterator pointing to the first constraint, if *this
is not empty; otherwise, returns the past-the-end const_iterator.
Reimplemented from Parma_Polyhedra_Library::Matrix.
Definition at line 162 of file Constraint_System.inlines.hh.
References Parma_Polyhedra_Library::Matrix::begin().
Referenced by Parma_Polyhedra_Library::BD_Shape< T >::add_constraints(), Parma_Polyhedra_Library::Polyhedron::add_recycled_constraints(), Parma_Polyhedra_Library::Polyhedron::add_recycled_constraints_and_minimize(), Parma_Polyhedra_Library::Polyhedron::affine_dimension(), Parma_Polyhedra_Library::BD_Shape< T >::BD_Shape(), Parma_Polyhedra_Library::BD_Shape< T >::bds_difference_assign(), Parma_Polyhedra_Library::BHRZ03_Certificate::BHRZ03_Certificate(), Parma_Polyhedra_Library::C_Polyhedron::C_Polyhedron(), Parma_Polyhedra_Library::H79_Certificate::compare(), Parma_Polyhedra_Library::BHRZ03_Certificate::compare(), Parma_Polyhedra_Library::Congruence_System::Congruence_System(), Parma_Polyhedra_Library::Polyhedron::expand_space_dimension(), Parma_Polyhedra_Library::BD_Shape< T >::get_limiting_shape(), Parma_Polyhedra_Library::Grid::Grid(), Parma_Polyhedra_Library::H79_Certificate::H79_Certificate(), Parma_Polyhedra_Library::Polyhedra_Powerset< PH >::linear_partition(), operator<<(), Parma_Polyhedra_Library::Polyhedron::poly_difference_assign(), ppl_Constraint_System_begin(), ppl_LP_Problem_constraints(), ppl_Polyhedron_get_constraints(), ppl_Polyhedron_get_minimized_constraints(), and Parma_Polyhedra_Library::Polyhedron::shrink_bounding_box().
00162 { 00163 const_iterator i(Linear_System::begin(), *this); 00164 i.skip_forward(); 00165 return i; 00166 }
Constraint_System::const_iterator Parma_Polyhedra_Library::Constraint_System::end | ( | ) | const [inline] |
Returns the past-the-end const_iterator.
Reimplemented from Parma_Polyhedra_Library::Matrix.
Definition at line 169 of file Constraint_System.inlines.hh.
References Parma_Polyhedra_Library::Matrix::end().
Referenced by Parma_Polyhedra_Library::BD_Shape< T >::add_constraints(), Parma_Polyhedra_Library::Polyhedron::add_recycled_constraints(), Parma_Polyhedra_Library::Polyhedron::add_recycled_constraints_and_minimize(), Parma_Polyhedra_Library::Polyhedron::affine_dimension(), Parma_Polyhedra_Library::BD_Shape< T >::BD_Shape(), Parma_Polyhedra_Library::BD_Shape< T >::bds_difference_assign(), Parma_Polyhedra_Library::BHRZ03_Certificate::BHRZ03_Certificate(), Parma_Polyhedra_Library::C_Polyhedron::C_Polyhedron(), Parma_Polyhedra_Library::H79_Certificate::compare(), Parma_Polyhedra_Library::BHRZ03_Certificate::compare(), Parma_Polyhedra_Library::Congruence_System::Congruence_System(), Parma_Polyhedra_Library::Polyhedron::expand_space_dimension(), Parma_Polyhedra_Library::BD_Shape< T >::get_limiting_shape(), Parma_Polyhedra_Library::Grid::Grid(), Parma_Polyhedra_Library::H79_Certificate::H79_Certificate(), Parma_Polyhedra_Library::Polyhedra_Powerset< PH >::linear_partition(), operator<<(), Parma_Polyhedra_Library::Polyhedron::poly_difference_assign(), ppl_Constraint_System_end(), ppl_LP_Problem_constraints(), ppl_Polyhedron_get_constraints(), ppl_Polyhedron_get_minimized_constraints(), and Parma_Polyhedra_Library::Polyhedron::shrink_bounding_box().
00169 { 00170 const const_iterator i(Linear_System::end(), *this); 00171 return i; 00172 }
bool Parma_Polyhedra_Library::Constraint_System::OK | ( | ) | const |
Checks if all the invariants are satisfied.
Returns true
if and only if *this
is a valid Linear_System and each row in the system is a valid Constraint.
Reimplemented from Parma_Polyhedra_Library::Matrix.
Definition at line 562 of file Constraint_System.cc.
References Parma_Polyhedra_Library::Matrix::num_rows(), and Parma_Polyhedra_Library::Matrix::OK().
Referenced by adjust_topology_and_space_dimension(), ascii_load(), insert(), insert_pending(), and Parma_Polyhedra_Library::Polyhedron::OK().
00562 { 00563 // A Constraint_System must be a valid Linear_System; do not check for 00564 // strong normalization, since this will be done when 00565 // checking each individual constraint. 00566 if (!Linear_System::OK(false)) 00567 return false; 00568 00569 // Checking each constraint in the system. 00570 const Constraint_System& x = *this; 00571 for (dimension_type i = num_rows(); i-- > 0; ) 00572 if (!x[i].OK()) 00573 return false; 00574 00575 // All checks passed. 00576 return true; 00577 }
void Parma_Polyhedra_Library::Constraint_System::ascii_dump | ( | ) | const |
Writes to std::cerr
an ASCII representation of *this
.
Reimplemented from Parma_Polyhedra_Library::Linear_System.
Referenced by Parma_Polyhedra_Library::Polyhedron::ascii_dump(), Parma_Polyhedra_Library::LP_Problem::ascii_dump(), and Parma_Polyhedra_Library::Polyhedron::OK().
void Parma_Polyhedra_Library::Constraint_System::ascii_dump | ( | std::ostream & | s | ) | const |
Writes to s
an ASCII representation of *this
.
Reimplemented from Parma_Polyhedra_Library::Linear_System.
Definition at line 456 of file Constraint_System.cc.
References Parma_Polyhedra_Library::Constraint::EQUALITY, Parma_Polyhedra_Library::Linear_System::first_pending_row(), Parma_Polyhedra_Library::Linear_System::is_necessarily_closed(), Parma_Polyhedra_Library::Linear_System::is_sorted(), Parma_Polyhedra_Library::Constraint::NONSTRICT_INEQUALITY, Parma_Polyhedra_Library::Matrix::num_columns(), Parma_Polyhedra_Library::Matrix::num_rows(), Parma_Polyhedra_Library::Constraint::STRICT_INEQUALITY, and Parma_Polyhedra_Library::Constraint::type().
00456 { 00457 const Constraint_System& x = *this; 00458 const dimension_type x_num_rows = x.num_rows(); 00459 const dimension_type x_num_columns = x.num_columns(); 00460 s << "topology " << (is_necessarily_closed() 00461 ? "NECESSARILY_CLOSED" 00462 : "NOT_NECESSARILY_CLOSED") 00463 << "\n" 00464 << x_num_rows << " x " << x_num_columns << ' ' 00465 << (x.is_sorted() ? "(sorted)" : "(not_sorted)") 00466 << "\n" 00467 << "index_first_pending " << x.first_pending_row() 00468 << "\n"; 00469 for (dimension_type i = 0; i < x_num_rows; ++i) { 00470 const Constraint& c = x[i]; 00471 for (dimension_type j = 0; j < x_num_columns; ++j) 00472 s << c[j] << ' '; 00473 switch (c.type()) { 00474 case Constraint::EQUALITY: 00475 s << "="; 00476 break; 00477 case Constraint::NONSTRICT_INEQUALITY: 00478 s << ">="; 00479 break; 00480 case Constraint::STRICT_INEQUALITY: 00481 s << ">"; 00482 break; 00483 } 00484 s << "\n"; 00485 } 00486 }
void Parma_Polyhedra_Library::Constraint_System::print | ( | ) | const |
Prints *this
to std::cerr
using operator<<
.
Reimplemented from Parma_Polyhedra_Library::Linear_System.
bool Parma_Polyhedra_Library::Constraint_System::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.
Reimplemented from Parma_Polyhedra_Library::Linear_System.
Definition at line 491 of file Constraint_System.cc.
References Parma_Polyhedra_Library::Constraint::EQUALITY, Parma_Polyhedra_Library::Constraint::NONSTRICT_INEQUALITY, Parma_Polyhedra_Library::Matrix::num_columns(), Parma_Polyhedra_Library::Matrix::num_rows(), OK(), Parma_Polyhedra_Library::Linear_System::resize_no_copy(), Parma_Polyhedra_Library::Linear_System::set_index_first_pending_row(), Parma_Polyhedra_Library::Linear_System::set_necessarily_closed(), Parma_Polyhedra_Library::Linear_System::set_not_necessarily_closed(), Parma_Polyhedra_Library::Linear_System::set_sorted(), and Parma_Polyhedra_Library::Constraint::STRICT_INEQUALITY.
Referenced by Parma_Polyhedra_Library::Polyhedron::ascii_load().
00491 { 00492 std::string str; 00493 if (!(s >> str) || str != "topology") 00494 return false; 00495 if (!(s >> str)) 00496 return false; 00497 if (str == "NECESSARILY_CLOSED") 00498 set_necessarily_closed(); 00499 else { 00500 if (str != "NOT_NECESSARILY_CLOSED") 00501 return false; 00502 set_not_necessarily_closed(); 00503 } 00504 00505 dimension_type nrows; 00506 dimension_type ncols; 00507 if (!(s >> nrows)) 00508 return false; 00509 if (!(s >> str)) 00510 return false; 00511 if (!(s >> ncols)) 00512 return false; 00513 resize_no_copy(nrows, ncols); 00514 00515 if (!(s >> str) || (str != "(sorted)" && str != "(not_sorted)")) 00516 return false; 00517 set_sorted(str == "(sorted)"); 00518 dimension_type index; 00519 if (!(s >> str) || str != "index_first_pending") 00520 return false; 00521 if (!(s >> index)) 00522 return false; 00523 set_index_first_pending_row(index); 00524 00525 Constraint_System& x = *this; 00526 for (dimension_type i = 0; i < x.num_rows(); ++i) { 00527 for (dimension_type j = 0; j < x.num_columns(); ++j) 00528 if (!(s >> x[i][j])) 00529 return false; 00530 00531 if (!(s >> str)) 00532 return false; 00533 if (str == "=") 00534 x[i].set_is_equality(); 00535 else 00536 x[i].set_is_inequality(); 00537 00538 // Checking for equality of actual and declared types. 00539 switch (x[i].type()) { 00540 case Constraint::EQUALITY: 00541 if (str == "=") 00542 continue; 00543 break; 00544 case Constraint::NONSTRICT_INEQUALITY: 00545 if (str == ">=") 00546 continue; 00547 break; 00548 case Constraint::STRICT_INEQUALITY: 00549 if (str == ">") 00550 continue; 00551 break; 00552 } 00553 // Reaching this point means that the input was illegal. 00554 return false; 00555 } 00556 // Check for well-formedness. 00557 assert(OK()); 00558 return true; 00559 }
memory_size_type Parma_Polyhedra_Library::Constraint_System::total_memory_in_bytes | ( | ) | const [inline] |
Returns the total size in bytes of the memory occupied by *this
.
Reimplemented from Parma_Polyhedra_Library::Linear_System.
Definition at line 197 of file Constraint_System.inlines.hh.
References Parma_Polyhedra_Library::Checked::total_memory_in_bytes().
00197 { 00198 return Linear_System::total_memory_in_bytes(); 00199 }
memory_size_type Parma_Polyhedra_Library::Constraint_System::external_memory_in_bytes | ( | ) | const [inline] |
Returns the size in bytes of the memory managed by *this
.
Reimplemented from Parma_Polyhedra_Library::Linear_System.
Definition at line 192 of file Constraint_System.inlines.hh.
References Parma_Polyhedra_Library::Checked::external_memory_in_bytes().
Referenced by Parma_Polyhedra_Library::Polyhedron::external_memory_in_bytes(), and Parma_Polyhedra_Library::LP_Problem::external_memory_in_bytes().
00192 { 00193 return Linear_System::external_memory_in_bytes(); 00194 }
void Parma_Polyhedra_Library::Constraint_System::swap | ( | Constraint_System & | y | ) | [inline] |
Swaps *this
with y
.
Definition at line 187 of file Constraint_System.inlines.hh.
References Parma_Polyhedra_Library::Linear_System::swap().
Referenced by Parma_Polyhedra_Library::Polyhedron::Polyhedron(), and swap().
00187 { 00188 Linear_System::swap(y); 00189 }
bool Parma_Polyhedra_Library::Constraint_System::adjust_topology_and_space_dimension | ( | Topology | topol, | |
dimension_type | num_dimensions | |||
) | [private] |
Adjusts *this
so that it matches the topology and the number of space dimensions given as parameters (adding or removing columns if needed). Returns false
if and only if topol
is equal to NECESSARILY_CLOSED
and *this
contains strict inequalities.
Definition at line 39 of file Constraint_System.cc.
References Parma_Polyhedra_Library::Matrix::add_zero_columns(), Parma_Polyhedra_Library::Matrix::erase_to_end(), Parma_Polyhedra_Library::Linear_System::first_pending_row(), has_strict_inequalities(), Parma_Polyhedra_Library::Linear_System::is_sorted(), Parma_Polyhedra_Library::NECESSARILY_CLOSED, Parma_Polyhedra_Library::NOT_NECESSARILY_CLOSED, Parma_Polyhedra_Library::Matrix::num_columns(), Parma_Polyhedra_Library::Linear_System::num_pending_rows(), Parma_Polyhedra_Library::Matrix::num_rows(), OK(), Parma_Polyhedra_Library::Linear_System::remove_trailing_columns(), Parma_Polyhedra_Library::Linear_System::set_index_first_pending_row(), Parma_Polyhedra_Library::Linear_System::set_necessarily_closed(), Parma_Polyhedra_Library::Linear_System::set_not_necessarily_closed(), Parma_Polyhedra_Library::Linear_System::set_sorted(), Parma_Polyhedra_Library::Linear_System::sort_rows(), space_dimension(), Parma_Polyhedra_Library::Matrix::swap_columns(), Parma_Polyhedra_Library::Linear_System::topology(), and Parma_Polyhedra_Library::Linear_System::unset_pending_rows().
Referenced by Parma_Polyhedra_Library::Polyhedron::add_recycled_constraints(), Parma_Polyhedra_Library::Polyhedron::add_recycled_constraints_and_minimize(), Parma_Polyhedra_Library::Polyhedron::constraints(), and Parma_Polyhedra_Library::Polyhedron::Polyhedron().
00040 { 00041 assert(space_dimension() <= new_space_dim); 00042 00043 const dimension_type old_space_dim = space_dimension(); 00044 const Topology old_topology = topology(); 00045 dimension_type cols_to_be_added = new_space_dim - old_space_dim; 00046 00047 // Dealing with empty constraint systems first. 00048 if (num_rows() == 0) { 00049 if (num_columns() == 0) 00050 if (new_topology == NECESSARILY_CLOSED) { 00051 add_zero_columns(++cols_to_be_added); 00052 set_necessarily_closed(); 00053 } 00054 else { 00055 cols_to_be_added += 2; 00056 add_zero_columns(cols_to_be_added); 00057 set_not_necessarily_closed(); 00058 } 00059 else 00060 // Here `num_columns() > 0'. 00061 if (old_topology != new_topology) 00062 if (new_topology == NECESSARILY_CLOSED) { 00063 switch (cols_to_be_added) { 00064 case 0: 00065 remove_trailing_columns(1); 00066 break; 00067 case 1: 00068 // Nothing to do. 00069 break; 00070 default: 00071 add_zero_columns(--cols_to_be_added); 00072 } 00073 set_necessarily_closed(); 00074 } 00075 else { 00076 // Here old_topology == NECESSARILY_CLOSED 00077 // and new_topology == NOT_NECESSARILY_CLOSED. 00078 add_zero_columns(++cols_to_be_added); 00079 set_not_necessarily_closed(); 00080 } 00081 else { 00082 // Here topologies agree. 00083 if (cols_to_be_added > 0) 00084 add_zero_columns(cols_to_be_added); 00085 } 00086 assert(OK()); 00087 return true; 00088 } 00089 00090 // Here `num_rows() > 0'. 00091 if (cols_to_be_added > 0) 00092 if (old_topology != new_topology) 00093 if (new_topology == NECESSARILY_CLOSED) { 00094 // A NOT_NECESSARILY_CLOSED constraint system 00095 // can be converted to a NECESSARILY_CLOSED one 00096 // only if it does not contain strict inequalities. 00097 if (has_strict_inequalities()) 00098 return false; 00099 // Since there were no strict inequalities, 00100 // the only constraints that may have a non-zero epsilon coefficient 00101 // are the eps-leq-one and the eps-geq-zero constraints. 00102 // If they are present, we erase these rows, so that the 00103 // epsilon column will only contain zeroes: as a consequence, 00104 // we just decrement the number of columns to be added. 00105 Constraint_System& cs = *this; 00106 const dimension_type eps_index = old_space_dim + 1; 00107 dimension_type cs_num_rows = cs.num_rows(); 00108 bool was_sorted = cs.is_sorted(); 00109 if (was_sorted) 00110 cs.set_sorted(false); 00111 00112 // If we have no pending rows, we only check if 00113 // we must erase some rows. 00114 if (cs.num_pending_rows() == 0) { 00115 for (dimension_type i = cs_num_rows; i-- > 0; ) 00116 if (cs[i][eps_index] != 0) { 00117 --cs_num_rows; 00118 std::swap(cs[i], cs[cs_num_rows]); 00119 } 00120 cs.erase_to_end(cs_num_rows); 00121 cs.unset_pending_rows(); 00122 } 00123 else { 00124 // There are pending rows, and we cannot swap them 00125 // into the non-pending part of the matrix. 00126 // Thus, we first work on the non-pending part as if it was 00127 // an independent matrix; then we work on the pending part. 00128 const dimension_type old_first_pending = cs.first_pending_row(); 00129 dimension_type new_first_pending = old_first_pending; 00130 for (dimension_type i = new_first_pending; i-- > 0; ) 00131 if (cs[i][eps_index] != 0) { 00132 --new_first_pending; 00133 std::swap(cs[i], cs[new_first_pending]); 00134 } 00135 const dimension_type num_swaps 00136 = old_first_pending - new_first_pending; 00137 cs.set_index_first_pending_row(new_first_pending); 00138 // Move the swapped rows to the real end of the matrix. 00139 for (dimension_type i = num_swaps; i-- > 0; ) 00140 std::swap(cs[old_first_pending - i], cs[cs_num_rows - i]); 00141 cs_num_rows -= num_swaps; 00142 // Now iterate through the pending rows. 00143 for (dimension_type i = cs_num_rows; i-- > new_first_pending; ) 00144 if (cs[i][eps_index] != 0) { 00145 --cs_num_rows; 00146 std::swap(cs[i], cs[cs_num_rows]); 00147 } 00148 cs.erase_to_end(cs_num_rows); 00149 } 00150 00151 // If `cs' was sorted we sort it again. 00152 if (was_sorted) 00153 cs.sort_rows(); 00154 if (--cols_to_be_added > 0) 00155 add_zero_columns(cols_to_be_added); 00156 set_necessarily_closed(); 00157 } 00158 else { 00159 // A NECESSARILY_CLOSED constraint system is converted to 00160 // a NOT_NECESSARILY_CLOSED one by adding a further column 00161 // of zeroes for the epsilon coefficients. 00162 add_zero_columns(++cols_to_be_added); 00163 set_not_necessarily_closed(); 00164 } 00165 else { 00166 // Topologies agree: first add the required zero columns ... 00167 add_zero_columns(cols_to_be_added); 00168 // ... and, if needed, move the epsilon coefficients 00169 // to the new last column. 00170 if (old_topology == NOT_NECESSARILY_CLOSED) 00171 swap_columns(old_space_dim + 1, new_space_dim + 1); 00172 } 00173 else 00174 // Here `cols_to_be_added == 0'. 00175 if (old_topology != new_topology) 00176 if (new_topology == NECESSARILY_CLOSED) { 00177 // A NOT_NECESSARILY_CLOSED constraint system 00178 // can be converted to a NECESSARILY_CLOSED one 00179 // only if it does not contain strict inequalities. 00180 if (has_strict_inequalities()) 00181 return false; 00182 // We just remove the column of the epsilon coefficients. 00183 remove_trailing_columns(1); 00184 set_necessarily_closed(); 00185 } 00186 else { 00187 // We just add the column of the epsilon coefficients. 00188 add_zero_columns(1); 00189 set_not_necessarily_closed(); 00190 } 00191 // We successfully adjusted space dimensions and topology. 00192 assert(OK()); 00193 return true; 00194 }
Constraint & Parma_Polyhedra_Library::Constraint_System::operator[] | ( | dimension_type | k | ) | [inline, private] |
Returns the k-
th constraint of the system.
Reimplemented from Parma_Polyhedra_Library::Linear_System.
Definition at line 69 of file Constraint_System.inlines.hh.
References Parma_Polyhedra_Library::Linear_System::operator[]().
00069 { 00070 return static_cast<Constraint&>(Linear_System::operator[](k)); 00071 }
const Constraint & Parma_Polyhedra_Library::Constraint_System::operator[] | ( | dimension_type | k | ) | const [inline, private] |
Returns a constant reference to the k-
th constraint of the system.
Reimplemented from Parma_Polyhedra_Library::Linear_System.
Definition at line 74 of file Constraint_System.inlines.hh.
References Parma_Polyhedra_Library::Linear_System::operator[]().
00074 { 00075 return static_cast<const Constraint&>(Linear_System::operator[](k)); 00076 }
bool Parma_Polyhedra_Library::Constraint_System::satisfies_all_constraints | ( | const Generator & | g | ) | const [private] |
Returns true
if g
satisfies all the constraints.
Definition at line 308 of file Constraint_System.cc.
References Parma_Polyhedra_Library::Generator::CLOSURE_POINT, Parma_Polyhedra_Library::Constraint::EQUALITY, Parma_Polyhedra_Library::Constraint::is_inequality(), Parma_Polyhedra_Library::Generator::is_line(), Parma_Polyhedra_Library::Linear_System::is_necessarily_closed(), Parma_Polyhedra_Library::Generator::LINE, Parma_Polyhedra_Library::Constraint::NONSTRICT_INEQUALITY, Parma_Polyhedra_Library::Matrix::num_rows(), Parma_Polyhedra_Library::Generator::POINT, Parma_Polyhedra_Library::Generator::RAY, space_dimension(), Parma_Polyhedra_Library::Generator::space_dimension(), Parma_Polyhedra_Library::Constraint::STRICT_INEQUALITY, Parma_Polyhedra_Library::Constraint::type(), and Parma_Polyhedra_Library::Generator::type().
Referenced by Parma_Polyhedra_Library::LP_Problem::OK(), and Parma_Polyhedra_Library::Polyhedron::relation_with().
00308 { 00309 assert(g.space_dimension() <= space_dimension()); 00310 00311 // Setting `sps' to the appropriate scalar product sign operator. 00312 // This also avoids problems when having _legal_ topology mismatches 00313 // (which could also cause a mismatch in the number of columns). 00314 Topology_Adjusted_Scalar_Product_Sign sps(g); 00315 00316 const Constraint_System& cs = *this; 00317 if (cs.is_necessarily_closed()) { 00318 if (g.is_line()) { 00319 // Lines must saturate all constraints. 00320 for (dimension_type i = cs.num_rows(); i-- > 0; ) 00321 if (sps(g, cs[i]) != 0) 00322 return false; 00323 } 00324 else 00325 // `g' is either a ray, a point or a closure point. 00326 for (dimension_type i = cs.num_rows(); i-- > 0; ) { 00327 const Constraint& c = cs[i]; 00328 const int sp_sign = sps(g, c); 00329 if (c.is_inequality()) { 00330 // As `cs' is necessarily closed, 00331 // `c' is a non-strict inequality. 00332 if (sp_sign < 0) 00333 return false; 00334 } 00335 else 00336 // `c' is an equality. 00337 if (sp_sign != 0) 00338 return false; 00339 } 00340 } 00341 else 00342 // `cs' is not necessarily closed. 00343 switch (g.type()) { 00344 00345 case Generator::LINE: 00346 // Lines must saturate all constraints. 00347 for (dimension_type i = cs.num_rows(); i-- > 0; ) 00348 if (sps(g, cs[i]) != 0) 00349 return false; 00350 break; 00351 00352 case Generator::POINT: 00353 // Have to perform the special test 00354 // when dealing with a strict inequality. 00355 for (dimension_type i = cs.num_rows(); i-- > 0; ) { 00356 const Constraint& c = cs[i]; 00357 const int sp_sign = sps(g, c); 00358 switch (c.type()) { 00359 case Constraint::EQUALITY: 00360 if (sp_sign != 0) 00361 return false; 00362 break; 00363 case Constraint::NONSTRICT_INEQUALITY: 00364 if (sp_sign < 0) 00365 return false; 00366 break; 00367 case Constraint::STRICT_INEQUALITY: 00368 if (sp_sign <= 0) 00369 return false; 00370 break; 00371 } 00372 } 00373 break; 00374 00375 case Generator::RAY: 00376 // Intentionally fall through. 00377 case Generator::CLOSURE_POINT: 00378 for (dimension_type i = cs.num_rows(); i-- > 0; ) { 00379 const Constraint& c = cs[i]; 00380 const int sp_sign = sps(g, c); 00381 if (c.is_inequality()) { 00382 // Constraint `c' is either a strict or a non-strict inequality. 00383 if (sp_sign < 0) 00384 return false; 00385 } 00386 else 00387 // Constraint `c' is an equality. 00388 if (sp_sign != 0) 00389 return false; 00390 } 00391 break; 00392 } 00393 00394 // If we reach this point, `g' satisfies all constraints. 00395 return true; 00396 }
void Parma_Polyhedra_Library::Constraint_System::affine_preimage | ( | dimension_type | v, | |
const Linear_Expression & | expr, | |||
Coefficient_traits::const_reference | denominator | |||
) | [private] |
Substitutes a given column of coefficients by a given affine expression.
v | Index of the column to which the affine transformation is substituted. | |
expr | The numerator of the affine transformation: ![]() | |
denominator | The denominator of the affine transformation. |
denominator
that will be used as denominator of the affine transformation. The denominator is required to be a positive integer.
The affine transformation substitutes the matrix of constraints by a new matrix whose elements are built from the old one
as follows:
expr
is a constant parameter and unaltered by this computation.
Definition at line 401 of file Constraint_System.cc.
References Parma_Polyhedra_Library::add_mul_assign(), Parma_Polyhedra_Library::Matrix::num_columns(), Parma_Polyhedra_Library::Matrix::num_rows(), Parma_Polyhedra_Library::Row::size(), Parma_Polyhedra_Library::Linear_Expression::space_dimension(), space_dimension(), and Parma_Polyhedra_Library::Linear_System::strong_normalize().
Referenced by Parma_Polyhedra_Library::Polyhedron::affine_image(), and Parma_Polyhedra_Library::Polyhedron::affine_preimage().
00403 { 00404 Constraint_System& x = *this; 00405 // `v' is the index of a column corresponding to 00406 // a "user" variable (i.e., it cannot be the inhomogeneous term, 00407 // nor the epsilon dimension of NNC polyhedra). 00408 assert(v > 0 && v <= x.space_dimension()); 00409 assert(expr.space_dimension() <= x.space_dimension()); 00410 assert(denominator > 0); 00411 00412 const dimension_type n_columns = x.num_columns(); 00413 const dimension_type n_rows = x.num_rows(); 00414 const dimension_type expr_size = expr.size(); 00415 const bool not_invertible = (v >= expr_size || expr[v] == 0); 00416 00417 if (denominator != 1) 00418 for (dimension_type i = n_rows; i-- > 0; ) { 00419 Constraint& row = x[i]; 00420 Coefficient& row_v = row[v]; 00421 if (row_v != 0) { 00422 for (dimension_type j = n_columns; j-- > 0; ) 00423 if (j != v) { 00424 Coefficient& row_j = row[j]; 00425 row_j *= denominator; 00426 if (j < expr_size) 00427 add_mul_assign(row_j, row_v, expr[j]); 00428 } 00429 if (not_invertible) 00430 row_v = 0; 00431 else 00432 row_v *= expr[v]; 00433 } 00434 } 00435 else 00436 // Here `denominator' == 1: optimized computation 00437 // only considering columns having indexes < expr_size. 00438 for (dimension_type i = n_rows; i-- > 0; ) { 00439 Constraint& row = x[i]; 00440 Coefficient& row_v = row[v]; 00441 if (row_v != 0) { 00442 for (dimension_type j = expr_size; j-- > 0; ) 00443 if (j != v) 00444 add_mul_assign(row[j], row_v, expr[j]); 00445 if (not_invertible) 00446 row_v = 0; 00447 else 00448 row_v *= expr[v]; 00449 } 00450 } 00451 // Strong normalization also resets the sortedness flag. 00452 x.strong_normalize(); 00453 }
PPL::dimension_type Parma_Polyhedra_Library::Constraint_System::num_equalities | ( | ) | const [private] |
Returns the number of equality constraints.
Definition at line 293 of file Constraint_System.cc.
References num_inequalities(), Parma_Polyhedra_Library::Linear_System::num_pending_rows(), and Parma_Polyhedra_Library::Matrix::num_rows().
Referenced by Parma_Polyhedra_Library::Polyhedron::H79_widening_assign(), Parma_Polyhedra_Library::Polyhedron::OK(), Parma_Polyhedra_Library::Polyhedron::quick_equivalence_test(), and Parma_Polyhedra_Library::Polyhedron::strongly_minimize_generators().
00293 { 00294 // We are sure that we call this method only when 00295 // the matrix has no pending rows. 00296 assert(num_pending_rows() == 0); 00297 return num_rows() - num_inequalities(); 00298 }
PPL::dimension_type Parma_Polyhedra_Library::Constraint_System::num_inequalities | ( | ) | const [private] |
Returns the number of inequality constraints.
Definition at line 274 of file Constraint_System.cc.
References Parma_Polyhedra_Library::Linear_System::is_sorted(), Parma_Polyhedra_Library::Linear_System::num_pending_rows(), and Parma_Polyhedra_Library::Matrix::num_rows().
Referenced by num_equalities().
00274 { 00275 // We are sure that we call this method only when 00276 // the matrix has no pending rows. 00277 assert(num_pending_rows() == 0); 00278 const Constraint_System& cs = *this; 00279 dimension_type n = 0; 00280 // If the Linear_System happens to be sorted, take advantage of the fact 00281 // that inequalities are at the bottom of the system. 00282 if (is_sorted()) 00283 for (dimension_type i = num_rows(); i > 0 && cs[--i].is_inequality(); ) 00284 ++n; 00285 else 00286 for (dimension_type i = num_rows(); i-- > 0 ; ) 00287 if (cs[i].is_inequality()) 00288 ++n; 00289 return n; 00290 }
void Parma_Polyhedra_Library::Constraint_System::simplify | ( | ) | [inline, private] |
Applies Gaussian's elimination and back-substitution so as to provide a partial simplification of the system of constraints.
It is assumed that the system has no pending constraints.
Reimplemented from Parma_Polyhedra_Library::Linear_System.
Definition at line 202 of file Constraint_System.inlines.hh.
References Parma_Polyhedra_Library::Linear_System::simplify().
Referenced by Parma_Polyhedra_Library::Polyhedron::OK(), and Parma_Polyhedra_Library::Polyhedron::shrink_bounding_box().
00202 { 00203 Linear_System::simplify(); 00204 }
void Parma_Polyhedra_Library::Constraint_System::insert_pending | ( | const Constraint & | c | ) | [private] |
Inserts in *this
a copy of the constraint c
, increasing the number of space dimensions if needed. It is a pending constraint.
Definition at line 248 of file Constraint_System.cc.
References Parma_Polyhedra_Library::Matrix::add_zero_columns(), Parma_Polyhedra_Library::Linear_System::insert_pending(), Parma_Polyhedra_Library::Linear_System::is_necessarily_closed(), OK(), Parma_Polyhedra_Library::Linear_System::set_not_necessarily_closed(), space_dimension(), Parma_Polyhedra_Library::Constraint::space_dimension(), Parma_Polyhedra_Library::Linear_Row::topology(), and Parma_Polyhedra_Library::Linear_System::topology().
Referenced by Parma_Polyhedra_Library::Polyhedron::add_constraint().
00248 { 00249 if (topology() == c.topology()) 00250 Linear_System::insert_pending(c); 00251 else 00252 // `*this' and `c' have different topologies. 00253 if (is_necessarily_closed()) { 00254 // Padding the matrix with a columns of zeroes 00255 // corresponding to the epsilon coefficients. 00256 add_zero_columns(1); 00257 set_not_necessarily_closed(); 00258 Linear_System::insert_pending(c); 00259 } 00260 else { 00261 // Here `*this' is NNC and `c' is necessarily closed. 00262 // Copying the constraint adding the epsilon coefficient 00263 // and the missing space dimensions, if any. 00264 const dimension_type new_size = 2 + std::max(c.space_dimension(), 00265 space_dimension()); 00266 Constraint tmp_c(c, new_size); 00267 tmp_c.set_not_necessarily_closed(); 00268 Linear_System::insert_pending(tmp_c); 00269 } 00270 assert(OK()); 00271 }
void Parma_Polyhedra_Library::Constraint_System::add_low_level_constraints | ( | ) | [inline, private] |
Adds low-level constraints to the constraint system.
Definition at line 175 of file Constraint_System.inlines.hh.
References Parma_Polyhedra_Library::Constraint::epsilon_geq_zero(), Parma_Polyhedra_Library::Constraint::epsilon_leq_one(), insert(), Parma_Polyhedra_Library::Linear_System::is_necessarily_closed(), and Parma_Polyhedra_Library::Constraint::zero_dim_positivity().
Referenced by Parma_Polyhedra_Library::Polyhedron::Polyhedron().
00175 { 00176 if (is_necessarily_closed()) 00177 // The positivity constraint. 00178 insert(Constraint::zero_dim_positivity()); 00179 else { 00180 // Add the epsilon constraints. 00181 insert(Constraint::epsilon_leq_one()); 00182 insert(Constraint::epsilon_geq_zero()); 00183 } 00184 }
friend class const_iterator [friend] |
Definition at line 289 of file Constraint_System.defs.hh.
friend class Parma_Polyhedra_Library::Polyhedron [friend] |
Definition at line 290 of file Constraint_System.defs.hh.
friend class Parma_Polyhedra_Library::LP_Problem [friend] |
Definition at line 291 of file Constraint_System.defs.hh.
bool operator== | ( | const Polyhedron & | x, | |
const Polyhedron & | y | |||
) | [friend] |
Returns true
if and only if x
and y
are the same polyhedron.
Note that x
and y
may be topology- and/or dimension-incompatible polyhedra: in those cases, the value false
is returned.
Definition at line 2815 of file Polyhedron_public.cc.
02815 { 02816 // If the two polyhedra are topology-incompatible or dimension-incompatible, 02817 // then they cannot be the same polyhedron. 02818 if (x.topology() != y.topology() || x.space_dim != y.space_dim) 02819 return false; 02820 02821 if (x.marked_empty()) 02822 return y.is_empty(); 02823 else if (y.marked_empty()) 02824 return x.is_empty(); 02825 else if (x.space_dim == 0) 02826 return true; 02827 02828 switch (x.quick_equivalence_test(y)) { 02829 case Polyhedron::TVB_TRUE: 02830 return true; 02831 02832 case Polyhedron::TVB_FALSE: 02833 return false; 02834 02835 default: 02836 if (x.is_included_in(y)) 02837 if (x.marked_empty()) 02838 return y.is_empty(); 02839 else 02840 return y.is_included_in(x); 02841 else 02842 return false; 02843 } 02844 }
std::ostream & operator<< | ( | std::ostream & | s, | |
const Constraint_System & | cs | |||
) | [related] |
Output operator.
Writes true
if cs
is empty. Otherwise, writes on s
the constraints of cs
, all in one row and separated by ", ".
Definition at line 581 of file Constraint_System.cc.
References begin(), and end().
00581 { 00582 Constraint_System::const_iterator i = cs.begin(); 00583 const Constraint_System::const_iterator cs_end = cs.end(); 00584 if (i == cs_end) 00585 s << "true"; 00586 else { 00587 while (i != cs_end) { 00588 s << *i++; 00589 if (i != cs_end) 00590 s << ", "; 00591 } 00592 } 00593 return s; 00594 }
void swap | ( | Parma_Polyhedra_Library::Constraint_System & | x, | |
Parma_Polyhedra_Library::Constraint_System & | y | |||
) | [related] |
Specializes std::swap
.
Definition at line 213 of file Constraint_System.inlines.hh.
References swap().
00214 { 00215 x.swap(y); 00216 }