[PPL-devel] [GIT] ppl/ppl(pip): Fully normalize artificial parameters on construction.

[Enea Zaffanella]

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

Author: Enea Zaffanella <zaffanella at cs.unipr.it>
Date:   Fri Feb  4 09:52:58 2011 +0100

Fully normalize artificial parameters on construction.
When in noisy mode, print normalized parameters.

---

 src/PIP_Tree.cc         |   71 +++++++++++++++++++++++++++++++++++++++++-----
 src/PIP_Tree.inlines.hh |   17 -----------
 2 files changed, 63 insertions(+), 25 deletions(-)

diff --git a/src/PIP_Tree.cc b/src/PIP_Tree.cc
index 8c22a25..b9a818d 100644
--- a/src/PIP_Tree.cc
+++ b/src/PIP_Tree.cc
@@ -29,6 +29,9 @@ site: http://www.cs.unipr.it/ppl/ . */
 #include <memory>
 #include <map>
 
+// #define NOISY_PIP
+// #define VERY_NOISY_PIP 0
+
 namespace Parma_Polyhedra_Library {
 
 namespace {
@@ -802,6 +805,60 @@ PIP_Tree_Node::PIP_Tree_Node(const PIP_Tree_Node& y)
     artificial_parameters(y.artificial_parameters) {
 }
 
+PIP_Tree_Node::Artificial_Parameter
+::Artificial_Parameter(const Linear_Expression& expr,
+                       Coefficient_traits::const_reference den)
+  : Linear_Expression(expr), denom(den) {
+  if (denom == 0)
+    throw std::invalid_argument("PIP_Tree_Node::Artificial_Parameter(e, d): "
+                                "denominator d is zero.");
+
+  // Normalize if needed.
+  // FIXME: Provide a proper normalization helper.
+  Linear_Expression& param_expr = *this;
+  if (denom < 0) {
+    neg_assign(denom);
+    param_expr *= -1;
+  }
+
+  // Compute GCD of parameter expression and denum.
+  PPL_DIRTY_TEMP_COEFFICIENT(gcd);
+  gcd = denom;
+  gcd_assign(gcd, param_expr.inhomogeneous_term(), gcd);
+  if (gcd == 1)
+    return;
+  const dimension_type space_dim = param_expr.space_dimension();
+  for (dimension_type i = space_dim; i-- > 0; ) {
+    Coefficient_traits::const_reference
+      e_i = param_expr.coefficient(Variable(i));
+    if (e_i != 0) {
+      gcd_assign(gcd, e_i, gcd);
+      if (gcd == 1)
+        return;
+    }
+  }
+
+  // Divide coefficients and denominator by their (non-trivial) GCD.
+  PPL_ASSERT(gcd > 1);
+  Linear_Expression normalized(0 * Variable(space_dim-1));
+  PPL_DIRTY_TEMP_COEFFICIENT(coeff);
+  exact_div_assign(coeff, param_expr.inhomogeneous_term(), gcd);
+  normalized += coeff;
+  for (dimension_type i = space_dim; i-- > 0; ) {
+    Coefficient_traits::const_reference
+      e_i = param_expr.coefficient(Variable(i));
+    if (e_i != 0) {
+      exact_div_assign(coeff, e_i, gcd);
+      add_mul_assign(normalized, coeff, Variable(i));
+    }
+  }
+  // Replace the parameter expression with the normalized one.
+  param_expr = normalized;
+  exact_div_assign(denom, denom, gcd);
+
+  PPL_ASSERT(OK());
+}
+
 bool
 PIP_Tree_Node::Artificial_Parameter
 ::operator==(const PIP_Tree_Node::Artificial_Parameter& y) const {
@@ -2262,11 +2319,11 @@ PIP_Solution_Node::solve(const PIP_Problem& pip,
     const dimension_type num_params = tableau.t.num_columns();
     Coefficient_traits::const_reference tableau_den = tableau.denominator();
 
-#ifdef NOISY_PIP
+#ifdef VERY_NOISY_PIP
     tableau.ascii_dump(std::cerr);
     std::cerr << "context ";
     context.ascii_dump(std::cerr);
-#endif
+#endif // #ifdef VERY_NOISY_PIP
 
     // (Re-) Compute parameter row signs.
     // While at it, keep track of the first parameter rows
@@ -2407,7 +2464,7 @@ PIP_Solution_Node::solve(const PIP_Problem& pip,
 
 #ifdef NOISY_PIP
       std::cerr << "Pivot (pi, pj) = (" << pi << ", " << pj << ")\n";
-#endif
+#endif // #ifdef NOISY_PIP
 
       // Normalize the tableau before pivoting.
       tableau.normalize();
@@ -2617,7 +2674,7 @@ PIP_Solution_Node::solve(const PIP_Problem& pip,
         std::cerr << "Found row (" << i_neg << ") with mixed parameter sign "
                   << "and negative variable coefficients.\n"
                   << "==> adding tautology.\n";
-#endif
+#endif // #ifdef NOISY_PIP
         Row copy = tableau.t[i_neg];
         copy.normalize();
         context.add_row(copy);
@@ -2994,8 +3051,7 @@ PIP_Solution_Node::generate_cut(const dimension_type index,
 #ifdef NOISY_PIP
       using namespace IO_Operators;
       std::cout << "Re-using parameter " << Variable(ap_column)
-                << " = (" << expr << ")/" << den
-                << std::endl;
+                << " = " << ap << std::endl;
 #endif // #ifdef NOISY_PIP
       ap_column = ap_column - num_vars + 1;
     }
@@ -3010,8 +3066,7 @@ PIP_Solution_Node::generate_cut(const dimension_type index,
       using namespace IO_Operators;
       std::cout << "Creating new parameter "
                 << Variable(space_dimension)
-                << " = (" << expr << ")/" << den
-                << std::endl;
+                << " = " << ap << std::endl;
 #endif // #ifdef NOISY_PIP
       ++space_dimension;
       ap_column = num_params;
diff --git a/src/PIP_Tree.inlines.hh b/src/PIP_Tree.inlines.hh
index ef0e8e0..ddd1bc0 100644
--- a/src/PIP_Tree.inlines.hh
+++ b/src/PIP_Tree.inlines.hh
@@ -111,23 +111,6 @@ PIP_Tree_Node::Artificial_Parameter::Artificial_Parameter()
 
 inline
 PIP_Tree_Node::Artificial_Parameter
-::Artificial_Parameter(const Linear_Expression& expr,
-                       Coefficient_traits::const_reference den)
-  : Linear_Expression(expr), denom(den) {
-  if (denom == 0)
-    throw std::invalid_argument("PIP_Tree_Node::Artificial_Parameter(e, d): "
-                                "denominator d is zero.");
-  // Normalize if needed.
-  if (denom < 0) {
-    neg_assign(denom);
-    Linear_Expression& e = *this;
-    e *= -1;
-  }
-  PPL_ASSERT(OK());
-}
-
-inline
-PIP_Tree_Node::Artificial_Parameter
 ::Artificial_Parameter(const Artificial_Parameter& y)
   : Linear_Expression(y), denom(y.denom) {
   PPL_ASSERT(OK());