[PPL-devel] [GIT] ppl/ppl(pip): Added support for equality constraints; fixed a bug for strict inequalities.

[François Galea]

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

Author: François Galea <francois.galea at uvsq.fr>
Date:   Tue Oct 27 20:12:47 2009 +0100

Added support for equality constraints; fixed a bug for strict inequalities.

---

 src/PIP_Problem.cc               |    7 +++++++
 src/PIP_Tree.cc                  |   18 +++++++++++++-----
 tests/PIP_Problem/pipproblem1.cc |   12 ++++--------
 3 files changed, 24 insertions(+), 13 deletions(-)

diff --git a/src/PIP_Problem.cc b/src/PIP_Problem.cc
index b228911..f4c7422 100644
--- a/src/PIP_Problem.cc
+++ b/src/PIP_Problem.cc
@@ -122,7 +122,14 @@ PPL::PIP_Problem::solve() const {
           for (pi = param_begin, i = 1; pi != param_end; ++pi, ++i)
             row[i] = c->coefficient(Variable(*pi));
           row[0] = c->inhomogeneous_term();
+          if (c->is_strict_inequality())
+            row[0] -= 1;
           x.initial_context.add_row(row);
+          if (c->is_equality()) {
+            for (i = 0; i < width; ++i)
+              row[i] = -row[i];
+            x.initial_context.add_row(row);
+          }
         }
       }
 
diff --git a/src/PIP_Tree.cc b/src/PIP_Tree.cc
index 1047be0..f7706e4 100644
--- a/src/PIP_Tree.cc
+++ b/src/PIP_Tree.cc
@@ -74,9 +74,11 @@ negate_assign(Row& x, const Row& y, const Coefficient& sc) {
   PPL_ASSERT(x.size() == y.size());
   for (dimension_type i = x.size(); i-- > 0; )
     x[i] = -y[i];
-  PPL_DIRTY_TEMP_COEFFICIENT(mod);
-  mod_assign(mod, x[0], sc);
-  x[0] -= ((mod == 0) ? sc : mod);
+  if (sc != 0) {
+    PPL_DIRTY_TEMP_COEFFICIENT(mod);
+    mod_assign(mod, x[0], sc);
+    x[0] -= ((mod == 0) ? sc : mod);
+  }
 }
 
 // Update given context matrix using local artificials
@@ -867,7 +869,7 @@ PIP_Solution_Node::update_tableau(dimension_type external_space_dim,
   }
   internal_space_dim = external_space_dim;
 
-  const Coefficient &denom = tableau.get_denominator();
+  const Coefficient& denom = tableau.get_denominator();
 
   for (cst = input_cs.begin() + first_pending_constraint;
        cst < input_cs.end(); ++cst) {
@@ -897,7 +899,6 @@ PIP_Solution_Node::update_tableau(dimension_type external_space_dim,
         ++v;
       }
     }
-    // FIXME: must handle equality constraints
     if (row_sign(var) != ZERO) {
       /* parametric-only constraints have already been inserted in initial
         context, so no need to insert them in the tableau
@@ -905,6 +906,13 @@ PIP_Solution_Node::update_tableau(dimension_type external_space_dim,
       tableau.s.add_row(var);
       tableau.t.add_row(param);
       sign.push_back(row_sign(param));
+      if (cst->is_equality()) {
+        negate_assign(var, var, 0);
+        negate_assign(param, param, 0);
+        tableau.s.add_row(var);
+        tableau.t.add_row(param);
+        sign.push_back(row_sign(param));
+      }
     }
   }
 }
diff --git a/tests/PIP_Problem/pipproblem1.cc b/tests/PIP_Problem/pipproblem1.cc
index f250ccb..c8a93fb 100644
--- a/tests/PIP_Problem/pipproblem1.cc
+++ b/tests/PIP_Problem/pipproblem1.cc
@@ -93,8 +93,7 @@ test01() {
   Constraint_System cs;
   cs.insert(-X1 + N - 1 >= 0);
   cs.insert(X1 - X2 >= 0);
-  cs.insert(X1 + I0 - N >= 0);
-  cs.insert(-X1 - I0 + N >= 0);
+  cs.insert(X1 + I0 == N);
   cs.insert(X2 + J0 - N - 1 >= 0);
   cs.insert(I0 >= 1);
   cs.insert(N >= 1);
@@ -150,8 +149,7 @@ test03() {
   Constraint_System cs;
   cs.insert(i <= m);
   cs.insert(j <= n);
-  cs.insert(2*i+j <= 2*m+n-k);
-  cs.insert(2*i+j >= 2*m+n-k);
+  cs.insert(2*i+j == 2*m+n-k);
 
   PIP_Problem pip(cs.space_dimension(), cs.begin(), cs.end(), params);
 
@@ -177,8 +175,7 @@ test04() {
   Constraint_System cs;
   cs.insert(i <= m);
   cs.insert(j <= n);
-  cs.insert(2*i+j <= 2*m+n-k);
-  cs.insert(2*i+j >= 2*m+n-k);
+  cs.insert(2*i+j == 2*m+n-k);
 
   PIP_Problem pip(cs.space_dimension(), cs.begin(), cs.end(), params);
 
@@ -236,8 +233,7 @@ test06() {
   Variables_Set params(n);
 
   Constraint_System cs;
-  cs.insert(4*i + 2*n >= 1);
-  cs.insert(4*i + 2*n <= 1);
+  cs.insert(4*i + 2*n == 1);
 
   PIP_Problem pip(cs.space_dimension(), cs.begin(), cs.end(), params);