March 2010 - PPL-devel - BUGSENG Mailman

[GIT] ppl/ppl(sparse_matrices): PIP_Solution_Node: optimize solve() method for sparse matrices.
by Marco Poletti 19 Mar '10

19 Mar '10

Module: ppl/ppl Branch: sparse_matrices Commit: b5918be076131cafc2ae20474a451b125aa0288a URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=b5918be07613… Author: Marco Poletti <poletti.marco(a)gmail.com> Date: Fri Mar 19 09:24:39 2010 +0100 PIP_Solution_Node: optimize solve() method for sparse matrices. --- src/PIP_Tree.cc | 8 ++++++-- 1 files changed, 6 insertions(+), 2 deletions(-) diff --git a/src/PIP_Tree.cc b/src/PIP_Tree.cc index 1339d3e..1ebbaba 100644 --- a/src/PIP_Tree.cc +++ b/src/PIP_Tree.cc @@ -2765,7 +2765,7 @@ PIP_Solution_Node::solve(const PIP_Problem& pip, if (s_pivot_pj != pivot_den) { for (dimension_type i = num_rows; i-- > 0; ) { matrix_row_reference_type s_i = tableau.s[i]; - product = s_i[pj] * pivot_den; + product = s_i.get(pj) * pivot_den; if (product % s_pivot_pj != 0) { // As above, perform matrix scaling. gcd_assign(gcd, product, s_pivot_pj); @@ -2774,7 +2774,11 @@ PIP_Solution_Node::solve(const PIP_Problem& pip, product *= scale_factor; } PPL_ASSERT(product % s_pivot_pj == 0); - exact_div_assign(s_i[pj], product, s_pivot_pj); + if (product != 0 || s_i.get(pj) != 0) { + Coefficient x = Coefficient_zero(); + exact_div_assign(x, product, s_pivot_pj); + s_i[pj] = x; + } } }

1 0

[GIT] ppl/ppl(sparse_matrices): PIP_Tree.cc: fix regression in find_lexico_minimum_column_in_set() introduced by commit 8EE0EA53.
by Marco Poletti 19 Mar '10

19 Mar '10

Module: ppl/ppl Branch: sparse_matrices Commit: 14ccb421f1f328ea02825cd56a095d661971652b URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=14ccb421f1f3… Author: Marco Poletti <poletti.marco(a)gmail.com> Date: Fri Mar 19 09:14:08 2010 +0100 PIP_Tree.cc: fix regression in find_lexico_minimum_column_in_set() introduced by commit 8EE0EA53. --- src/PIP_Tree.cc | 135 ++++++++++++++++-------------------------------------- 1 files changed, 40 insertions(+), 95 deletions(-) diff --git a/src/PIP_Tree.cc b/src/PIP_Tree.cc index 6e5c765..1339d3e 100644 --- a/src/PIP_Tree.cc +++ b/src/PIP_Tree.cc @@ -498,104 +498,49 @@ find_lexico_minimum_column_in_set(std::set<dimension_type>& candidates, = row.lower_bound(min_column); PIP_Tree_Node::matrix_const_row_const_iterator row_end = row.end(); const Coefficient* row_jb; - if (row_itr == row_end || (*row_itr).first > min_column) { - // Found a zero element, keep only zero elements in the current row. - for (++i; i!=i_end; ++i) { - if (row_itr != row_end) { - if ((*row_itr).first == *i) { - if ((*row_itr).second == 0) - new_candidates.insert(*i); - ++row_itr; - } else { - if ((*row_itr).first < *i) { - ++row_itr; - row_itr = row.lower_bound(*i,row_itr); - if (row_itr == row_end || (*row_itr).first > *i) - new_candidates.insert(*i); - else { - PPL_ASSERT((*row_itr).first == *i); - if ((*row_itr).second == 0) - new_candidates.insert(*i); - ++row_itr; - } - } else { - PPL_ASSERT((*row_itr).first > *i); - new_candidates.insert(*i); - } - } - } else - new_candidates.insert(*i); - } - } else { + if (row_itr == row_end || (*row_itr).first > min_column) + row_jb = &(Coefficient_zero()); + else { PPL_ASSERT((*row_itr).first == min_column); row_jb = &((*row_itr).second); ++row_itr; - for ( ; i!=i_end; ++i) { - pivot_itr = pivot_row.find(*i,pivot_itr); - PPL_ASSERT(pivot_itr != pivot_end); - const Coefficient& sij_a = (*pivot_itr).second; - PPL_ASSERT(sij_a > 0); - PPL_ASSERT(*sij_b > 0); - - PPL_DIRTY_TEMP_COEFFICIENT(lhs); - PPL_DIRTY_TEMP_COEFFICIENT(rhs); - bool found_better_candidate = false; - if (row_itr != row_end && (*row_itr).first < *i) - row_itr = row.lower_bound(*i,row_itr); - const Coefficient* row_ja; - if (row_itr != row_end) { - row_ja = &((*row_itr).second); - ++row_itr; - } else { - // Found a zero element, keep only zero elements in the current - // row. - new_candidates.clear(); - new_candidates.insert(*i); - for (++i; i!=i_end; ++i) { - if (row_itr != row_end) { - if ((*row_itr).first == *i) { - if ((*row_itr).second == 0) - new_candidates.insert(*i); - ++row_itr; - } else { - if ((*row_itr).first < *i) { - ++row_itr; - row_itr = row.lower_bound(*i,row_itr); - if (row_itr == row_end || (*row_itr).first > *i) - new_candidates.insert(*i); - else { - PPL_ASSERT((*row_itr).first == *i); - if ((*row_itr).second == 0) - new_candidates.insert(*i); - ++row_itr; - } - } else { - PPL_ASSERT((*row_itr).first > *i); - new_candidates.insert(*i); - } - } - } else - new_candidates.insert(*i); - } - break; - } - // lhs is actually the left-hand side with toggled sign. - // rhs is actually the right-hand side with toggled sign. - lhs = *sij_b * *row_ja; - rhs = sij_a * *row_jb; - if (lhs == rhs) - new_candidates.insert(*i); - else { - if (lhs < rhs) - found_better_candidate = true; - } - if (found_better_candidate) { - new_candidates.clear(); - min_column = *i; - row_jb = row_ja; - sij_b = &sij_a; - new_candidates.insert(min_column); - } + } + for ( ; i!=i_end; ++i) { + pivot_itr = pivot_row.find(*i,pivot_itr); + PPL_ASSERT(pivot_itr != pivot_end); + const Coefficient& sij_a = (*pivot_itr).second; + PPL_ASSERT(sij_a > 0); + PPL_ASSERT(*sij_b > 0); + + PPL_DIRTY_TEMP_COEFFICIENT(lhs); + PPL_DIRTY_TEMP_COEFFICIENT(rhs); + bool found_better_candidate = false; + if (row_itr != row_end && (*row_itr).first < *i) + row_itr = row.lower_bound(*i,row_itr); + const Coefficient* row_ja; + if (row_itr == row_end || (*row_itr).first > *i) + row_ja = &(Coefficient_zero()); + else { + PPL_ASSERT((*row_itr).first == *i); + row_ja = &((*row_itr).second); + ++row_itr; + } + // lhs is actually the left-hand side with toggled sign. + // rhs is actually the right-hand side with toggled sign. + lhs = *sij_b * *row_ja; + rhs = sij_a * *row_jb; + if (lhs == rhs) + new_candidates.insert(*i); + else { + if (lhs < rhs) + found_better_candidate = true; + } + if (found_better_candidate) { + new_candidates.clear(); + min_column = *i; + row_jb = row_ja; + sij_b = &sij_a; + new_candidates.insert(min_column); } } }

1 0

[GIT] ppl/ppl(sparse_matrices): Unlimited_Sparse_Row, Unlimited_Sparse_Row_Backend_*: move find*() and lower_bound*() implementation to backends.
by Marco Poletti 19 Mar '10

19 Mar '10

Module: ppl/ppl Branch: sparse_matrices Commit: 583f1e3eed39dd9fd5796c6b72a0dc25ea332e99 URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=583f1e3eed39… Author: Marco Poletti <poletti.marco(a)gmail.com> Date: Thu Mar 18 16:24:01 2010 +0100 Unlimited_Sparse_Row, Unlimited_Sparse_Row_Backend_*: move find*() and lower_bound*() implementation to backends. --- src/Unlimited_Sparse_Row.defs.hh | 42 ---- src/Unlimited_Sparse_Row.inlines.hh | 155 ++------------ ...limited_Sparse_Row_Custom_Slist_Backend.defs.hh | 84 ++++++++ ...ited_Sparse_Row_Custom_Slist_Backend.inlines.hh | 222 ++++++++++++++++++++ src/Unlimited_Sparse_Row_Std_List_Backend.defs.hh | 82 +++++++ ...nlimited_Sparse_Row_Std_List_Backend.inlines.hh | 220 +++++++++++++++++++ ...Unlimited_Sparse_Row_Std_Vector_Backend.defs.hh | 85 ++++++++ ...imited_Sparse_Row_Std_Vector_Backend.inlines.hh | 219 +++++++++++++++++++ 8 files changed, 927 insertions(+), 182 deletions(-) Diff: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commitdiff;h=583f1e3e…

1 0

[GIT] ppl/ppl(sparse_matrices): Unlimited_Sparse_Row, Sparse_Row, Sparse_Row_Reference: remove useless upper_bound() methods.
by Marco Poletti 19 Mar '10

19 Mar '10

Module: ppl/ppl Branch: sparse_matrices Commit: 5e39d1a88965c86d3be7f6f3310fb61f88bdf4fc URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=5e39d1a88965… Author: Marco Poletti <poletti.marco(a)gmail.com> Date: Thu Mar 18 15:44:17 2010 +0100 Unlimited_Sparse_Row, Sparse_Row, Sparse_Row_Reference: remove useless upper_bound() methods. --- src/Sparse_Row.defs.hh | 6 ---- src/Sparse_Row.inlines.hh | 25 --------------- src/Unlimited_Sparse_Row.defs.hh | 10 ------ src/Unlimited_Sparse_Row.inlines.hh | 57 ----------------------------------- 4 files changed, 0 insertions(+), 98 deletions(-) diff --git a/src/Sparse_Row.defs.hh b/src/Sparse_Row.defs.hh index 8381250..d72b0d6 100644 --- a/src/Sparse_Row.defs.hh +++ b/src/Sparse_Row.defs.hh @@ -165,13 +165,10 @@ public: dangerous_iterator find_dangerous(const dimension_type c); dangerous_iterator lower_bound_dangerous(const dimension_type c); - dangerous_iterator upper_bound_dangerous(const dimension_type c); iterator find(const dimension_type c); iterator lower_bound(const dimension_type c); - iterator upper_bound(const dimension_type c); const_iterator find(const dimension_type c) const; const_iterator lower_bound(const dimension_type c) const; - const_iterator upper_bound(const dimension_type c) const; //! Equivalent to find_create(i,x,begin_dangerous()) . iterator find_create(const dimension_type i,const Coefficient& x); @@ -349,13 +346,10 @@ public: dangerous_iterator find_dangerous(const dimension_type c); dangerous_iterator lower_bound_dangerous(const dimension_type c); - dangerous_iterator upper_bound_dangerous(const dimension_type c); iterator find(const dimension_type c); iterator lower_bound(const dimension_type c); - iterator upper_bound(const dimension_type c); const_iterator find(const dimension_type c) const; const_iterator lower_bound(const dimension_type c) const; - const_iterator upper_bound(const dimension_type c) const; //! Equivalent to find_create(i,x,begin_dangerous()) . iterator find_create(const dimension_type i,const Coefficient& x); diff --git a/src/Sparse_Row.inlines.hh b/src/Sparse_Row.inlines.hh index 385cef0..bde9ddc 100644 --- a/src/Sparse_Row.inlines.hh +++ b/src/Sparse_Row.inlines.hh @@ -223,11 +223,6 @@ Sparse_Row::lower_bound(const dimension_type k) { return row.lower_bound(k); } -inline Sparse_Row::iterator -Sparse_Row::upper_bound(const dimension_type k) { - return row.upper_bound(k); -} - inline Sparse_Row::const_iterator Sparse_Row::find(const dimension_type k) const { return row.find(k); @@ -238,11 +233,6 @@ Sparse_Row::lower_bound(const dimension_type k) const { return row.lower_bound(k); } -inline Sparse_Row::const_iterator -Sparse_Row::upper_bound(const dimension_type k) const { - return row.upper_bound(k); -} - inline Sparse_Row::iterator Sparse_Row::find_create(const dimension_type i,const Coefficient& x) { PPL_ASSERT(i < size_); @@ -516,11 +506,6 @@ Sparse_Row_Reference::lower_bound_dangerous(const dimension_type c) { return row.lower_bound_dangerous(c); } -inline Sparse_Row_Reference::dangerous_iterator -Sparse_Row_Reference::upper_bound_dangerous(const dimension_type c) { - return row.upper_bound_dangerous(c); -} - inline Sparse_Row_Reference::iterator Sparse_Row_Reference::find(const dimension_type c) { return row.find(c); @@ -531,11 +516,6 @@ Sparse_Row_Reference::lower_bound(const dimension_type c) { return row.lower_bound(c); } -inline Sparse_Row_Reference::iterator -Sparse_Row_Reference::upper_bound(const dimension_type c) { - return row.upper_bound(c); -} - inline Sparse_Row_Reference::const_iterator Sparse_Row_Reference::find(const dimension_type c) const { return row.find(c); @@ -546,11 +526,6 @@ Sparse_Row_Reference::lower_bound(const dimension_type c) const { return row.lower_bound(c); } -inline Sparse_Row_Reference::const_iterator -Sparse_Row_Reference::upper_bound(const dimension_type c) const { - return row.upper_bound(c); -} - inline Sparse_Row_Reference::iterator Sparse_Row_Reference::find_create(const dimension_type i) { PPL_ASSERT(i < size_); diff --git a/src/Unlimited_Sparse_Row.defs.hh b/src/Unlimited_Sparse_Row.defs.hh index 5d0d43e..65e234d 100644 --- a/src/Unlimited_Sparse_Row.defs.hh +++ b/src/Unlimited_Sparse_Row.defs.hh @@ -343,13 +343,10 @@ public: dangerous_iterator find_dangerous(const dimension_type c); dangerous_iterator lower_bound_dangerous(const dimension_type c); - dangerous_iterator upper_bound_dangerous(const dimension_type c); iterator find(const dimension_type c); iterator lower_bound(const dimension_type c); - iterator upper_bound(const dimension_type c); const_iterator find(const dimension_type c) const; const_iterator lower_bound(const dimension_type c) const; - const_iterator upper_bound(const dimension_type c) const; //! Looks for an element with key c, assuming it is in [itr,end()) . dangerous_iterator find_dangerous(const dimension_type c, @@ -357,23 +354,16 @@ public: //! Lower bound of key c, assuming it is in [itr,end()) . dangerous_iterator lower_bound_dangerous(const dimension_type c, dangerous_iterator itr); - //! Upper bound of key c, assuming it is in [itr,end()) . - dangerous_iterator upper_bound_dangerous(const dimension_type c, - dangerous_iterator itr); //! Looks for an element with key c, assuming it is in [itr,end()) . iterator find(const dimension_type c,iterator itr); //! Lower bound of key c, assuming it is in [itr,end()) . iterator lower_bound(const dimension_type c,iterator itr); - //! Upper bound of key c, assuming it is in [itr,end()) . - iterator upper_bound(const dimension_type c,iterator itr); //! Looks for an element with key c, assuming it is in [itr,end()) . const_iterator find(const dimension_type c,const_iterator itr) const; //! Lower bound of key c, assuming it is in [itr,end()) . const_iterator lower_bound(const dimension_type c,const_iterator itr) const; - //! Upper bound of key c, assuming it is in [itr,end()) . - const_iterator upper_bound(const dimension_type c,const_iterator itr) const; //! A faster equivalent of //! itr1=find_dangerous(c1); itr2=find_dangerous(c2); . diff --git a/src/Unlimited_Sparse_Row.inlines.hh b/src/Unlimited_Sparse_Row.inlines.hh index f627960..a4645a0 100644 --- a/src/Unlimited_Sparse_Row.inlines.hh +++ b/src/Unlimited_Sparse_Row.inlines.hh @@ -316,17 +316,6 @@ Unlimited_Sparse_Row::lower_bound_dangerous(const dimension_type k) { return lower_bound_dangerous(k,i); } -inline Unlimited_Sparse_Row::dangerous_iterator -Unlimited_Sparse_Row::upper_bound_dangerous(const dimension_type k) { - if (begin() == end()) - return end_dangerous(); - dangerous_iterator i = begin_dangerous(); - if ((*i).first > k) - return i; - // Now we can call upper_bound(k,i) without triggering asserts. - return upper_bound_dangerous(k,i); -} - inline Unlimited_Sparse_Row::iterator Unlimited_Sparse_Row::find(const dimension_type k) { if (begin() == end()) @@ -349,17 +338,6 @@ Unlimited_Sparse_Row::lower_bound(const dimension_type k) { return lower_bound(k,i); } -inline Unlimited_Sparse_Row::iterator -Unlimited_Sparse_Row::upper_bound(const dimension_type k) { - if (begin() == end()) - return end(); - iterator i = begin(); - if ((*i).first > k) - return i; - // Now we can call upper_bound(k,i) without triggering asserts. - return upper_bound(k,i); -} - inline Unlimited_Sparse_Row::const_iterator Unlimited_Sparse_Row::find(const dimension_type k) const { if (begin() == end()) @@ -382,17 +360,6 @@ Unlimited_Sparse_Row::lower_bound(const dimension_type k) const { return lower_bound(k,i); } -inline Unlimited_Sparse_Row::const_iterator -Unlimited_Sparse_Row::upper_bound(const dimension_type k) const { - if (begin() == end()) - return end(); - const_iterator i = begin(); - if ((*i).first > k) - return i; - // Now we can call upper_bound(k,i) without triggering asserts. - return upper_bound(k,i); -} - inline Unlimited_Sparse_Row::dangerous_iterator Unlimited_Sparse_Row ::find_dangerous(const dimension_type k,dangerous_iterator itr1) { @@ -412,14 +379,6 @@ Unlimited_Sparse_Row value_key_compare(std::less<dimension_type>())); } -inline Unlimited_Sparse_Row::dangerous_iterator -Unlimited_Sparse_Row -::upper_bound_dangerous(const dimension_type k,dangerous_iterator itr) { - PPL_ASSERT(itr == end_dangerous() || (*itr).first <= k); - return std::upper_bound(itr,end_dangerous(),k, - key_value_compare(std::less<dimension_type>())); -} - inline Unlimited_Sparse_Row::iterator Unlimited_Sparse_Row::find(const dimension_type k,iterator itr1) { PPL_ASSERT(itr1 == end() || (*itr1).first <= k); @@ -437,14 +396,6 @@ Unlimited_Sparse_Row::lower_bound(const dimension_type k, iterator itr) { value_key_compare(std::less<dimension_type>())); } -inline Unlimited_Sparse_Row::iterator -Unlimited_Sparse_Row -::upper_bound(const dimension_type k,iterator itr) { - PPL_ASSERT(itr == end() || (*itr).first <= k); - return std::upper_bound(itr,end(),k, - key_value_compare(std::less<dimension_type>())); -} - inline Unlimited_Sparse_Row::const_iterator Unlimited_Sparse_Row::find(const dimension_type k,const_iterator itr1) const { PPL_ASSERT(itr1 == end() || (*itr1).first <= k); @@ -463,14 +414,6 @@ Unlimited_Sparse_Row value_key_compare(std::less<dimension_type>())); } -inline Unlimited_Sparse_Row::const_iterator -Unlimited_Sparse_Row -::upper_bound(const dimension_type k,const_iterator itr1) const { - PPL_ASSERT(itr1 == end() || (*itr1).first <= k); - return std::upper_bound(itr1,end(),k, - key_value_compare(std::less<dimension_type>())); -} - inline void Unlimited_Sparse_Row ::find2_dangerous(const dimension_type c1,const dimension_type c2,

1 0

[GIT] ppl/ppl(master): Corrected/improved a few tests in BD_Shape/ frequency1.cc.
by Enea Zaffanella 19 Mar '10

19 Mar '10

Module: ppl/ppl Branch: master Commit: 5c439aeac0c888387e97686f09a820e0cd3ea0e5 URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=5c439aeac0c8… Author: Enea Zaffanella <zaffanella(a)cs.unipr.it> Date: Fri Mar 19 08:55:40 2010 +0100 Corrected/improved a few tests in BD_Shape/frequency1.cc. --- tests/BD_Shape/frequency1.cc | 51 ++++++++++++++++++++++++++++++++---------- 1 files changed, 39 insertions(+), 12 deletions(-) diff --git a/tests/BD_Shape/frequency1.cc b/tests/BD_Shape/frequency1.cc index 8075fb6..7c420b6 100644 --- a/tests/BD_Shape/frequency1.cc +++ b/tests/BD_Shape/frequency1.cc @@ -46,7 +46,11 @@ test01() { bool ok = (!bds1.frequency(A, num1, den1, valn1, vald1) && !bds2.frequency(A, num2, den2, valn2, vald2)); print_constraints(bds1, "*** bds1 ***"); + nout << "num1 " << num1 << ", den1 " << den1 << endl; + nout << "valn1 " << valn1 << ", vald1 " << vald1 << endl; print_constraints(bds2, "*** bds2 ***"); + nout << "num2 " << num2 << ", den2 " << den2 << endl; + nout << "valn2 " << valn2 << ", vald2 " << vald2 << endl; return ok; } @@ -66,11 +70,16 @@ test02() { Coefficient den2; Coefficient valn2; Coefficient vald2; - bool ok = (bds1.frequency(Linear_Expression(3), num1, den1, valn1, vald1) + Linear_Expression three(3); + bool ok = (bds1.frequency(three, num1, den1, valn1, vald1) && num1 == 0 && den1 == 1 && valn1 == 3 && vald1 == 1 - && !bds2.frequency(Linear_Expression(3), num2, den2, valn2, vald2)); + && !bds2.frequency(three, num2, den2, valn2, vald2)); print_constraints(bds1, "*** bds1 ***"); + nout << "num1 " << num1 << ", den1 " << den1 << endl; + nout << "valn1 " << valn1 << ", vald1 " << vald1 << endl; print_constraints(bds2, "*** bds2 ***"); + nout << "num2 " << num2 << ", den2 " << den2 << endl; + nout << "valn2 " << valn2 << ", vald2 " << vald2 << endl; return ok; } @@ -90,6 +99,8 @@ test03() { bool ok = (bds.frequency(Linear_Expression(A), num, den, valn, vald) && num == 0 && den == 1 && valn == 0 && vald == 1); print_constraints(bds, "*** bds ***"); + nout << "num " << num << ", den " << den << endl; + nout << "valn " << valn << ", vald " << vald << endl; return ok; } @@ -108,6 +119,8 @@ test04() { Coefficient vald; bool ok = (!bds.frequency(Linear_Expression(A), num, den, valn, vald)); print_constraints(bds, "*** bds ***"); + nout << "num " << num << ", den " << den << endl; + nout << "valn " << valn << ", vald " << vald << endl; return ok; } @@ -127,6 +140,8 @@ test05() { Coefficient vald; bool ok = (!bds.frequency(Linear_Expression(B), num, den, valn, vald)); print_constraints(bds, "*** bds ***"); + nout << "num " << num << ", den " << den << endl; + nout << "valn " << valn << ", vald " << vald << endl; return ok; } @@ -137,7 +152,7 @@ test06() { Variable B(1); TBD_Shape bds(2); - bds.add_constraint(2*A == 1); + bds.add_constraint(A == 1); bds.add_constraint(B == 2); Coefficient num; @@ -145,8 +160,10 @@ test06() { Coefficient valn; Coefficient vald; bool ok = (bds.frequency(Linear_Expression(A + B - 3), num, den, valn, vald) - && num == 0 && den == 1 && valn == -1 && vald == 2); + && num == 0 && den == 1 && valn == 0 && vald == 1); print_constraints(bds, "*** bds ***"); + nout << "num " << num << ", den " << den << endl; + nout << "valn " << valn << ", vald " << vald << endl; return ok; } @@ -166,6 +183,8 @@ test07() { Coefficient vald; bool ok = (!bds.frequency(Linear_Expression(A - B), num, den, valn, vald)); print_constraints(bds, "*** bds ***"); + nout << "num " << num << ", den " << den << endl; + nout << "valn " << valn << ", vald " << vald << endl; return ok; } @@ -177,8 +196,8 @@ test08() { Variable C(2); TBD_Shape bds(3); - bds.add_constraint(2*A - 2*B == 1); - bds.add_constraint(3*C == 2); + bds.add_constraint(2*A - 2*B == 2); + bds.add_constraint(3*C == 3); bds.add_constraint(B <= 2); Coefficient num; @@ -187,8 +206,10 @@ test08() { Coefficient vald; bool ok = (bds.frequency(Linear_Expression(A - B + C + 1), num, den, valn, vald) - && num == 0 && den == 1 && valn == 13 && vald == 6); + && num == 0 && den == 1 && valn == 3 && vald == 1); print_constraints(bds, "*** bds ***"); + nout << "num " << num << ", den " << den << endl; + nout << "valn " << valn << ", vald " << vald << endl; return ok; } @@ -200,18 +221,24 @@ test09() { Variable C(2); TBD_Shape bds(3); - bds.add_constraint(2*A - 2*B == 1); - bds.add_constraint(2*C == 1); + bds.add_constraint(4*A - 4*B == 1); + bds.add_constraint(3*C == 1); bds.add_constraint(B <= 2); Coefficient num; Coefficient den; Coefficient valn; Coefficient vald; - bool ok = (bds.frequency(Linear_Expression(A - B + C + 1), - num, den, valn, vald) - && num == 0 && den == 1 && valn == 2 && vald == 1); + bool discrete = bds.frequency(Linear_Expression(A - B), + num, den, valn, vald); + // If the shape is based on an integral coefficient type, then + // approximations will induce non discreteness of the linear expression. + bool ok = std::numeric_limits<TBD_Shape::coefficient_type_base>::is_integer + ? (!discrete && num == 0 && den == 0 && valn == 0 && vald == 0) + : (discrete && num == 0 && den == 1 && valn == 1 && vald == 4); print_constraints(bds, "*** bds ***"); + nout << "num " << num << ", den " << den << endl; + nout << "valn " << valn << ", vald " << vald << endl; return ok; }

1 0

[GIT] ppl/ppl(master): Mention header file partially_reduced_product_test. hh.
by Enea Zaffanella 18 Mar '10

18 Mar '10

Module: ppl/ppl Branch: master Commit: ec22adde10fd400c963bc6f1a68a2c5ffbbc3fdc URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=ec22adde10fd… Author: Enea Zaffanella <zaffanella(a)cs.unipr.it> Date: Thu Mar 18 22:36:41 2010 +0100 Mention header file partially_reduced_product_test.hh. --- tests/Partially_Reduced_Product/Makefile.am | 4 ++++ 1 files changed, 4 insertions(+), 0 deletions(-) diff --git a/tests/Partially_Reduced_Product/Makefile.am b/tests/Partially_Reduced_Product/Makefile.am index 301f1cb..4bf657d 100644 --- a/tests/Partially_Reduced_Product/Makefile.am +++ b/tests/Partially_Reduced_Product/Makefile.am @@ -36,9 +36,13 @@ endif !VALGRIND_TESTS_ENABLED TESTS_ENVIRONMENT = $(CHECKER) +noinst_HEADERS = \ +partially_reduced_product_test.hh + AM_CPPFLAGS = \ -I$(top_builddir)/src \ -I$(top_srcdir)/src -I$(top_srcdir)/tests \ +-I$(top_srcdir)/tests/Partially_Reduced_Product \ -I$(top_srcdir)/utils \ @extra_includes@ \ @debug_flag@

1 0

[GIT] ppl/ppl(master): Don't take the address of a temporary object.
by Enea Zaffanella 18 Mar '10

18 Mar '10

Module: ppl/ppl Branch: master Commit: 3fe09524b326e388a74486f407583a902d592d75 URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=3fe09524b326… Author: Enea Zaffanella <zaffanella(a)cs.unipr.it> Date: Thu Mar 18 18:37:22 2010 +0100 Don't take the address of a temporary object. --- ...ppl_interface_generator_java_classes_cc_code.m4 | 6 ++---- 1 files changed, 2 insertions(+), 4 deletions(-) diff --git a/interfaces/Java/jni/ppl_interface_generator_java_classes_cc_code.m4 b/interfaces/Java/jni/ppl_interface_generator_java_classes_cc_code.m4 index 9e4d8b5..b6aed73 100644 --- a/interfaces/Java/jni/ppl_interface_generator_java_classes_cc_code.m4 +++ b/interfaces/Java/jni/ppl_interface_generator_java_classes_cc_code.m4 @@ -859,12 +859,10 @@ Java_parma_1polyhedra_1library_@1CLASS@_wrap_1assign Bounded_Integer_Type_Representation r = build_cxx_bounded_rep(env, j_r); Bounded_Integer_Type_Overflow o = build_cxx_bounded_overflow(env, j_o); Constraint_System cs = build_cxx_constraint_system(env, j_cs); - Constraint_System* pcs = &build_cxx_constraint_system(env, j_cs); - unsigned int cx = - jtype_to_unsigned<unsigned int>(j_integer_to_j_int(env, j_cx)); + unsigned cx = jtype_to_unsigned<unsigned>(j_integer_to_j_int(env, j_cx)); bool ind = (j_boolean_to_bool(env, j_ind)); - this_ptr->wrap_assign(vars, w, r, o, pcs, cx, ind); + this_ptr->wrap_assign(vars, w, r, o, &cs, cx, ind); } CATCH_ALL

1 0

[GIT] ppl/ppl(termination): All_affine_ranking_functions_PR* functions,
by Patricia Hill 18 Mar '10

18 Mar '10

Module: ppl/ppl Branch: termination Commit: 9c9130e247463a5500fabf77b26852d9587e30c3 URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=9c9130e24746… Author: Patricia Hill <p.m.hill(a)leeds.ac.uk> Date: Thu Mar 18 17:00:03 2010 +0000 All_affine_ranking_functions_PR* functions, for the C and Prolog interfaces now take an NNC polyhedron as the last argument and not a C one. Interface Linear_Expression::is_zero() and Linear_Expression::all_homogeneous_terms_are_zero() added to the C and Prolog interfaces. --- interfaces/C/ppl_c_header.h | 14 +++++++++++ interfaces/C/ppl_c_implementation_common.cc | 13 ++++++++++ interfaces/C/ppl_interface_generator_c_cc_code.m4 | 12 ++++----- .../ppl_interface_generator_prolog_cc_code.m4 | 4 +- interfaces/Prolog/ppl_prolog_common.cc | 24 ++++++++++++++++++++ interfaces/Prolog/ppl_prolog_common.defs.hh | 6 +++++ interfaces/ppl_interface_generator_common_dat.m4 | 4 +++ 7 files changed, 68 insertions(+), 9 deletions(-) diff --git a/interfaces/C/ppl_c_header.h b/interfaces/C/ppl_c_header.h index d899321..a6c24e8 100644 --- a/interfaces/C/ppl_c_header.h +++ b/interfaces/C/ppl_c_header.h @@ -1013,6 +1013,20 @@ PPL_PROTO((ppl_const_Linear_Expression_t le, ppl_Coefficient_t n)); int ppl_Linear_Expression_OK PPL_PROTO((ppl_const_Linear_Expression_t le)); +/*! \relates ppl_Linear_Expression_tag \brief + Returns <CODE>true</CODE> if and only if \p *this is \f$0\f$. +*/ +int +ppl_Linear_Expression_is_zero PPL_PROTO((ppl_const_Linear_Expression_t le)); + +/*! \relates ppl_Linear_Expression_tag \brief + Returns <CODE>true</CODE> if and only if all the homogeneous + terms of \p *this are \f$0\f$. +*/ +int +ppl_Linear_Expression_all_homogeneous_terms_are_zero +PPL_PROTO((ppl_const_Linear_Expression_t le)); + /*@}*/ /* Functions that Do Not Modify the Linear Expression */ /*! \brief \name Functions that May Modify the Linear Expression */ diff --git a/interfaces/C/ppl_c_implementation_common.cc b/interfaces/C/ppl_c_implementation_common.cc index 8884870..3380207 100644 --- a/interfaces/C/ppl_c_implementation_common.cc +++ b/interfaces/C/ppl_c_implementation_common.cc @@ -616,6 +616,19 @@ ppl_Linear_Expression_OK(ppl_const_Linear_Expression_t le) try { } CATCH_ALL +int +ppl_Linear_Expression_is_zero(ppl_const_Linear_Expression_t le) try { + return to_const(le)->is_zero() ? 1 : 0; +} +CATCH_ALL + +int +ppl_Linear_Expression_all_homogeneous_terms_are_zero + (ppl_const_Linear_Expression_t le) try { + return to_const(le)->all_homogeneous_terms_are_zero() ? 1 : 0; +} +CATCH_ALL + /* Interface for Constraint. */ int diff --git a/interfaces/C/ppl_interface_generator_c_cc_code.m4 b/interfaces/C/ppl_interface_generator_c_cc_code.m4 index ec9efca..3cef2d7 100644 --- a/interfaces/C/ppl_interface_generator_c_cc_code.m4 +++ b/interfaces/C/ppl_interface_generator_c_cc_code.m4 @@ -1226,9 +1226,8 @@ ppl_all_affine_ranking_functions_@TERMINATION_ID@_@TOPOLOGY@@CLASS@ ppl_Polyhedron_t ph) try { const @TOPOLOGY@@CPP_CLASS@& ppset = *static_cast<const @TOPOLOGY@@CPP_CLASS@*>(to_const(pset)); - all_affine_ranking_functions_@TERMINATION_ID@(ppset, - *static_cast<C_Polyhedron*> - (to_nonconst(ph))); + all_affine_ranking_functions_@TERMINATION_ID@ + (ppset, *static_cast<@A_TERMINATION_ID@Polyhedron*> (to_nonconst(ph))); return 0; } CATCH_ALL @@ -1245,10 +1244,9 @@ ppl_all_affine_ranking_functions_@TERMINATION_ID@_@TOPOLOGY@@CLASS@_2 = *static_cast<const @TOPOLOGY@@CPP_CLASS@*>(to_const(pset_before)); const @TOPOLOGY@@CPP_CLASS@& ppset_after = *static_cast<const @TOPOLOGY@@CPP_CLASS@*>(to_const(pset_after)); - all_affine_ranking_functions_@TERMINATION_ID@_2(ppset_before, - ppset_after, - *static_cast<C_Polyhedron*> - (to_nonconst(ph))); + all_affine_ranking_functions_@TERMINATION_ID@_2 + (ppset_before, ppset_after, + *static_cast<@A_TERMINATION_ID@Polyhedron*>(to_nonconst(ph))); return 0; } CATCH_ALL diff --git a/interfaces/Prolog/ppl_interface_generator_prolog_cc_code.m4 b/interfaces/Prolog/ppl_interface_generator_prolog_cc_code.m4 index 4135130..eda31cf 100644 --- a/interfaces/Prolog/ppl_interface_generator_prolog_cc_code.m4 +++ b/interfaces/Prolog/ppl_interface_generator_prolog_cc_code.m4 @@ -1324,7 +1324,7 @@ m4_define(`ppl_all_affine_ranking_functions_@TERMINATION_ID@_@TOPOLOGY@@CLASS@_c try { @TOPOLOGY@@CPP_CLASS@* pset = term_to_handle<@TOPOLOGY@@CPP_CLASS@ >(t_pset, where); PPL_CHECK(pset); - C_Polyhedron* ph = new C_Polyhedron(); + @A_TERMINATION_ID@Polyhedron* ph = new @A_TERMINATION_ID@Polyhedron(); Parma_Polyhedra_Library ::all_affine_ranking_functions_@TERMINATION_ID@(*pset, *ph); Prolog_term_ref tmp = Prolog_new_term_ref(); @@ -1357,7 +1357,7 @@ m4_define(`ppl_all_affine_ranking_functions_@TERMINATION_ID@_@TOPOLOGY@@CLASS@_2 = term_to_handle<@TOPOLOGY@@CPP_CLASS@ >(t_pset_after, where); PPL_CHECK(pset_before); PPL_CHECK(pset_after); - C_Polyhedron* ph = new C_Polyhedron(); + @A_TERMINATION_ID@Polyhedron* ph = new @A_TERMINATION_ID@Polyhedron(); Parma_Polyhedra_Library ::all_affine_ranking_functions_@TERMINATION_ID@_2(*pset_before, *pset_after, diff --git a/interfaces/Prolog/ppl_prolog_common.cc b/interfaces/Prolog/ppl_prolog_common.cc index 5a186e8..19c666f 100644 --- a/interfaces/Prolog/ppl_prolog_common.cc +++ b/interfaces/Prolog/ppl_prolog_common.cc @@ -1704,6 +1704,30 @@ ppl_Coefficient_max(Prolog_term_ref t_max) { } extern "C" Prolog_foreign_return_type +ppl_Linear_Expression_is_zero(Prolog_term_ref t_le_expr) { + static const char* where = "ppl_Linear_Expression_is_zero/1"; + try { + Linear_Expression le_expr = build_linear_expression(t_le_expr, where); + if (le_expr.is_zero()) + return PROLOG_SUCCESS; + } + CATCH_ALL; +} + +extern "C" Prolog_foreign_return_type +ppl_Linear_Expression_all_homogeneous_terms_are_zero(Prolog_term_ref t_le_expr) +{ + static const char* where + = "ppl_Linear_Expression_all_homogeneous_terms_are_zero/1"; + try { + Linear_Expression le_expr = build_linear_expression(t_le_expr, where); + if (le_expr.all_homogeneous_terms_are_zero()) + return PROLOG_SUCCESS; + } + CATCH_ALL; +} + +extern "C" Prolog_foreign_return_type ppl_new_MIP_Problem_from_space_dimension (Prolog_term_ref t_nd, Prolog_term_ref t_mip) { static const char* where = "ppl_MIP_Problem_from_space_dimension/2"; diff --git a/interfaces/Prolog/ppl_prolog_common.defs.hh b/interfaces/Prolog/ppl_prolog_common.defs.hh index 33af32d..3511064 100644 --- a/interfaces/Prolog/ppl_prolog_common.defs.hh +++ b/interfaces/Prolog/ppl_prolog_common.defs.hh @@ -719,6 +719,12 @@ extern "C" Prolog_foreign_return_type ppl_Coefficient_max(Prolog_term_ref t_max); extern "C" Prolog_foreign_return_type +ppl_Linear_Expression_is_zero(Prolog_term_ref t_bool); + +extern "C" Prolog_foreign_return_type +ppl_Linear_Expression_all_homogeneous_terms_are_zero(Prolog_term_ref t_bool); + +extern "C" Prolog_foreign_return_type ppl_new_MIP_Problem_from_space_dimension (Prolog_term_ref t_nd, Prolog_term_ref t_mip); diff --git a/interfaces/ppl_interface_generator_common_dat.m4 b/interfaces/ppl_interface_generator_common_dat.m4 index 64ae91f..57cd897 100644 --- a/interfaces/ppl_interface_generator_common_dat.m4 +++ b/interfaces/ppl_interface_generator_common_dat.m4 @@ -988,3 +988,7 @@ m4_define(`m4_Pointset_Powerset_membytes_replacements', dnl The termination algorithms are either sourced from MS or PR. m4_define(`m4_termination_id_replacements', `MS, PR') + +dnl If sourced from MS, the last argument is C_Polyhedron, +dnl If sourced from PR, the last argument is NNC_Polyhedron. +m4_define(`m4_a_termination_id_replacements', `C_, NNC_')

1 0

[GIT] ppl/ppl(master): Fixed tests/Partially_Reduced_Product/Makefile.am.
by Enea Zaffanella 18 Mar '10

18 Mar '10

Module: ppl/ppl Branch: master Commit: cc825f2bac6aad42678e58b0de97a6a311072ecd URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=cc825f2bac6a… Author: Enea Zaffanella <zaffanella(a)cs.unipr.it> Date: Thu Mar 18 17:38:26 2010 +0100 Fixed tests/Partially_Reduced_Product/Makefile.am. --- tests/Partially_Reduced_Product/Makefile.am | 10 ++++++++++ 1 files changed, 10 insertions(+), 0 deletions(-) diff --git a/tests/Partially_Reduced_Product/Makefile.am b/tests/Partially_Reduced_Product/Makefile.am index 541da86..301f1cb 100644 --- a/tests/Partially_Reduced_Product/Makefile.am +++ b/tests/Partially_Reduced_Product/Makefile.am @@ -130,6 +130,12 @@ constraintsproduct1_SOURCES = constraintsproduct1.cc constraints1_SOURCES = constraints1.cc +contains1_SOURCES = contains1.cc + +difference1_SOURCES = difference1.cc + +dimension1_SOURCES = dimension1.cc + directproduct1_SOURCES = directproduct1.cc discrete1_SOURCES = discrete1.cc @@ -152,6 +158,8 @@ fromproduct1_SOURCES = fromproduct1.cc generalizedaffineimage1_SOURCES = generalizedaffineimage1.cc +intersection1_SOURCES = intersection1.cc + isempty1_SOURCES = isempty1.cc isuniverse1_SOURCES = isuniverse1.cc @@ -175,6 +183,8 @@ topclosed1_SOURCES = topclosed1.cc topclosure1_SOURCES = topclosure1.cc +upperbound1_SOURCES = upperbound1.cc + DERIVED_CXXFLAGS = -DREVERSED_TESTS $(AM_CXXFLAGS) reverse_congruences1_SOURCES = congruences1.cc

1 0

[GIT] ppl/ppl(master): Avoid a broken reference to another manual that is built later.
by Enea Zaffanella 18 Mar '10

18 Mar '10

Module: ppl/ppl Branch: master Commit: b0ff1e07c69512ffd4c5783fdfdc8479f23e281f URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=b0ff1e07c695… Author: Enea Zaffanella <zaffanella(a)cs.unipr.it> Date: Thu Mar 18 17:15:05 2010 +0100 Avoid a broken reference to another manual that is built later. --- Watchdog/src/Threshold_Watcher.defs.hh | 5 +++-- 1 files changed, 3 insertions(+), 2 deletions(-) diff --git a/Watchdog/src/Threshold_Watcher.defs.hh b/Watchdog/src/Threshold_Watcher.defs.hh index ef3e638..f565e67 100644 --- a/Watchdog/src/Threshold_Watcher.defs.hh +++ b/Watchdog/src/Threshold_Watcher.defs.hh @@ -31,8 +31,9 @@ site: http://www.cs.unipr.it/ppl/ . */ /*! \brief A class of watchdogs controlling the exceeding of a threshold. - \tparam Traits class to set data types and functions for the - threshold handling. See \ref Weightwatch_Traits for an example. + \tparam Traits + A class to set data types and functions for the threshold handling. + See \c Parma_Polyhedra_Library::Weightwatch_Traits for an example. */ template <typename Traits> class Parma_Watchdog_Library::Threshold_Watcher {

1 0