January 2010 - PPL-devel - BUGSENG Mailman

Problems with test suite on alpha
by Michael Tautschnig 09 Sep '10

09 Sep '10

Hi PPL developers, I've reported problems with some test cases because of suspected gcc bugs on alpha earlier already. Now it seems that even more test cases are broken, most probably because of the very same bug (I suspect it to be http://gcc.gnu.org/bugzilla/show_bug.cgi?id=8966). My question now is: How to proceed? Shall I specifically disable the failing test cases by surrounding them with an #ifndef __alpha__ or disable the entire test suite on alpha? Thanks, Michael

2 6

[GIT] ppl/ppl(pip): Improved method PIP_Solution_Node::::parametric_values( ).
by Enea Zaffanella 31 Jan '10

31 Jan '10

Module: ppl/ppl Branch: pip Commit: 85c05c902ae1f0e620be68f1b2bbae1bf072aaaa URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=85c05c902ae1… Author: Enea Zaffanella <zaffanella(a)cs.unipr.it> Date: Sun Jan 31 22:21:51 2010 +0100 Improved method PIP_Solution_Node::::parametric_values(). --- src/PIP_Tree.cc | 33 ++++++++++++++++----------------- 1 files changed, 16 insertions(+), 17 deletions(-) diff --git a/src/PIP_Tree.cc b/src/PIP_Tree.cc index 7abb188..61ab579 100644 --- a/src/PIP_Tree.cc +++ b/src/PIP_Tree.cc @@ -772,7 +772,7 @@ PIP_Tree_Node::ascii_dump(std::ostream& s) const { constraints_.ascii_dump(s); dimension_type artificial_parameters_size = artificial_parameters.size(); s << "\nartificial_parameters( " << artificial_parameters_size << " )\n"; - for (dimension_type i=0; i<artificial_parameters_size; ++i) + for (dimension_type i = 0; i < artificial_parameters_size; ++i) artificial_parameters[i].ascii_dump(s); } @@ -1039,32 +1039,31 @@ PIP_Solution_Node::ascii_load(std::istream& s) { const Linear_Expression& PIP_Solution_Node -::parametric_values(Variable v, +::parametric_values(const Variable var, const Variables_Set& parameters) const { Variables_Set all_parameters(parameters); // Complete the parameter set with artificials. insert_artificials(all_parameters, tableau.s.num_columns() + tableau.t.num_columns() - 1); + { + PIP_Solution_Node& x = const_cast<PIP_Solution_Node&>(*this); + x.update_solution(all_parameters); + } - const_cast<PIP_Solution_Node&>(*this).update_solution(all_parameters); - dimension_type id = v.id(); - dimension_type j; - Variables_Set::iterator location = all_parameters.lower_bound(id); - if (location == all_parameters.end()) - j = id; + const Variables_Set::iterator pos = all_parameters.lower_bound(var.id()); + if (pos == all_parameters.end()) + return solution[var.id()]; else { - if (*location == id) { #ifndef NDEBUG + if (*pos == var.id()) { std::cerr << "PIP_Solution_Node::parametric_values(Variable): " - "Supplied Variable corresponds to a parameter" - << std::endl; -#endif - j = not_a_dimension(); - } else - j = id - std::distance(all_parameters.begin(),location); + << "Supplied Variable corresponds to a parameter.\n"; + PPL_ASSERT(false); + } +#endif // #ifndef NDEBUG + const dimension_type dist = std::distance(all_parameters.begin(), pos); + return solution[var.id() - dist]; } - - return solution[j]; } PIP_Solution_Node::Row_Sign

1 0

[GIT] ppl/ppl(pip): Stylistic improvements to Tableau methods normalize() and scale().
by Enea Zaffanella 31 Jan '10

31 Jan '10

Module: ppl/ppl Branch: pip Commit: 2e6d5a18fb1e1bc5b702e8a3f59d291b9cc9a69b URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=2e6d5a18fb1e… Author: Enea Zaffanella <zaffanella(a)cs.unipr.it> Date: Sun Jan 31 21:59:21 2010 +0100 Stylistic improvements to Tableau methods normalize() and scale(). --- src/PIP_Tree.cc | 112 ++++++++++++++++++++++++++----------------------------- 1 files changed, 53 insertions(+), 59 deletions(-) diff --git a/src/PIP_Tree.cc b/src/PIP_Tree.cc index b26cfb9..7abb188 100644 --- a/src/PIP_Tree.cc +++ b/src/PIP_Tree.cc @@ -234,17 +234,17 @@ row_normalize(Row& x, Coefficient& den) { PPL_DIRTY_TEMP_COEFFICIENT(gcd); gcd = den; for (dimension_type i = x_size; i-- > 0; ) { - const Coefficient& c = x[i]; - if (c != 0) { - gcd_assign(gcd, c, gcd); + const Coefficient& x_i = x[i]; + if (x_i != 0) { + gcd_assign(gcd, x_i, gcd); if (gcd == 1) return; } } // Divide the coefficients by the GCD. for (dimension_type i = x_size; i-- > 0; ) { - Coefficient& c = x[i]; - exact_div_assign(c, c, gcd); + Coefficient& x_i = x[i]; + exact_div_assign(x_i, x_i, gcd); } // Divide the denominator by the GCD. exact_div_assign(den, den, gcd); @@ -478,12 +478,12 @@ PIP_Tree_Node::OK() const { using std::endl; using std::cerr; #endif - Constraint_System::const_iterator begin = constraints_.begin(); - Constraint_System::const_iterator end = constraints_.end(); + const Constraint_System::const_iterator begin = constraints_.begin(); + const Constraint_System::const_iterator end = constraints_.end(); // Parameter constraint system should contain no strict inequalities. - for (Constraint_System::const_iterator c = begin; c != end; c++) - if (c->is_strict_inequality()) { + for (Constraint_System::const_iterator ci = begin; ci != end; ++ci) + if (ci->is_strict_inequality()) { #ifndef NDEBUG cerr << "The feasible region of the PIP_Problem parameter context" << "is defined by a constraint system containing strict " @@ -514,7 +514,6 @@ PIP_Tree_Node bool PIP_Solution_Node::OK() const { #ifndef NDEBUG - using std::endl; using std::cerr; #endif if (!PIP_Tree_Node::OK()) @@ -529,8 +528,7 @@ PIP_Solution_Node::OK() const { if (basis.size() != mapping.size()) { #ifndef NDEBUG cerr << "The PIP_Solution_Node::basis and PIP_Solution_Node::mapping " - << "vectors do not have the same number of elements." - << endl; + << "vectors do not have the same number of elements.\n"; #endif return false; } @@ -538,8 +536,7 @@ PIP_Solution_Node::OK() const { #ifndef NDEBUG cerr << "The sum of number of elements in the PIP_Solution_Node::var_row " << "and PIP_Solution_Node::var_column vectors is different from the " - << "number of elements in the PIP_Solution_Node::basis vector." - << endl; + << "number of elements in the PIP_Solution_Node::basis vector.\n"; #endif return false; } @@ -547,8 +544,7 @@ PIP_Solution_Node::OK() const { #ifndef NDEBUG cerr << "The number of elements in the PIP_Solution_Node::var_column " << "vector is different from the number of columns in the " - << "PIP_Solution_Node::tableau.s Matrix." - << endl; + << "PIP_Solution_Node::tableau.s Matrix.\n"; #endif return false; } @@ -556,19 +552,17 @@ PIP_Solution_Node::OK() const { #ifndef NDEBUG cerr << "The number of elements in the PIP_Solution_Node::var_row " << "vector is different from the number of rows in the " - << "PIP_Solution_Node::tableau.s Matrix." - << endl; + << "PIP_Solution_Node::tableau.s Matrix.\n"; #endif return false; } for (dimension_type i = mapping.size(); i-- > 0; ) { - dimension_type rowcol = mapping[i]; + const dimension_type rowcol = mapping[i]; if (basis[i] && var_column[rowcol] != i) { #ifndef NDEBUG cerr << "Variable " << i << " is basic and corresponds to column " << rowcol << " but PIP_Solution_Node::var_column[" << rowcol - << "] does not correspond to variable " << i << "." - << endl; + << "] does not correspond to variable " << i << ".\n"; #endif return false; } @@ -576,13 +570,12 @@ PIP_Solution_Node::OK() const { #ifndef NDEBUG cerr << "Variable " << i << " is nonbasic and corresponds to row " << rowcol << " but PIP_Solution_Node::var_row[" << rowcol - << "] does not correspond to variable " << i << "." - << endl; + << "] does not correspond to variable " << i << ".\n"; #endif return false; } } - + // All checks passed. return true; } @@ -679,61 +672,62 @@ void PIP_Solution_Node::Tableau::normalize() { if (denominator == 1) return; - dimension_type i_max = s.num_rows(); - dimension_type j_max = s.num_columns(); - dimension_type k_max = t.num_columns(); - dimension_type i, j, k; + + const dimension_type num_rows = s.num_rows(); + const dimension_type s_cols = s.num_columns(); + const dimension_type t_cols = t.num_columns(); + + // Compute global gcd. PPL_DIRTY_TEMP_COEFFICIENT(gcd); gcd = denominator; - - for (i=0; i<i_max; ++i) { - const Row& row_s = s[i]; - for (j=0; j<j_max; ++j) { - const Coefficient& x = row_s[j]; - if (x != 0) { - gcd_assign(gcd, x, gcd); + for (dimension_type i = num_rows; i-- > 0; ) { + const Row& s_i = s[i]; + for (dimension_type j = s_cols; j-- > 0; ) { + const Coefficient& s_ij = s_i[j]; + if (s_ij != 0) { + gcd_assign(gcd, s_ij, gcd); if (gcd == 1) return; } } - const Row& row_t = t[i]; - for (k=0; k<k_max; ++k) { - const Coefficient& x = row_t[k]; - if (x != 0) { - gcd_assign(gcd, x, gcd); + const Row& t_i = t[i]; + for (dimension_type j = t_cols; j-- > 0; ) { + const Coefficient& t_ij = t_i[j]; + if (t_ij != 0) { + gcd_assign(gcd, t_ij, gcd); if (gcd == 1) return; } } } - // Divide the coefficients by the GCD. - for (i=0; i<i_max; ++i) { - Row& row_s = s[i]; - for (j=0; j<j_max; ++j) { - Coefficient& x = row_s[j]; - exact_div_assign(x, x, gcd); + PPL_ASSERT(gcd > 1); + // Normalize all coefficients. + for (dimension_type i = num_rows; i-- > 0; ) { + Row& s_i = s[i]; + for (dimension_type j = s_cols; j-- > 0; ) { + Coefficient& s_ij = s_i[j]; + exact_div_assign(s_ij, s_ij, gcd); } - Row& row_t = t[i]; - for (k=0; k<k_max; ++k) { - Coefficient& x = row_t[k]; - exact_div_assign(x, x, gcd); + Row& t_i = t[i]; + for (dimension_type j = t_cols; j-- > 0; ) { + Coefficient& t_ij = t_i[j]; + exact_div_assign(t_ij, t_ij, gcd); } } + // Normalize denominator. exact_div_assign(denominator, denominator, gcd); } void PIP_Solution_Node::Tableau::scale(Coefficient_traits::const_reference ratio) { - dimension_type i, j, k; - dimension_type i_max = s.num_rows(); - dimension_type j_max = s.num_columns(); - dimension_type k_max = t.num_columns(); - for (i=0; i<i_max; ++i) { - for (j=0; j<j_max; ++j) - s[i][j] *= ratio; - for (k=0; k<k_max; ++k) - t[i][k] *= ratio; + for (dimension_type i = s.num_rows(); i-- > 0; ) { + Row& s_i = s[i]; + for (dimension_type j = s.num_columns(); j-- > 0; ) + s_i[j] *= ratio; + Row& t_i = t[i]; + for (dimension_type j = t.num_columns(); j-- > 0; ) + t_i[j] *= ratio; } denominator *= ratio; }

1 0

[GIT] ppl/ppl(pip): A few more stylistic improvements.
by Enea Zaffanella 31 Jan '10

31 Jan '10

Module: ppl/ppl Branch: pip Commit: c1f10d956a03ff30b0c5ba08e199c9b238155344 URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=c1f10d956a03… Author: Enea Zaffanella <zaffanella(a)cs.unipr.it> Date: Sun Jan 31 21:36:40 2010 +0100 A few more stylistic improvements. --- src/PIP_Tree.cc | 109 ++++++++++++++++++++++++++++--------------------------- 1 files changed, 55 insertions(+), 54 deletions(-) Diff: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commitdiff;h=c1f10d95…

1 0

[GIT] ppl/ppl(pip): Several improvements to PIP_Solution_Node::generate_cut ().
by Enea Zaffanella 31 Jan '10

31 Jan '10

Module: ppl/ppl Branch: pip Commit: a30d0933cfa193dfb981bf714dc0442c85dd5175 URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=a30d0933cfa1… Author: Enea Zaffanella <zaffanella(a)cs.unipr.it> Date: Sun Jan 31 19:36:12 2010 +0100 Several improvements to PIP_Solution_Node::generate_cut(). Added method OK() to Artificial_Parameter. --- src/PIP_Tree.cc | 235 ++++++++++++++++++++++------------------------ src/PIP_Tree.defs.hh | 3 + src/PIP_Tree.inlines.hh | 39 ++++++++ 3 files changed, 154 insertions(+), 123 deletions(-) Diff: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commitdiff;h=a30d0933…

1 0

[GIT] ppl/ppl(pip): Further optimization to helper function column_lower().
by Enea Zaffanella 31 Jan '10

31 Jan '10

Module: ppl/ppl Branch: pip Commit: 353f9b79d1079e7485f904d5ddacbdafc5195a10 URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=353f9b79d107… Author: Enea Zaffanella <zaffanella(a)cs.unipr.it> Date: Sun Jan 31 16:19:41 2010 +0100 Further optimization to helper function column_lower(). --- src/PIP_Tree.cc | 55 ++++++++++++++++++++++++++++++++++--------------------- 1 files changed, 34 insertions(+), 21 deletions(-) diff --git a/src/PIP_Tree.cc b/src/PIP_Tree.cc index 8a3fad3..a7c173b 100644 --- a/src/PIP_Tree.cc +++ b/src/PIP_Tree.cc @@ -152,36 +152,49 @@ column_lower(const Matrix& tableau, return lhs_coeff > rhs_coeff; } - PPL_DIRTY_TEMP_COEFFICIENT(cij_a); - PPL_DIRTY_TEMP_COEFFICIENT(cij_b); PPL_DIRTY_TEMP_COEFFICIENT(lhs); PPL_DIRTY_TEMP_COEFFICIENT(rhs); const dimension_type num_vars = mapping.size(); dimension_type k = 0; - do { + // While loop guard is: (k < num_rows && lhs == rhs). + // Return value is false, if k >= num_rows; lhs < rhs, otherwise. + // Try to optimize the computation of lhs and rhs. + while (true) { const dimension_type mk = mapping[k]; - if (basis[k]) { + const bool in_base = basis[k]; + if (++k >= num_vars) + return false; + if (in_base) { // Reconstitute the identity submatrix part of tableau. - cij_a = (mk == ja) ? 1 : 0; - cij_b = (mk == jb) ? 1 : 0; + if (mk == ja) { + // Optimizing for: lhs == lhs_coeff && rhs == 0; + if (lhs_coeff == 0) + continue; + else + return lhs_coeff > 0; + } + if (mk == jb) { + // Optimizing for: lhs == 0 && rhs == rhs_coeff; + if (rhs_coeff == 0) + continue; + else + return 0 > rhs_coeff; + } + // Optimizing for: lhs == 0 && rhs == 0; + continue; } else { + // Not in base. const Row& t_mk = tableau[mk]; - cij_a = t_mk[ja]; - cij_b = t_mk[jb]; + lhs = lhs_coeff * t_mk[ja]; + rhs = rhs_coeff * t_mk[jb]; + if (lhs == rhs) + continue; + else + return lhs > rhs; } - ++k; - // Optimizing computation of while guard (and return value): - // (k < num_vars && cij_a * cst_a * sij_b == cij_b * cst_b * sij_a) - if (k == num_vars) - return false; - lhs = cij_a * lhs_coeff; - rhs = cij_b * rhs_coeff; - } while (lhs == rhs); - - // Optimizing computation of return value: - // return k < num_vars && cij_a * cst_a * sij_b > cij_b * cst_b * sij_a; - assert(k < num_vars); - return lhs > rhs; + } + // This point should be unreachable. + throw std::runtime_error("PPL internal error"); } /* Find the column j in revised simplex tableau such as

1 0

[GIT] ppl/ppl(pip): Several minor stylistic improvements.
by Enea Zaffanella 31 Jan '10

31 Jan '10

Module: ppl/ppl Branch: pip Commit: af2068fb4971617c277cc0da51ee2590b6b894b2 URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=af2068fb4971… Author: Enea Zaffanella <zaffanella(a)cs.unipr.it> Date: Sun Jan 31 00:07:27 2010 +0100 Several minor stylistic improvements. --- src/PIP_Tree.cc | 84 ++++++++++++++++++++++++------------------------- src/PIP_Tree.defs.hh | 32 +++++++++--------- 2 files changed, 57 insertions(+), 59 deletions(-) diff --git a/src/PIP_Tree.cc b/src/PIP_Tree.cc index 8958d0d..8a3fad3 100644 --- a/src/PIP_Tree.cc +++ b/src/PIP_Tree.cc @@ -256,10 +256,10 @@ PIP_Tree_Node::PIP_Tree_Node() artificial_parameters() { } -PIP_Tree_Node::PIP_Tree_Node(const PIP_Tree_Node &x) - : parent_(0), - constraints_(x.constraints_), - artificial_parameters(x.artificial_parameters) { +PIP_Tree_Node::PIP_Tree_Node(const PIP_Tree_Node& y) + : parent_(0), // Parent is not copied. + constraints_(y.constraints_), + artificial_parameters(y.artificial_parameters) { } PIP_Tree_Node::Artificial_Parameter::Artificial_Parameter() @@ -273,13 +273,12 @@ PIP_Tree_Node::Artificial_Parameter } PIP_Tree_Node::Artificial_Parameter -::Artificial_Parameter(const Artificial_Parameter &x) - : Linear_Expression(x), denominator(x.denominator) { +::Artificial_Parameter(const Artificial_Parameter& y) + : Linear_Expression(y), denominator(y.denominator) { } -const Coefficient& -PIP_Tree_Node::Artificial_Parameter -::get_denominator() const { +Coefficient_traits::const_reference +PIP_Tree_Node::Artificial_Parameter::get_denominator() const { return denominator; } @@ -319,8 +318,7 @@ PIP_Tree_Node::Artificial_Parameter::ascii_load(std::istream& s) { PIP_Decision_Node::~PIP_Decision_Node() { delete true_child; - if (false_child) - delete false_child; + delete false_child; } PIP_Solution_Node::~PIP_Solution_Node() { @@ -340,36 +338,36 @@ PIP_Solution_Node::PIP_Solution_Node() solution_valid(false) { } -PIP_Solution_Node::PIP_Solution_Node(const PIP_Solution_Node &x) - : PIP_Tree_Node(x), - tableau(x.tableau), - basis(x.basis), - mapping(x.mapping), - var_row(x.var_row), - var_column(x.var_column), - special_equality_row(x.special_equality_row), - big_dimension(x.big_dimension), - sign(x.sign), - solution(x.solution), - solution_valid(x.solution_valid) { +PIP_Solution_Node::PIP_Solution_Node(const PIP_Solution_Node& y) + : PIP_Tree_Node(y), + tableau(y.tableau), + basis(y.basis), + mapping(y.mapping), + var_row(y.var_row), + var_column(y.var_column), + special_equality_row(y.special_equality_row), + big_dimension(y.big_dimension), + sign(y.sign), + solution(y.solution), + solution_valid(y.solution_valid) { } -PIP_Solution_Node::PIP_Solution_Node(const PIP_Solution_Node &x, +PIP_Solution_Node::PIP_Solution_Node(const PIP_Solution_Node& y, bool empty_constraints) : PIP_Tree_Node(), - tableau(x.tableau), - basis(x.basis), - mapping(x.mapping), - var_row(x.var_row), - var_column(x.var_column), - special_equality_row(x.special_equality_row), - big_dimension(x.big_dimension), - sign(x.sign), - solution(x.solution), - solution_valid(x.solution_valid) { + tableau(y.tableau), + basis(y.basis), + mapping(y.mapping), + var_row(y.var_row), + var_column(y.var_column), + special_equality_row(y.special_equality_row), + big_dimension(y.big_dimension), + sign(y.sign), + solution(y.solution), + solution_valid(y.solution_valid) { if (!empty_constraints) { - constraints_ = x.constraints_; - artificial_parameters = x.artificial_parameters; + constraints_ = y.constraints_; + artificial_parameters = y.artificial_parameters; } } @@ -384,16 +382,16 @@ PIP_Decision_Node::PIP_Decision_Node(PIP_Tree_Node* fcp, tcp->set_parent(this); } -PIP_Decision_Node ::PIP_Decision_Node(const PIP_Decision_Node& x) - : PIP_Tree_Node(x), +PIP_Decision_Node ::PIP_Decision_Node(const PIP_Decision_Node& y) + : PIP_Tree_Node(y), true_child(0), false_child(0) { - if (x.true_child != 0) { - true_child = x.true_child->clone(); + if (y.true_child != 0) { + true_child = y.true_child->clone(); true_child->set_parent(this); } - if (x.false_child != 0) { - false_child = x.false_child->clone(); + if (y.false_child != 0) { + false_child = y.false_child->clone(); false_child->set_parent(this); } } @@ -1053,7 +1051,7 @@ PIP_Solution_Node::ascii_load(std::istream& s) { const Linear_Expression& PIP_Solution_Node -::parametric_values(const Variable &v, +::parametric_values(Variable v, const Variables_Set& parameters) const { Variables_Set all_parameters(parameters); // Complete the parameter set with artificials. diff --git a/src/PIP_Tree.defs.hh b/src/PIP_Tree.defs.hh index 9c07242..19d83fc 100644 --- a/src/PIP_Tree.defs.hh +++ b/src/PIP_Tree.defs.hh @@ -46,7 +46,7 @@ protected: PIP_Tree_Node(); //! Copy constructor. - PIP_Tree_Node(const PIP_Tree_Node &x); + PIP_Tree_Node(const PIP_Tree_Node& y); public: //! Returns a pointer to a dynamically-allocated copy of \p *this. @@ -90,9 +90,9 @@ public: class Artificial_Parameter : public Linear_Expression { public: Artificial_Parameter(); - Artificial_Parameter(const Linear_Expression &e, + Artificial_Parameter(const Linear_Expression& e, Coefficient_traits::const_reference d); - Artificial_Parameter(const Artificial_Parameter &x); + Artificial_Parameter(const Artificial_Parameter& y); Coefficient_traits::const_reference get_denominator() const; @@ -167,7 +167,7 @@ protected: \return the number of inserted artificial parameters. */ - dimension_type insert_artificials(Variables_Set &params, + dimension_type insert_artificials(Variables_Set& params, dimension_type space_dimension) const; /*! \brief @@ -192,8 +192,8 @@ protected: virtual void update_tableau(const PIP_Problem& problem, dimension_type external_space_dim, dimension_type first_pending_constraint, - const Constraint_Sequence &input_cs, - const Variables_Set &parameters) = 0; + const Constraint_Sequence& input_cs, + const Variables_Set& parameters) = 0; /*! \brief Execute a parametric simplex on the tableau, under specified context. @@ -224,7 +224,7 @@ protected: dimension_type space_dimension) = 0; //! Inserts a new parametric constraint in internal Row format - void add_constraint(const Row &x, const Variables_Set& parameters); + void add_constraint(const Row& x, const Variables_Set& parameters); }; // class PIP_Tree_Node @@ -267,7 +267,7 @@ public: or if \p v is a parameter. */ const Linear_Expression& - parametric_values(const Variable &v, + parametric_values(Variable v, const Variables_Set& parameters) const; void ascii_dump(std::ostream& s) const; @@ -286,7 +286,7 @@ private: //! Default constructor. Tableau(); //! Copy constructor. - Tableau(const Tableau& x); + Tableau(const Tableau& y); //! Destructor. ~Tableau(); @@ -462,7 +462,7 @@ private: bool solution_valid; //! Determines the sign of given Row. - static Row_Sign row_sign(const Row &x, dimension_type big_dimension); + static Row_Sign row_sign(const Row& x, dimension_type big_dimension); /*! \brief Checks whether a constraint is compatible with a context, ie. does not @@ -476,17 +476,17 @@ private: The algorithm ensures the feasible solutions are integer, by applying a cut generation method when intermediate non-integer solutions are found. */ - static bool compatibility_check(const Matrix &ctx, const Row &cnst); + static bool compatibility_check(const Matrix& ctx, const Row& cnst); protected: //! Copy constructor. - PIP_Solution_Node(const PIP_Solution_Node &x); + PIP_Solution_Node(const PIP_Solution_Node& y); /*! \brief Copy constructor, allowing not to copy the constraint system and artificial parameters */ - PIP_Solution_Node(const PIP_Solution_Node &x, bool empty_constraints); + PIP_Solution_Node(const PIP_Solution_Node& y, bool empty_constraints); /*! \brief Populates the parametric simplex tableau using external data, if necessary @@ -628,7 +628,7 @@ private: protected: //! Copy constructor. - PIP_Decision_Node(const PIP_Decision_Node &x); + PIP_Decision_Node(const PIP_Decision_Node& y); /*! \brief Populates the parametric simplex tableau using external data, if necessary @@ -652,8 +652,8 @@ protected: virtual void update_tableau(const PIP_Problem& problem, dimension_type external_space_dim, dimension_type first_pending_constraint, - const Constraint_Sequence &input_cs, - const Variables_Set &parameters); + const Constraint_Sequence& input_cs, + const Variables_Set& parameters); /*! \brief Execute a parametric simplex on the tableau, under specified context.

1 0

[GIT] ppl/ppl(pip): Prefer C++ named casts to C style casts.
by Enea Zaffanella 30 Jan '10

30 Jan '10

Module: ppl/ppl Branch: pip Commit: b4fe5c5c5a5b0f79809a956b1b739a9b5ce14540 URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=b4fe5c5c5a5b… Author: Enea Zaffanella <zaffanella(a)cs.unipr.it> Date: Sat Jan 30 23:43:40 2010 +0100 Prefer C++ named casts to C style casts. --- src/PIP_Tree.cc | 3 ++- 1 files changed, 2 insertions(+), 1 deletions(-) diff --git a/src/PIP_Tree.cc b/src/PIP_Tree.cc index 2460bf5..8958d0d 100644 --- a/src/PIP_Tree.cc +++ b/src/PIP_Tree.cc @@ -243,7 +243,8 @@ namespace IO_Operators { std::ostream& operator<<(std::ostream& os, const PIP_Tree_Node::Artificial_Parameter& x) { - os << "(" << ((Linear_Expression)x) << ") div " << x.get_denominator(); + const Linear_Expression& expr = static_cast<const Linear_Expression&>(x); + os << "(" << expr << ") div " << x.get_denominator(); return os; }

1 0

[GIT] ppl/ppl(pip): Minor readability improvements to row_normalize.
by Enea Zaffanella 30 Jan '10

30 Jan '10

Module: ppl/ppl Branch: pip Commit: 6864f73b1fba0f6029af61fd5fce662f661d2f31 URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=6864f73b1fba… Author: Enea Zaffanella <zaffanella(a)cs.unipr.it> Date: Sat Jan 30 23:38:59 2010 +0100 Minor readability improvements to row_normalize. --- src/PIP_Tree.cc | 39 ++++++++++++++++++++------------------- 1 files changed, 20 insertions(+), 19 deletions(-) diff --git a/src/PIP_Tree.cc b/src/PIP_Tree.cc index 7d6781b..2460bf5 100644 --- a/src/PIP_Tree.cc +++ b/src/PIP_Tree.cc @@ -193,35 +193,35 @@ find_lexico_minimum_column(const Matrix& tableau, const std::vector<dimension_type>& mapping, const std::vector<bool>& basis, const Row& pivot_row, - dimension_type start_j, - dimension_type& j) { - dimension_type num_cols = tableau.num_columns(); + const dimension_type start_j, + dimension_type& j_out) { + const dimension_type num_cols = tableau.num_columns(); bool has_positive_coefficient = false; - j = num_cols; - for (dimension_type j_ = start_j; j_ < num_cols; ++j_) { - const Coefficient& c = pivot_row[j_]; + j_out = num_cols; + for (dimension_type j = start_j; j < num_cols; ++j) { + const Coefficient& c = pivot_row[j]; if (c <= 0) continue; has_positive_coefficient = true; - if (j == num_cols - || column_lower(tableau, mapping, basis, pivot_row, j_, pivot_row, j)) - j = j_; + if (j_out == num_cols + || column_lower(tableau, mapping, basis, + pivot_row, j, pivot_row, j_out)) + j_out = j; } return has_positive_coefficient; } // Divide all coefficients in row x and denominator y by their GCD. void -row_normalize(Row& x, Coefficient& y) { - if (y == 1) +row_normalize(Row& x, Coefficient& den) { + if (den == 1) return; - dimension_type size = x.size(); - dimension_type j; + const dimension_type x_size = x.size(); PPL_DIRTY_TEMP_COEFFICIENT(gcd); - gcd = y; - for (j=0; j<size; ++j) { - const Coefficient& c = x[j]; + gcd = den; + for (dimension_type i = x_size; i-- > 0; ) { + const Coefficient& c = x[i]; if (c != 0) { gcd_assign(gcd, c, gcd); if (gcd == 1) @@ -229,11 +229,12 @@ row_normalize(Row& x, Coefficient& y) { } } // Divide the coefficients by the GCD. - exact_div_assign(y, y, gcd); - for (j=0; j<size; ++j) { - Coefficient& c = x[j]; + for (dimension_type i = x_size; i-- > 0; ) { + Coefficient& c = x[i]; exact_div_assign(c, c, gcd); } + // Divide the denominator by the GCD. + exact_div_assign(den, den, gcd); } } // namespace

1 0

[GIT] ppl/ppl(pip): Optimized some computation in helper function column_lower().
by Enea Zaffanella 30 Jan '10

30 Jan '10

Module: ppl/ppl Branch: pip Commit: cd6b0004b5f79b0eeba6f21f58f5158cbbaab6b8 URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=cd6b0004b5f7… Author: Enea Zaffanella <zaffanella(a)cs.unipr.it> Date: Sat Jan 30 23:23:24 2010 +0100 Optimized some computation in helper function column_lower(). --- src/PIP_Tree.cc | 69 +++++++++++++++++++++++++++++++++++------------------- 1 files changed, 45 insertions(+), 24 deletions(-) diff --git a/src/PIP_Tree.cc b/src/PIP_Tree.cc index cb85de7..7d6781b 100644 --- a/src/PIP_Tree.cc +++ b/src/PIP_Tree.cc @@ -99,9 +99,9 @@ negate_assign(Row& x, const Row& y, Coefficient_traits::const_reference sc) { // Update given context matrix using local artificials dimension_type -update_context(Matrix &context, - const PIP_Tree_Node::Artificial_Parameter_Sequence &ap) { - dimension_type ap_size = ap.size(); +update_context(Matrix& context, + const PIP_Tree_Node::Artificial_Parameter_Sequence& ap) { + const dimension_type ap_size = ap.size(); if (ap_size > 0) context.add_zero_columns(ap_size); return ap_size; @@ -109,14 +109,15 @@ update_context(Matrix &context, // Update given context matrix and parameter set using local artificials void -update_context(Variables_Set &params, Matrix &context, - const PIP_Tree_Node::Artificial_Parameter_Sequence &ap, - dimension_type &space_dimension) { - dimension_type ap_size = update_context(context, ap); - if (ap_size > 0) { - for (dimension_type i = 0; i < ap_size; ++i) - params.insert(space_dimension++); - } +update_context(Variables_Set& params, Matrix& context, + const PIP_Tree_Node::Artificial_Parameter_Sequence& ap, + dimension_type& space_dimension) { + const dimension_type ap_size = update_context(context, ap); + // Update parameters. + for (dimension_type i = 0; i < ap_size; ++i) + params.insert(space_dimension + i); + // Update space dimension. + space_dimension += ap_size; } /* Compares two columns lexicographically in revised simplex tableau @@ -129,38 +130,58 @@ column_lower(const Matrix& tableau, const std::vector<dimension_type>& mapping, const std::vector<bool>& basis, const Row& pivot_a, - dimension_type ja, + const dimension_type ja, const Row& pivot_b, - dimension_type jb, + const dimension_type jb, Coefficient_traits::const_reference cst_a = -1, Coefficient_traits::const_reference cst_b = -1) { - PPL_DIRTY_TEMP_COEFFICIENT(cij_a); - PPL_DIRTY_TEMP_COEFFICIENT(cij_b); const Coefficient& sij_a = pivot_a[ja]; const Coefficient& sij_b = pivot_b[jb]; PPL_ASSERT(sij_a > 0); PPL_ASSERT(sij_b > 0); + + PPL_DIRTY_TEMP_COEFFICIENT(lhs_coeff); + PPL_DIRTY_TEMP_COEFFICIENT(rhs_coeff); + lhs_coeff = cst_a * sij_b; + rhs_coeff = cst_b * sij_a; + if (ja == jb) { // Same column: just compare the ratios. // This works since all columns are lexico-positive. - return cst_a * sij_b > cst_b * sij_a; + // return cst_a * sij_b > cst_b * sij_a; + return lhs_coeff > rhs_coeff; } + PPL_DIRTY_TEMP_COEFFICIENT(cij_a); + PPL_DIRTY_TEMP_COEFFICIENT(cij_b); + PPL_DIRTY_TEMP_COEFFICIENT(lhs); + PPL_DIRTY_TEMP_COEFFICIENT(rhs); + const dimension_type num_vars = mapping.size(); dimension_type k = 0; - dimension_type num_vars = mapping.size(); do { - dimension_type mk = mapping[k]; + const dimension_type mk = mapping[k]; if (basis[k]) { // Reconstitute the identity submatrix part of tableau. - cij_a = (mk==ja) ? 1 : 0; - cij_b = (mk==jb) ? 1 : 0; + cij_a = (mk == ja) ? 1 : 0; + cij_b = (mk == jb) ? 1 : 0; } else { - cij_a = tableau[mk][ja]; - cij_b = tableau[mk][jb]; + const Row& t_mk = tableau[mk]; + cij_a = t_mk[ja]; + cij_b = t_mk[jb]; } ++k; - } while (k < num_vars && cij_a * cst_a * sij_b == cij_b * cst_b * sij_a); - return k < num_vars && cij_a * cst_a * sij_b > cij_b * cst_b * sij_a; + // Optimizing computation of while guard (and return value): + // (k < num_vars && cij_a * cst_a * sij_b == cij_b * cst_b * sij_a) + if (k == num_vars) + return false; + lhs = cij_a * lhs_coeff; + rhs = cij_b * rhs_coeff; + } while (lhs == rhs); + + // Optimizing computation of return value: + // return k < num_vars && cij_a * cst_a * sij_b > cij_b * cst_b * sij_a; + assert(k < num_vars); + return lhs > rhs; } /* Find the column j in revised simplex tableau such as

1 0