March 2010 - PPL-devel - BUGSENG Mailman

[GIT] ppl/ppl(master): Documentation fixes. Added a paragraph about optimizing a linear cost function.
by François Galea 11 Mar '10

11 Mar '10

Module: ppl/ppl Branch: master Commit: 6060bda39a0fb7b5d8d114d436b81a5a5b1eb74e URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=6060bda39a0f… Author: François Galea <francois.galea(a)uvsq.fr> Date: Thu Mar 11 19:58:03 2010 +0100 Documentation fixes. Added a paragraph about optimizing a linear cost function. --- src/PIP_Problem.defs.hh | 42 +++++++++++++++++++++++++++++++----------- 1 files changed, 31 insertions(+), 11 deletions(-) diff --git a/src/PIP_Problem.defs.hh b/src/PIP_Problem.defs.hh index 4def1e5..32920d9 100644 --- a/src/PIP_Problem.defs.hh +++ b/src/PIP_Problem.defs.hh @@ -323,33 +323,53 @@ operator<<(std::ostream& s, const PIP_Problem& p); which we will call \f$M\f$. - Reformulate each of the maximization problem constraints by substituting each \f$x_i\f$ variable with an expression of the form - \f$M-x'_i\f$, where the \f$x'_i\f$ variables are to be minimized. + \f$M-x'_i\f$, where the \f$x'_i\f$ variables are positive variables to + be minimized. - Solve the lexicographic minimum for the \f$x'\f$ variable vector. - - In the solution expressions, substitute each \f$x'_i\f$ variable back - to \f$M-x_i\f$. - + - In the solution expressions, the values of the original variables are + obtained from the resulting values of the \f$x'_i\f$ variables by + applying the equality \f$x_i = M-x'_i\f$. + \par You can choose to maximize only a subset of the variables while minimizing the other variables. In that case, just apply the variable substitution method on the variables you want to be maximized. The variable optimization priority will still be in lexicographic order. - \par Allowing variables to be arbitrarily signed - You can deal with arbitrarily signed variables by reformulating the - constraints using variable substitution. Proceed the following steps: + \par Allowing variables and parameters to be arbitrarily signed + You can deal with arbitrarily signed variables and/or parameters by + reformulating the constraints using variable and/or parameter + substitution. Proceed the following steps: - Create a big parameter (see PIP_Problem::set_big_parameter_dimension), which we will call \f$M\f$. - Reformulate each of the maximization problem constraints by substituting each \f$x_i\f$ variable with an expression of the form - \f$M+x'_i\f$, where the \f$x'_i\f$ variables are positive. + \f$x'_i-M\f$, where the \f$x'_i\f$ variables are positive, and/or by + substituting each \f$p_i\f$ parameter with an expression of the form + \f$p'_i-M\f$, where the \f$p'_i\f$ parameters are positive. - Solve the lexicographic minimum for the \f$x'\f$ variable vector. - - In the solution expressions, substitute each \f$x'_i\f$ variable back - to \f$x_i-M\f$. + - In the solution expressions, the values of the original variables + and/or parameters are obtained from the resulting values of the + \f$x'_i\f$ variables and/or the \f$p'_i\f$ parameters by applying the + equalities \f$x_i = M-x'_i\f$ and/or \f$p_i = M-p'_i\f$. + \par You can choose to define only a subset of the variables to be sign-unrestricted. In that case, just apply the variable substitution method on the variables you want to be sign-unrestricted. - FIXME: Solving problems with arbitrarily signed parameters + \par Minimizing a linear cost function + Lexicographic solving can be used to find the parametric minimum of a + linear cost function. + \par + Suppose the variables are named \f$x_1, x_2, \dots, x_n\f$, and the + parameters \f$p_1, p_2, \dots, p_m\f$. You can minimize a linear cost + function \f$f(x_2, \dots, x_n, p_1, \dots, p_m)\f$ by simply adding the + constraint \f$x_1 \geq f(x_2, \dots, x_n, p_1, \dots, p_m)\f$ to the + constraint system. As lexicographic minimization ensures \f$x_1\f$ is + minimized in priority, and because \f$x_1\f$ is forced by a constraint to + be superior or equal to the cost function, optimal solutions of the + problem necessarily ensure that the solution value of \f$x_1\f$ is the + optimal value of the cost function. */ class Parma_Polyhedra_Library::PIP_Problem { public:

1 0

[GIT] ppl/ppl(sparse_matrices): PIP_Tree.cc: split out compatibility_check_find_pivot_in_set() from compatibility_check_find_pivot().
by Marco Poletti 11 Mar '10

11 Mar '10

Module: ppl/ppl Branch: sparse_matrices Commit: 710981bf623314ef9b714396a984aa7d590ab749 URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=710981bf6233… Author: Marco Poletti <poletti.marco(a)gmail.com> Date: Thu Mar 11 13:26:16 2010 +0100 PIP_Tree.cc: split out compatibility_check_find_pivot_in_set() from compatibility_check_find_pivot(). --- src/PIP_Tree.cc | 56 ++++++++++++++++++++++++++++++++++++++++-------------- 1 files changed, 41 insertions(+), 15 deletions(-) diff --git a/src/PIP_Tree.cc b/src/PIP_Tree.cc index bac549a..76e75c3 100644 --- a/src/PIP_Tree.cc +++ b/src/PIP_Tree.cc @@ -549,6 +549,37 @@ row_normalize(PIP_Tree_Node::matrix_row_reference_type x, Coefficient& den) { exact_div_assign(den, den, gcd); } +void +compatibility_check_find_pivot_in_set(std::set<std::pair<dimension_type, + dimension_type> >& + candidates, + const PIP_Tree_Node::matrix_type& s, + const std::vector<dimension_type>& + mapping, + const std::vector<bool>& basis) { + dimension_type pi = s.num_rows(); // pi is the pivot's row index. + dimension_type pj = 0; // pj is the pivot's column index. + typedef std::set<std::pair<dimension_type,dimension_type> > candidates_t; + candidates_t::iterator i = candidates.begin(); + candidates_t::iterator i_end = candidates.end(); + for ( ; i!=i_end; ++i) { + PIP_Tree_Node::matrix_row_const_reference_type s_i = s[i->first]; + // Update pair (pi, pj) if they are still unset or + // if the challenger pair (i, j) is better in the ordering. + if (pj == 0 + || column_lower(s, mapping, basis, + s[pi], pj, s_i, i->second, + s[pi].get(0), s_i.get(0))) { + pi = i->first; + pj = i->second; + } + } + candidates.clear(); + candidates.insert(std::make_pair(pi,pj)); +} + +// Returns false if there isn't a posivive pivot candidate. +// Otherwise, it sets pi, pj to the coordinates of the pivot in s. bool compatibility_check_find_pivot(const PIP_Tree_Node::matrix_type& s, const std::vector<dimension_type>& mapping, @@ -570,19 +601,14 @@ compatibility_check_find_pivot(const PIP_Tree_Node::matrix_type& s, candidates.insert(std::make_pair(i,j)); } } - candidates_t::iterator i = candidates.begin(); - candidates_t::iterator i_end = candidates.end(); - for ( ; i!=i_end; ++i) { - PIP_Tree_Node::matrix_row_const_reference_type s_i = s[i->first]; - // Update pair (pi, pj) if they are still unset or - // if the challenger pair (i, j) is better in the ordering. - if (pj == 0 - || column_lower(s, mapping, basis, - s[pi], pj, s_i, i->second, - s[pi].get(0), s_i.get(0))) { - pi = i->first; - pj = i->second; - } + if (!candidates.empty()) { + compatibility_check_find_pivot_in_set(candidates,s,mapping,basis); + PPL_ASSERT(!candidates.empty()); + pi = candidates.begin()->first; + pj = candidates.begin()->second; + } else { + pi = s.num_rows(); + pj = 0; } return true; @@ -1666,8 +1692,8 @@ PIP_Tree_Node::compatibility_check(matrix_type& s) { // Perform simplex pivots on the context // until we find an empty solution or an optimum. while (true) { - dimension_type pi = num_rows; // pi is the pivot's row index. - dimension_type pj = 0; // pj is the pivot's column index. + dimension_type pi; // pi is the pivot's row index. + dimension_type pj; // pj is the pivot's column index. bool found_positive_pivot_candidate = compatibility_check_find_pivot(s,mapping,basis,pi,pj);

1 0

[GIT] ppl/ppl(sparse_matrices): PIP_Tree.cc: don' t uselessly copy the candidates set in find_lexico_minimum_column_in_set().
by Marco Poletti 11 Mar '10

11 Mar '10

Module: ppl/ppl Branch: sparse_matrices Commit: 6fe8cb08db6d6271010663e0b624eafa2b92221c URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=6fe8cb08db6d… Author: Marco Poletti <poletti.marco(a)gmail.com> Date: Thu Mar 11 13:11:37 2010 +0100 PIP_Tree.cc: don't uselessly copy the candidates set in find_lexico_minimum_column_in_set(). --- src/PIP_Tree.cc | 43 +++++++++++++++++++++++-------------------- 1 files changed, 23 insertions(+), 20 deletions(-) diff --git a/src/PIP_Tree.cc b/src/PIP_Tree.cc index edb0cea..bac549a 100644 --- a/src/PIP_Tree.cc +++ b/src/PIP_Tree.cc @@ -419,30 +419,26 @@ column_lower(const PIP_Tree_Node::matrix_type& tableau, /* Find the column j in revised simplex tableau such as - j is in candidates - (column j) / pivot_row[j] is lexico-minimal + When this function returns, candidates contains the minimum(s) column(s) + index(es). */ -bool -find_lexico_minimum_column_in_set(const std::set<dimension_type>& candidates, +void +find_lexico_minimum_column_in_set(std::set<dimension_type>& candidates, const PIP_Tree_Node::matrix_type& tableau, const std::vector<dimension_type>& mapping, const std::vector<bool>& basis, PIP_Tree_Node:: - matrix_row_const_reference_type pivot_row, - dimension_type& j_out) { - const dimension_type num_cols = tableau.num_columns(); + matrix_row_const_reference_type pivot_row) { const dimension_type num_vars = mapping.size(); - if (candidates.empty()) { - j_out = num_cols; - return false; - } - std::set<dimension_type> current_candidates = candidates; + PPL_ASSERT(!candidates.empty()); for (dimension_type var_index=0; var_index<num_vars; ++var_index) { if (basis[var_index]) continue; const dimension_type row_index = mapping[var_index]; PIP_Tree_Node::matrix_row_const_reference_type row = tableau[row_index]; PIP_Tree_Node::matrix_const_row_const_iterator row_end = row.end(); - std::set<dimension_type>::iterator i = current_candidates.begin(); - std::set<dimension_type>::iterator i_end = current_candidates.end(); + std::set<dimension_type>::iterator i = candidates.begin(); + std::set<dimension_type>::iterator i_end = candidates.end(); PPL_ASSERT(i != i_end); dimension_type min_index = *i; ++i; @@ -457,7 +453,7 @@ find_lexico_minimum_column_in_set(const std::set<dimension_type>& candidates, if (current_itr != row_end) for (++current_itr; current_itr!=row_end; ++current_itr) if ((*current_itr).second != 0) - current_candidates.erase((*current_itr).first); + candidates.erase((*current_itr).first); } else { PPL_ASSERT((*current_itr).first == min_index); PIP_Tree_Node::matrix_const_row_const_iterator last_itr = current_itr; @@ -488,13 +484,11 @@ find_lexico_minimum_column_in_set(const std::set<dimension_type>& candidates, // If min_value < challenger_value, we don't add *i to new_candidates, // so it will be ignored in the next pass. } - std::swap(current_candidates,new_candidates); + std::swap(candidates,new_candidates); } - PPL_ASSERT(!current_candidates.empty()); + PPL_ASSERT(!candidates.empty()); } - PPL_ASSERT(!current_candidates.empty()); - j_out = *(current_candidates.begin()); - return true; + PPL_ASSERT(!candidates.empty()); } /* Find the column j in revised simplex tableau such as @@ -516,8 +510,17 @@ find_lexico_minimum_column(const PIP_Tree_Node::matrix_type& tableau, if (c > 0) candidates.insert(j); } - return find_lexico_minimum_column_in_set(candidates,tableau,mapping,basis, - pivot_row, j_out); + if (candidates.empty()) { + j_out = num_cols; + return false; + } + + find_lexico_minimum_column_in_set(candidates,tableau,mapping,basis, + pivot_row); + PPL_ASSERT(!candidates.empty()); + j_out = *(candidates.begin()); + + return true; } // Divide all coefficients in row x and denominator y by their GCD.

1 0

[GIT] ppl/ppl(sparse_matrices): PIP_Tree.cc: fix indentation.
by Marco Poletti 11 Mar '10

11 Mar '10

Module: ppl/ppl Branch: sparse_matrices Commit: 3489f0659fd755bc5887479f3b70d4765d10b031 URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=3489f0659fd7… Author: Marco Poletti <poletti.marco(a)gmail.com> Date: Thu Mar 11 12:06:08 2010 +0100 PIP_Tree.cc: fix indentation. --- src/PIP_Tree.cc | 9 +++++---- 1 files changed, 5 insertions(+), 4 deletions(-) diff --git a/src/PIP_Tree.cc b/src/PIP_Tree.cc index 3ca256f..edb0cea 100644 --- a/src/PIP_Tree.cc +++ b/src/PIP_Tree.cc @@ -546,10 +546,11 @@ row_normalize(PIP_Tree_Node::matrix_row_reference_type x, Coefficient& den) { exact_div_assign(den, den, gcd); } -bool compatibility_check_find_pivot(const PIP_Tree_Node::matrix_type& s, - const std::vector<dimension_type>& mapping, - const std::vector<bool>& basis, - dimension_type& pi, dimension_type& pj) { +bool +compatibility_check_find_pivot(const PIP_Tree_Node::matrix_type& s, + const std::vector<dimension_type>& mapping, + const std::vector<bool>& basis, + dimension_type& pi, dimension_type& pj) { // Look for a negative RHS (i.e., constant term, stored in column 0), // maximizing pivot column. const dimension_type num_rows = s.num_rows();

1 0

[GIT] ppl/ppl(sparse_matrices): New commits
by Roberto Bagnara 11 Mar '10

11 Mar '10

URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=f5617349a006… Author: Marco Poletti <poletti.marco(a)gmail.com> Date: Thu Mar 11 12:03:08 2010 +0100 PIP_Tree_Node: split out compatibility_check_find_pivot() from compatibility_check() method. URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=8e57fb94d5c3… Author: Marco Poletti <poletti.marco(a)gmail.com> Date: Thu Mar 11 11:37:36 2010 +0100 PIP_Tree.cc: split out find_lexico_minimum_column_in_set() from find_lexico_minimum_column(). URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=02a87e1e21ac… Author: Marco Poletti <poletti.marco(a)gmail.com> Date: Thu Mar 11 11:06:33 2010 +0100 PIP_Tree_Node: refactor method compatibility_check(), preparing it for optimizations. URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=3af59c9d9a26… Author: Marco Poletti <poletti.marco(a)gmail.com> Date: Thu Mar 11 10:54:36 2010 +0100 PIP_Solution_Node: optimize static method row_sign() for sparse rows. URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=be470a72ee88… Author: Marco Poletti <poletti.marco(a)gmail.com> Date: Thu Mar 11 10:51:22 2010 +0100 PIP_Solution_Node::Tableau: optimize is_better_pivot() method for sparse matrices. URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=3fcad58b66e6… Author: Marco Poletti <poletti.marco(a)gmail.com> Date: Thu Mar 11 10:25:28 2010 +0100 PIP_Solution_Node: fix unvalid references in solve() method, when using sparse matrices. URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=447f959b25d7… Author: Marco Poletti <poletti.marco(a)gmail.com> Date: Thu Mar 11 09:36:13 2010 +0100 PIP_Solution_Node::Tableau: optimize normalize() method for sparse matrices. URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=1341d37c9a0d… Author: Marco Poletti <poletti.marco(a)gmail.com> Date: Thu Mar 11 09:20:01 2010 +0100 PIP_Tree_Node: optimize add_constraint() method for sparse rows. URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=27f89cfe8325… Author: Marco Poletti <poletti.marco(a)gmail.com> Date: Thu Mar 11 08:38:46 2010 +0100 PIP_Tree.cc: fix static function find_lexico_minimum_column().

1 0

[GIT] ppl/ppl(sparse_matrices): Unlimited_Sparse_Row: use Coefficient_zero( ) instead of Coefficient(0).
by Marco Poletti 10 Mar '10

10 Mar '10

Module: ppl/ppl Branch: sparse_matrices Commit: 09072c8426f13b3ca4bfff74c9b5b800cf52f5b2 URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=09072c8426f1… Author: Marco Poletti <poletti.marco(a)gmail.com> Date: Wed Mar 10 20:56:31 2010 +0100 Unlimited_Sparse_Row: use Coefficient_zero() instead of Coefficient(0). --- src/Unlimited_Sparse_Row.inlines.hh | 2 +- 1 files changed, 1 insertions(+), 1 deletions(-) diff --git a/src/Unlimited_Sparse_Row.inlines.hh b/src/Unlimited_Sparse_Row.inlines.hh index 66f83c9..ff7ae4b 100644 --- a/src/Unlimited_Sparse_Row.inlines.hh +++ b/src/Unlimited_Sparse_Row.inlines.hh @@ -131,7 +131,7 @@ Unlimited_Sparse_Row::operator[](const dimension_type i) { if (itr->first == i) return itr->second; - itr = data.insert(itr,std::make_pair(i,Coefficient(0))); + itr = data.insert(itr,std::make_pair(i,Coefficient_zero())); return itr->second; }

1 0

[GIT] ppl/ppl(sparse_matrices): Sparse_Row, Unlimited_Sparse_Row, Unlimited_Sparse_Row_Backend_*: use iterator instead of dangerous_iterator when possible.
by Marco Poletti 10 Mar '10

10 Mar '10

Module: ppl/ppl Branch: sparse_matrices Commit: 11bb49819a71df2b105a17fc10e36680f1732a3f URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=11bb49819a71… Author: Marco Poletti <poletti.marco(a)gmail.com> Date: Wed Mar 10 20:54:47 2010 +0100 Sparse_Row, Unlimited_Sparse_Row, Unlimited_Sparse_Row_Backend_*: use iterator instead of dangerous_iterator when possible. --- src/Sparse_Row.defs.hh | 30 +++-- src/Sparse_Row.inlines.hh | 61 +++++++- src/Unlimited_Sparse_Row.cc | 12 +- src/Unlimited_Sparse_Row.defs.hh | 44 ++++-- src/Unlimited_Sparse_Row.inlines.hh | 145 ++++++++++++++----- ...limited_Sparse_Row_Custom_Slist_Backend.defs.hh | 6 +- ...ited_Sparse_Row_Custom_Slist_Backend.inlines.hh | 20 ++- src/Unlimited_Sparse_Row_Std_List_Backend.defs.hh | 3 + ...nlimited_Sparse_Row_Std_List_Backend.inlines.hh | 10 ++ ...Unlimited_Sparse_Row_Std_Vector_Backend.defs.hh | 3 + ...imited_Sparse_Row_Std_Vector_Backend.inlines.hh | 10 ++ 11 files changed, 261 insertions(+), 83 deletions(-) Diff: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commitdiff;h=11bb4981…

1 0

[GIT] ppl/ppl(sparse_matrices): Indentation fixes.
by Marco Poletti 10 Mar '10

10 Mar '10

Module: ppl/ppl Branch: sparse_matrices Commit: d2c5f939e5493f77223848aafdf3c4b2440bbcc1 URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=d2c5f939e549… Author: Marco Poletti <poletti.marco(a)gmail.com> Date: Wed Mar 10 19:07:30 2010 +0100 Indentation fixes. --- src/Dense_Matrix.cc | 90 ++++++++++---------- src/Dense_Matrix.defs.hh | 2 +- src/Dense_Row.defs.hh | 4 +- src/Dense_Row.inlines.hh | 18 ++-- src/MIP_Problem.cc | 14 ++-- src/MIP_Problem.defs.hh | 48 +++++----- src/PIP_Tree.cc | 6 +- src/Sparse_Matrix.cc | 4 +- src/Sparse_Matrix.inlines.hh | 10 +- src/Sparse_Row.inlines.hh | 24 +++--- src/Unlimited_Sparse_Row.cc | 4 +- src/Unlimited_Sparse_Row.defs.hh | 2 +- ...imited_Sparse_Row_Std_Vector_Backend.inlines.hh | 3 +- 13 files changed, 117 insertions(+), 112 deletions(-) Diff: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commitdiff;h=d2c5f939…

1 0

[GIT] ppl/ppl(master): Improved checks in PIP_Decision_Node::OK() method.
by Enea Zaffanella 10 Mar '10

10 Mar '10

Module: ppl/ppl Branch: master Commit: ed91bdf10a46c8a1c886a2f05986e4d90db5f136 URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=ed91bdf10a46… Author: Enea Zaffanella <zaffanella(a)cs.unipr.it> Date: Wed Mar 10 18:29:05 2010 +0100 Improved checks in PIP_Decision_Node::OK() method. There is no reason to have Artificial_Parameter::OK() inlined. Added a couple of comments on code that should be normally unreachable. --- src/PIP_Tree.cc | 141 ++++++++++++++++++++++++++++------------------- src/PIP_Tree.inlines.hh | 13 ---- 2 files changed, 85 insertions(+), 69 deletions(-) diff --git a/src/PIP_Tree.cc b/src/PIP_Tree.cc index 79d254e..f2a06dc 100644 --- a/src/PIP_Tree.cc +++ b/src/PIP_Tree.cc @@ -332,6 +332,18 @@ PIP_Tree_Node::Artificial_Parameter return !operator==(y); } +bool +PIP_Tree_Node::Artificial_Parameter::OK() const { + if (denom <= 0) { +#ifndef NDEBUG + std::cerr << "PIP_Tree_Node::Artificial_Parameter " + << "has a non-positive denominator.\n"; +#endif + return false; + } + return true; +} + void PIP_Tree_Node::Artificial_Parameter::ascii_dump(std::ostream& s) const { s << "artificial_parameter "; @@ -639,8 +651,6 @@ PIP_Solution_Node::OK() const { bool PIP_Decision_Node::OK() const { - /* FIXME: finish me! */ - // Perform base class well-formedness check on this node. if (!PIP_Tree_Node::OK()) return false; @@ -651,6 +661,14 @@ PIP_Decision_Node::OK() const { if (true_child && !true_child->OK()) return false; + // Decision nodes should always have a true child. + if (!true_child) { +#ifndef NDEBUG + std::cerr << "PIP_Decision_Node with no 'true' child.\n"; +#endif + return false; + } + // Decision nodes with a false child must have exactly one constraint. if (false_child) { dimension_type @@ -717,59 +735,59 @@ PIP_Decision_Node::solve(const PIP_Problem& pip, context_false, all_params, space_dim); } - if (true_child != 0 || false_child != 0) { - PIP_Tree_Node* node = this; - if (has_false_child && false_child == 0) { - // False child has become unfeasible: merge this node's artificials with - // the true child, while removing the local parameter constraints, which - // are no longer discriminative. + if (true_child == 0 && false_child == 0) { + // No childs: the whole subtree is unfeasible. + delete this; + return 0; + } + + PIP_Tree_Node* node = this; + if (has_false_child && false_child == 0) { + // False child has become unfeasible: merge this node's artificials with + // the true child, while removing the local parameter constraints, which + // are no longer discriminative. + true_child->parent_merge(); + true_child->set_parent(parent()); + node = true_child; + true_child = 0; + delete this; + } + else if (has_true_child && true_child == 0) { + // True child has become unfeasible: merge this node's artificials + // with the false child. + false_child->parent_merge(); + false_child->set_parent(parent()); + node = false_child; + false_child = 0; + delete this; + } + else if (check_feasible_context) { + // Test all constraints for redundancy with the context, and eliminate + // them if not necessary. + Constraint_System cs; + cs.swap(constraints_); + const Constraint_System::const_iterator end = cs.end(); + for (Constraint_System::const_iterator ci = cs.begin(); ci != end; ++ci) { + Matrix ctx_copy(context); + merge_assign(ctx_copy, Constraint_System(*ci), all_params); + Row& last = ctx_copy[ctx_copy.num_rows()-1]; + complement_assign(last, last, 1); + if (compatibility_check(ctx_copy)) { + // The constraint is not redundant with the context: we must keep it. + constraints_.insert(*ci); + } + } + // If the constraints set has become empty, only keep the true child. + if (constraints_.empty()) { true_child->parent_merge(); true_child->set_parent(parent()); node = true_child; true_child = 0; delete this; } - else if (has_true_child && true_child == 0) { - // True child has become unfeasible: merge this node's artificials - // with the false child. - false_child->parent_merge(); - false_child->set_parent(parent()); - node = false_child; - false_child = 0; - delete this; - } - else if (check_feasible_context) { - // Test all constraints for redundancy with the context, and eliminate - // them if not necessary. - Constraint_System cs; - cs.swap(constraints_); - const Constraint_System::const_iterator end = cs.end(); - for (Constraint_System::const_iterator ci = cs.begin(); ci != end; ++ci) { - Matrix ctx_copy(context); - merge_assign(ctx_copy, Constraint_System(*ci), all_params); - Row& last = ctx_copy[ctx_copy.num_rows()-1]; - complement_assign(last, last, 1); - if (compatibility_check(ctx_copy)) { - // The constraint is not redundant with the context: we must keep it. - constraints_.insert(*ci); - } - } - // If the constraints set has become empty, only keep the true child. - if (constraints_.empty()) { - true_child->parent_merge(); - true_child->set_parent(parent()); - node = true_child; - true_child = 0; - delete this; - } - } - PPL_ASSERT(node->OK()); - return node; - } - else { - delete this; - return 0; } + PPL_ASSERT(node->OK()); + return node; } void @@ -779,8 +797,12 @@ PIP_Decision_Node::ascii_dump(std::ostream& s) const { // Dump true child (if any). s << "\ntrue_child: "; - if (true_child == 0) + if (true_child == 0) { + // Note: this branch should normally be unreachable code, since a + // well-formed decision node always has a true child. We keep this code + // for debugging purposes (since we want to dump broken nodes). s << "BOTTOM\n"; + } else if (const PIP_Decision_Node* dec = true_child->as_decision()) { s << "DECISION\n"; dec->ascii_dump(s); @@ -797,6 +819,11 @@ PIP_Decision_Node::ascii_dump(std::ostream& s) const { if (false_child == 0) s << "BOTTOM\n"; else if (const PIP_Decision_Node* dec = false_child->as_decision()) { + // Note: this branch should normally be unreachable code. + // Since a well-formed decision node having a false child should have + // a single context constraint, its false child will have no context + // constraints at all, so that no further branch is possible. + // We keep this code for debugging purposes. s << "DECISION\n"; dec->ascii_dump(s); } @@ -826,6 +853,7 @@ PIP_Decision_Node::ascii_load(std::istream& s) { if (!(s >> str)) return false; if (str == "BOTTOM") + // Note: normally unreachable code (see comment on ascii_dump). true_child = 0; else if (str == "DECISION") { PIP_Decision_Node* dec = new PIP_Decision_Node(0, 0, 0); @@ -855,6 +883,7 @@ PIP_Decision_Node::ascii_load(std::istream& s) { if (str == "BOTTOM") false_child = 0; else if (str == "DECISION") { + // Note: normally unreachable code (see comment on ascii_dump). PIP_Decision_Node* dec = new PIP_Decision_Node(0, 0, 0); false_child = dec; if (!dec->ascii_load(s)) @@ -1015,7 +1044,8 @@ PIP_Tree_Node::ascii_load(std::istream& s) { artificial_parameters.push_back(ap); } - PPL_ASSERT(OK()); + // Note: do not assert OK() here. + // The node invariants should be checked on derived nodes. return true; } @@ -1055,6 +1085,7 @@ PIP_Solution_Node::Tableau::ascii_load(std::istream& st) { return false; if (!t.ascii_load(st)) return false; + PPL_ASSERT(OK()); return true; } @@ -2502,8 +2533,8 @@ PIP_Tree_Node::external_memory_in_bytes() const { memory_size_type PIP_Decision_Node::external_memory_in_bytes() const { memory_size_type n = PIP_Tree_Node::external_memory_in_bytes(); - if (true_child) - n += true_child->total_memory_in_bytes(); + PPL_ASSERT(true_child != 0); + n += true_child->total_memory_in_bytes(); if (false_child) n += false_child->total_memory_in_bytes(); return n; @@ -2610,10 +2641,8 @@ PIP_Decision_Node::print_tree(std::ostream& s, unsigned indent, // Then print info specific of decision nodes. dimension_type child_first_art_dim = first_art_dim + art_parameter_count(); - if (true_child) - true_child->print_tree(s, indent+1, pip_dim_is_param, child_first_art_dim); - else - indent_and_print(s, indent+1, "_|_\n"); + PPL_ASSERT(true_child != 0); + true_child->print_tree(s, indent+1, pip_dim_is_param, child_first_art_dim); indent_and_print(s, indent, "else\n"); diff --git a/src/PIP_Tree.inlines.hh b/src/PIP_Tree.inlines.hh index 18a27d0..159b5c1 100644 --- a/src/PIP_Tree.inlines.hh +++ b/src/PIP_Tree.inlines.hh @@ -102,19 +102,6 @@ PIP_Decision_Node::child_node(bool v) { return v ? true_child : false_child; } - -inline bool -PIP_Tree_Node::Artificial_Parameter::OK() const { - if (denom <= 0) { -#ifndef NDEBUG - std::cerr << "PIP_Tree_Node::Artificial_Parameter " - << "has a non-positive denominator.\n"; -#endif - return false; - } - return true; -} - inline PIP_Tree_Node::Artificial_Parameter::Artificial_Parameter() : Linear_Expression(), denom(1) {

1 0

[GIT] ppl/ppl(master): Fixed documentation reference.
by Enea Zaffanella 10 Mar '10

10 Mar '10

Module: ppl/ppl Branch: master Commit: 61b4c1817137f7ffcf2d996e1aee6aea4f32d2bf URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=61b4c1817137… Author: Enea Zaffanella <zaffanella(a)cs.unipr.it> Date: Wed Mar 10 18:27:08 2010 +0100 Fixed documentation reference. --- interfaces/C/ppl_c_header.h | 2 +- 1 files changed, 1 insertions(+), 1 deletions(-) diff --git a/interfaces/C/ppl_c_header.h b/interfaces/C/ppl_c_header.h index 403a3ce..d899321 100644 --- a/interfaces/C/ppl_c_header.h +++ b/interfaces/C/ppl_c_header.h @@ -734,7 +734,7 @@ PPL_TYPE_DECLARATION(PIP_Solution_Node) The types and functions for PIP artificial parameters provide an interface towards - \extref{Parma_Polyhedra_Library::Artificial_Parameter, Artificial_Parameter}. + \extref{Parma_Polyhedra_Library::PIP_Tree_Node::Artificial_Parameter, Artificial_Parameter}. */ PPL_TYPE_DECLARATION(Artificial_Parameter) PPL_TYPE_DECLARATION(Artificial_Parameter_Sequence)

1 0