- PPL-devel - BUGSENG Mailman

Minkowski-Sum
by Stefan Schupp 24 Jul '14

24 Jul '14

-----BEGIN PGP SIGNED MESSAGE----- Hash: SHA512 Hello, I am currently searching for a possibility to obtain the Minkowski-Sum of two polyhedra. My first idea was to unify the sets of generators from both polyhedra, as from the documentation I can take that a single polytope is generated by the Minkowski-Sum of its generators. Would you suggest this approach or is there a better way to go? Best regards, Stefan Schupp - -- Stefan Schupp M.Sc. RWTH Aachen University Computer Science Department, Informatik 2 D-52056 Aachen, Germany http://www-i2.informatik.rwth-aachen.de/i2/schupp/ Tel.: +49 241 80 21243 -----BEGIN PGP SIGNATURE----- Version: GnuPG/MacGPG2 v2.0.22 (Darwin) Comment: GPGTools - https://gpgtools.org Comment: Using GnuPG with Thunderbird - http://www.enigmail.net/ iQEcBAEBCgAGBQJTxm5XAAoJEFPSi5GyofDjy3MH+QHKFgXlkBdnH6kfS4uN5shl y/M8N4al1B2+py6fFPMcOqiHBu2O7r2K/kw16QuSuBDJwL/dPHhgpMBYdp22+aQy V+x9UVC70LaDm038pMcwrOLSn1Y2MZgxkblBnYisaYAYbSbUv05AxWF45u0f2yNS PH3yG7OWochrdY9s9ySbgM2DtFHg5jsd9VhE18OM/v05aALrccdT2BxmZcdEatGn nRwbnff2Xg71bFjhRwGlC4IY+OGgCpjtAdvmvqNy1VX+FBx5Lqy4ejtkoBOH/FB1 WUIEJchhaQXfHv+UxVY7MAht8cAdrSgUkevVeNpsB5YapXK5UCdnIrFoEH1Y04k= =P0qH -----END PGP SIGNATURE-----

2 1

[GIT] ppl/ppl(compliance): Keep source lines to a length of 120 characters or less.
by Roberto Bagnara 02 Jul '14

02 Jul '14

Module: ppl/ppl Branch: compliance Commit: b1f5eb2caa2b3459167784509b2cae4a94920a46 URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=b1f5eb2caa2b… Author: Roberto Bagnara <bagnara(a)cs.unipr.it> Date: Wed Jul 2 16:58:24 2014 +0200 Keep source lines to a length of 120 characters or less. Fixes violations of rule LP1.41 detected by ECLAIR. --- src/Checked_Number_defs.hh | 4 ++- src/Checked_Number_inlines.hh | 4 ++- src/Linear_Expression_defs.hh | 26 ++++++++++++++------- src/Linear_Expression_inlines.hh | 32 +++++++++++++++++---------- src/checked_int_inlines.hh | 44 ++++++++++++++++++++++++++++--------- src/fpu-ia32.cc | 4 ++- 6 files changed, 79 insertions(+), 35 deletions(-) Diff: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commitdiff;h=b1f5eb2c…

1 0

[GIT] ppl/ppl(compliance): Avoid tabs. Fixes violations of rule UCRP1. RS1 detected by ECLAIR.
by Roberto Bagnara 30 Jun '14

30 Jun '14

Module: ppl/ppl Branch: compliance Commit: 10368f7e6fda94a39706d476e8fda445aff2cd36 URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=10368f7e6fda… Author: Roberto Bagnara <roberto.bagnara(a)bugseng.com> Date: Mon Jun 30 18:00:31 2014 +0200 Avoid tabs. Fixes violations of rule UCRP1.RS1 detected by ECLAIR. --- src/Polyhedron_nonpublic.cc | 16 ++++++++-------- 1 files changed, 8 insertions(+), 8 deletions(-) diff --git a/src/Polyhedron_nonpublic.cc b/src/Polyhedron_nonpublic.cc index 4511e09..4743e3c 100644 --- a/src/Polyhedron_nonpublic.cc +++ b/src/Polyhedron_nonpublic.cc @@ -2484,19 +2484,19 @@ PPL::Polyhedron::positive_time_elapse_assign_impl(const Polyhedron& y) { } new_g.expr.normalize(); PPL_ASSERT(new_g.OK()); - new_gs.insert(new_g); + new_gs.insert(new_g); } break; case Generator::CLOSURE_POINT: // If g is not the origin, insert g into new_gs, as a ray. if (!g.expr.all_homogeneous_terms_are_zero()) { - // Turn a copy of g into a ray. - Generator g_as_a_ray = g; - g_as_a_ray.expr.set_inhomogeneous_term(0); - g_as_a_ray.expr.normalize(); - PPL_ASSERT(g_as_a_ray.OK()); - // Insert the ray. - new_gs.insert(g_as_a_ray); + // Turn a copy of g into a ray. + Generator g_as_a_ray = g; + g_as_a_ray.expr.set_inhomogeneous_term(0); + g_as_a_ray.expr.normalize(); + PPL_ASSERT(g_as_a_ray.OK()); + // Insert the ray. + new_gs.insert(g_as_a_ray); } break; case Generator::RAY:

1 0

[GIT] ppl/ppl(compliance): Added missing braces. Fixes violations of rule MP1.6-4-1 detected by ECLAIR.
by Roberto Bagnara 30 Jun '14

30 Jun '14

Module: ppl/ppl Branch: compliance Commit: 7a2ba6b6089aacd1abb3af0f8171b11c594879dd URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=7a2ba6b6089a… Author: Roberto Bagnara <roberto.bagnara(a)bugseng.com> Date: Mon Jun 30 14:33:02 2014 +0200 Added missing braces. Fixes violations of rule MP1.6-4-1 detected by ECLAIR. --- demos/ppl_lcdd/ppl_lcdd.cc | 15 +++++--- src/BD_Shape_templates.hh | 3 +- src/Constraint_System.cc | 6 ++- src/Generator_System.cc | 3 +- src/Linear_System_templates.hh | 3 +- src/MIP_Problem.cc | 69 +++++++++++++++++++++++++------------ src/Matrix_templates.hh | 3 +- src/OR_Matrix_templates.hh | 3 +- src/Octagonal_Shape_templates.hh | 54 ++++++++++++++++++++---------- src/PIP_Tree.cc | 6 ++- src/Polyhedron_public.cc | 6 ++- src/globals_defs.hh | 6 ++- src/intervals_defs.hh | 6 ++- 13 files changed, 122 insertions(+), 61 deletions(-) Diff: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commitdiff;h=7a2ba6b6…

1 0

[GIT] ppl/ppl(compliance): Added missing braces. Fixes violations of rule MP1.6-4-1 detected by ECLAIR.
by Patrik Pomelli 30 Jun '14

30 Jun '14

1 0

[GIT] ppl/ppl(compliance): Added missing braces. Fixes violations of rule MP1.6-3-1 detected by ECLAIR.
by Patrik Pomelli 30 Jun '14

30 Jun '14

Module: ppl/ppl Branch: compliance Commit: 36d6c98178210d2180d25997fd40a2431f59a1af URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=36d6c9817821… Author: Patrik Pomelli <patrik.pomelli(a)bugseng.com> Date: Mon Jun 30 02:32:03 2014 +0200 Added missing braces. Fixes violations of rule MP1.6-3-1 detected by ECLAIR. Signed-off-by: Roberto Bagnara <roberto.bagnara(a)bugseng.com> --- src/Generator_System_inlines.hh | 3 ++- src/Linear_System_templates.hh | 3 ++- src/MIP_Problem.cc | 4 ++-- src/Polyhedron_conversion_templates.hh | 3 ++- src/Polyhedron_minimize_templates.hh | 3 ++- 5 files changed, 10 insertions(+), 6 deletions(-) diff --git a/src/Generator_System_inlines.hh b/src/Generator_System_inlines.hh index 74d8427..2fa2294 100644 --- a/src/Generator_System_inlines.hh +++ b/src/Generator_System_inlines.hh @@ -104,8 +104,9 @@ Generator_System::set_space_dimension(dimension_type space_dim) { } #ifndef NDEBUG - for (dimension_type i = 0; i < sys.num_rows(); ++i) + for (dimension_type i = 0; i < sys.num_rows(); ++i) { PPL_ASSERT(sys[i].OK()); + } #endif PPL_ASSERT(sys.OK()); PPL_ASSERT(OK()); diff --git a/src/Linear_System_templates.hh b/src/Linear_System_templates.hh index 752b588..1e00935 100644 --- a/src/Linear_System_templates.hh +++ b/src/Linear_System_templates.hh @@ -569,8 +569,9 @@ Linear_System<Row>::gauss(const dimension_type n_lines_or_equalities) { PPL_ASSERT(num_pending_rows() == 0); PPL_ASSERT(n_lines_or_equalities == num_lines_or_equalities()); #ifndef NDEBUG - for (dimension_type i = n_lines_or_equalities; i-- > 0; ) + for (dimension_type i = n_lines_or_equalities; i-- > 0; ) { PPL_ASSERT((*this)[i].is_line_or_equality()); + } #endif dimension_type rank = 0; diff --git a/src/MIP_Problem.cc b/src/MIP_Problem.cc index c1ada16..3494b59 100644 --- a/src/MIP_Problem.cc +++ b/src/MIP_Problem.cc @@ -1675,7 +1675,7 @@ PPL::MIP_Problem::erase_artificials(const dimension_type begin_artificials, const dimension_type old_last_column = tableau.num_columns() - 1; dimension_type tableau_n_rows = tableau.num_rows(); // Step 1: try to remove from the base all the remaining slack variables. - for (dimension_type i = 0; i < tableau_n_rows; ++i) + for (dimension_type i = 0; i < tableau_n_rows; ++i) { if (begin_artificials <= base[i] && base[i] < end_artificials) { // Search for a non-zero element to enter the base. Row& tableau_i = tableau[i]; @@ -1707,7 +1707,7 @@ PPL::MIP_Problem::erase_artificials(const dimension_type begin_artificials, base.pop_back(); } } - + } // Step 2: Adjust data structures so as to enter phase 2 of the simplex. // Resize the tableau. diff --git a/src/Polyhedron_conversion_templates.hh b/src/Polyhedron_conversion_templates.hh index 77d2be0..e9fffd7 100644 --- a/src/Polyhedron_conversion_templates.hh +++ b/src/Polyhedron_conversion_templates.hh @@ -918,8 +918,9 @@ Polyhedron::conversion(Source_Linear_System& source, #ifndef NDEBUG // The previous code can modify the rows' fields, exploiting the friendness. // Check that all rows are OK now. - for (dimension_type i = dest.num_rows(); i-- > 0; ) + for (dimension_type i = dest.num_rows(); i-- > 0; ) { PPL_ASSERT(dest.sys.rows[i].OK()); + } #endif dest.sys.index_first_pending = dest.num_rows(); diff --git a/src/Polyhedron_minimize_templates.hh b/src/Polyhedron_minimize_templates.hh index 5a51172..eacf57f 100644 --- a/src/Polyhedron_minimize_templates.hh +++ b/src/Polyhedron_minimize_templates.hh @@ -152,8 +152,9 @@ Polyhedron::minimize(const bool con_to_gen, dest_num_rows = dest.num_rows(); #ifndef NDEBUG - for (dimension_type i = dest.num_rows(); i-- > 0; ) + for (dimension_type i = dest.num_rows(); i-- > 0; ) { PPL_ASSERT(dest[i].OK()); + } #endif // Checking if the generators in `dest' represent an empty polyhedron:

1 0

Generator safety
by Stefan Schupp 28 Jun '14

28 Jun '14

-----BEGIN PGP SIGNED MESSAGE----- Hash: SHA512 Hi, just a short question: Are generators and generator systems "safe" in their type? E.g. if I create a C_Polytope from a generator system consisting of points and apply some operation on the constructed polytope: Is the generator system of the resulting polytope guaranteed to consist only of points? Best regards, Stefan - -- Stefan Schupp M.Sc. RWTH Aachen University Computer Science Department, Informatik 2 D-52056 Aachen, Germany http://www-i2.informatik.rwth-aachen.de/i2/schupp/ Tel.: +49 241 80 21243 -----BEGIN PGP SIGNATURE----- Version: GnuPG/MacGPG2 v2.0.22 (Darwin) Comment: GPGTools - https://gpgtools.org Comment: Using GnuPG with Thunderbird - http://www.enigmail.net/ iQEcBAEBCgAGBQJTrTYLAAoJEFPSi5GyofDjZfYIAJTobizL3bkMRMHk/YtRTDVP OI7mwAd0mBgBq6XwSM9aODqpDflXmLQPiTnJZK00C5ovaLYkh4t6ccWL5XD9tMfg c+mkuWm4V/DHVpA1VUaSMYi0yoLWPyAdhibx8G0q5+ekfHYsR7SrYtF5J63PuaAX PyLDggnSwxatRJJ3/yecf4tUVGxM6rV25h/ZShEkbBtuH5TWz+ilL0C+CZOUdS8P +beTfV7IGRsW7SBzrdzxNAHEsxqrOp435H6J771QRT3HBcMYRc2WJK/nPssyu1sT j1hJ/hN7JtPRd2183jN3S4yQVDasXZmekdgS1hDwm5GsT9hloMybh/cA3XwPVsA= =/edB -----END PGP SIGNATURE-----

2 1

[GIT] ppl/ppl(compliance): Fixed permissions.
by Roberto Bagnara 25 Jun '14

25 Jun '14

Module: ppl/ppl Branch: compliance Commit: a4125de9f40fc1c1a879b7337b1f0d8196e3ef02 URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=a4125de9f40f… Author: Roberto Bagnara <roberto.bagnara(a)bugseng.com> Date: Wed Jun 25 09:15:41 2014 +0200 Fixed permissions. --- 0 files changed, 0 insertions(+), 0 deletions(-) Diff: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commitdiff;h=a4125de9…

1 0

[GIT] ppl/ppl(compliance): Fixed brace position.
by Patrik Pomelli 24 Jun '14

24 Jun '14

Module: ppl/ppl Branch: compliance Commit: cf56af994e36020b7ef73f9f8e61409333bbd062 URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=cf56af994e36… Author: Patrik Pomelli <patrik.pomelli(a)bugseng.com> Date: Sat Jun 21 18:44:47 2014 +0200 Fixed brace position. Signed-off-by: Roberto Bagnara <roberto.bagnara(a)bugseng.com> --- src/wrap_assign.hh | 10 +++++----- 1 files changed, 5 insertions(+), 5 deletions(-) diff --git a/src/wrap_assign.hh b/src/wrap_assign.hh index e78df5a..49959a8 100644 --- a/src/wrap_assign.hh +++ b/src/wrap_assign.hh @@ -114,12 +114,12 @@ wrap_assign_col(PSET& dest, PSET p(src); if (cs_p != 0) { p.refine_with_constraints(*cs_p); - for (Variables_Set::const_iterator i = vars.begin(), + } + for (Variables_Set::const_iterator i = vars.begin(), vars_end = vars.end(); i != vars_end; ++i) { - const Variable x(*i); - p.refine_with_constraint(min_value <= x); - p.refine_with_constraint(x <= max_value); - } + const Variable x(*i); + p.refine_with_constraint(min_value <= x); + p.refine_with_constraint(x <= max_value); } dest.upper_bound_assign(p); }

1 0

[GIT] ppl/ppl(compliance): Deleted trailing whitespace.
by Roberto Bagnara 24 Jun '14

24 Jun '14

Module: ppl/ppl Branch: compliance Commit: 3d652b0b9d20a32cb8fb02faddae8943514dbcc7 URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=3d652b0b9d20… Author: Roberto Bagnara <bagnara(a)cs.unipr.it> Date: Tue Jun 24 12:53:52 2014 +0200 Deleted trailing whitespace. --- src/Box_templates.hh | 160 +++++++------- src/H79_Certificate.cc | 7 +- src/Init.cc | 4 +- src/Interval_templates.hh | 4 +- src/Linear_Expression_Impl.cc | 15 +- src/Linear_Expression_Impl_inlines.hh | 2 +- src/Linear_Expression_Impl_templates.hh | 8 +- src/Linear_Form_inlines.hh | 2 +- src/Linear_System_inlines.hh | 8 +- src/Linear_System_templates.hh | 26 +- src/MIP_Problem.cc | 60 +++--- src/Matrix_templates.hh | 2 +- src/Octagonal_Shape.cc | 2 +- src/Octagonal_Shape_inlines.hh | 8 +- src/Octagonal_Shape_templates.hh | 248 ++++++++++---------- src/Og_Status_inlines.hh | 8 +- src/Opposite_Floating_Point_Expression_inlines.hh | 2 +- src/PIP_Problem.cc | 49 ++-- src/PIP_Tree.cc | 42 ++-- src/Partial_Function_inlines.hh | 2 +- src/Partially_Reduced_Product_templates.hh | 8 +- src/Pending_List_templates.hh | 2 +- src/Ph_Status.cc | 20 +- src/Pointset_Ask_Tell_templates.hh | 8 +- src/Pointset_Powerset_templates.hh | 22 +- src/Polyhedron_chdims.cc | 28 ++-- src/Polyhedron_inlines.hh | 2 +- src/Polyhedron_nonpublic.cc | 36 ++-- src/Polyhedron_public.cc | 156 +++++++------- src/Polyhedron_templates.hh | 34 ++-- src/Polyhedron_widenings.cc | 44 ++-- src/Sparse_Row.cc | 16 +- src/Sparse_Row_inlines.hh | 18 +- src/Variables_Set.cc | 6 +- src/linearize.hh | 18 +- src/swapping_sort_templates.hh | 2 +- src/termination.cc | 2 +- 37 files changed, 539 insertions(+), 542 deletions(-) Diff: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commitdiff;h=3d652b0b…

1 0