Module: ppl/ppl Branch: pip Commit: 9ce39ca898aa35e1639b768a5d7c92e987a9d3d2 URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=9ce39ca898aa3...
Author: François Galea francois.galea@uvsq.fr Date: Fri Sep 11 13:16:08 2009 +0200
Implemented row sign detection.
---
src/PIP_Tree.cc | 33 +++++++++++++++++++++++++++++++++ src/PIP_Tree.defs.hh | 20 ++++++++++++++++++++ 2 files changed, 53 insertions(+), 0 deletions(-)
diff --git a/src/PIP_Tree.cc b/src/PIP_Tree.cc index 2f1afe0..b552c72 100644 --- a/src/PIP_Tree.cc +++ b/src/PIP_Tree.cc @@ -209,6 +209,38 @@ PIP_Solution_Node::ascii_load(std::istream& s) { return true; }
+PIP_Solution_Node::Row_Sign +PIP_Solution_Node::row_sign(const Row &x) { + PIP_Solution_Node::Row_Sign sign = ZERO; + Coefficient c; + for (int i = x.size(); i-- > 0; ) { + c = x[i]; + switch (sign) { + case UNKNOWN: + // cannot happen + break; + case ZERO: + if (c < 0) + sign = NEGATIVE; + else if (c > 0) + sign = POSITIVE; + break; + case NEGATIVE: + if (c > 0) + return MIXED; + break; + case POSITIVE: + if (c < 0) + return MIXED; + break; + case MIXED: + // cannot happen + break; + } + } + return sign; +} + void PIP_Solution_Node::update_tableau(PIP_Tree_Node ** /* parent_ref */, dimension_type external_space_dim, @@ -273,6 +305,7 @@ PIP_Solution_Node::update_tableau(PIP_Tree_Node ** /* parent_ref */, // FIXME: must handle equality constraints tableau.s.add_row(var); tableau.t.add_row(param); + sign.push_back(row_sign(param)); } // FIXME: decide emptiness detection (and node removal) } diff --git a/src/PIP_Tree.defs.hh b/src/PIP_Tree.defs.hh index 13dc12b..e0ce99c 100644 --- a/src/PIP_Tree.defs.hh +++ b/src/PIP_Tree.defs.hh @@ -232,9 +232,29 @@ private: */ std::vector<dimension_type> mapping;
+ //! The possible values for the sign of a parametric linear expression. + enum Row_Sign { + //! Not computed yet (default) + UNKNOWN, + //! All row coefficients are zero. + ZERO, + //! All nonzero row coefficients are positive. + POSITIVE, + //! All nonzero row coefficients are negative. + NEGATIVE, + //! The row contains positive and negative coefficients. + MIXED + }; + + //! A cache for computed sign values of constraint parametric RHS + std::vector<Row_Sign> sign; + //! The local system of parameter constraints Constraint_System constraints_;
+ //! Determines the sign of given Row + static Row_Sign row_sign(const Row &x); + protected: /*! \brief Populates the parametric simplex tableau using external data, if necessary