October 2001 - PPL-devel - BUGSENG Mailman

Zero-dimensional constraint systems.
by Enea Zaffanella 28 Oct '01

28 Oct '01

In various places in the source files, we have assertions requiring that matrices (of constraints and generators) have a number of columns <> 1. These assertions can be violated by the following code, that should be considered legal, since it builds the simplest form of an always-flase constraint: LinExpression e0 = LinExpression(0); LinExpression e1 = LinExpression(1); Constraint c0(e0 == e1); // Built the always-false 0-dim constraint c0, that is 0 = 1. ConSys cs; cs.insert(c0); Polyhedron ph(cs); error6: ../../ppl/src/Polyhedron.cc:155: Parma_Polyhedra_Library::Polyhedron::Polyhedron (Parma_Polyhedra_Library::ConSys &): Assertion `cs.num_columns() != 1' failed. There are three ways to solve such a situation: 1. We prevent the creation of 0-dim constraints, throwing an exception when executing Constraint c0(e0 == e1); 2. we force the creation of a dimension when building constraints (e.g., we force c0 to be the 1-dim constraint ``0*Variable(0) == 1''). This is not a very clean solution, since in the code above the user thinks ph to be a 0-dim polyhedron. By silently converting it to a 1-dim polyhedron, we probably trigger some dimension-incompatibility problems later in the code. 3. we remove all assertions of this kind. Non-empty 0-dim constraint systems will be legal and will contain constraints that are either always false (like the one above) or always true (like the positivity constraint 1 >= 0). Note that the representation of the empty polyhedron needs not to be changed, i.e., we just look at the status flag and do not need to explicitly insert have a matrix for the always false constraint. The easiest-to-implement solution is 1. The cleanest one, in my opinion, is solution 3. Here are some other reasons: a) consider an 0-dim empty polyhedron ph; if a user invokes the method ph.constraints(), the user will obtain an exception. If a 0-dim constraint can be built, the implementation can return a constraint system including it. b) the same considerations can be extended to systems of generators. The following code build the 0-dim vertex (the only point of the 0-dim universe polyhedron): LinExpression e0 = LinExpression(0); Generator g0(vertex(e0)); // Built the 0-dim vertex. GenSys gs; gs.insert(g0); Polyhedron ph(gs); error6: ../../ppl/src/Polyhedron.cc:183: Parma_Polyhedra_Library::Polyhedron::Polyhedron (Parma_Polyhedra_Library::GenSys &): Assertion `gs.num_columns() != 1' failed. Also, we now throw an exception when we inkoke ph.generators() for a 0-dim universe polyhedron. In constrast, we could just return the system of generators containing the 0-dim vertex. It seems to me that, when inserting an n-dimension (n > 0) generator in a 0-dim system of generators, the 0-dim vertex (if present in the system) would be correctly dimension-expanded to the origin of the space \Rset^n. Is anyone foreseeing other problems for such a change ? -- Enea Zaffanella Dipartimento di Matematica - Universita' di Parma Via M. D'Azeglio, 85/A I 43100 - PARMA (Italy) Tel: +39 0521 032317 Fax: +39 0521 032350

2 1

ppl doc/Makefile.am doc/devref-browse.doxyconf ...
by Roberto Bagnara 28 Oct '01

28 Oct '01

CVSROOT: /cvs/ppl Module name: ppl Changes by: roberto(a)cs.unipr.it 2001-10-28 13:46:46 Modified files: doc : Makefile.am devref-browse.doxyconf-latex.in devref-print.doxyconf-latex.in devref.doxyconf-html.in user-browse.doxyconf-latex.in user-print.doxyconf-latex.in user.doxyconf-html.in Added files: interfaces/Prolog: Prolog_interface.dox Log message: Provide a framework for the Prolog interface documentation. Patches: http://www.cs.unipr.it/cgi-bin/cvsweb.cgi/ppl/doc/Makefile.am.diff?cvsroot=… http://www.cs.unipr.it/cgi-bin/cvsweb.cgi/ppl/doc/devref-browse.doxyconf-la… http://www.cs.unipr.it/cgi-bin/cvsweb.cgi/ppl/doc/devref-print.doxyconf-lat… http://www.cs.unipr.it/cgi-bin/cvsweb.cgi/ppl/doc/devref.doxyconf-html.in.d… http://www.cs.unipr.it/cgi-bin/cvsweb.cgi/ppl/doc/user-browse.doxyconf-late… http://www.cs.unipr.it/cgi-bin/cvsweb.cgi/ppl/doc/user-print.doxyconf-latex… http://www.cs.unipr.it/cgi-bin/cvsweb.cgi/ppl/doc/user.doxyconf-html.in.dif… http://www.cs.unipr.it/cgi-bin/cvsweb.cgi/ppl/interfaces/Prolog/Prolog_inte…

1 0

ppl/tests removedim2.cc
by Enea Zaffanella 28 Oct '01

28 Oct '01

CVSROOT: /cvs/ppl Module name: ppl Changes by: zaffanella(a)cs.unipr.it 2001-10-28 11:12:29 Modified files: tests : removedim2.cc Log message: Moved creation of lin-expr infrastructure outside the loop. Patches: http://www.cs.unipr.it/cgi-bin/cvsweb.cgi/ppl/tests/removedim2.cc.diff?cvsr…

1 0

ppl/interfaces/Prolog/SICStus ppl_check.pl ppl ...
by Roberto Bagnara 28 Oct '01

28 Oct '01

CVSROOT: /cvs/ppl Module name: ppl Changes by: roberto(a)cs.unipr.it 2001-10-28 10:39:27 Modified files: interfaces/Prolog/SICStus: ppl_check.pl ppl_sicstus.cc ppl_sicstus.pl Log message: Added ppl_get_constraints/2 and ppl_get_generators/2. Patches: http://www.cs.unipr.it/cgi-bin/cvsweb.cgi/ppl/interfaces/Prolog/SICStus/ppl… http://www.cs.unipr.it/cgi-bin/cvsweb.cgi/ppl/interfaces/Prolog/SICStus/ppl… http://www.cs.unipr.it/cgi-bin/cvsweb.cgi/ppl/interfaces/Prolog/SICStus/ppl…

1 0

ppl/src Polyhedron.defs.hh
by Roberto Bagnara 28 Oct '01

28 Oct '01

CVSROOT: /cvs/ppl Module name: ppl Changes by: roberto(a)cs.unipr.it 2001-10-28 10:38:31 Modified files: src : Polyhedron.defs.hh Log message: Do not create yet another Integer set to one to use as default parameter: use Integer::one instead. Patches: http://www.cs.unipr.it/cgi-bin/cvsweb.cgi/ppl/src/Polyhedron.defs.hh.diff?c…

1 0

ppl/src Constraint.defs.hh Generator.defs.hh G ...
by Roberto Bagnara 28 Oct '01

28 Oct '01

CVSROOT: /cvs/ppl Module name: ppl Changes by: roberto(a)cs.unipr.it 2001-10-28 10:38:04 Modified files: src : Constraint.defs.hh Generator.defs.hh Generator.inlines.hh Log message: New methods of Generator: last_variable(), coefficient(), and divisor(). Harmonized with the ones of Constraint. Do not create yet another Integer set to one to use as default parameter: use Integer::one instead. Patches: http://www.cs.unipr.it/cgi-bin/cvsweb.cgi/ppl/src/Constraint.defs.hh.diff?c… http://www.cs.unipr.it/cgi-bin/cvsweb.cgi/ppl/src/Generator.defs.hh.diff?cv… http://www.cs.unipr.it/cgi-bin/cvsweb.cgi/ppl/src/Generator.inlines.hh.diff…

1 0

ppl/src Polyhedron.cc
by Enea Zaffanella 28 Oct '01

28 Oct '01

CVSROOT: /cvs/ppl Module name: ppl Changes by: zaffanella(a)cs.unipr.it 2001-10-28 08:37:34 Modified files: src : Polyhedron.cc Log message: Corrected the error making test `randchull1' fail (I was forgetting to clear flags after insertion of the generator). Patches: http://www.cs.unipr.it/cgi-bin/cvsweb.cgi/ppl/src/Polyhedron.cc.diff?cvsroo…

1 0

ppl/tests onepoint.cc
by Roberto Bagnara 27 Oct '01

27 Oct '01

CVSROOT: /cvs/ppl Module name: ppl Changes by: roberto(a)cs.unipr.it 2001-10-27 22:53:08 Added files: tests : onepoint.cc Log message: New test on the creation of a one-point polyhedron. Patches: http://www.cs.unipr.it/cgi-bin/cvsweb.cgi/ppl/tests/onepoint.cc.diff?cvsroo…

1 0

ppl/tests Makefile.am error1.cc error2.cc erro ...
by Roberto Bagnara 27 Oct '01

27 Oct '01

1 0

ppl/src Constraint.defs.hh Constraint.inlines.hh
by Roberto Bagnara 27 Oct '01

27 Oct '01

CVSROOT: /cvs/ppl Module name: ppl Changes by: roberto(a)cs.unipr.it 2001-10-27 18:32:35 Modified files: src : Constraint.defs.hh Constraint.inlines.hh Log message: New Constraint methods: last_variable(), coefficient(Variable v) and coefficient() to return the last variable, the homogeneous and inhomogeneous coefficients. Patches: http://www.cs.unipr.it/cgi-bin/cvsweb.cgi/ppl/src/Constraint.defs.hh.diff?c… http://www.cs.unipr.it/cgi-bin/cvsweb.cgi/ppl/src/Constraint.inlines.hh.dif…

1 0