#include <ppl-config.h>
#include "Polyhedron.defs.hh"
#include "Scalar_Products.defs.hh"
#include "MIP_Problem.defs.hh"
#include <cstdlib>
#include <cassert>
#include <iostream>
Go to the source code of this file.
Defines | |
#define | ENSURE_SORTEDNESS 0 |
Functions | |
bool | add_to_system_and_check_independence (PPL::Linear_System &eq_sys, const PPL::Linear_Row &eq) |
void | drop_redundant_inequalities (std::vector< const PPL::Constraint * > &p_ineqs, const PPL::Topology topology, const PPL::Bit_Matrix &sat, const PPL::dimension_type rank) |
#define ENSURE_SORTEDNESS 0 |
Definition at line 32 of file Polyhedron_public.cc.
bool @125::add_to_system_and_check_independence | ( | PPL::Linear_System & | eq_sys, | |
const PPL::Linear_Row & | eq | |||
) | [static] |
Definition at line 2141 of file Polyhedron_public.cc.
References Parma_Polyhedra_Library::Matrix::erase_to_end(), Parma_Polyhedra_Library::Linear_System::gauss(), Parma_Polyhedra_Library::Linear_System::insert(), Parma_Polyhedra_Library::Linear_Row::is_line_or_equality(), and Parma_Polyhedra_Library::Matrix::num_rows().
Referenced by Parma_Polyhedra_Library::Polyhedron::simplify_using_context_assign().
02142 { 02143 // Check if equality eqn is linear independent from eq_sys. 02144 assert(eq.is_line_or_equality()); 02145 eq_sys.insert(eq); 02146 const PPL::dimension_type eq_sys_num_rows = eq_sys.num_rows(); 02147 const PPL::dimension_type rank = eq_sys.gauss(eq_sys_num_rows); 02148 if (rank == eq_sys_num_rows) 02149 // eq is linear independent. 02150 return true; 02151 else { 02152 // eq is not linear independent. 02153 assert(rank == eq_sys_num_rows - 1); 02154 eq_sys.erase_to_end(rank); 02155 return false; 02156 } 02157 }
void @125::drop_redundant_inequalities | ( | std::vector< const PPL::Constraint * > & | p_ineqs, | |
const PPL::Topology | topology, | |||
const PPL::Bit_Matrix & | sat, | |||
const PPL::dimension_type | rank | |||
) | [static] |
Definition at line 2167 of file Polyhedron_public.cc.
References empty, Parma_Polyhedra_Library::NECESSARILY_CLOSED, Parma_Polyhedra_Library::Bit_Matrix::num_columns(), and Parma_Polyhedra_Library::Polyhedron::space_dim.
Referenced by Parma_Polyhedra_Library::Polyhedron::simplify_using_context_assign().
02170 { 02171 using namespace Parma_Polyhedra_Library; 02172 const dimension_type num_rows = p_ineqs.size(); 02173 assert(num_rows > 0); 02174 // `rank' is the rank of the (implicit) system of equalities. 02175 const dimension_type space_dim = p_ineqs[0]->space_dimension(); 02176 assert(space_dim > 0 && space_dim >= rank); 02177 const dimension_type num_coefficients 02178 = space_dim + (topology == NECESSARILY_CLOSED ? 0 : 1); 02179 const dimension_type min_sat = num_coefficients - rank; 02180 const dimension_type num_cols_sat = sat.num_columns(); 02181 02182 // Perform quick redundancy test based on the number of saturators. 02183 for (dimension_type i = num_rows; i-- > 0; ) { 02184 if (sat[i].empty()) 02185 // Masked equalities are redundant. 02186 p_ineqs[i] = 0; 02187 else { 02188 const dimension_type num_sat = num_cols_sat - sat[i].count_ones(); 02189 if (num_sat < min_sat) 02190 p_ineqs[i] = 0; 02191 } 02192 } 02193 02194 // Re-examine remaining inequalities. 02195 // Iteration index `i' is _intentionally_ increasing. 02196 for (dimension_type i = 0; i < num_rows; ++i) { 02197 if (p_ineqs[i]) { 02198 for (dimension_type j = 0; j < num_rows; ++j) { 02199 bool strict_subset; 02200 if (p_ineqs[j] && i != j 02201 && subset_or_equal(sat[j], sat[i], strict_subset)) { 02202 if (strict_subset) { 02203 p_ineqs[i] = 0; 02204 break; 02205 } 02206 else 02207 // Here `sat[j] == sat[i]'. 02208 p_ineqs[j] = 0; 02209 } 02210 } 02211 } 02212 } 02213 }
PPL::dimension_type constraint_index |
Definition at line 2129 of file Polyhedron_public.cc.
PPL::dimension_type num_ruled_out |
Definition at line 2130 of file Polyhedron_public.cc.