00001 /* H79_Certificate class implementation 00002 (non-inline member functions). 00003 Copyright (C) 2001-2008 Roberto Bagnara <bagnara@cs.unipr.it> 00004 00005 This file is part of the Parma Polyhedra Library (PPL). 00006 00007 The PPL is free software; you can redistribute it and/or modify it 00008 under the terms of the GNU General Public License as published by the 00009 Free Software Foundation; either version 3 of the License, or (at your 00010 option) any later version. 00011 00012 The PPL is distributed in the hope that it will be useful, but WITHOUT 00013 ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or 00014 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License 00015 for more details. 00016 00017 You should have received a copy of the GNU General Public License 00018 along with this program; if not, write to the Free Software Foundation, 00019 Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02111-1307, USA. 00020 00021 For the most up-to-date information see the Parma Polyhedra Library 00022 site: http://www.cs.unipr.it/ppl/ . */ 00023 00024 #include <ppl-config.h> 00025 00026 #include "H79_Certificate.defs.hh" 00027 00028 #include "Polyhedron.defs.hh" 00029 #include <cassert> 00030 #include <iostream> 00031 00032 namespace PPL = Parma_Polyhedra_Library; 00033 00034 PPL::H79_Certificate::H79_Certificate(const Polyhedron& ph) 00035 : affine_dim(0), num_constraints(0) { 00036 // The affine dimension of the polyhedron is obtained by subtracting 00037 // the number of equalities from the space dimension. 00038 // When counting constraints, for a correct reasoning, we have 00039 // to disregard the low-level constraints (i.e., the positivity 00040 // constraint and epsilon bounds). 00041 const dimension_type space_dim = ph.space_dimension(); 00042 affine_dim = space_dim; 00043 const Constraint_System& cs = ph.minimized_constraints(); 00044 // It is assumed that `ph' is not an empty polyhedron. 00045 assert(!ph.marked_empty()); 00046 for (Constraint_System::const_iterator i = cs.begin(), 00047 cs_end = cs.end(); i != cs_end; ++i) { 00048 ++num_constraints; 00049 if (i->is_equality()) 00050 --affine_dim; 00051 } 00052 00053 // TODO: this is an inefficient workaround. 00054 // For NNC polyhedra, generators might be no longer up-to-date 00055 // (and hence, neither minimized) due to the strong minimization 00056 // process applied to constraints when constructing the certificate. 00057 // We have to reinforce the (normal) minimization of the generator 00058 // system. The future, lazy implementation of the strong minimization 00059 // process will solve this problem. 00060 if (!ph.is_necessarily_closed()) 00061 ph.minimize(); 00062 } 00063 00064 int 00065 PPL::H79_Certificate::compare(const H79_Certificate& y) const { 00066 if (affine_dim != y.affine_dim) 00067 return affine_dim > y.affine_dim ? 1 : -1; 00068 if (num_constraints != y.num_constraints) 00069 return num_constraints > y.num_constraints ? 1 : -1; 00070 // All components are equal. 00071 return 0; 00072 } 00073 00074 int 00075 PPL::H79_Certificate::compare(const Polyhedron& ph) const { 00076 // The affine dimension of the polyhedron is obtained by subtracting 00077 // the number of equalities from the space dimension. 00078 // When counting constraints, for a correct reasoning, we have 00079 // to disregard the low-level constraints (i.e., the positivity 00080 // constraint and epsilon bounds). 00081 const dimension_type space_dim = ph.space_dimension(); 00082 dimension_type ph_affine_dim = space_dim; 00083 dimension_type ph_num_constraints = 0; 00084 const Constraint_System& cs = ph.minimized_constraints(); 00085 // It is assumed that `ph' is a polyhedron containing the 00086 // polyhedron described by `*this': hence, it cannot be empty. 00087 assert(!ph.marked_empty()); 00088 for (Constraint_System::const_iterator i = cs.begin(), 00089 cs_end = cs.end(); i != cs_end; ++i) { 00090 ++ph_num_constraints; 00091 if (i->is_equality()) 00092 --ph_affine_dim; 00093 } 00094 // TODO: this is an inefficient workaround. 00095 // For NNC polyhedra, generators might be no longer up-to-date 00096 // (and hence, neither minimized) due to the strong minimization 00097 // process applied to constraints when constructing the certificate. 00098 // We have to reinforce the (normal) minimization of the generator 00099 // system. The future, lazy implementation of the strong minimization 00100 // process will solve this problem. 00101 if (!ph.is_necessarily_closed()) 00102 ph.minimize(); 00103 00104 // If the affine dimension of `ph' is increasing, the chain is stabilizing. 00105 if (ph_affine_dim > affine_dim) 00106 return 1; 00107 00108 // At this point the two polyhedra must have the same affine dimension. 00109 assert(ph_affine_dim == affine_dim); 00110 00111 // If the number of constraints of `ph' is decreasing, then the chain 00112 // is stabilizing. If it is increasing, the chain is not stabilizing. 00113 if (ph_num_constraints != num_constraints) 00114 return ph_num_constraints < num_constraints ? 1 : -1; 00115 00116 // All components are equal. 00117 return 0; 00118 } 00119