[PPL-devel] [GIT] ppl/ppl(sparse_matrices): PIP_Tree.cc: prepare find_lexico_minimum_column_in_set() for optimization (#2).

[Marco Poletti]

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

Author: Marco Poletti <poletti.marco at gmail.com>
Date:   Fri Mar 12 14:03:09 2010 +0100

PIP_Tree.cc: prepare find_lexico_minimum_column_in_set() for optimization (#2).

---

 src/PIP_Tree.cc |   86 +++++++++++++++++++++++++++----------------------------
 1 files changed, 42 insertions(+), 44 deletions(-)

diff --git a/src/PIP_Tree.cc b/src/PIP_Tree.cc
index 0d0d95d..491a6e3 100644
--- a/src/PIP_Tree.cc
+++ b/src/PIP_Tree.cc
@@ -429,81 +429,79 @@ find_lexico_minimum_column_in_set(std::set<dimension_type>& candidates,
                                   const std::vector<bool>& basis,
                                   PIP_Tree_Node::
                                   matrix_row_const_reference_type pivot_row) {
-  std::set<dimension_type>::iterator i = candidates.begin();
-  std::set<dimension_type>::iterator i_end = candidates.end();
+  const dimension_type num_vars = mapping.size();
 
   PPL_ASSERT(!candidates.empty());
-  dimension_type min_index = *i;
-  ++i;
-  for ( ; i!=i_end; ++i) {
-    bool found_better_candidate;
-    const Coefficient& sij_a = pivot_row.get(*i);
-    const Coefficient& sij_b = pivot_row.get(min_index);
-    PPL_ASSERT(sij_a > 0);
-    PPL_ASSERT(sij_b > 0);
-
-    PPL_DIRTY_TEMP_COEFFICIENT(lhs_coeff);
-    PPL_DIRTY_TEMP_COEFFICIENT(rhs_coeff);
-    lhs_coeff = -sij_b;
-    rhs_coeff = -sij_a;
-
-    PPL_DIRTY_TEMP_COEFFICIENT(lhs);
-    PPL_DIRTY_TEMP_COEFFICIENT(rhs);
-    const dimension_type num_vars = mapping.size();
-    dimension_type k = 0;
-    // 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) {
+  for (dimension_type var_index = 0; var_index < num_vars; ++var_index) {
+    std::set<dimension_type> new_candidates;
+    std::set<dimension_type>::iterator i = candidates.begin();
+    std::set<dimension_type>::iterator i_end = candidates.end();
+    PPL_ASSERT(!candidates.empty());
+    new_candidates.insert(*i);
+    dimension_type min_column = *i;
+    ++i;
+    for ( ; i!=i_end; ++i) {
+      const Coefficient& sij_a = pivot_row.get(*i);
+      const Coefficient& sij_b = pivot_row.get(min_column);
+      PPL_ASSERT(sij_a > 0);
+      PPL_ASSERT(sij_b > 0);
+
+      PPL_DIRTY_TEMP_COEFFICIENT(lhs_coeff);
+      PPL_DIRTY_TEMP_COEFFICIENT(rhs_coeff);
+      lhs_coeff = -sij_b;
+      rhs_coeff = -sij_a;
+
+      PPL_DIRTY_TEMP_COEFFICIENT(lhs);
+      PPL_DIRTY_TEMP_COEFFICIENT(rhs);
+      dimension_type k = var_index;
       const dimension_type mk = mapping[k];
       const bool in_base = basis[k];
-      if (++k >= num_vars) {
-        found_better_candidate = false;
-        break;
-      }
+      bool found_better_candidate = false;
       if (in_base) {
         // Reconstitute the identity submatrix part of tableau.
         if (mk == *i) {
           // Optimizing for: lhs == lhs_coeff && rhs == 0;
           if (lhs_coeff == 0)
-            continue;
+            new_candidates.insert(*i);
           else {
-            found_better_candidate = lhs_coeff > 0;
-            break;
+            if (lhs_coeff > 0)
+              found_better_candidate = true;
           }
         }
-        if (mk == min_index) {
+        if (mk == min_column) {
           // Optimizing for: lhs == 0 && rhs == rhs_coeff;
           if (rhs_coeff == 0)
-            continue;
+            new_candidates.insert(*i);
           else {
-            found_better_candidate = 0 > rhs_coeff;
-            break;
+            if (0 > rhs_coeff)
+              found_better_candidate = true;
           }
         }
         // Optimizing for: lhs == 0 && rhs == 0;
-        continue;
+        new_candidates.insert(*i);
       } else {
         // Not in base.
         PIP_Tree_Node::matrix_row_const_reference_type t_mk = tableau[mk];
         const Coefficient* t_mk_ja;
         const Coefficient* t_mk_jb;
-        t_mk.get2(*i,min_index,t_mk_ja,t_mk_jb);
+        t_mk.get2(*i,min_column,t_mk_ja,t_mk_jb);
         lhs = lhs_coeff * *t_mk_ja;
         rhs = rhs_coeff * *t_mk_jb;
         if (lhs == rhs)
-          continue;
+          new_candidates.insert(*i);
         else {
-          found_better_candidate = lhs > rhs;
-          break;
+          if (lhs > rhs)
+            found_better_candidate = true;
         }
       }
+      if (found_better_candidate) {
+        new_candidates.clear();
+        min_column = *i;
+        new_candidates.insert(min_column);
+      }
     }
-    if (found_better_candidate)
-      min_index = *i;
+    std::swap(candidates,new_candidates);
   }
-  candidates.clear();
-  candidates.insert(min_index);
 }
 
 /* Find the column j in revised simplex tableau such as