Parma Polyhedra Library NEWS -- history of user-visible changes
===============================================================
--------------------------------------------------------------------------
NEWS for version 0.6.1 (released on August 20, 2004)
--------------------------------------------------------------------------
New and Changed Features
========================
o Some packaging issues have been fixed.
o The documentation has been completed and improved.
o The methods
Polyhedra_PowerSet::semantically_contains(const Polyhedra_PowerSet&) and
Polyhedra_PowerSet::semantically_equals(const Polyhedra_PowerSet&)
have been renamed
Polyhedra_PowerSet::geometrically_covers(const Polyhedra_PowerSet&) and
Polyhedra_PowerSet::geometrically_equals(const Polyhedra_PowerSet& y),
respectively.
--------------------------------------------------------------------------
NEWS for version 0.6 (released on August 18, 2004)
--------------------------------------------------------------------------
New and Changed Features
========================
o New templatic classes Determinate, PowerSet, and Polyhedra_PowerSet.
The first two classes realize, in a completely generic way, the
determinate and powerset constructions described by Roberto Bagnara
in his 1998, Science of Computer Programming paper. The third class
is a specialization of the powerset construction on polyhedra.
The powerset construction comes with the generic widening technique
proposed by Roberto Bagnara, Patricia Hill and Enea Zaffanella
in their VMCAI 2004 paper. Actually, the Polyhedra_PowerSet class
provides the first genuine, non-trivial widening ever proposed
(let alone made available) on a domain of sets of convex polyhedra.
o New methods
void Polyhedron::expand_dimension(Variable, dimension_type) and
void Polyhedron::fold_dimensions(const Variables_Set&, Variable)
allow the easy realization of summary dimensions as proposed
by Denis Gopan and colleagues in their TACAS 2004 paper.
o A new `demos' directory has been added. In the `ppl_lcdd'
subdirectory, this contains a sort of clone of the cddlib test
program `lcdd', written using the PPL's C++ interface, together
with several example polyhedra in the formats that the program can
handle. The `ppl_lpsol' subdirectory contains another demo program
that solves linear programming problems by vertex/point
enumeration. This is written using the PPL's C interface and comes
with several example problems in the Mathematical Programming
System (MPS) format. In order to read MPS files, `ppl_lpsol' uses
the GNU Linear Programming Kit (GLPK); thus `ppl_lpsol' is only compiled
if a suitable version of GLPK is available.
o New macro PPL_VERSION expands to the version string of the library.
o New file README.configure provides additional information about
the configuration and compilation of the library.
o The documentation has been improved in various ways.
o The documentation for users, in PostScript, PDF and HTML formats,
is now installed in a standard place by `make install'.
o The variable `abandon_exponential_computations' has been renamed
`abandon_expensive_computations'.
o The methods
void Polyhedron::add_constraints(ConSys& cs),
void Polyhedron::add_generators(GenSys& gs),
bool Polyhedron::add_constraints_and_minimize(ConSys& cs), and
bool Polyhedron::add_generators_and_minimize(GenSys& gs)
have been renamed
void Polyhedron::add_recycled_constraints(ConSys& cs),
void Polyhedron::add_recycled_generators(GenSys& gs),
bool Polyhedron::add_recycled_constraints_and_minimize(ConSys& cs), and
bool Polyhedron::add_recycled_generators_and_minimize(GenSys& gs),
respectively. At the same time, the methods
void Polyhedron::add_constraints(const ConSys& cs),
void Polyhedron::add_generators(const GenSys& gs),
bool Polyhedron::add_constraints_and_minimize(const ConSys& cs), and
bool Polyhedron::add_generators_and_minimize(const GenSys& gs)
have been added. Corresponding changes have been made to the C and
Prolog interfaces.
o New methods Polyhedron::maximize() and Polyhedron::minimize()
for maximizing and minimizing a linear expression subject to the
polyhedron.
o New output operator in namespace IO_Operators:
std::ostream& operator<<(std::ostream&, const LinExpression&).
o The method Polyhedron::map_dimensions(const PartialFunction& pfunc)
has been significantly optimized for the case when `pfunc' is a
permutation. A simple "renaming" of the dimensions is now
extremely cheap.
o The function Parma_Polyhedra_Library::max_space_dimension() has been
given a new semantics and destiny: it returns the maximum space
dimension that _all_ the abstractions provided by the library can
handle. Each individual abstraction provides its versions of this
function. Thus, e.g., NNC_Polyhedron::max_space_dimension()
gives the maximum space dimensions an NNC_Polyhedron can handle.
o The type of output functions for the class Variable,
`Variable::Output_Function_Type', has been renamed
`Variable::output_function_type' and is now defined as
void output_function_type(std::ostream& s, const Variable& v).
In other words, `v' is now passed by const reference and not by value.
o Thanks to Bruno Haible, it is now possible to use versions of the
GMP library installed into nonstandard places. The new configure
options --with-libgmp-prefix[=DIR] and --with-libgmpxx-prefix[=DIR]
substitute the old (and not really working) options
--with-gmp-includes=DIR and --with-gmp-dir=DIR.
Bugfixes
========
o Fixed a bug in the C interface function ppl_Polyhedron_map_dimensions()
whereby a wrong result was computed.
o Fixed a bug in Polyhedron::poly_difference_assign(const Polyhedron&)
whereby a wrong result was computed.
o Fixed a bug in the Prolog interface predicate
ppl_Polyhedron_get_bounding_box/3 whereby a wrong result was
sometimes computed in the case of an empty polyhedron.
o Fixed a bug in the Prolog interface predicate
ppl_new_Polyhedron_from_bounding_box/3 whereby the predicate was
failing when given an empty bounding box.
--------------------------------------------------------------------------
NEWS for version 0.5 (released on April 28, 2003)
--------------------------------------------------------------------------
New and Changed Features
========================
o New methods Polyhedron::BHRZ03_widening_assign() and
Polyhedron::BHRZ03_limited_extrapolation_assign(). The BHRZ03 widening
is a novel widening that is always more precise than the one, by now
standard, we call H79.
o The novel "widening with tokens" technique improves on the good old
widening delay technique by refraining from widening only when
necessary. Precision is thus increased still guaranteeing
convergence. All widening operators can now be supplied with an
optional argument, recording the number of available tokens, which
is decremented when tokens are used.
o Two new methods have been defined that compute the image of
a polyhedron under an affine relation. The first method,
Polyhedron::generalized_affine_image(var, relsym, expr, denom),
generalizes the classical Polyhedron::affine_image() method by allowing
`relsym' to denote any of the relations <, <=, =, >=, >.
The second method, Polyhedron::generalized_affine_image(lhs, relsym, rhs),
is a variant where an arbitrary linear expression `lhs' is allowed to
occur on the left-hand side of the affine relation.
o New constructors to build polyhedra from read-only constraint and
generator systems: C_Polyhedron(const ConSys&),
C_Polyhedron(const GenSys&), NNC_Polyhedron(const ConSys&), and
NNC_Polyhedron(const GenSys&). In the C interface the functions
taking non-const arguments named ppl_new__from_~~ have been
renamed ppl_new__recycle_~~~~, where is either "C" or "NNC",
and ~~~~ is either "ConSys" or "GenSys". The old names have been
given to the new const functions.
o New function LinExpression& operator*=(LinExpression&, const Integer&)
to multiply (in place) an expression by a scalar.
o The methods Polyhedron::check_empty() and Polyhedron::check_universe()
have been renamed is_empty() and is_universe(), respectively.
o New method bool Polyhedron::is_disjoint_from(const Polyhedron& y)
returning true if and only `*this' and `y' are disjoint.
o New methods bool Polyhedron::add_constraint_and_minimize(const
Constraint&) and bool Polyhedron::add_generator_and_minimize(const
Generator&) to add a constraint or a generator and minimizing the
result at the same time.
o New method: template
void Polyhedron::map_dimensions(const PartialFunction&).
This allows to rename the dimensions of a polyhedron according
to a partial function mapping dimensions to dimensions.
o New function LinExpression operator+(const LinExpression&): previously
an expressions like `+x2-x3-x4 <= 0' could not constitute valid syntax
for a constraint.
o New type `dimension_type': an unsigned integral type for representing
space dimensions.
o New function dimension_type max_space_dimension():
returns the maximum space dimension this library can handle.
o New function dimension_type not_a_dimension():
returns a value that does not designate a valid dimension.
o The method Polyhedron::add_dimensions_and_constraints(ConSys&)
has gone. A similar functionality is provided by the new method
Polyhedron::concatenate_assign(const Polyhedron&). The same change
has, of course, been performed on all the PPL interfaces.
o New macros PPL_VERSION_MAJOR, PPL_VERSION_MINOR, PPL_VERSION_REVISION,
and PPL_VERSION_BETA allow the client application to adapt to different
versions of the library.
o New function const char* version() returns a character string
containing the PPL version.
o New function const char* banner() returns a character string
containing information about the PPL version, the licensing,
the lack of any warranty whatsoever, the C++ compiler used
to build the library, where to report bugs and where to look
for further information.
o The Prolog interface now supports also Ciao Prolog and XSB.
o The C and Prolog interfaces have been extended so as to make more of
the library's functionality available to Prolog and C users.
o Timeout computation facilities have been added to the Prolog interfaces:
new predicates ppl_set_timeout_exception_atom/1,
ppl_timeout_exception_atom/1, ppl_set_timeout/1, ppl_reset_timeout/0.
o Many efficiency improvements have been achieved. Part of these have
been obtained by increasing the degree of "lazyness" of the library.
o Many portability and standard-conformance improvements: the library
can now be compiled with GNU g++, Intel C++ Compiler 7.0 for Linux,
and Comeau C/C++ 4.3.0.1 Compiler Front-End; the library has also
been tested on a variety of platforms.
o The functions
Polyhedron::operator<=(const Polyhedron&, const Polyhedron&),
Polyhedron::operator>=(const Polyhedron&, const Polyhedron&),
Polyhedron::operator<(const Polyhedron&, const Polyhedron&), and
Polyhedron::operator>(const Polyhedron&, const Polyhedron&)
have been removed. The methods
Polyhedron::contains(const Polyhedron&) and
Polyhedron::strictly_contains(const Polyhedron&)
provide the same functionality.
o The method Polyhedron::limited_H79_widening_assign() has been renamed
Polyhedron::limited_H79_extrapolation_assign(). From now on, the name
`widening' is reserved for operators that come with a convergence
guarantee (i.e., with the ability of turning infinite chains to finite
ones). Upper bound operators without such a guarantee contain the word
`extrapolation' in their name.
o The renamed method Polyhedron::limited_H79_extrapolation_assign()
takes the constraint system argument by const reference (in the
old Polyhedron::limited_H79_widening_assign() that argument was
passed by non-const reference).
o We now require GMP 4.1.2 or higher.
o In conformance with the C++ standard [17.4.3.1.2], in all the
identifiers exported by the C interface, any occurrence
of "__" (double underscore) has been replaced by "_" (underscore).
o Added a parameter to Polyhedron::shrink_bounding_box(): this specifies
the complexity class of the algorithm to be used.
o All the input/output operators have been confined into namespace
Parma_Polyhedra_Library::IO_Operators. This way they do not conflict
with the operators the user might want to define.
o The operator Constraint operator>>(const Constraint&, unsigned int)
has been removed.
o The method
Polyhedron::poly_difference_assign_and_minimize(const Polyhedron&)
has been removed.
Bugfixes
========
o Fixed a bug in operator-=(LinExpression&, const LinExpression&)
whereby we computed a wrong result in some circumstances.
o Fixed a bug in method Polyhedron::minimized_constraints() that,
under some circumstances, could cause a wrong result or a program
crash.
--------------------------------------------------------------------------
NEWS for version 0.4.2 (released on October 4, 2002)
--------------------------------------------------------------------------
Bugfixes
========
o Fixed a bug in method Polyhedron::add_generator(const Generator&)
whereby we were not adding the corresponding closure point when adding
a point to an empty NNC polyhedron.
o Fixed a bug in method GenSys::insert(const Generator&) whereby the
insertion of a generator into an empty generator system might be
mishandled.
o Fixed a bug in method Polyhedron::operator<=(const Polyhedron&)
whereby the lines of the polyhedron were handled improperly.
o Fixed a bug in a private method used to implement public method
Polyhedron::relation_with(const Generator& g),
whereby a wrong result was obtained when `g' was a line.
o Fixed a bug in methods Polyhedron::affine_image() and
Polyhedron::affine_preimage(), whereby a wrong result could be
obtained when using a negative denominator for the affine expression.
o Fixed a bug in methods Polyhedron::minimized_constraints() and
Polyhedron::minimized_generators(), whereby a library invariant
was violated when calling these methods on a zero-dimensional space
universe NNC polyhedron.
--------------------------------------------------------------------------
NEWS for version 0.4.1 (released on July 30, 2002)
--------------------------------------------------------------------------
Bugfixes
========
o Fixed a bug in Polyhedron::poly_difference_assign(const Polyhedron& y)
whereby the equality constraints of `y' were ignored (the bug was
affecting both C and NNC computations).
o Fixed a bug in Polyhedron::operator=(const Polyhedron& y). This bug,
which is triggered in some cases when `y' is empty, should only affect
versions of the library obtained with the `--enable-assertions'
configuration flag.
o Fixed a bug in Polyhedron::check_universe(), which was returning
the wrong result when called on a zero-dim universe polyhedron.
o Fixed a bug in NNC_Polyhedron::NNC_Polyhedron(ConSys& cs) whereby
an invariant was violated in case `cs' was empty. This bug
should only affect versions of the library obtained with the
`--enable-assertions' configuration flag.
--------------------------------------------------------------------------
NEWS for version 0.4 (released on July 1, 2002)
--------------------------------------------------------------------------
New and Changed Features
========================
o Added full support for Not Necessarily Closed (NNC) polyhedra:
- creation of strict inequality constraints and mixed constraint
systems;
- creation of closure points and extended generator systems;
- added classes C_Polyhedron (for the representation of Closed
polyhedra) and NNC_Polyhedron (the user no longer can create
Polyhedron objects);
- added topology compatibility checks to avoid mixing objects of
the two kinds;
- added explicit constructors to create a polyhedron of a given
topology kind starting from a polyhedron of the other kind;
- added methods Polyhedron::is_topologically_closed() and
Polyhedron::topological_closure_assign();
- implemented methods Polyhedron::minimized_constraints() and
Polyhedron::minimized_generators() to obtain minimal
descriptions, both for closed and for NNC polyhedra.
o New method Polyhedron::time_elapse_assign(const Polyhedron&):
it computes the time-elapse operation defined in
N. Halbwachs, Y.-E. Proy, and P. Roumanoff.
Verification of real-time systems using linear relation analysis.
Formal Methods in System Design, 11(2):157-185, 1997.
o New method Polyhedron::is_bounded(): it returns true if and only
if the polyhedron is bounded, i.e., finite.
o New methods Polyhedron::bounds_from_above(const LinExpression& e)
and Polyhedron::bounds_from_below(const LinExpression& e): they
return true if and only if the linear expression `e' is bounded
from above/below in the polyhedron.
o New, complete C interface. As a demo, a toy solver for pure linear
programming problems has been implemented using this interface.
Notice that solving linear programming problems is completely
outside the scope of the library. As a consequence the toy provided
as a demo is only a toy provided as a demo.
o Revised and completed Prolog interface:
- now supporting GNU Prolog, SICStus Prolog, SWI Prolog and YAP.
- all predicates have been renamed to match their intended
semantics;
- arguments have been reordered where necessary so as to follow the
rule "input arguments before output arguments";
- predicates added so that all the public methods for Polyhedra in
the C++ library are available as Prolog predicates;
- the interface has been extended to allow for closed and not
necessarily closed polyhedra.
o Added support for timeout-guarded operations. It is now possible
for client applications to safely interrupt any exponential
computation paths in the library and get control back in a time
that is a linear function of the space dimension of the object
(polyhedron, system of constraints or generators) of highest
dimension on which the library is operating upon.
o The methods named convex_hull_* and convex_difference_*
have been renamed poly_hull_* and poly_difference_*.
o All methods named *_and_minimize() now return a boolean
flag that is false if the result is empty.
o All method and variable names containing the word "vertex"
have been replaced by names containing the word "point"
(some previous uses of the word "vertex" were not formally correct).
o The methods Polyhedron::includes(const Generator&) and
Polyhedron::satisfies(const Constraint&) have been removed,
as well as the enumeration GenSys_Con_Rel.
They have been replaced by the new methods
Polyhedron::relation_with(const Generator&) and
Polyhedron::relation_with(const Constraint&),
which return values of the new enumeration types
Relation_Poly_Gen and Relation_Poly_Con, respectively.
o The method Constraint::coefficient(void) has been renamed
to Constraint::inhomogeneous_term(void).
o The methods Polyhedron::widening_assign() and
Polyhedron::limited_widening_assign() have been renamed
Polyhedron::H79_widening_assign() and
Polyhedron::limited_H79_widening_assign(), respectively.
This emphasizes the fact that they implement extensions
of the widenings introduced in
N. Halbwachs.
Détermination Automatique de Relations Linéaires
Vérifiées par les Variables d'un Programme.
Thèse de 3ème cicle d'informatique,
Université scientifique et médicale de Grenoble,
Grenoble, France, March 1979.
and described in
N. Halbwachs, Y.-E. Proy, and P. Roumanoff.
Verification of real-time systems using linear relation analysis.
Formal Methods in System Design, 11(2):157-185, 1997.
o The library no longer calls abort(): appropriate exceptions
are always thrown instead.
Bugfixes
========
o Fixed a bug whereby creating a point with a negative denominator
caused the library to misbehave.
o Fixed a bug in Polyhedron::add_constraints(ConSys&) whereby
we could have created constraint systems having rows with
different capacities.
o Several other bugs have been fixed.
--------------------------------------------------------------------------
NEWS for version 0.3 (released on February 26, 2002)
--------------------------------------------------------------------------
New Features
============
o The library has been ported under libtool: it is now possible
to build dynamic libraries as well.
o We now use the integer C++ class of GMP to represent the
coefficients of constraints and generators, instead of our own
(very much inferior) Integer class. The drawback is that we
now require GMP 4.0.1 or higher.
o New methods Polyhedron::convex_difference_assign(const Polyhedron&) and
Polyhedron::convex_difference_assign_and_minimize(const Polyhedron&).
They assign to `*this' the convex hull of the set-theoretic difference
of `*this' and the argument (possibly non minimized or minimized,
respectively).
o The method Polyhedron::add_generators(GenSys&) is now lazy,
i.e., no minimization is performed. Adding generators and
minimizing at the same time is provided by the method
Polyhedron::add_generators_and_minimize(GenSys&).
These methods now throw an exception if the resulting
polyhedron would be illegal.
o Some performance improvements.
o Added more test programs.
Bugfixes
========
o Fixed Polyhedron::satisfies(const Constraint&) and
Polyhedron::affine_image().
o Polyhedron::limited_widening_assign(const Polyhedron&, ConSys&)
was erroneously returning a (random) boolean: it is now a void
method.
--------------------------------------------------------------------------
NEWS for version 0.2 (released on November 14, 2001)
--------------------------------------------------------------------------
New Features
============
o Massive API changes. This would not normally be called "a feature",
but the old API was very wrong in a number of ways. More API changes
are to be expected for the next few releases.
o All user-accessible library methods are now guarded by suitable
sanity checks. Exception are thrown whenever the library is not
called in the intended way.
o A SICStus Prolog interface is now available. It comes with a somewhat
interesting demo: a toy CLP(Q) interpreter.
o Greatly improved documentation.
Bugfixes
========
o Many, many more than we would like to admit.
--------------------------------------------------------------------------
NEWS for version 0.1 (released on October 24, 2001)
--------------------------------------------------------------------------
New Features
============
o The library has been released under the GNU General Public License.
~~