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

Author: François Galea francois.galea@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);