Module: ppl/ppl Branch: sparse_matrices Commit: 710981bf623314ef9b714396a984aa7d590ab749 URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=710981bf62331...

Author: Marco Poletti poletti.marco@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);