Module: ppl/ppl Branch: pip Commit: e8b3c7c191b3abc667676f0dc00fcf15af5b9bb5 URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=e8b3c7c191b3a... Author: François Galea <francois.galea@uvsq.fr> Date: Mon Sep 14 13:13:27 2009 +0200 Changed modelization of contexts from Constraint_System to Matrix. --- src/PIP_Problem.cc | 2 +- src/PIP_Tree.cc | 43 ++++++++++++++++++++++++++++--------------- src/PIP_Tree.defs.hh | 6 +++--- 3 files changed, 32 insertions(+), 19 deletions(-) diff --git a/src/PIP_Problem.cc b/src/PIP_Problem.cc index 86777f5..34affcd 100644 --- a/src/PIP_Problem.cc +++ b/src/PIP_Problem.cc @@ -85,7 +85,7 @@ PPL::PIP_Problem::solve() const { input_cs, parameters); - Constraint_System initial_context; + Matrix initial_context(0, parameters.size()+1); return_value = x.current_solution->solve(&x.current_solution, initial_context); diff --git a/src/PIP_Tree.cc b/src/PIP_Tree.cc index b7948f5..c43715e 100644 --- a/src/PIP_Tree.cc +++ b/src/PIP_Tree.cc @@ -37,12 +37,29 @@ add_assign(Row& x, const Row& y, Coefficient_traits::const_reference c) { add_mul_assign(x[i], c, y[i]); } -// Merge constraint systems such as x = x U y +// Merge constraint system to a Matrix-form context such as x = x U y void -merge_assign(Constraint_System& x, const Constraint_System& y) { +merge_assign(Matrix& x, const Constraint_System& y) { + dimension_type width = x.num_columns(); + PPL_ASSERT(y.empty() || y.begin()->space_dimension() == width-1); + Row row(width, Row::Flags()); for (Constraint_System::const_iterator y_i = y.begin(), - y_end = y.end(); y_i != y_end; ++y_i) - x.insert(*y_i); + y_end = y.end(); y_i != y_end; ++y_i) { + PPL_ASSERT(y_i->is_nonstrict_inequality()); + for (dimension_type j=width-1; j-- > 0; ) + row[j+1] = y_i->coefficient(Variable(j)); + row[0] = -y_i->inhomogeneous_term(); + x.add_row(row); + } +} + +// Tranform expression "expr" into "-expr-1" +void +negate_assign(Row& x, const Row& y) { + PPL_ASSERT(x.size() == y.size()); + for (dimension_type i = x.size(); i-- > 0; ) + x[i] = -y[i]; + x[0] -= 1; } } // namespace @@ -204,24 +221,20 @@ PIP_Decision_Node::update_tableau(PIP_Tree_Node ** /* parent_ref */, } PIP_Problem_Status -PIP_Decision_Node::solve(PIP_Tree_Node **parent_ref, - const Constraint_System& context) { +PIP_Decision_Node::solve(PIP_Tree_Node **parent_ref, const Matrix& context) { PIP_Problem_Status return_status; PIP_Problem_Status stt; PIP_Problem_Status stf = UNFEASIBLE_PIP_PROBLEM; - Constraint_System context_true(context); + Matrix context_true(context); merge_assign(context_true, constraints_); stt = true_child->solve(&true_child, context_true); if (false_child) { // Decision nodes with false child must have exactly one constraint PPL_ASSERT(1 == std::distance(constraints_.begin(), constraints_.end())); - Constraint_System context_false(context); - Constraint_System::const_iterator ci = constraints_.begin(); - PPL_ASSERT(ci->is_nonstrict_inequality()); - Linear_Expression expr = Linear_Expression(*ci); - expr += 1; - Constraint c(expr <= 0); - context_false.insert(c); + Matrix context_false(context); + merge_assign(context_false, constraints_); + Row &last = context_false[context_false.num_rows()-1]; + negate_assign(last, last); stf = false_child->solve(&false_child, context_false); } @@ -326,7 +339,7 @@ PIP_Solution_Node::compatibility_check(const Matrix &ctx, const Row &cnst) { dimension_type num_cols = s.num_columns(); bool result = false; - /* Perform nonparametric simplex pivots until we find an empty solution + /* Perform simplex pivots on the context until we find an empty solution * or an optimum */ for(;;) { // Look for a negative RHS (=constant term, stored in matrix column 0) diff --git a/src/PIP_Tree.defs.hh b/src/PIP_Tree.defs.hh index 5393c02..c8b2a16 100644 --- a/src/PIP_Tree.defs.hh +++ b/src/PIP_Tree.defs.hh @@ -121,7 +121,7 @@ protected: attempt (unfeasible or optimized problem). */ virtual PIP_Problem_Status solve(PIP_Tree_Node **parent_ref, - const Constraint_System& context) = 0; + const Matrix& context) = 0; }; //! A tree node representing part of the space of solutions. @@ -308,7 +308,7 @@ protected: attempt (unfeasible or optimized problem). */ virtual PIP_Problem_Status solve(PIP_Tree_Node **parent_ref, - const Constraint_System& context); + const Matrix& context); // FIXME: constructors to be decided. }; @@ -415,7 +415,7 @@ protected: attempt (unfeasible or optimized problem). */ virtual PIP_Problem_Status solve(PIP_Tree_Node **parent_ref, - const Constraint_System& context); + const Matrix& context); }; typedef const PIP_Tree_Node* PIP_Tree;