Polyhedron_public.cc File Reference

#include <ppl-config.h>
#include "Polyhedron.defs.hh"
#include "Scalar_Products.defs.hh"
#include "MIP_Problem.defs.hh"
#include <cstdlib>
#include <cassert>
#include <iostream>

Include dependency graph for Polyhedron_public.cc:

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 Documentation

#define ENSURE_SORTEDNESS   0

Definition at line 32 of file Polyhedron_public.cc.


Function Documentation

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 }


Variable Documentation

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.


Generated on Sat Oct 11 10:40:42 2008 for PPL by  doxygen 1.5.6