#include <Linear_System.defs.hh>
Public Member Functions | |
Linear_System (Topology topol) | |
Builds an empty linear system with specified topology. | |
Linear_System (Topology topol, dimension_type n_rows, dimension_type n_columns) | |
Builds a system with specified topology and dimensions. | |
Linear_System (const Linear_System &y) | |
Copy-constructor: pending rows are transformed into non-pending ones. | |
Linear_System (const Linear_System &y, With_Pending) | |
Full copy-constructor: pending rows are copied as pending. | |
Linear_System & | operator= (const Linear_System &y) |
Assignment operator: pending rows are transformed into non-pending ones. | |
void | assign_with_pending (const Linear_System &y) |
Full assignment operator: pending rows are copied as pending. | |
void | swap (Linear_System &y) |
Swaps *this with y . | |
dimension_type | space_dimension () const |
Returns the space dimension of the rows in the system. | |
void | remove_trailing_columns (dimension_type n) |
Makes the system shrink by removing its n trailing columns. | |
void | permute_columns (const std::vector< dimension_type > &cycles) |
Permutes the columns of the system. | |
void | strong_normalize () |
Strongly normalizes the system. | |
void | sign_normalize () |
Sign-normalizes the system. | |
bool | check_sorted () const |
Returns true if and only if *this is sorted, without checking for duplicates. | |
void | set_necessarily_closed () |
Sets the system topology to NECESSARILY_CLOSED . | |
void | set_not_necessarily_closed () |
Sets the system topology to NOT_NECESSARILY_CLOSED . | |
void | set_rows_topology () |
Sets the topology of all rows equal to the system topology. | |
void | unset_pending_rows () |
Sets the index to indicate that the system has no pending rows. | |
void | set_index_first_pending_row (dimension_type i) |
Sets the index of the first pending row to i . | |
void | set_sorted (bool b) |
Sets the sortedness flag of the system to b . | |
void | resize_no_copy (dimension_type new_n_rows, dimension_type new_n_columns) |
Resizes the system without worrying about the old contents. | |
void | add_rows_and_columns (dimension_type n) |
Adds n rows and columns to the system. | |
void | insert (const Linear_Row &r) |
Adds a copy of r to the system, automatically resizing the system or the row's copy, if needed. | |
void | insert_pending (const Linear_Row &r) |
Adds a copy of the given row to the pending part of the system, automatically resizing the system or the row, if needed. | |
void | add_row (const Linear_Row &r) |
Adds a copy of the given row to the system. | |
void | add_pending_row (Linear_Row::Flags flags) |
Adds a new empty row to the system, setting only its flags. | |
void | add_pending_row (const Linear_Row &r) |
Adds a copy of the given row to the pending part of the system. | |
void | add_rows (const Linear_System &y) |
Adds to *this a copy of the rows of `y'. | |
void | add_pending_rows (const Linear_System &y) |
Adds a copy of the rows of `y' to the pending part of `*this'. | |
void | sort_rows () |
Sorts the non-pending rows (in growing order) and eliminates duplicated ones. | |
void | sort_rows (dimension_type first_row, dimension_type last_row) |
Sorts the rows (in growing order) form first_row to last_row and eliminates duplicated ones. | |
void | merge_rows_assign (const Linear_System &y) |
Assigns to *this the result of merging its rows with those of y , obtaining a sorted system. | |
void | sort_pending_and_remove_duplicates () |
Sorts the pending rows and eliminates those that also occur in the non-pending part of the system. | |
void | sort_and_remove_with_sat (Saturation_Matrix &sat) |
Sorts the system, removing duplicates, keeping the saturation matrix consistent. | |
dimension_type | gauss (dimension_type n_lines_or_equalities) |
Minimizes the subsystem of equations contained in *this . | |
void | back_substitute (dimension_type n_lines_or_equalities) |
Back-substitutes the coefficients to reduce the complexity of the system. | |
void | simplify () |
Applies Gaussian's elimination and back-substitution so as to simplify the linear system. | |
void | normalize () |
Normalizes the system by dividing each row for the GCD of the row's elements. | |
void | clear () |
Clears the system deallocating all its rows. | |
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 . | |
bool | OK (bool check_strong_normalized=true) const |
Checks if all the invariants are satisfied. | |
Subscript operators | |
Linear_Row & | operator[] (dimension_type k) |
Returns a reference to the k-th row of the system. | |
const Linear_Row & | operator[] (dimension_type k) const |
Returns a constant reference to the k-th row of the system. | |
Accessors | |
Topology | topology () const |
Returns the system topology. | |
bool | is_sorted () const |
Returns the value of the sortedness flag. | |
bool | is_necessarily_closed () const |
Returns true if and only if the system topology is NECESSARILY_CLOSED . | |
dimension_type | num_lines_or_equalities () const |
Returns the number of rows in the system that represent either lines or equalities. | |
dimension_type | first_pending_row () const |
Returns the index of the first pending row. | |
dimension_type | num_pending_rows () const |
Returns the number of rows that are in the pending part of the system. | |
Static Public Member Functions | |
static dimension_type | max_space_dimension () |
Returns the maximum space dimension a Linear_System can handle. | |
Private Attributes | |
Topology | row_topology |
The topological kind of the rows in the system. | |
dimension_type | index_first_pending |
The index of the first pending row. | |
bool | sorted |
true if rows are sorted in the ascending order as defined by bool compare(const Linear_Row&, const Linear_Row&) . If false may not be sorted. | |
Related Functions | |
(Note that these are not member functions.) | |
void | swap (Parma_Polyhedra_Library::Linear_System &x, Parma_Polyhedra_Library::Linear_System &y) |
Specializes std::swap . | |
bool | operator== (const Linear_System &x, const Linear_System &y) |
Returns true if and only if x and y are identical. | |
bool | operator!= (const Linear_System &x, const Linear_System &y) |
Returns true if and only if x and y are different. | |
Classes | |
struct | Row_Less_Than |
Ordering predicate (used when implementing the sort algorithm). More... | |
struct | With_Pending |
A tag class. More... | |
class | With_Saturation_Matrix_iterator |
An iterator keeping a Linear_System consistent with a Saturation_Matrix. More... |
An object of this class represents either a constraint system or a generator system. Each Linear_System object can be viewed as a finite sequence of strong-normalized Linear_Row objects, where each Linear_Row implements a constraint or a generator. Linear systems are characterized by the matrix of coefficients, also encoding the number, size and capacity of Linear_row objects, as well as a few additional information, including:
true
, ensures that the non-pending prefix of the sequence of rows is sorted. Definition at line 54 of file Linear_System.defs.hh.
Parma_Polyhedra_Library::Linear_System::Linear_System | ( | Topology | topol | ) | [inline] |
Builds an empty linear system with specified topology.
Rows size and capacity are initialized to .
Definition at line 56 of file Linear_System.inlines.hh.
00057 : Matrix(), 00058 row_topology(topol), 00059 index_first_pending(0), 00060 sorted(true) { 00061 }
Parma_Polyhedra_Library::Linear_System::Linear_System | ( | Topology | topol, | |
dimension_type | n_rows, | |||
dimension_type | n_columns | |||
) | [inline] |
Builds a system with specified topology and dimensions.
topol | The topology of the system that will be created; | |
n_rows | The number of rows of the system that will be created; | |
n_columns | The number of columns of the system that will be created. |
n_rows
n_columns
system whose coefficients are all zero and whose rows are all initialized to be of the given topology.
Definition at line 64 of file Linear_System.inlines.hh.
00066 : Matrix(n_rows, n_columns, Linear_Row::Flags(topol)), 00067 row_topology(topol), 00068 index_first_pending(n_rows), 00069 sorted(true) { 00070 }
Parma_Polyhedra_Library::Linear_System::Linear_System | ( | const Linear_System & | y | ) | [inline] |
Copy-constructor: pending rows are transformed into non-pending ones.
Definition at line 94 of file Linear_System.inlines.hh.
References num_pending_rows(), sorted, and unset_pending_rows().
00095 : Matrix(y), 00096 row_topology(y.row_topology) { 00097 unset_pending_rows(); 00098 // Previously pending rows may violate sortedness. 00099 sorted = (y.num_pending_rows() > 0) ? false : y.sorted; 00100 assert(num_pending_rows() == 0); 00101 }
Parma_Polyhedra_Library::Linear_System::Linear_System | ( | const Linear_System & | y, | |
With_Pending | ||||
) | [inline] |
Full copy-constructor: pending rows are copied as pending.
Definition at line 104 of file Linear_System.inlines.hh.
00105 : Matrix(y), 00106 row_topology(y.row_topology), 00107 index_first_pending(y.index_first_pending), 00108 sorted(y.sorted) { 00109 }
Linear_System & Parma_Polyhedra_Library::Linear_System::operator= | ( | const Linear_System & | y | ) | [inline] |
Assignment operator: pending rows are transformed into non-pending ones.
Definition at line 112 of file Linear_System.inlines.hh.
References num_pending_rows(), Parma_Polyhedra_Library::Matrix::operator=(), row_topology, sorted, and unset_pending_rows().
Referenced by Parma_Polyhedra_Library::Generator_System::operator=(), and Parma_Polyhedra_Library::Constraint_System::operator=().
00112 { 00113 Matrix::operator=(y); 00114 row_topology = y.row_topology; 00115 unset_pending_rows(); 00116 // Previously pending rows may violate sortedness. 00117 sorted = (y.num_pending_rows() > 0) ? false : y.sorted; 00118 assert(num_pending_rows() == 0); 00119 return *this; 00120 }
void Parma_Polyhedra_Library::Linear_System::assign_with_pending | ( | const Linear_System & | y | ) | [inline] |
Full assignment operator: pending rows are copied as pending.
Definition at line 123 of file Linear_System.inlines.hh.
References index_first_pending, Parma_Polyhedra_Library::Matrix::operator=(), row_topology, and sorted.
Referenced by Parma_Polyhedra_Library::Polyhedron::operator=(), and Parma_Polyhedra_Library::Polyhedron::Polyhedron().
00123 { 00124 Matrix::operator=(y); 00125 row_topology = y.row_topology; 00126 index_first_pending = y.index_first_pending; 00127 sorted = y.sorted; 00128 }
void Parma_Polyhedra_Library::Linear_System::swap | ( | Linear_System & | y | ) | [inline] |
Swaps *this
with y
.
Definition at line 131 of file Linear_System.inlines.hh.
References index_first_pending, row_topology, sorted, and Parma_Polyhedra_Library::Matrix::swap().
Referenced by swap(), Parma_Polyhedra_Library::Generator_System::swap(), and Parma_Polyhedra_Library::Constraint_System::swap().
00131 { 00132 Matrix::swap(y); 00133 std::swap(row_topology, y.row_topology); 00134 std::swap(index_first_pending, y.index_first_pending); 00135 std::swap(sorted, y.sorted); 00136 }
dimension_type Parma_Polyhedra_Library::Linear_System::max_space_dimension | ( | ) | [inline, static] |
Returns the maximum space dimension a Linear_System can handle.
Reimplemented in Parma_Polyhedra_Library::Constraint_System, Parma_Polyhedra_Library::Generator_System, and Parma_Polyhedra_Library::Grid_Generator_System.
Definition at line 193 of file Linear_System.inlines.hh.
References Parma_Polyhedra_Library::Matrix::max_num_columns().
Referenced by Parma_Polyhedra_Library::Generator_System::max_space_dimension(), and Parma_Polyhedra_Library::Constraint_System::max_space_dimension().
00193 { 00194 // Column zero holds the inhomogeneous term or the divisor. 00195 // In NNC linear systems, the last column holds the coefficient 00196 // of the epsilon dimension. 00197 return max_num_columns() - 2; 00198 }
dimension_type Parma_Polyhedra_Library::Linear_System::space_dimension | ( | ) | const [inline] |
Returns the space dimension of the rows in the system.
The computation of the space dimension correctly ignores the column encoding the inhomogeneous terms of constraint (resp., the divisors of generators); if the system topology is NOT_NECESSARILY_CLOSED
, also the column of the -dimension coefficients will be ignored.
Reimplemented in Parma_Polyhedra_Library::Constraint_System, Parma_Polyhedra_Library::Generator_System, and Parma_Polyhedra_Library::Grid_Generator_System.
Definition at line 201 of file Linear_System.inlines.hh.
References is_necessarily_closed(), and Parma_Polyhedra_Library::Matrix::num_columns().
Referenced by Parma_Polyhedra_Library::Generator_System::space_dimension(), and Parma_Polyhedra_Library::Constraint_System::space_dimension().
00201 { 00202 const dimension_type n_columns = num_columns(); 00203 return (n_columns == 0) 00204 ? 0 00205 : n_columns - (is_necessarily_closed() ? 1 : 2); 00206 }
void Parma_Polyhedra_Library::Linear_System::remove_trailing_columns | ( | dimension_type | n | ) | [inline] |
Makes the system shrink by removing its n
trailing columns.
Reimplemented from Parma_Polyhedra_Library::Matrix.
Definition at line 209 of file Linear_System.inlines.hh.
References Parma_Polyhedra_Library::Matrix::remove_trailing_columns(), and strong_normalize().
Referenced by Parma_Polyhedra_Library::Generator_System::adjust_topology_and_space_dimension(), Parma_Polyhedra_Library::Constraint_System::adjust_topology_and_space_dimension(), Parma_Polyhedra_Library::Polyhedron::remove_higher_space_dimensions(), and Parma_Polyhedra_Library::Polyhedron::remove_space_dimensions().
00209 { 00210 Matrix::remove_trailing_columns(n); 00211 // Have to re-normalize the rows of the system, 00212 // since we removed some coefficients. 00213 strong_normalize(); 00214 }
void Parma_Polyhedra_Library::Linear_System::permute_columns | ( | const std::vector< dimension_type > & | cycles | ) | [inline] |
Permutes the columns of the system.
Reimplemented from Parma_Polyhedra_Library::Matrix.
Reimplemented in Parma_Polyhedra_Library::Grid_Generator_System.
Definition at line 217 of file Linear_System.inlines.hh.
References Parma_Polyhedra_Library::Matrix::permute_columns(), and sign_normalize().
Referenced by Parma_Polyhedra_Library::Polyhedron::bounded_affine_preimage(), Parma_Polyhedra_Library::Polyhedron::map_space_dimensions(), and Parma_Polyhedra_Library::Grid_Generator_System::permute_columns().
00217 { 00218 Matrix::permute_columns(cycles); 00219 // The rows with permuted columns are still normalized but may 00220 // be not strongly normalized: sign normalization is necessary. 00221 sign_normalize(); 00222 }
Linear_Row & Parma_Polyhedra_Library::Linear_System::operator[] | ( | dimension_type | k | ) | [inline] |
Returns a reference to the k-th
row of the system.
Reimplemented from Parma_Polyhedra_Library::Matrix.
Reimplemented in Parma_Polyhedra_Library::Constraint_System, Parma_Polyhedra_Library::Generator_System, and Parma_Polyhedra_Library::Grid_Generator_System.
Definition at line 178 of file Linear_System.inlines.hh.
References Parma_Polyhedra_Library::Matrix::operator[]().
Referenced by Parma_Polyhedra_Library::Generator_System::operator[](), and Parma_Polyhedra_Library::Constraint_System::operator[]().
00178 { 00179 return static_cast<Linear_Row&>(Matrix::operator[](k)); 00180 }
const Linear_Row & Parma_Polyhedra_Library::Linear_System::operator[] | ( | dimension_type | k | ) | const [inline] |
Returns a constant reference to the k-th
row of the system.
Reimplemented from Parma_Polyhedra_Library::Matrix.
Reimplemented in Parma_Polyhedra_Library::Constraint_System, Parma_Polyhedra_Library::Generator_System, and Parma_Polyhedra_Library::Grid_Generator_System.
Definition at line 183 of file Linear_System.inlines.hh.
References Parma_Polyhedra_Library::Matrix::operator[]().
00183 { 00184 return static_cast<const Linear_Row&>(Matrix::operator[](k)); 00185 }
void Parma_Polyhedra_Library::Linear_System::strong_normalize | ( | ) |
Strongly normalizes the system.
Definition at line 463 of file Linear_System.cc.
References Parma_Polyhedra_Library::Matrix::num_rows(), and set_sorted().
Referenced by Parma_Polyhedra_Library::Generator_System::affine_image(), Parma_Polyhedra_Library::Constraint_System::affine_preimage(), Parma_Polyhedra_Library::Polyhedron::OK(), OK(), and remove_trailing_columns().
00463 { 00464 Linear_System& x = *this; 00465 // We strongly normalize also the pending rows. 00466 for (dimension_type i = num_rows(); i-- > 0; ) 00467 x[i].strong_normalize(); 00468 set_sorted(false); 00469 }
void Parma_Polyhedra_Library::Linear_System::sign_normalize | ( | ) |
Sign-normalizes the system.
Definition at line 472 of file Linear_System.cc.
References Parma_Polyhedra_Library::Matrix::num_rows(), and set_sorted().
Referenced by permute_columns(), and Parma_Polyhedra_Library::Polyhedron::simplify().
00472 { 00473 Linear_System& x = *this; 00474 // We sign-normalize also the pending rows. 00475 for (dimension_type i = num_rows(); i-- > 0; ) 00476 x[i].sign_normalize(); 00477 set_sorted(false); 00478 }
Topology Parma_Polyhedra_Library::Linear_System::topology | ( | ) | const [inline] |
Returns the system topology.
Definition at line 188 of file Linear_System.inlines.hh.
References row_topology.
Referenced by Parma_Polyhedra_Library::Polyhedron::add_space_dimensions(), Parma_Polyhedra_Library::Generator_System::adjust_topology_and_space_dimension(), Parma_Polyhedra_Library::Constraint_System::adjust_topology_and_space_dimension(), Parma_Polyhedra_Library::Polyhedron::BHRZ03_combining_constraints(), Parma_Polyhedra_Library::Polyhedron::conversion(), insert(), Parma_Polyhedra_Library::Grid_Generator_System::insert(), Parma_Polyhedra_Library::Generator_System::insert(), Parma_Polyhedra_Library::Constraint_System::insert(), insert_pending(), Parma_Polyhedra_Library::Generator_System::insert_pending(), Parma_Polyhedra_Library::Constraint_System::insert_pending(), Parma_Polyhedra_Library::Polyhedron::minimize(), Parma_Polyhedra_Library::Polyhedron::OK(), OK(), Parma_Polyhedra_Library::Grid_Generator_System::OK(), Parma_Polyhedra_Library::Polyhedron::select_CH78_constraints(), Parma_Polyhedra_Library::Polyhedron::select_H79_constraints(), and Parma_Polyhedra_Library::Polyhedron::topology().
00188 { 00189 return row_topology; 00190 }
bool Parma_Polyhedra_Library::Linear_System::is_sorted | ( | ) | const [inline] |
Returns the value of the sortedness flag.
Definition at line 41 of file Linear_System.inlines.hh.
References check_sorted(), and sorted.
Referenced by Parma_Polyhedra_Library::Polyhedron::add_and_minimize(), Parma_Polyhedra_Library::Polyhedron::add_recycled_constraints_and_minimize(), Parma_Polyhedra_Library::Polyhedron::add_recycled_generators_and_minimize(), add_row(), add_rows(), add_rows_and_columns(), Parma_Polyhedra_Library::Polyhedron::add_space_dimensions(), Parma_Polyhedra_Library::Polyhedron::add_space_dimensions_and_embed(), Parma_Polyhedra_Library::Polyhedron::add_space_dimensions_and_project(), Parma_Polyhedra_Library::Constraint_System::adjust_topology_and_space_dimension(), Parma_Polyhedra_Library::Generator_System::ascii_dump(), Parma_Polyhedra_Library::Constraint_System::ascii_dump(), back_substitute(), Parma_Polyhedra_Library::Polyhedron::conversion(), Parma_Polyhedra_Library::Polyhedron::intersection_assign(), Parma_Polyhedra_Library::Polyhedron::minimize(), Parma_Polyhedra_Library::Constraint_System::num_inequalities(), Parma_Polyhedra_Library::Generator_System::num_lines(), Parma_Polyhedra_Library::Generator_System::num_rays(), Parma_Polyhedra_Library::Polyhedron::obtain_sorted_constraints(), Parma_Polyhedra_Library::Polyhedron::obtain_sorted_constraints_with_sat_c(), Parma_Polyhedra_Library::Polyhedron::obtain_sorted_generators(), Parma_Polyhedra_Library::Polyhedron::obtain_sorted_generators_with_sat_g(), Parma_Polyhedra_Library::Grid_Generator_System::OK(), Parma_Polyhedra_Library::Polyhedron::poly_hull_assign(), Parma_Polyhedra_Library::Polyhedron::process_pending_constraints(), Parma_Polyhedra_Library::Polyhedron::process_pending_generators(), sort_pending_and_remove_duplicates(), and Parma_Polyhedra_Library::Polyhedron::time_elapse_assign().
00041 { 00042 // The flag `sorted' does not really reflect the sortedness status 00043 // of a system (if `sorted' evaluates to `false' nothing is known). 00044 // This assertion is used to ensure that the system 00045 // is actually sorted when `sorted' value is 'true'. 00046 assert(!sorted || check_sorted()); 00047 return sorted; 00048 }
bool Parma_Polyhedra_Library::Linear_System::is_necessarily_closed | ( | ) | const [inline] |
Returns true
if and only if the system topology is NECESSARILY_CLOSED
.
Definition at line 173 of file Linear_System.inlines.hh.
References Parma_Polyhedra_Library::NECESSARILY_CLOSED, and row_topology.
Referenced by Parma_Polyhedra_Library::Polyhedron::add_and_minimize(), Parma_Polyhedra_Library::Generator_System::add_corresponding_closure_points(), Parma_Polyhedra_Library::Generator_System::add_corresponding_points(), Parma_Polyhedra_Library::Constraint_System::add_low_level_constraints(), Parma_Polyhedra_Library::Polyhedron::add_space_dimensions(), ascii_dump(), Parma_Polyhedra_Library::Generator_System::ascii_dump(), Parma_Polyhedra_Library::Constraint_System::ascii_dump(), Parma_Polyhedra_Library::Generator_System::begin(), Parma_Polyhedra_Library::Generator_System::has_closure_points(), Parma_Polyhedra_Library::Generator_System::has_points(), Parma_Polyhedra_Library::Constraint_System::has_strict_inequalities(), insert(), Parma_Polyhedra_Library::Grid_Generator_System::insert(), Parma_Polyhedra_Library::Generator_System::insert(), Parma_Polyhedra_Library::Constraint_System::insert(), insert_pending(), Parma_Polyhedra_Library::Generator_System::insert_pending(), Parma_Polyhedra_Library::Constraint_System::insert_pending(), Parma_Polyhedra_Library::Polyhedron::is_necessarily_closed(), Parma_Polyhedra_Library::Polyhedron::minimize(), OK(), Parma_Polyhedra_Library::Generator_System::const_iterator::operator++(), Parma_Polyhedra_Library::Constraint_System::satisfies_all_constraints(), set_rows_topology(), and space_dimension().
00173 { 00174 return row_topology == NECESSARILY_CLOSED; 00175 }
PPL::dimension_type Parma_Polyhedra_Library::Linear_System::num_lines_or_equalities | ( | ) | const |
Returns the number of rows in the system that represent either lines or equalities.
Definition at line 40 of file Linear_System.cc.
References num_pending_rows(), and Parma_Polyhedra_Library::Matrix::num_rows().
Referenced by Parma_Polyhedra_Library::Polyhedron::add_and_minimize(), back_substitute(), and gauss().
00040 { 00041 assert(num_pending_rows() == 0); 00042 const Linear_System& x = *this; 00043 dimension_type n = 0; 00044 for (dimension_type i = num_rows(); i-- > 0; ) 00045 if (x[i].is_line_or_equality()) 00046 ++n; 00047 return n; 00048 }
dimension_type Parma_Polyhedra_Library::Linear_System::first_pending_row | ( | ) | const [inline] |
Returns the index of the first pending row.
Definition at line 73 of file Linear_System.inlines.hh.
References index_first_pending.
Referenced by Parma_Polyhedra_Library::Polyhedron::add_and_minimize(), Parma_Polyhedra_Library::Polyhedron::add_space_dimensions(), Parma_Polyhedra_Library::Constraint_System::adjust_topology_and_space_dimension(), ascii_dump(), Parma_Polyhedra_Library::Generator_System::ascii_dump(), Parma_Polyhedra_Library::Constraint_System::ascii_dump(), check_sorted(), Parma_Polyhedra_Library::Polyhedron::conversion(), Parma_Polyhedra_Library::Polyhedron::is_universe(), num_pending_rows(), Parma_Polyhedra_Library::Polyhedron::OK(), OK(), operator==(), Parma_Polyhedra_Library::Generator_System::remove_invalid_lines_and_rays(), sort_and_remove_with_sat(), sort_pending_and_remove_duplicates(), sort_rows(), Parma_Polyhedra_Library::Polyhedron::update_sat_c(), and Parma_Polyhedra_Library::Polyhedron::update_sat_g().
00073 { 00074 return index_first_pending; 00075 }
dimension_type Parma_Polyhedra_Library::Linear_System::num_pending_rows | ( | ) | const [inline] |
Returns the number of rows that are in the pending part of the system.
Definition at line 78 of file Linear_System.inlines.hh.
References first_pending_row(), and Parma_Polyhedra_Library::Matrix::num_rows().
Referenced by Parma_Polyhedra_Library::Polyhedron::add_and_minimize(), add_pending_row(), Parma_Polyhedra_Library::Polyhedron::add_recycled_constraints_and_minimize(), Parma_Polyhedra_Library::Polyhedron::add_recycled_generators(), Parma_Polyhedra_Library::Polyhedron::add_recycled_generators_and_minimize(), add_row(), add_rows(), Parma_Polyhedra_Library::Constraint_System::adjust_topology_and_space_dimension(), back_substitute(), gauss(), insert(), Parma_Polyhedra_Library::Grid_Generator_System::insert(), Parma_Polyhedra_Library::Generator_System::insert(), Parma_Polyhedra_Library::Constraint_System::insert(), insert_pending(), Parma_Polyhedra_Library::Polyhedron::intersection_assign_and_minimize(), Linear_System(), merge_rows_assign(), Parma_Polyhedra_Library::Constraint_System::num_equalities(), Parma_Polyhedra_Library::Constraint_System::num_inequalities(), Parma_Polyhedra_Library::Generator_System::num_lines(), num_lines_or_equalities(), Parma_Polyhedra_Library::Generator_System::num_rays(), Parma_Polyhedra_Library::Polyhedron::OK(), operator=(), Parma_Polyhedra_Library::Polyhedron::poly_hull_assign_and_minimize(), Parma_Polyhedra_Library::Polyhedron::Polyhedron(), Parma_Polyhedra_Library::Polyhedron::process_pending_constraints(), Parma_Polyhedra_Library::Polyhedron::process_pending_generators(), Parma_Polyhedra_Library::Generator_System::remove_invalid_lines_and_rays(), Parma_Polyhedra_Library::Polyhedron::shrink_bounding_box(), simplify(), sort_and_remove_with_sat(), sort_pending_and_remove_duplicates(), and sort_rows().
00078 { 00079 assert(num_rows() >= first_pending_row()); 00080 return num_rows() - first_pending_row(); 00081 }
bool Parma_Polyhedra_Library::Linear_System::check_sorted | ( | ) | const |
Returns true
if and only if *this
is sorted, without checking for duplicates.
Definition at line 821 of file Linear_System.cc.
References first_pending_row().
Referenced by is_sorted(), merge_rows_assign(), Parma_Polyhedra_Library::Polyhedron::obtain_sorted_constraints(), Parma_Polyhedra_Library::Polyhedron::obtain_sorted_constraints_with_sat_c(), Parma_Polyhedra_Library::Polyhedron::obtain_sorted_generators(), Parma_Polyhedra_Library::Polyhedron::obtain_sorted_generators_with_sat_g(), OK(), and sort_and_remove_with_sat().
00821 { 00822 const Linear_System& x = *this; 00823 for (dimension_type i = first_pending_row(); i-- > 1; ) 00824 if (compare(x[i], x[i-1]) < 0) 00825 return false; 00826 return true; 00827 }
void Parma_Polyhedra_Library::Linear_System::set_necessarily_closed | ( | ) | [inline] |
Sets the system topology to NECESSARILY_CLOSED
.
Definition at line 159 of file Linear_System.inlines.hh.
References Parma_Polyhedra_Library::NECESSARILY_CLOSED, Parma_Polyhedra_Library::Matrix::num_rows(), row_topology, and set_rows_topology().
Referenced by Parma_Polyhedra_Library::Generator_System::adjust_topology_and_space_dimension(), Parma_Polyhedra_Library::Constraint_System::adjust_topology_and_space_dimension(), ascii_load(), Parma_Polyhedra_Library::Grid_Generator_System::ascii_load(), Parma_Polyhedra_Library::Generator_System::ascii_load(), Parma_Polyhedra_Library::Constraint_System::ascii_load(), set_rows_topology(), and Parma_Polyhedra_Library::Polyhedron::strongly_minimize_constraints().
00159 { 00160 row_topology = NECESSARILY_CLOSED; 00161 if (num_rows() > 0) 00162 set_rows_topology(); 00163 }
void Parma_Polyhedra_Library::Linear_System::set_not_necessarily_closed | ( | ) | [inline] |
Sets the system topology to NOT_NECESSARILY_CLOSED
.
Definition at line 166 of file Linear_System.inlines.hh.
References Parma_Polyhedra_Library::NOT_NECESSARILY_CLOSED, Parma_Polyhedra_Library::Matrix::num_rows(), row_topology, and set_rows_topology().
Referenced by Parma_Polyhedra_Library::Generator_System::adjust_topology_and_space_dimension(), Parma_Polyhedra_Library::Constraint_System::adjust_topology_and_space_dimension(), ascii_load(), Parma_Polyhedra_Library::Grid_Generator_System::ascii_load(), Parma_Polyhedra_Library::Generator_System::ascii_load(), Parma_Polyhedra_Library::Constraint_System::ascii_load(), Parma_Polyhedra_Library::Generator_System::insert(), Parma_Polyhedra_Library::Constraint_System::insert(), Parma_Polyhedra_Library::Generator_System::insert_pending(), Parma_Polyhedra_Library::Constraint_System::insert_pending(), set_rows_topology(), and Parma_Polyhedra_Library::Polyhedron::strongly_minimize_constraints().
00166 { 00167 row_topology = NOT_NECESSARILY_CLOSED; 00168 if (num_rows() > 0) 00169 set_rows_topology(); 00170 }
void Parma_Polyhedra_Library::Linear_System::set_rows_topology | ( | ) |
Sets the topology of all rows equal to the system topology.
Definition at line 102 of file Linear_System.cc.
References is_necessarily_closed(), Parma_Polyhedra_Library::Matrix::num_rows(), set_necessarily_closed(), and set_not_necessarily_closed().
Referenced by set_necessarily_closed(), and set_not_necessarily_closed().
00102 { 00103 Linear_System& x = *this; 00104 if (is_necessarily_closed()) 00105 for (dimension_type i = num_rows(); i-- > 0; ) 00106 x[i].set_necessarily_closed(); 00107 else 00108 for (dimension_type i = num_rows(); i-- > 0; ) 00109 x[i].set_not_necessarily_closed(); 00110 }
void Parma_Polyhedra_Library::Linear_System::unset_pending_rows | ( | ) | [inline] |
Sets the index to indicate that the system has no pending rows.
Reimplemented in Parma_Polyhedra_Library::Grid_Generator_System.
Definition at line 84 of file Linear_System.inlines.hh.
References index_first_pending, and Parma_Polyhedra_Library::Matrix::num_rows().
Referenced by Parma_Polyhedra_Library::Polyhedron::add_recycled_constraints(), Parma_Polyhedra_Library::Polyhedron::add_recycled_constraints_and_minimize(), Parma_Polyhedra_Library::Polyhedron::add_recycled_generators(), Parma_Polyhedra_Library::Polyhedron::add_recycled_generators_and_minimize(), add_rows(), Parma_Polyhedra_Library::Polyhedron::add_space_dimensions_and_embed(), Parma_Polyhedra_Library::Polyhedron::add_space_dimensions_and_project(), Parma_Polyhedra_Library::Constraint_System::adjust_topology_and_space_dimension(), Parma_Polyhedra_Library::Polyhedron::concatenate_assign(), Parma_Polyhedra_Library::Polyhedron::conversion(), Linear_System(), merge_rows_assign(), Parma_Polyhedra_Library::Polyhedron::OK(), operator=(), Parma_Polyhedra_Library::Polyhedron::Polyhedron(), Parma_Polyhedra_Library::Polyhedron::remove_pending_to_obtain_constraints(), Parma_Polyhedra_Library::Polyhedron::remove_pending_to_obtain_generators(), Parma_Polyhedra_Library::Polyhedron::shrink_bounding_box(), Parma_Polyhedra_Library::Polyhedron::simplify(), simplify(), Parma_Polyhedra_Library::Polyhedron::strongly_minimize_constraints(), Parma_Polyhedra_Library::Polyhedron::strongly_minimize_generators(), Parma_Polyhedra_Library::Polyhedron::time_elapse_assign(), Parma_Polyhedra_Library::Polyhedron::topological_closure_assign(), and Parma_Polyhedra_Library::Grid_Generator_System::unset_pending_rows().
00084 { 00085 index_first_pending = num_rows(); 00086 }
void Parma_Polyhedra_Library::Linear_System::set_index_first_pending_row | ( | dimension_type | i | ) | [inline] |
Sets the index of the first pending row to i
.
Reimplemented in Parma_Polyhedra_Library::Grid_Generator_System.
Definition at line 89 of file Linear_System.inlines.hh.
References index_first_pending.
Referenced by add_row(), Parma_Polyhedra_Library::Polyhedron::add_space_dimensions(), Parma_Polyhedra_Library::Constraint_System::adjust_topology_and_space_dimension(), ascii_load(), Parma_Polyhedra_Library::Generator_System::ascii_load(), Parma_Polyhedra_Library::Constraint_System::ascii_load(), Parma_Polyhedra_Library::Polyhedron::minimize(), Parma_Polyhedra_Library::Polyhedron::Polyhedron(), Parma_Polyhedra_Library::Generator_System::remove_invalid_lines_and_rays(), Parma_Polyhedra_Library::Grid_Generator_System::set_index_first_pending_row(), sort_and_remove_with_sat(), and sort_rows().
00089 { 00090 index_first_pending = i; 00091 }
void Parma_Polyhedra_Library::Linear_System::set_sorted | ( | bool | b | ) | [inline] |
Sets the sortedness flag of the system to b
.
Reimplemented in Parma_Polyhedra_Library::Grid_Generator_System.
Definition at line 51 of file Linear_System.inlines.hh.
References sorted.
Referenced by Parma_Polyhedra_Library::Polyhedron::add_recycled_constraints(), Parma_Polyhedra_Library::Polyhedron::add_recycled_generators(), add_row(), add_rows(), add_rows_and_columns(), Parma_Polyhedra_Library::Constraint_System::adjust_topology_and_space_dimension(), ascii_load(), Parma_Polyhedra_Library::Generator_System::ascii_load(), Parma_Polyhedra_Library::Constraint_System::ascii_load(), back_substitute(), Parma_Polyhedra_Library::Polyhedron::concatenate_assign(), Parma_Polyhedra_Library::Polyhedron::conversion(), gauss(), Parma_Polyhedra_Library::Polyhedron::generalized_affine_image(), Parma_Polyhedra_Library::Polyhedron::minimize(), normalize(), Parma_Polyhedra_Library::Polyhedron::obtain_sorted_constraints_with_sat_c(), Parma_Polyhedra_Library::Polyhedron::obtain_sorted_generators_with_sat_g(), Parma_Polyhedra_Library::Polyhedron::Polyhedron(), Parma_Polyhedra_Library::Generator_System::remove_invalid_lines_and_rays(), Parma_Polyhedra_Library::Polyhedron::remove_pending_to_obtain_constraints(), Parma_Polyhedra_Library::Polyhedron::remove_pending_to_obtain_generators(), resize_no_copy(), Parma_Polyhedra_Library::Grid_Generator_System::set_sorted(), sign_normalize(), Parma_Polyhedra_Library::Polyhedron::simplify(), simplify(), sort_and_remove_with_sat(), strong_normalize(), Parma_Polyhedra_Library::Polyhedron::strongly_minimize_constraints(), Parma_Polyhedra_Library::Polyhedron::strongly_minimize_generators(), and Parma_Polyhedra_Library::Polyhedron::topological_closure_assign().
00051 { 00052 sorted = b; 00053 }
void Parma_Polyhedra_Library::Linear_System::resize_no_copy | ( | dimension_type | new_n_rows, | |
dimension_type | new_n_columns | |||
) | [inline] |
Resizes the system without worrying about the old contents.
new_n_rows | The number of rows of the resized system; | |
new_n_columns | The number of columns of the resized system. |
Reimplemented in Parma_Polyhedra_Library::Grid_Generator_System.
Definition at line 147 of file Linear_System.inlines.hh.
References Parma_Polyhedra_Library::Matrix::resize_no_copy(), row_topology, and set_sorted().
Referenced by ascii_load(), Parma_Polyhedra_Library::Generator_System::ascii_load(), Parma_Polyhedra_Library::Constraint_System::ascii_load(), Parma_Polyhedra_Library::Polyhedron::minimize(), and Parma_Polyhedra_Library::Grid_Generator_System::resize_no_copy().
00148 { 00149 Matrix::resize_no_copy(new_n_rows, new_n_columns, 00150 Linear_Row::Flags(row_topology)); 00151 // Even though `*this' may happen to keep its sortedness, we believe 00152 // that checking such a property is not worth the effort. In fact, 00153 // it is very likely that the system will be overwritten as soon as 00154 // we return. 00155 set_sorted(false); 00156 }
void Parma_Polyhedra_Library::Linear_System::add_rows_and_columns | ( | dimension_type | n | ) |
Adds n
rows and columns to the system.
n | The number of rows and columns to be added: must be strictly positive. |
Definition at line 730 of file Linear_System.cc.
References Parma_Polyhedra_Library::Matrix::add_zero_rows_and_columns(), is_sorted(), Parma_Polyhedra_Library::Matrix::num_columns(), Parma_Polyhedra_Library::Matrix::num_rows(), Parma_Polyhedra_Library::Matrix::OK(), row_topology, Parma_Polyhedra_Library::Linear_Row::set_is_line_or_equality(), and set_sorted().
Referenced by Parma_Polyhedra_Library::Polyhedron::add_space_dimensions(), Parma_Polyhedra_Library::Polyhedron::add_space_dimensions_and_embed(), Parma_Polyhedra_Library::Polyhedron::add_space_dimensions_and_project(), and Parma_Polyhedra_Library::Polyhedron::concatenate_assign().
00730 { 00731 assert(n > 0); 00732 const bool was_sorted = is_sorted(); 00733 const dimension_type old_n_rows = num_rows(); 00734 const dimension_type old_n_columns = num_columns(); 00735 add_zero_rows_and_columns(n, n, Linear_Row::Flags(row_topology)); 00736 Linear_System& x = *this; 00737 // The old system is moved to the bottom. 00738 for (dimension_type i = old_n_rows; i-- > 0; ) 00739 std::swap(x[i], x[i + n]); 00740 for (dimension_type i = n, c = old_n_columns; i-- > 0; ) { 00741 // The top right-hand sub-system (i.e., the system made of new 00742 // rows and columns) is set to the specular image of the identity 00743 // matrix. 00744 Linear_Row& r = x[i]; 00745 r[c++] = 1; 00746 r.set_is_line_or_equality(); 00747 // Note: `r' is strongly normalized. 00748 } 00749 // If the old system was empty, the last row added is either 00750 // a positivity constraint or a point. 00751 if (old_n_columns == 0) { 00752 x[n-1].set_is_ray_or_point_or_inequality(); 00753 // Since ray, points and inequalities come after lines 00754 // and equalities, this case implies the system is sorted. 00755 set_sorted(true); 00756 } 00757 else if (was_sorted) 00758 set_sorted(compare(x[n-1], x[n]) <= 0); 00759 00760 // A well-formed system has to be returned. 00761 assert(OK(true)); 00762 }
void Parma_Polyhedra_Library::Linear_System::insert | ( | const Linear_Row & | r | ) |
Adds a copy of r
to the system, automatically resizing the system or the row's copy, if needed.
Definition at line 182 of file Linear_System.cc.
References add_row(), Parma_Polyhedra_Library::Matrix::add_zero_columns(), Parma_Polyhedra_Library::Linear_Row::check_strong_normalized(), is_necessarily_closed(), Parma_Polyhedra_Library::Matrix::num_columns(), num_pending_rows(), Parma_Polyhedra_Library::Matrix::num_rows(), Parma_Polyhedra_Library::Matrix::OK(), Parma_Polyhedra_Library::Matrix::row_capacity, Parma_Polyhedra_Library::Row::size(), Parma_Polyhedra_Library::Matrix::swap_columns(), Parma_Polyhedra_Library::Linear_Row::topology(), and topology().
Referenced by Parma_Polyhedra_Library::Constraint_System::Constraint_System(), Parma_Polyhedra_Library::Generator_System::Generator_System(), Parma_Polyhedra_Library::Generator_System::insert(), and Parma_Polyhedra_Library::Constraint_System::insert().
00182 { 00183 // The added row must be strongly normalized and have the same 00184 // topology of the system. 00185 assert(r.check_strong_normalized()); 00186 assert(topology() == r.topology()); 00187 // This method is only used when the system has no pending rows. 00188 assert(num_pending_rows() == 0); 00189 00190 const dimension_type old_num_rows = num_rows(); 00191 const dimension_type old_num_columns = num_columns(); 00192 const dimension_type r_size = r.size(); 00193 00194 // Resize the system, if necessary. 00195 if (r_size > old_num_columns) { 00196 add_zero_columns(r_size - old_num_columns); 00197 if (!is_necessarily_closed() && old_num_rows != 0) 00198 // Move the epsilon coefficients to the last column 00199 // (note: sorting is preserved). 00200 swap_columns(old_num_columns - 1, r_size - 1); 00201 add_row(r); 00202 } 00203 else if (r_size < old_num_columns) 00204 if (is_necessarily_closed() || old_num_rows == 0) 00205 add_row(Linear_Row(r, old_num_columns, row_capacity)); 00206 else { 00207 // Create a resized copy of the row (and move the epsilon 00208 // coefficient to its last position). 00209 Linear_Row tmp_row(r, old_num_columns, row_capacity); 00210 std::swap(tmp_row[r_size - 1], tmp_row[old_num_columns - 1]); 00211 add_row(tmp_row); 00212 } 00213 else 00214 // Here r_size == old_num_columns. 00215 add_row(r); 00216 00217 // The added row was not a pending row. 00218 assert(num_pending_rows() == 0); 00219 // Do not check for strong normalization, 00220 // because no modification of rows has occurred. 00221 assert(OK(false)); 00222 }
void Parma_Polyhedra_Library::Linear_System::insert_pending | ( | const Linear_Row & | r | ) |
Adds a copy of the given row to the pending part of the system, automatically resizing the system or the row, if needed.
Definition at line 225 of file Linear_System.cc.
References add_pending_row(), Parma_Polyhedra_Library::Matrix::add_zero_columns(), Parma_Polyhedra_Library::Linear_Row::check_strong_normalized(), is_necessarily_closed(), Parma_Polyhedra_Library::Matrix::num_columns(), num_pending_rows(), Parma_Polyhedra_Library::Matrix::num_rows(), Parma_Polyhedra_Library::Matrix::OK(), Parma_Polyhedra_Library::Matrix::row_capacity, Parma_Polyhedra_Library::Row::size(), Parma_Polyhedra_Library::Matrix::swap_columns(), Parma_Polyhedra_Library::Linear_Row::topology(), and topology().
Referenced by Parma_Polyhedra_Library::Generator_System::insert_pending(), and Parma_Polyhedra_Library::Constraint_System::insert_pending().
00225 { 00226 // The added row must be strongly normalized and have the same 00227 // topology of the system. 00228 assert(r.check_strong_normalized()); 00229 assert(topology() == r.topology()); 00230 00231 const dimension_type old_num_rows = num_rows(); 00232 const dimension_type old_num_columns = num_columns(); 00233 const dimension_type r_size = r.size(); 00234 00235 // Resize the system, if necessary. 00236 if (r_size > old_num_columns) { 00237 add_zero_columns(r_size - old_num_columns); 00238 if (!is_necessarily_closed() && old_num_rows != 0) 00239 // Move the epsilon coefficients to the last column 00240 // (note: sorting is preserved). 00241 swap_columns(old_num_columns - 1, r_size - 1); 00242 add_pending_row(r); 00243 } 00244 else if (r_size < old_num_columns) 00245 if (is_necessarily_closed() || old_num_rows == 0) 00246 add_pending_row(Linear_Row(r, old_num_columns, row_capacity)); 00247 else { 00248 // Create a resized copy of the row (and move the epsilon 00249 // coefficient to its last position). 00250 Linear_Row tmp_row(r, old_num_columns, row_capacity); 00251 std::swap(tmp_row[r_size - 1], tmp_row[old_num_columns - 1]); 00252 add_pending_row(tmp_row); 00253 } 00254 else 00255 // Here r_size == old_num_columns. 00256 add_pending_row(r); 00257 00258 // The added row was a pending row. 00259 assert(num_pending_rows() > 0); 00260 // Do not check for strong normalization, 00261 // because no modification of rows has occurred. 00262 assert(OK(false)); 00263 }
void Parma_Polyhedra_Library::Linear_System::add_row | ( | const Linear_Row & | r | ) |
Adds a copy of the given row to the system.
Definition at line 348 of file Linear_System.cc.
References Parma_Polyhedra_Library::Matrix::add_row(), Parma_Polyhedra_Library::Linear_Row::check_strong_normalized(), is_sorted(), num_pending_rows(), Parma_Polyhedra_Library::Matrix::num_rows(), Parma_Polyhedra_Library::Matrix::OK(), Parma_Polyhedra_Library::Matrix::row_size, set_index_first_pending_row(), set_sorted(), and Parma_Polyhedra_Library::Row::size().
Referenced by Parma_Polyhedra_Library::Polyhedron::generalized_affine_image(), and insert().
00348 { 00349 // The added row must be strongly normalized and have the same 00350 // number of elements as the existing rows of the system. 00351 assert(r.check_strong_normalized()); 00352 assert(r.size() == row_size); 00353 // This method is only used when the system has no pending rows. 00354 assert(num_pending_rows() == 0); 00355 00356 const bool was_sorted = is_sorted(); 00357 00358 Matrix::add_row(r); 00359 00360 // We update `index_first_pending', because it must be equal to 00361 // `num_rows()'. 00362 set_index_first_pending_row(num_rows()); 00363 00364 if (was_sorted) { 00365 const dimension_type nrows = num_rows(); 00366 // The added row may have caused the system to be not sorted anymore. 00367 if (nrows > 1) { 00368 // If the system is not empty and the inserted row is the 00369 // greatest one, the system is set to be sorted. 00370 // If it is not the greatest one then the system is no longer sorted. 00371 Linear_System& x = *this; 00372 set_sorted(compare(x[nrows-2], x[nrows-1]) <= 0); 00373 } 00374 else 00375 // A system having only one row is sorted. 00376 set_sorted(true); 00377 } 00378 // The added row was not a pending row. 00379 assert(num_pending_rows() == 0); 00380 // Do not check for strong normalization, because no modification of 00381 // rows has occurred. 00382 assert(OK(false)); 00383 }
void Parma_Polyhedra_Library::Linear_System::add_pending_row | ( | Linear_Row::Flags | flags | ) |
Adds a new empty row to the system, setting only its flags.
Definition at line 424 of file Linear_System.cc.
References Parma_Polyhedra_Library::compute_capacity(), Parma_Polyhedra_Library::Matrix::max_num_rows(), num_pending_rows(), Parma_Polyhedra_Library::Matrix::row_capacity, Parma_Polyhedra_Library::Matrix::row_size, and Parma_Polyhedra_Library::Matrix::rows.
Referenced by Parma_Polyhedra_Library::Polyhedron::add_and_minimize(), Parma_Polyhedra_Library::Generator_System::add_corresponding_closure_points(), Parma_Polyhedra_Library::Generator_System::add_corresponding_points(), Parma_Polyhedra_Library::Polyhedron::conversion(), and insert_pending().
00424 { 00425 const dimension_type new_rows_size = rows.size() + 1; 00426 if (rows.capacity() < new_rows_size) { 00427 // Reallocation will take place. 00428 std::vector<Row> new_rows; 00429 new_rows.reserve(compute_capacity(new_rows_size, max_num_rows())); 00430 new_rows.insert(new_rows.end(), new_rows_size, Row()); 00431 // Put the new row in place. 00432 Linear_Row new_row(row_size, row_capacity, flags); 00433 dimension_type i = new_rows_size-1; 00434 std::swap(new_rows[i], new_row); 00435 // Steal the old rows. 00436 while (i-- > 0) 00437 new_rows[i].swap(rows[i]); 00438 // Put the new vector into place. 00439 std::swap(rows, new_rows); 00440 } 00441 else { 00442 // Reallocation will NOT take place. 00443 // Insert a new empty row at the end, then construct it assigning 00444 // it the given type. 00445 Row& new_row = *rows.insert(rows.end(), Row()); 00446 static_cast<Linear_Row&>(new_row).construct(row_size, row_capacity, flags); 00447 } 00448 00449 // The added row was a pending row. 00450 assert(num_pending_rows() > 0); 00451 }
void Parma_Polyhedra_Library::Linear_System::add_pending_row | ( | const Linear_Row & | r | ) |
Adds a copy of the given row to the pending part of the system.
Definition at line 386 of file Linear_System.cc.
References Parma_Polyhedra_Library::Linear_Row::check_strong_normalized(), Parma_Polyhedra_Library::compute_capacity(), Parma_Polyhedra_Library::Matrix::max_num_rows(), num_pending_rows(), Parma_Polyhedra_Library::Matrix::OK(), Parma_Polyhedra_Library::Matrix::row_capacity, Parma_Polyhedra_Library::Matrix::row_size, Parma_Polyhedra_Library::Matrix::rows, and Parma_Polyhedra_Library::Row::size().
00386 { 00387 // The added row must be strongly normalized and have the same 00388 // number of elements of the existing rows of the system. 00389 assert(r.check_strong_normalized()); 00390 assert(r.size() == row_size); 00391 00392 const dimension_type new_rows_size = rows.size() + 1; 00393 if (rows.capacity() < new_rows_size) { 00394 // Reallocation will take place. 00395 std::vector<Row> new_rows; 00396 new_rows.reserve(compute_capacity(new_rows_size, max_num_rows())); 00397 new_rows.insert(new_rows.end(), new_rows_size, Row()); 00398 // Put the new row in place. 00399 Row new_row(r, row_capacity); 00400 dimension_type i = new_rows_size-1; 00401 std::swap(new_rows[i], new_row); 00402 // Steal the old rows. 00403 while (i-- > 0) 00404 new_rows[i].swap(rows[i]); 00405 // Put the new rows into place. 00406 std::swap(rows, new_rows); 00407 } 00408 else { 00409 // Reallocation will NOT take place. 00410 // Inserts a new empty row at the end, then substitutes it with a 00411 // copy of the given row. 00412 Row tmp(r, row_capacity); 00413 std::swap(*rows.insert(rows.end(), Row()), tmp); 00414 } 00415 00416 // The added row was a pending row. 00417 assert(num_pending_rows() > 0); 00418 // Do not check for strong normalization, because no modification of 00419 // rows has occurred. 00420 assert(OK(false)); 00421 }
void Parma_Polyhedra_Library::Linear_System::add_rows | ( | const Linear_System & | y | ) |
Adds to *this
a copy of the rows of `y'.
It is assumed that *this
has no pending rows.
Definition at line 288 of file Linear_System.cc.
References add_pending_rows(), is_sorted(), num_pending_rows(), Parma_Polyhedra_Library::Matrix::num_rows(), Parma_Polyhedra_Library::Matrix::OK(), set_sorted(), and unset_pending_rows().
Referenced by Parma_Polyhedra_Library::Polyhedron::intersection_assign(), and Parma_Polyhedra_Library::Polyhedron::poly_hull_assign().
00288 { 00289 assert(num_pending_rows() == 0); 00290 00291 // Adding no rows is a no-op. 00292 if (y.num_rows() == 0) 00293 return; 00294 00295 // Check if sortedness is preserved. 00296 if (is_sorted()) 00297 if (!y.is_sorted() || y.num_pending_rows() > 0) 00298 set_sorted(false); 00299 else { 00300 // `y' is sorted and has no pending rows. 00301 const dimension_type n_rows = num_rows(); 00302 if (n_rows > 0) 00303 set_sorted(compare((*this)[n_rows-1], y[0]) <= 0); 00304 } 00305 00306 // Add the rows of `y' as if they were pending. 00307 add_pending_rows(y); 00308 // There are no pending_rows. 00309 unset_pending_rows(); 00310 00311 // Do not check for strong normalization, 00312 // because no modification of rows has occurred. 00313 assert(OK(false)); 00314 }
void Parma_Polyhedra_Library::Linear_System::add_pending_rows | ( | const Linear_System & | y | ) |
Adds a copy of the rows of `y' to the pending part of `*this'.
Definition at line 266 of file Linear_System.cc.
References Parma_Polyhedra_Library::Matrix::add_zero_rows(), Parma_Polyhedra_Library::Matrix::num_rows(), Parma_Polyhedra_Library::Matrix::OK(), Parma_Polyhedra_Library::Matrix::row_capacity, Parma_Polyhedra_Library::Matrix::row_size, row_topology, and sorted.
Referenced by add_rows(), Parma_Polyhedra_Library::Polyhedron::intersection_assign(), Parma_Polyhedra_Library::Polyhedron::intersection_assign_and_minimize(), Parma_Polyhedra_Library::Polyhedron::poly_hull_assign(), Parma_Polyhedra_Library::Polyhedron::poly_hull_assign_and_minimize(), and Parma_Polyhedra_Library::Polyhedron::time_elapse_assign().
00266 { 00267 Linear_System& x = *this; 00268 assert(x.row_size == y.row_size); 00269 00270 const dimension_type x_n_rows = x.num_rows(); 00271 const dimension_type y_n_rows = y.num_rows(); 00272 // Grow to the required size without changing sortedness. 00273 const bool was_sorted = sorted; 00274 add_zero_rows(y_n_rows, Linear_Row::Flags(row_topology)); 00275 sorted = was_sorted; 00276 00277 // Copy the rows of `y', forcing size and capacity. 00278 for (dimension_type i = y_n_rows; i-- > 0; ) { 00279 Row copy(y[i], x.row_size, x.row_capacity); 00280 std::swap(copy, x[x_n_rows+i]); 00281 } 00282 // Do not check for strong normalization, 00283 // because no modification of rows has occurred. 00284 assert(OK(false)); 00285 }
void Parma_Polyhedra_Library::Linear_System::sort_rows | ( | ) |
Sorts the non-pending rows (in growing order) and eliminates duplicated ones.
Definition at line 317 of file Linear_System.cc.
References first_pending_row(), num_pending_rows(), Parma_Polyhedra_Library::Matrix::num_rows(), Parma_Polyhedra_Library::Matrix::OK(), set_index_first_pending_row(), and sorted.
Referenced by Parma_Polyhedra_Library::Polyhedron::add_recycled_constraints_and_minimize(), Parma_Polyhedra_Library::Polyhedron::add_recycled_generators_and_minimize(), Parma_Polyhedra_Library::Constraint_System::adjust_topology_and_space_dimension(), Parma_Polyhedra_Library::Polyhedron::concatenate_assign(), Parma_Polyhedra_Library::Polyhedron::minimize(), Parma_Polyhedra_Library::Polyhedron::obtain_sorted_constraints(), Parma_Polyhedra_Library::Polyhedron::obtain_sorted_generators(), Parma_Polyhedra_Library::Polyhedron::OK(), sort_pending_and_remove_duplicates(), and Parma_Polyhedra_Library::Polyhedron::time_elapse_assign().
00317 { 00318 const dimension_type num_pending = num_pending_rows(); 00319 // We sort the non-pending rows only. 00320 sort_rows(0, first_pending_row()); 00321 set_index_first_pending_row(num_rows() - num_pending); 00322 sorted = true; 00323 // Do not check for strong normalization, 00324 // because no modification of rows has occurred. 00325 assert(OK(false)); 00326 }
void Parma_Polyhedra_Library::Linear_System::sort_rows | ( | dimension_type | first_row, | |
dimension_type | last_row | |||
) |
Sorts the rows (in growing order) form first_row
to last_row
and eliminates duplicated ones.
Definition at line 329 of file Linear_System.cc.
References first_pending_row(), Parma_Polyhedra_Library::Matrix::num_rows(), and Parma_Polyhedra_Library::Matrix::rows.
00330 { 00331 assert(first_row <= last_row && last_row <= num_rows()); 00332 // We cannot mix pending and non-pending rows. 00333 assert(first_row >= first_pending_row() || last_row <= first_pending_row()); 00334 00335 // First sort without removing duplicates. 00336 std::vector<Row>::iterator first = rows.begin() + first_row; 00337 std::vector<Row>::iterator last = rows.begin() + last_row; 00338 swapping_sort(first, last, Row_Less_Than()); 00339 // Second, move duplicates to the end. 00340 std::vector<Row>::iterator new_last = swapping_unique(first, last); 00341 // Finally, remove duplicates. 00342 rows.erase(new_last, last); 00343 // NOTE: we cannot check for well-formedness of the system here, 00344 // because the caller still has to update `index_first_pending'. 00345 }
void Parma_Polyhedra_Library::Linear_System::merge_rows_assign | ( | const Linear_System & | y | ) |
Assigns to *this
the result of merging its rows with those of y
, obtaining a sorted system.
Duplicated rows will occur only once in the result. On entry, both systems are assumed to be sorted and have no pending rows.
Definition at line 51 of file Linear_System.cc.
References check_sorted(), Parma_Polyhedra_Library::compute_capacity(), Parma_Polyhedra_Library::Matrix::max_num_rows(), num_pending_rows(), Parma_Polyhedra_Library::Matrix::num_rows(), Parma_Polyhedra_Library::Matrix::row_capacity, Parma_Polyhedra_Library::Matrix::row_size, Parma_Polyhedra_Library::Matrix::rows, and unset_pending_rows().
Referenced by Parma_Polyhedra_Library::Polyhedron::intersection_assign(), Parma_Polyhedra_Library::Polyhedron::poly_hull_assign(), and Parma_Polyhedra_Library::Polyhedron::time_elapse_assign().
00051 { 00052 assert(row_size >= y.row_size); 00053 // Both systems have to be sorted and have no pending rows. 00054 assert(check_sorted() && y.check_sorted()); 00055 assert(num_pending_rows() == 0 && y.num_pending_rows() == 0); 00056 00057 Linear_System& x = *this; 00058 00059 // A temporary vector of rows... 00060 std::vector<Row> tmp; 00061 // ... with enough capacity not to require any reallocations. 00062 tmp.reserve(compute_capacity(x.num_rows() + y.num_rows(), max_num_rows())); 00063 00064 dimension_type xi = 0; 00065 dimension_type x_num_rows = x.num_rows(); 00066 dimension_type yi = 0; 00067 dimension_type y_num_rows = y.num_rows(); 00068 00069 while (xi < x_num_rows && yi < y_num_rows) { 00070 const int comp = compare(x[xi], y[yi]); 00071 if (comp <= 0) { 00072 // Elements that can be taken from `x' are actually _stolen_ from `x' 00073 std::swap(x[xi++], *tmp.insert(tmp.end(), Linear_Row())); 00074 if (comp == 0) 00075 // A duplicate element. 00076 ++yi; 00077 } 00078 else { 00079 // (comp > 0) 00080 Linear_Row copy(y[yi++], row_size, row_capacity); 00081 std::swap(copy, *tmp.insert(tmp.end(), Linear_Row())); 00082 } 00083 } 00084 // Insert what is left. 00085 if (xi < x_num_rows) 00086 while (xi < x_num_rows) 00087 std::swap(x[xi++], *tmp.insert(tmp.end(), Linear_Row())); 00088 else 00089 while (yi < y_num_rows) { 00090 Linear_Row copy(y[yi++], row_size, row_capacity); 00091 std::swap(copy, *tmp.insert(tmp.end(), Linear_Row())); 00092 } 00093 00094 // We get the result vector and let the old one be destroyed. 00095 std::swap(tmp, rows); 00096 // There are no pending rows. 00097 unset_pending_rows(); 00098 assert(check_sorted()); 00099 }
void Parma_Polyhedra_Library::Linear_System::sort_pending_and_remove_duplicates | ( | ) |
Sorts the pending rows and eliminates those that also occur in the non-pending part of the system.
Definition at line 765 of file Linear_System.cc.
References Parma_Polyhedra_Library::cmp(), Parma_Polyhedra_Library::Matrix::erase_to_end(), first_pending_row(), is_sorted(), num_pending_rows(), Parma_Polyhedra_Library::Matrix::num_rows(), Parma_Polyhedra_Library::Matrix::OK(), and sort_rows().
Referenced by Parma_Polyhedra_Library::Polyhedron::intersection_assign_and_minimize(), Parma_Polyhedra_Library::Polyhedron::poly_hull_assign_and_minimize(), Parma_Polyhedra_Library::Polyhedron::process_pending_constraints(), and Parma_Polyhedra_Library::Polyhedron::process_pending_generators().
00765 { 00766 assert(num_pending_rows() > 0); 00767 assert(is_sorted()); 00768 Linear_System& x = *this; 00769 00770 // The non-pending part of the system is already sorted. 00771 // Now sorting the pending part.. 00772 const dimension_type first_pending = x.first_pending_row(); 00773 x.sort_rows(first_pending, x.num_rows()); 00774 // Recompute the number of rows, because we may have removed 00775 // some rows occurring more than once in the pending part. 00776 dimension_type num_rows = x.num_rows(); 00777 00778 dimension_type k1 = 0; 00779 dimension_type k2 = first_pending; 00780 dimension_type num_duplicates = 0; 00781 // In order to erase them, put at the end of the system 00782 // those pending rows that also occur in the non-pending part. 00783 while (k1 < first_pending && k2 < num_rows) { 00784 const int cmp = compare(x[k1], x[k2]); 00785 if (cmp == 0) { 00786 // We found the same row. 00787 ++num_duplicates; 00788 --num_rows; 00789 // By initial sortedness, we can increment index `k1'. 00790 ++k1; 00791 // Do not increment `k2'; instead, swap there the next pending row. 00792 if (k2 < num_rows) 00793 std::swap(x[k2], x[k2 + num_duplicates]); 00794 } 00795 else if (cmp < 0) 00796 // By initial sortedness, we can increment `k1'. 00797 ++k1; 00798 else { 00799 // Here `cmp > 0'. 00800 // Increment `k2' and, if we already found any duplicate, 00801 // swap the next pending row in position `k2'. 00802 ++k2; 00803 if (num_duplicates > 0 && k2 < num_rows) 00804 std::swap(x[k2], x[k2 + num_duplicates]); 00805 } 00806 } 00807 // If needed, swap any duplicates found past the pending rows 00808 // that has not been considered yet; then erase the duplicates. 00809 if (num_duplicates > 0) { 00810 if (k2 < num_rows) 00811 for (++k2; k2 < num_rows; ++k2) 00812 std::swap(x[k2], x[k2 + num_duplicates]); 00813 x.erase_to_end(num_rows); 00814 } 00815 // Do not check for strong normalization, 00816 // because no modification of rows has occurred. 00817 assert(OK(false)); 00818 }
void Parma_Polyhedra_Library::Linear_System::sort_and_remove_with_sat | ( | Saturation_Matrix & | sat | ) |
Sorts the system, removing duplicates, keeping the saturation matrix consistent.
sat | Saturation matrix with rows corresponding to the rows of *this . |
Definition at line 501 of file Linear_System.cc.
References check_sorted(), Parma_Polyhedra_Library::Matrix::erase_to_end(), first_pending_row(), num_pending_rows(), Parma_Polyhedra_Library::Matrix::num_rows(), Parma_Polyhedra_Library::Saturation_Matrix::num_rows(), Parma_Polyhedra_Library::Saturation_Matrix::rows, Parma_Polyhedra_Library::Matrix::rows, Parma_Polyhedra_Library::Saturation_Matrix::rows_erase_to_end(), set_index_first_pending_row(), and set_sorted().
Referenced by Parma_Polyhedra_Library::Polyhedron::obtain_sorted_constraints(), Parma_Polyhedra_Library::Polyhedron::obtain_sorted_constraints_with_sat_c(), Parma_Polyhedra_Library::Polyhedron::obtain_sorted_generators(), and Parma_Polyhedra_Library::Polyhedron::obtain_sorted_generators_with_sat_g().
00501 { 00502 Linear_System& sys = *this; 00503 // We can only sort the non-pending part of the system. 00504 assert(sys.first_pending_row() == sat.num_rows()); 00505 if (sys.first_pending_row() <= 1) { 00506 sys.set_sorted(true); 00507 return; 00508 } 00509 00510 // First, sort `sys' (keeping `sat' consistent) without removing duplicates. 00511 With_Saturation_Matrix_iterator first(sys.rows.begin(), sat.rows.begin()); 00512 With_Saturation_Matrix_iterator last = first + sat.num_rows(); 00513 swapping_sort(first, last, Row_Less_Than()); 00514 // Second, move duplicates in `sys' to the end (keeping `sat' consistent). 00515 With_Saturation_Matrix_iterator new_last = swapping_unique(first, last); 00516 00517 const dimension_type num_duplicates = last - new_last; 00518 const dimension_type new_first_pending_row 00519 = sys.first_pending_row() - num_duplicates; 00520 00521 if (sys.num_pending_rows() > 0) { 00522 // In this case, we must put the duplicates after the pending rows. 00523 const dimension_type n_rows = sys.num_rows() - 1; 00524 for (dimension_type i = 0; i < num_duplicates; ++i) 00525 std::swap(sys[new_first_pending_row + i], sys[n_rows - i]); 00526 } 00527 // Erasing the duplicated rows... 00528 sys.erase_to_end(sys.num_rows() - num_duplicates); 00529 sys.set_index_first_pending_row(new_first_pending_row); 00530 // ... and the corresponding rows of the saturation matrix. 00531 sat.rows_erase_to_end(sat.num_rows() - num_duplicates); 00532 assert(sys.check_sorted()); 00533 // Now the system is sorted. 00534 sys.set_sorted(true); 00535 }
PPL::dimension_type Parma_Polyhedra_Library::Linear_System::gauss | ( | dimension_type | n_lines_or_equalities | ) |
Minimizes the subsystem of equations contained in *this
.
This method works only on the equalities of the system: the system is required to be partially sorted, so that all the equalities are grouped at its top; it is assumed that the number of equalities is exactly n_lines_or_equalities
. The method finds a minimal system for the equalities and returns its rank, i.e., the number of linearly independent equalities. The result is an upper triangular subsystem of equalities: for each equality, the pivot is chosen starting from the right-most columns.
Definition at line 538 of file Linear_System.cc.
References Parma_Polyhedra_Library::Matrix::num_columns(), num_lines_or_equalities(), num_pending_rows(), OK(), and set_sorted().
Referenced by Parma_Polyhedra_Library::Polyhedron::simplify(), and simplify().
00538 { 00539 Linear_System& x = *this; 00540 // This method is only applied to a well-formed linear system 00541 // having no pending rows and exactly `n_lines_or_equalities' 00542 // lines or equalities, all of which occur before the rays or points 00543 // or inequalities. 00544 assert(x.OK(true)); 00545 assert(x.num_pending_rows() == 0); 00546 assert(n_lines_or_equalities == x.num_lines_or_equalities()); 00547 #ifndef NDEBUG 00548 for (dimension_type i = n_lines_or_equalities; i-- > 0; ) 00549 assert(x[i].is_line_or_equality()); 00550 #endif 00551 00552 dimension_type rank = 0; 00553 // Will keep track of the variations on the system of equalities. 00554 bool changed = false; 00555 for (dimension_type j = x.num_columns(); j-- > 0; ) 00556 for (dimension_type i = rank; i < n_lines_or_equalities; ++i) { 00557 // Search for the first row having a non-zero coefficient 00558 // (the pivot) in the j-th column. 00559 if (x[i][j] == 0) 00560 continue; 00561 // Pivot found: if needed, swap rows so that this one becomes 00562 // the rank-th row in the linear system. 00563 if (i > rank) { 00564 std::swap(x[i], x[rank]); 00565 // After swapping the system is no longer sorted. 00566 changed = true; 00567 } 00568 // Combine the row containing the pivot with all the lines or 00569 // equalities following it, so that all the elements on the j-th 00570 // column in these rows become 0. 00571 for (dimension_type k = i + 1; k < n_lines_or_equalities; ++k) 00572 if (x[k][j] != 0) { 00573 x[k].linear_combine(x[rank], j); 00574 changed = true; 00575 } 00576 // Already dealt with the rank-th row. 00577 ++rank; 00578 // Consider another column index `j'. 00579 break; 00580 } 00581 if (changed) 00582 x.set_sorted(false); 00583 // A well-formed system is returned. 00584 assert(x.OK(true)); 00585 return rank; 00586 }
void Parma_Polyhedra_Library::Linear_System::back_substitute | ( | dimension_type | n_lines_or_equalities | ) |
Back-substitutes the coefficients to reduce the complexity of the system.
Takes an upper triangular system having n_lines_or_equalities
rows. For each row, starting from the one having the minimum number of coefficients different from zero, computes the expression of an element as a function of the remaining ones and then substitutes this expression in all the other rows.
Definition at line 590 of file Linear_System.cc.
References is_sorted(), Parma_Polyhedra_Library::Linear_Row::linear_combine(), Parma_Polyhedra_Library::neg_assign(), Parma_Polyhedra_Library::Matrix::num_columns(), num_lines_or_equalities(), num_pending_rows(), Parma_Polyhedra_Library::Matrix::num_rows(), OK(), and set_sorted().
Referenced by Parma_Polyhedra_Library::Polyhedron::simplify(), and simplify().
00590 { 00591 Linear_System& x = *this; 00592 // This method is only applied to a well-formed system 00593 // having no pending rows and exactly `n_lines_or_equalities' 00594 // lines or equalities, all of which occur before the first ray 00595 // or point or inequality. 00596 assert(x.OK(true)); 00597 assert(x.num_pending_rows() == 0); 00598 assert(n_lines_or_equalities <= x.num_lines_or_equalities()); 00599 #ifndef NDEBUG 00600 for (dimension_type i = n_lines_or_equalities; i-- > 0; ) 00601 assert(x[i].is_line_or_equality()); 00602 #endif 00603 00604 const dimension_type nrows = x.num_rows(); 00605 const dimension_type ncols = x.num_columns(); 00606 // Trying to keep sortedness. 00607 bool still_sorted = x.is_sorted(); 00608 // This deque of booleans will be used to flag those rows that, 00609 // before exiting, need to be re-checked for sortedness. 00610 std::deque<bool> check_for_sortedness; 00611 if (still_sorted) 00612 check_for_sortedness.insert(check_for_sortedness.end(), nrows, false); 00613 00614 for (dimension_type k = n_lines_or_equalities; k-- > 0; ) { 00615 // For each line or equality, starting from the last one, 00616 // looks for the last non-zero element. 00617 // `j' will be the index of such a element. 00618 Linear_Row& x_k = x[k]; 00619 dimension_type j = ncols - 1; 00620 while (j != 0 && x_k[j] == 0) 00621 --j; 00622 00623 // Go through the equalities above `x_k'. 00624 for (dimension_type i = k; i-- > 0; ) { 00625 Linear_Row& x_i = x[i]; 00626 if (x_i[j] != 0) { 00627 // Combine linearly `x_i' with `x_k' 00628 // so that `x_i[j]' becomes zero. 00629 x_i.linear_combine(x_k, j); 00630 if (still_sorted) { 00631 // Trying to keep sortedness: remember which rows 00632 // have to be re-checked for sortedness at the end. 00633 if (i > 0) 00634 check_for_sortedness[i-1] = true; 00635 check_for_sortedness[i] = true; 00636 } 00637 } 00638 } 00639 00640 // Due to strong normalization during previous iterations, 00641 // the pivot coefficient `x_k[j]' may now be negative. 00642 // Since an inequality (or ray or point) cannot be multiplied 00643 // by a negative factor, the coefficient of the pivot must be 00644 // forced to be positive. 00645 const bool have_to_negate = (x_k[j] < 0); 00646 if (have_to_negate) 00647 for (dimension_type h = ncols; h-- > 0; ) 00648 PPL::neg_assign(x_k[h]); 00649 // Note: we do not mark index `k' in `check_for_sortedness', 00650 // because we will later negate back the row. 00651 00652 // Go through all the other rows of the system. 00653 for (dimension_type i = n_lines_or_equalities; i < nrows; ++i) { 00654 Linear_Row& x_i = x[i]; 00655 if (x_i[j] != 0) { 00656 // Combine linearly the `x_i' with `x_k' 00657 // so that `x_i[j]' becomes zero. 00658 x_i.linear_combine(x_k, j); 00659 if (still_sorted) { 00660 // Trying to keep sortedness: remember which rows 00661 // have to be re-checked for sortedness at the end. 00662 if (i > n_lines_or_equalities) 00663 check_for_sortedness[i-1] = true; 00664 check_for_sortedness[i] = true; 00665 } 00666 } 00667 } 00668 if (have_to_negate) 00669 // Negate `x_k' to restore strong-normalization. 00670 for (dimension_type h = ncols; h-- > 0; ) 00671 PPL::neg_assign(x_k[h]); 00672 } 00673 00674 // Trying to keep sortedness. 00675 for (dimension_type i = 0; still_sorted && i < nrows-1; ++i) 00676 if (check_for_sortedness[i]) 00677 // Have to check sortedness of `x[i]' with respect to `x[i+1]'. 00678 still_sorted = (compare(x[i], x[i+1]) <= 0); 00679 // Set the sortedness flag. 00680 x.set_sorted(still_sorted); 00681 00682 // A well-formed system is returned. 00683 assert(x.OK(true)); 00684 }
void Parma_Polyhedra_Library::Linear_System::simplify | ( | ) |
Applies Gaussian's elimination and back-substitution so as to simplify the linear system.
Reimplemented in Parma_Polyhedra_Library::Constraint_System, and Parma_Polyhedra_Library::Generator_System.
Definition at line 687 of file Linear_System.cc.
References back_substitute(), Parma_Polyhedra_Library::Matrix::erase_to_end(), gauss(), num_pending_rows(), Parma_Polyhedra_Library::Matrix::num_rows(), OK(), set_sorted(), sorted, and unset_pending_rows().
Referenced by Parma_Polyhedra_Library::Generator_System::simplify(), and Parma_Polyhedra_Library::Constraint_System::simplify().
00687 { 00688 Linear_System& x = *this; 00689 // This method is only applied to a well-formed system 00690 // having no pending rows. 00691 assert(x.OK(true)); 00692 assert(x.num_pending_rows() == 0); 00693 00694 // Partially sort the linear system so that all lines/equalities come first. 00695 dimension_type nrows = x.num_rows(); 00696 dimension_type n_lines_or_equalities = 0; 00697 for (dimension_type i = 0; i < nrows; ++i) 00698 if (x[i].is_line_or_equality()) { 00699 if (n_lines_or_equalities < i) { 00700 std::swap(x[i], x[n_lines_or_equalities]); 00701 // The system was not sorted. 00702 assert(!x.sorted); 00703 } 00704 ++n_lines_or_equalities; 00705 } 00706 // Apply Gaussian's elimination to the subsystem of lines/equalities. 00707 const dimension_type rank = x.gauss(n_lines_or_equalities); 00708 // Eliminate any redundant line/equality that has been detected. 00709 if (rank < n_lines_or_equalities) { 00710 const dimension_type 00711 n_rays_or_points_or_inequalities = nrows - n_lines_or_equalities; 00712 const dimension_type 00713 num_swaps = std::min(n_lines_or_equalities - rank, 00714 n_rays_or_points_or_inequalities); 00715 for (dimension_type i = num_swaps; i-- > 0; ) 00716 std::swap(x[--nrows], x[rank + i]); 00717 x.erase_to_end(nrows); 00718 x.unset_pending_rows(); 00719 if (n_rays_or_points_or_inequalities > num_swaps) 00720 x.set_sorted(false); 00721 n_lines_or_equalities = rank; 00722 } 00723 // Apply back-substitution to the system of rays/points/inequalities. 00724 x.back_substitute(n_lines_or_equalities); 00725 // A well-formed system is returned. 00726 assert(x.OK(true)); 00727 }
void Parma_Polyhedra_Library::Linear_System::normalize | ( | ) |
Normalizes the system by dividing each row for the GCD of the row's elements.
Definition at line 454 of file Linear_System.cc.
References Parma_Polyhedra_Library::Matrix::num_rows(), and set_sorted().
Referenced by Parma_Polyhedra_Library::Generator_System::adjust_topology_and_space_dimension().
00454 { 00455 Linear_System& x = *this; 00456 // We normalize also the pending rows. 00457 for (dimension_type i = num_rows(); i-- > 0; ) 00458 x[i].normalize(); 00459 set_sorted(false); 00460 }
void Parma_Polyhedra_Library::Linear_System::clear | ( | ) | [inline] |
Clears the system deallocating all its rows.
Reimplemented from Parma_Polyhedra_Library::Matrix.
Reimplemented in Parma_Polyhedra_Library::Constraint_System, Parma_Polyhedra_Library::Generator_System, and Parma_Polyhedra_Library::Grid_Generator_System.
Definition at line 139 of file Linear_System.inlines.hh.
References Parma_Polyhedra_Library::Matrix::clear(), index_first_pending, and sorted.
Referenced by Parma_Polyhedra_Library::Generator_System::clear(), and Parma_Polyhedra_Library::Constraint_System::clear().
00139 { 00140 // Note: do NOT modify the value of `row_topology'. 00141 Matrix::clear(); 00142 index_first_pending = 0; 00143 sorted = true; 00144 }
void Parma_Polyhedra_Library::Linear_System::ascii_dump | ( | ) | const |
Writes to std::cerr
an ASCII representation of *this
.
Reimplemented from Parma_Polyhedra_Library::Matrix.
Reimplemented in Parma_Polyhedra_Library::Constraint_System, Parma_Polyhedra_Library::Generator_System, and Parma_Polyhedra_Library::Grid_Generator_System.
Referenced by ascii_dump().
void Parma_Polyhedra_Library::Linear_System::ascii_dump | ( | std::ostream & | s | ) | const |
Writes to s
an ASCII representation of *this
.
Reimplemented from Parma_Polyhedra_Library::Matrix.
Reimplemented in Parma_Polyhedra_Library::Constraint_System, Parma_Polyhedra_Library::Generator_System, and Parma_Polyhedra_Library::Grid_Generator_System.
Definition at line 113 of file Linear_System.cc.
References ascii_dump(), first_pending_row(), is_necessarily_closed(), Parma_Polyhedra_Library::Matrix::num_columns(), Parma_Polyhedra_Library::Matrix::num_rows(), and sorted.
00113 { 00114 // Prints the topology, the number of rows, the number of columns 00115 // and the sorted flag. The specialized methods provided by 00116 // Constraint_System and Generator_System take care of properly 00117 // printing the contents of the system. 00118 const Linear_System& x = *this; 00119 dimension_type x_num_rows = x.num_rows(); 00120 dimension_type x_num_columns = x.num_columns(); 00121 s << "topology " << (is_necessarily_closed() 00122 ? "NECESSARILY_CLOSED" 00123 : "NOT_NECESSARILY_CLOSED") 00124 << "\n" 00125 << x_num_rows << " x " << x_num_columns 00126 << (x.sorted ? "(sorted)" : "(not_sorted)") 00127 << "\n" 00128 << "index_first_pending " << x.first_pending_row() 00129 << "\n"; 00130 for (dimension_type i = 0; i < x_num_rows; ++i) 00131 x[i].ascii_dump(s); 00132 }
void Parma_Polyhedra_Library::Linear_System::print | ( | ) | const |
Prints *this
to std::cerr
using operator<<
.
Reimplemented from Parma_Polyhedra_Library::Matrix.
Reimplemented in Parma_Polyhedra_Library::Constraint_System, Parma_Polyhedra_Library::Generator_System, and Parma_Polyhedra_Library::Grid_Generator_System.
bool Parma_Polyhedra_Library::Linear_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.
Reads into a Linear_System object the information produced by the output of ascii_dump()
. The specialized methods provided by Constraint_System and Generator_System take care of properly reading the contents of the system.
Reimplemented from Parma_Polyhedra_Library::Matrix.
Reimplemented in Parma_Polyhedra_Library::Constraint_System, Parma_Polyhedra_Library::Generator_System, and Parma_Polyhedra_Library::Grid_Generator_System.
Definition at line 137 of file Linear_System.cc.
References Parma_Polyhedra_Library::Matrix::OK(), resize_no_copy(), set_index_first_pending_row(), set_necessarily_closed(), set_not_necessarily_closed(), and set_sorted().
00137 { 00138 std::string str; 00139 if (!(s >> str) || str != "topology") 00140 return false; 00141 if (!(s >> str)) 00142 return false; 00143 if (str == "NECESSARILY_CLOSED") 00144 set_necessarily_closed(); 00145 else { 00146 if (str != "NOT_NECESSARILY_CLOSED") 00147 return false; 00148 set_not_necessarily_closed(); 00149 } 00150 00151 dimension_type nrows; 00152 dimension_type ncols; 00153 if (!(s >> nrows)) 00154 return false; 00155 if (!(s >> str)) 00156 return false; 00157 if (!(s >> ncols)) 00158 return false; 00159 resize_no_copy(nrows, ncols); 00160 00161 if (!(s >> str) || (str != "(sorted)" && str != "(not_sorted)")) 00162 return false; 00163 set_sorted(str == "(sorted)"); 00164 dimension_type index; 00165 if (!(s >> str) || str != "index_first_pending") 00166 return false; 00167 if (!(s >> index)) 00168 return false; 00169 set_index_first_pending_row(index); 00170 00171 Linear_System& x = *this; 00172 for (dimension_type row = 0; row < nrows; ++row) 00173 if (!x[row].ascii_load(s)) 00174 return false; 00175 00176 // Check for well-formedness. 00177 assert(OK(true)); 00178 return true; 00179 }
memory_size_type Parma_Polyhedra_Library::Linear_System::total_memory_in_bytes | ( | ) | const [inline] |
Returns the total size in bytes of the memory occupied by *this
.
Reimplemented from Parma_Polyhedra_Library::Matrix.
Reimplemented in Parma_Polyhedra_Library::Constraint_System, Parma_Polyhedra_Library::Generator_System, and Parma_Polyhedra_Library::Grid_Generator_System.
Definition at line 36 of file Linear_System.inlines.hh.
References external_memory_in_bytes().
00036 { 00037 return sizeof(*this) + external_memory_in_bytes(); 00038 }
memory_size_type Parma_Polyhedra_Library::Linear_System::external_memory_in_bytes | ( | ) | const [inline] |
Returns the size in bytes of the memory managed by *this
.
Reimplemented from Parma_Polyhedra_Library::Matrix.
Reimplemented in Parma_Polyhedra_Library::Constraint_System, Parma_Polyhedra_Library::Generator_System, and Parma_Polyhedra_Library::Grid_Generator_System.
Definition at line 31 of file Linear_System.inlines.hh.
References Parma_Polyhedra_Library::Checked::external_memory_in_bytes().
Referenced by total_memory_in_bytes().
00031 { 00032 return Matrix::external_memory_in_bytes(); 00033 }
bool Parma_Polyhedra_Library::Linear_System::OK | ( | bool | check_strong_normalized = true |
) | const |
Checks if all the invariants are satisfied.
check_strong_normalized | true if and only if the strong normalization of all the rows in the system has to be checked. |
Definition at line 830 of file Linear_System.cc.
References check_sorted(), first_pending_row(), is_necessarily_closed(), Parma_Polyhedra_Library::Matrix::num_columns(), Parma_Polyhedra_Library::Matrix::num_rows(), Parma_Polyhedra_Library::Matrix::OK(), Parma_Polyhedra_Library::Matrix::row_capacity, Parma_Polyhedra_Library::Matrix::row_size, sorted, strong_normalize(), and topology().
Referenced by back_substitute(), gauss(), Parma_Polyhedra_Library::Polyhedron::simplify(), and simplify().
00830 { 00831 #ifndef NDEBUG 00832 using std::endl; 00833 using std::cerr; 00834 #endif 00835 00836 // `index_first_pending' must be less than or equal to `num_rows()'. 00837 if (first_pending_row() > num_rows()) { 00838 #ifndef NDEBUG 00839 cerr << "Linear_System has a negative number of pending rows!" 00840 << endl; 00841 #endif 00842 return false; 00843 } 00844 00845 // An empty system is OK, 00846 // unless it is an NNC system with exactly one column. 00847 if (num_rows() == 0) 00848 if (is_necessarily_closed() || num_columns() != 1) 00849 return true; 00850 else { 00851 #ifndef NDEBUG 00852 cerr << "NNC Linear_System has one column" << endl; 00853 #endif 00854 return false; 00855 } 00856 00857 // A non-empty system will contain constraints or generators; in 00858 // both cases it must have at least one column for the inhomogeneous 00859 // term and, if it is NNC, another one for the epsilon coefficient. 00860 const dimension_type min_cols = is_necessarily_closed() ? 1 : 2; 00861 if (num_columns() < min_cols) { 00862 #ifndef NDEBUG 00863 cerr << "Linear_System has fewer columns than the minimum " 00864 << "allowed by its topology:" 00865 << endl 00866 << "num_columns is " << num_columns() 00867 << ", minimum is " << min_cols 00868 << endl; 00869 #endif 00870 return false; 00871 } 00872 00873 const Linear_System& x = *this; 00874 const dimension_type n_rows = num_rows(); 00875 for (dimension_type i = 0; i < n_rows; ++i) { 00876 if (!x[i].OK(row_size, row_capacity)) 00877 return false; 00878 // Checking for topology mismatches. 00879 if (x.topology() != x[i].topology()) { 00880 #ifndef NDEBUG 00881 cerr << "Topology mismatch between the system " 00882 << "and one of its rows!" 00883 << endl; 00884 #endif 00885 return false; 00886 } 00887 } 00888 00889 if (check_strong_normalized) { 00890 // Check for strong normalization of rows. 00891 // Note: normalization cannot be checked inside the 00892 // Linear_Row::OK() method, because a Linear_Row object may also 00893 // implement a Linear_Expression object, which in general cannot 00894 // be (strongly) normalized. 00895 Linear_System tmp(x, With_Pending()); 00896 tmp.strong_normalize(); 00897 if (x != tmp) { 00898 #ifndef NDEBUG 00899 cerr << "Linear_System rows are not strongly normalized!" 00900 << endl; 00901 #endif 00902 return false; 00903 } 00904 } 00905 00906 if (sorted && !check_sorted()) { 00907 #ifndef NDEBUG 00908 cerr << "The system declares itself to be sorted but it is not!" 00909 << endl; 00910 #endif 00911 return false; 00912 } 00913 00914 // All checks passed. 00915 return true; 00916 }
void swap | ( | Parma_Polyhedra_Library::Linear_System & | x, | |
Parma_Polyhedra_Library::Linear_System & | y | |||
) | [related] |
Specializes std::swap
.
Definition at line 242 of file Linear_System.inlines.hh.
References swap().
00243 { 00244 x.swap(y); 00245 }
bool operator== | ( | const Linear_System & | x, | |
const Linear_System & | y | |||
) | [related] |
Returns true
if and only if x
and y
are identical.
Definition at line 482 of file Linear_System.cc.
References first_pending_row(), Parma_Polyhedra_Library::Matrix::num_columns(), and Parma_Polyhedra_Library::Matrix::num_rows().
00482 { 00483 if (x.num_columns() != y.num_columns()) 00484 return false; 00485 const dimension_type x_num_rows = x.num_rows(); 00486 const dimension_type y_num_rows = y.num_rows(); 00487 if (x_num_rows != y_num_rows) 00488 return false; 00489 if (x.first_pending_row() != y.first_pending_row()) 00490 return false; 00491 // Notice that calling operator==(const Matrix&, const Matrix&) 00492 // would be wrong here, as equality of the type fields would 00493 // not be checked. 00494 for (dimension_type i = x_num_rows; i-- > 0; ) 00495 if (x[i] != y[i]) 00496 return false; 00497 return true; 00498 }
bool operator!= | ( | const Linear_System & | x, | |
const Linear_System & | y | |||
) | [related] |
Returns true
if and only if x
and y
are different.
Definition at line 226 of file Linear_System.inlines.hh.
The topological kind of the rows in the system.
Definition at line 380 of file Linear_System.defs.hh.
Referenced by add_pending_rows(), add_rows_and_columns(), assign_with_pending(), is_necessarily_closed(), operator=(), resize_no_copy(), set_necessarily_closed(), set_not_necessarily_closed(), swap(), and topology().
The index of the first pending row.
Definition at line 383 of file Linear_System.defs.hh.
Referenced by assign_with_pending(), clear(), first_pending_row(), set_index_first_pending_row(), swap(), and unset_pending_rows().
bool Parma_Polyhedra_Library::Linear_System::sorted [private] |
true
if rows are sorted in the ascending order as defined by bool compare(const Linear_Row&, const Linear_Row&)
. If false
may not be sorted.
Definition at line 390 of file Linear_System.defs.hh.
Referenced by add_pending_rows(), ascii_dump(), assign_with_pending(), clear(), is_sorted(), Linear_System(), OK(), operator=(), set_sorted(), simplify(), sort_rows(), and swap().