[PPL-devel] [GIT] ppl/ppl(pip): Implemented proper handling of nonbasic variables when adding rows.

[François Galea]

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

Author: François Galea <francois.galea at uvsq.fr>
Date:   Wed Sep  9 15:59:09 2009 +0200

Implemented proper handling of nonbasic variables when adding rows.

---

 src/PIP_Tree.cc      |   34 +++++++++++++++++++++-------------
 src/PIP_Tree.defs.hh |   22 ++++++++++++++++++++--
 2 files changed, 41 insertions(+), 15 deletions(-)

diff --git a/src/PIP_Tree.cc b/src/PIP_Tree.cc
index 28cfbc9..fc6e1db 100644
--- a/src/PIP_Tree.cc
+++ b/src/PIP_Tree.cc
@@ -150,7 +150,7 @@ PIP_Solution_Node::update_tableau(PIP_Tree_Node **parent_ref,
                                   dimension_type first_pending_constraint,
                                   const Constraint_Sequence &input_cs,
                                   const Variables_Set &parameters) {
-  dimension_type i;
+  dimension_type i, j;
   dimension_type n_params = parameters.size();
   dimension_type n_vars = external_space_dim - n_params;
   dimension_type n_vars_int = tableau.s.num_columns();
@@ -168,8 +168,11 @@ PIP_Solution_Node::update_tableau(PIP_Tree_Node **parent_ref,
   for (i=internal_space_dim; i<external_space_dim; ++i) {
     if (parameters.count(i) == 1)
       tableau.t.add_zero_columns(1);
-    else
+    else {
       tableau.s.add_zero_columns(1);
+      basis.push_back(true);
+      mapping.push_back(tableau.s.num_columns()-1);
+    }
   }
   internal_space_dim = external_space_dim;
 
@@ -178,7 +181,6 @@ PIP_Solution_Node::update_tableau(PIP_Tree_Node **parent_ref,
 
   for (cst = input_cs.begin() + first_pending_constraint;
        cst < input_cs.end(); ++cst) {
-    // FIXME: must handle nonbasic variables aswell
     int v = 0;
     int p = 1;
     Row var(n_vars, Row::Flags());
@@ -190,10 +192,22 @@ PIP_Solution_Node::update_tableau(PIP_Tree_Node **parent_ref,
     param[0] = cnst_term * denom_t;
     for (i=0; i<internal_space_dim; i++) {
       if (parameters.count(i) == 1) {
-        param[p] = cst->coefficient(Variable(i)) * denom_t;
-        ++p;
+        param[p++] = cst->coefficient(Variable(i)) * denom_t;
       } else {
-        var[v] = cst->coefficient(Variable(i)) * denom_s;
+        Coefficient c = cst->coefficient(Variable(i)) * denom_s;
+        dimension_type idx = mapping[v];
+        if (basis[v])
+          // Basic variable : add c * x_i
+          var[idx] += c;
+        else {
+          // Nonbasic variable : add c * row_i
+          const Row &sr = tableau.s[idx];
+          const Row &st = tableau.t[idx];
+          for (j=0; j<sr.size(); j++)
+            var[j] += c*sr[j];
+          for (j=0; j<st.size(); j++)
+            param[j] += c*st[j];
+        }
         ++v;
       }
     }
@@ -201,13 +215,7 @@ PIP_Solution_Node::update_tableau(PIP_Tree_Node **parent_ref,
     tableau.s.add_row(var);
     tableau.t.add_row(param);
   }
-
-  // update current basis with newly inserted variables
-  dimension_type next_var = n_vars_int + n_constr_int;
-  for (i=n_vars_int; i<n_vars; ++i)
-    basis.insert(next_var++);
+  // FIXME: decide emptiness detection (and node removal)
 }
 
-
-
 } // namespace Parma_Polyhedra_Library
diff --git a/src/PIP_Tree.defs.hh b/src/PIP_Tree.defs.hh
index 63659d8..bf46c8e 100644
--- a/src/PIP_Tree.defs.hh
+++ b/src/PIP_Tree.defs.hh
@@ -179,8 +179,26 @@ private:
   //! The parametric simplex tableau.
   Tableau tableau;
 
-  //! A set containing the internal indices of the basic variables
-  Variables_Set basis;
+  /*! \brief
+    A boolean vector for identifying the basic variables.
+
+    The value for <tt>basis[i]</tt> is:
+     - \b true if variable \p i is basic,
+     - \b false if variable \p i is nonbasic.
+  */
+  std::vector<bool> basis;
+
+  /*! \brief
+    A mapping between the tableau rows/columns and the original variables.
+
+    The value of <tt>mapping[i]</tt> depends of the value of <tt>basis[i]</tt>.
+
+     - If <tt>basis[i]</tt> is \b true, <tt>mapping[i]</tt> encodes the column
+       index of variable \p i in the \p s matrix of the tableau.
+     - If <tt>basis[i]</tt> is \b false, <tt>mapping[i]</tt> encodes the row
+       index of variable \p i in the tableau.
+  */
+  std::vector<dimension_type> mapping;
 
 protected:
   /*! \brief