- PPL-devel - BUGSENG Mailman

[GIT] ppl/ppl(devel): Fixed bug in Pointset_Powerset::relation_with( const Constraint&) const.
by Enea Zaffanella 19 Nov '15

19 Nov '15

Module: ppl/ppl Branch: devel Commit: 93b1fe4d63f7ea0cb9d515f5beeea595ca4d96d6 URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=93b1fe4d63f7… Author: Enea Zaffanella <zaffanella(a)cs.unipr.it> Date: Thu Nov 19 12:08:43 2015 +0100 Fixed bug in Pointset_Powerset::relation_with(const Constraint&) const. The bug was causing wrong results for relations strictly_intersects() and saturates() on some inputs. --- src/Pointset_Powerset_templates.hh | 37 +++++++++++++++++++++-------------- 1 files changed, 22 insertions(+), 15 deletions(-) diff --git a/src/Pointset_Powerset_templates.hh b/src/Pointset_Powerset_templates.hh index 393b96b..f2858c1 100644 --- a/src/Pointset_Powerset_templates.hh +++ b/src/Pointset_Powerset_templates.hh @@ -890,30 +890,37 @@ Pointset_Powerset<PSET>::relation_with(const Constraint& c) const { bool is_included = true; /* *this is disjoint with c if every disjunct is disjoint with c */ bool is_disjoint = true; - /* *this strictly_intersects with c if some disjunct strictly - intersects with c */ + /* *this strictly_intersects with c if: + - some disjunct strictly intersects with c + or + - there exists two disjoints d1 and d2 + such that d1 is included in c and d2 is disjoint with c + */ bool is_strictly_intersecting = false; - /* *this saturates c if some disjunct saturates c and - every disjunct is either disjoint from c or saturates c */ - bool saturates_once = false; - bool may_saturate = true; + bool included_once = false; + bool disjoint_once = false; + /* *this saturates c if all disjuncts saturate c */ + bool saturates = true; for (Sequence_const_iterator si = x.sequence.begin(), s_end = x.sequence.end(); si != s_end; ++si) { Poly_Con_Relation relation_i = si->pointset().relation_with(c); - if (!relation_i.implies(Poly_Con_Relation::is_included())) { + if (relation_i.implies(Poly_Con_Relation::is_included())) { + included_once = true; + } + else { is_included = false; } - if (!relation_i.implies(Poly_Con_Relation::is_disjoint())) { + if (relation_i.implies(Poly_Con_Relation::is_disjoint())) { + disjoint_once = true; + } + else { is_disjoint = false; } if (relation_i.implies(Poly_Con_Relation::strictly_intersects())) { is_strictly_intersecting = true; } - if (relation_i.implies(Poly_Con_Relation::saturates())) { - saturates_once = true; - } - else if (!relation_i.implies(Poly_Con_Relation::is_disjoint())) { - may_saturate = false; + if (!relation_i.implies(Poly_Con_Relation::saturates())) { + saturates = false; } } @@ -924,10 +931,10 @@ Pointset_Powerset<PSET>::relation_with(const Constraint& c) const { if (is_disjoint) { result = result && Poly_Con_Relation::is_disjoint(); } - if (is_strictly_intersecting) { + if (is_strictly_intersecting || (included_once && disjoint_once)) { result = result && Poly_Con_Relation::strictly_intersects(); } - if (saturates_once && may_saturate) { + if (saturates) { result = result && Poly_Con_Relation::saturates(); } return result;

1 0

[GIT] ppl/ppl(devel): Corrected expected result for test06().
by Enea Zaffanella 19 Nov '15

19 Nov '15

Module: ppl/ppl Branch: devel Commit: fd92d113b4b3a646573fbaa26d35f62701e3ac12 URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=fd92d113b4b3… Author: Enea Zaffanella <zaffanella(a)cs.unipr.it> Date: Thu Nov 19 11:57:02 2015 +0100 Corrected expected result for test06(). Added a new testcase as test11(). The two tests show a bug in current implementation of method Pointset_Powerset<PSET>::relation_with(const Constraint& c) const --- tests/Powerset/relationwith1.cc | 29 +++++++++++++++++++++++++++-- 1 files changed, 27 insertions(+), 2 deletions(-) diff --git a/tests/Powerset/relationwith1.cc b/tests/Powerset/relationwith1.cc index bff7e5b..a76856c 100644 --- a/tests/Powerset/relationwith1.cc +++ b/tests/Powerset/relationwith1.cc @@ -147,15 +147,15 @@ test06() { C_Polyhedron ph2(1); ph2.add_constraint(x == 2); - Pointset_Powerset<C_Polyhedron> ps(1, EMPTY); + Pointset_Powerset<C_Polyhedron> ps(1, EMPTY); ps.add_disjunct(ph1); ps.add_disjunct(ph2); Constraint c(x == 1); Poly_Con_Relation rel = ps.relation_with(c); - Poly_Con_Relation known_rel = Poly_Con_Relation::saturates(); + Poly_Con_Relation known_rel = Poly_Con_Relation::strictly_intersects(); bool ok = (rel == known_rel); @@ -262,6 +262,30 @@ test10() { return ok && ps.OK(); } +bool +test11() { + Variable x(0); + + C_Polyhedron ph1(1); + ph1.add_constraint(x <= 0); + + C_Polyhedron ph2(1); + ph2.add_constraint(x >= 2); + + Pointset_Powerset<C_Polyhedron> ps(1, EMPTY); + ps.add_disjunct(ph1); + ps.add_disjunct(ph2); + + Constraint c(x >= 2); + Poly_Con_Relation rel = ps.relation_with(c); + + Poly_Con_Relation known_rel = Poly_Con_Relation::strictly_intersects(); + + bool ok = (rel == known_rel); + + return ok && ps.OK(); +} + } // namespace BEGIN_MAIN @@ -275,4 +299,5 @@ BEGIN_MAIN DO_TEST(test08); DO_TEST(test09); DO_TEST(test10); + DO_TEST(test11); END_MAIN

1 0

[GIT] ppl/ppl(devel): Updated.
by Roberto Bagnara 18 Nov '15

18 Nov '15

Module: ppl/ppl Branch: devel Commit: 3d7c1e0242c21b9e8242527097270258f14a4cfe URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=3d7c1e0242c2… Author: Roberto Bagnara <roberto.bagnara(a)bugseng.com> Date: Tue Jun 30 19:10:15 2015 +0200 Updated. --- CREDITS | 50 ++++++++++++++++++++++++++------------------------ 1 files changed, 26 insertions(+), 24 deletions(-) diff --git a/CREDITS b/CREDITS index a0947c9..7310fc5 100644 --- a/CREDITS +++ b/CREDITS @@ -12,8 +12,8 @@ Core Development Team: Roberto Bagnara [1] (BUGSENG srl and University of Parma) Patricia M. Hill [2] (BUGSENG srl and University of Leeds) - Enea Zaffanella [3] (BUGSENG srl and University of Parma) Abramo Bagnara (BUGSENG srl) + Enea Zaffanella [3] (University of Parma) Former Members of the Core Development Team: @@ -29,29 +29,6 @@ Former Members of the Core Development Team: Current Contributors: --------------------- - Massimo Benerecetti (University of Naples) is working on additional - operators on polyhedra. - - Andrea Cimino (former student of the University of Parma) - wrote most of the mixed integer programming - solver, and also most of the Java and OCaml - interfaces. He keeps helping us, especially - with the web site. - - Marco Faella (University of Naples) is working on additional - operators on polyhedra. - - Stefano Minopoli (University of Naples) is working on additional - operators on polyhedra. - - Marco Poletti (student of the University of Bologna) - implemented the sparse matrices that are used - in the MIP and PIP solvers of the PPL; he also - did experiments on the parallelization of the - sparse matrices' computations; he is now working - on improving the PPL's memory footprint and - on other improvements to the library. - Alessandro Zaccagnini [4] (University of Parma) has helped with the efficient implementation of GCD and LCM for checked numbers. He is now working on the @@ -59,6 +36,9 @@ Current Contributors: Alessandro is always a very valuable source of mathematical advice. + Paulo Cesar Pereira de Andrade + Helps with Fedora packaging. + Past Contributors: ------------------ @@ -73,6 +53,9 @@ Past Contributors: whether or not the set-union of two polyhedra is the same as their poly-hull. + Massimo Benerecetti (University of Naples) worked on the positive + time-elapse operator on polyhedra. + Fabio Biselli (student of the University of Parma) did some work on the PPL support for the approximation of floating point computations. @@ -93,11 +76,19 @@ Past Contributors: one of the four students with which the PPL project started. + Andrea Cimino (former student of the University of Parma) + wrote most of the mixed integer programming + solver, and also most of the Java and OCaml + interfaces. He helped us a lot with the web site. + Katy Dobson (former student of the University of Leeds) worked on the formalization and definition of algorithms for rational grids and products of grids and polyhedra. + Marco Faella (University of Naples) worked on the positive + time-elapse operator on polyhedra. + Giordano Fracasso (former student of the University of Parma) wrote the initial version of the support for native and checked integer coefficients. @@ -121,6 +112,9 @@ Past Contributors: with the generation of the library's documentation using Doxygen. + Stefano Minopoli (University of Naples) worked on the positive + time-elapse operator on polyhedra. + Matthew Mundell [6] (formerly at the University of Leeds) worked on the implementation of rational grids. He has also helped on other implementation issues. @@ -130,6 +124,14 @@ Past Contributors: project started. Later, he helped a little with the library's documentation. + Marco Poletti (former student of the University of Bologna) + implemented the sparse matrices that are used + in the MIP and PIP solvers of the PPL; he also + did experiments on the parallelization of the + sparse matrices' computations; he also worked + on improving the PPL's memory footprint and + on other improvements to the library. + Barbara Quartieri (former student of the University of Parma) worked on our implementation of bounded differences and octagons.

1 0

Mathematica interface to PPL
by Han Xiao 24 Oct '15

24 Oct '15

Dear developers of PPL, I wonder whether there is an Mathermatica interface to PPL. My code are mostly written in Mathematica, and I have to do polyhedra vertex enumeration a lot in my research. A Mathemaitca interface to PPL will help me a lot. As I'm not so good at programming except for Mathematica, and PPL seems to be the most efficient tool for enumerating vertices of polyhedra so far. Best regards, Han Xiao

2 1

[GIT] ppl/ppl(master): Updated.
by Roberto Bagnara 30 Jun '15

30 Jun '15

Module: ppl/ppl Branch: master Commit: 3d7c1e0242c21b9e8242527097270258f14a4cfe URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=3d7c1e0242c2… Author: Roberto Bagnara <roberto.bagnara(a)bugseng.com> Date: Tue Jun 30 19:10:15 2015 +0200 Updated. --- CREDITS | 50 ++++++++++++++++++++++++++------------------------ 1 files changed, 26 insertions(+), 24 deletions(-) diff --git a/CREDITS b/CREDITS index a0947c9..7310fc5 100644 --- a/CREDITS +++ b/CREDITS @@ -12,8 +12,8 @@ Core Development Team: Roberto Bagnara [1] (BUGSENG srl and University of Parma) Patricia M. Hill [2] (BUGSENG srl and University of Leeds) - Enea Zaffanella [3] (BUGSENG srl and University of Parma) Abramo Bagnara (BUGSENG srl) + Enea Zaffanella [3] (University of Parma) Former Members of the Core Development Team: @@ -29,29 +29,6 @@ Former Members of the Core Development Team: Current Contributors: --------------------- - Massimo Benerecetti (University of Naples) is working on additional - operators on polyhedra. - - Andrea Cimino (former student of the University of Parma) - wrote most of the mixed integer programming - solver, and also most of the Java and OCaml - interfaces. He keeps helping us, especially - with the web site. - - Marco Faella (University of Naples) is working on additional - operators on polyhedra. - - Stefano Minopoli (University of Naples) is working on additional - operators on polyhedra. - - Marco Poletti (student of the University of Bologna) - implemented the sparse matrices that are used - in the MIP and PIP solvers of the PPL; he also - did experiments on the parallelization of the - sparse matrices' computations; he is now working - on improving the PPL's memory footprint and - on other improvements to the library. - Alessandro Zaccagnini [4] (University of Parma) has helped with the efficient implementation of GCD and LCM for checked numbers. He is now working on the @@ -59,6 +36,9 @@ Current Contributors: Alessandro is always a very valuable source of mathematical advice. + Paulo Cesar Pereira de Andrade + Helps with Fedora packaging. + Past Contributors: ------------------ @@ -73,6 +53,9 @@ Past Contributors: whether or not the set-union of two polyhedra is the same as their poly-hull. + Massimo Benerecetti (University of Naples) worked on the positive + time-elapse operator on polyhedra. + Fabio Biselli (student of the University of Parma) did some work on the PPL support for the approximation of floating point computations. @@ -93,11 +76,19 @@ Past Contributors: one of the four students with which the PPL project started. + Andrea Cimino (former student of the University of Parma) + wrote most of the mixed integer programming + solver, and also most of the Java and OCaml + interfaces. He helped us a lot with the web site. + Katy Dobson (former student of the University of Leeds) worked on the formalization and definition of algorithms for rational grids and products of grids and polyhedra. + Marco Faella (University of Naples) worked on the positive + time-elapse operator on polyhedra. + Giordano Fracasso (former student of the University of Parma) wrote the initial version of the support for native and checked integer coefficients. @@ -121,6 +112,9 @@ Past Contributors: with the generation of the library's documentation using Doxygen. + Stefano Minopoli (University of Naples) worked on the positive + time-elapse operator on polyhedra. + Matthew Mundell [6] (formerly at the University of Leeds) worked on the implementation of rational grids. He has also helped on other implementation issues. @@ -130,6 +124,14 @@ Past Contributors: project started. Later, he helped a little with the library's documentation. + Marco Poletti (former student of the University of Bologna) + implemented the sparse matrices that are used + in the MIP and PIP solvers of the PPL; he also + did experiments on the parallelization of the + sparse matrices' computations; he also worked + on improving the PPL's memory footprint and + on other improvements to the library. + Barbara Quartieri (former student of the University of Parma) worked on our implementation of bounded differences and octagons.

1 0

Re: [PPL-devel] can you create a brew recipe so that mac users can install PPL automatically ?
by Francois Berenger 23 Jun '15

23 Jun '15

I packaged your software for Mac OS X: https://github.com/Homebrew/homebrew/pull/40986 brew install ppl should work from now on On 05/21/2015 10:01 AM, Roberto Bagnara wrote: > On 05/21/15 09:42, Francois Berenger wrote: >> Cf. http://brew.sh/ for the homebrew package manager for macos. > > Hello Francois, > > support(a)bugseng.com is for BUGSENG customers. > Judging from the subject, the message was meant for > ppl-devel(a)cs.unipr.it, right? > Kind regards, > > Roberto > -- Regards, Francois. "When in doubt, use more types"

1 0

linking problems on OS X Yosemite
by Zanghirati Gaetano 19 Jun '15

19 Jun '15

Hi, I'm trying to compile a software which links your PPL library, but at the linking step I got the error: Undefined symbols for architecture x86_64 .... ld: symbol(s) not found for architecture x86_64 Here is my box configuration: MacBook Pro OS X Yosemite 10.10.3 gcc/mp-4.7 MacPorts 2.3.3 PPL 1.1 (installed by MacPorts) The installed libraries are located in /opt/local/lib: libppl.13.dylib libppl.a libppl.dylib libppl_c.4.dylib libppl_c.a libppl_c.dylib and the link options are -L/opt/local/lib -lppl I really cannot figure out why the library does not support the x86_64 architecture, because MacPorts had no problems at all in installing your library. It would be really nice if you could help me, since the code is for a research project. Looking forward to hearing from you as soon as possible Gaetano

2 1

merging hulls
by Rick Sprague 04 Jun '15

04 Jun '15

Not sure if the mailing list got my first message, but here goes... I have an input that's a set of generators/vertices. I'd like to split the input in two and compute hyper planes for each half. How can I merge the two constraint systems to get a final set of minimized constraints? Do I have to basically processes the whole input at once? Or point me to some literature that may address this (if it's actually possible)? I was hoping for a divide and conquer type approach to computing constraints. Thanks, M

3 2

Merging Convex Hulls
by Monty Hall 04 Jun '15

04 Jun '15

Is this possible on PPL? If so, how is it done? Suppose I have 2 sets of input generators. I compute the convex hull/faces for both via double description. My question is, would this be "concatenation" operation? If so, it doesn't just concatenate the list of input generators and then performs double description does it? Here's what I'm wondering, I often have in input that takes a long time to process. I was wondering if I could split the input into two perform double description. And then merge the convex hulls/hyperplanes together to get a final solution. Divide and conquer so to speak. Not sure if this would be faster than processing the input all at once. Thanks, M

2 1

PPL ranking functions
by Kafle, Bishoksan (ARC-TI)[SGT, INC] 21 May '15

21 May '15

Hi there, I have a question about ranking functions, which hopefully you can clarify me. I am using PPL-ciao prolog interface. The predicate ppl_one_affine_ranking_function_MS_C_Polyhedron(H,RF) gives a single ranking function if there exists one. But I would like to have the possibility of getting more than one ranking functions. The predicate ppl_all_affine_ranking_functions_MS_C_Polyhedron(H,RFs) gives a polyhedron which represent a space of all affine ranking functions but how can one generate or enumerate them systematically? Any help on this would be highly appreciated. Many thanks Bishoksan

2 6