Changeset 2312:07e46cbb7d85 in lemon-0.x for lemon/lp_base.h

Timestamp:

11/29/06 16:01:13 (17 years ago)

Author:

Balazs Dezso

Branch:

default

Phase:

public

Convert:

svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@3088

Message:

modified _setColCoeff and _setRowCoeff parameters
const simplify() for expressions

File:

• lemon/lp_base.h (modified) (35 diffs)

lemon/lp_base.h

@@ -33 +33 @@
 ///\ingroup gen_opt_group
 namespace lemon {
-  
+
+
   ///Internal data structure to convert floating id's to fix one's
     
@@ -110 +111 @@
     int firstIndex() {return _first_index;}
   };
-    
+
   ///Common base class for LP solvers
   
@@ -129 +130 @@
       ///has been proved.
       SOLVED = 0,
-      ///Any other case (including the case when some user specified limit has been exceeded)
+      ///Any other case (including the case when some user specified
+      ///limit has been exceeded)
       UNSOLVED = 1
     };
@@ -222 +224 @@
       }
     };
+
+    static int id(const Col& col) { return col.id; }
+ 
       
     ///Refer to a row of the LP.
@@ -246 +251 @@
       bool operator==(Row c) const  {return id==c.id;}
       bool operator!=(Row c) const  {return id!=c.id;} 
-   };
+    };
+
+    static int id(const Row& row) { return row.id; }
+
+  protected:
+
+    int _lpId(const Col& col) const {
+      return cols.floatingId(id(col));
+    }
+
+    int _lpId(const Row& row) const {
+      return rows.floatingId(id(row));
+    }
+
+
+  public:
     
     ///Linear expression of variables and a constant component
@@ -337 +357 @@
       }
 
+      void simplify() const {
+        const_cast<Expr*>(this)->simplify();
+      }
+
       ///Removes the coefficients closer to zero than \c tolerance.
       void simplify(double &tolerance) {
@@ -416 +440 @@
       typedef Expr::Value Value;
       
-//       static const Value INF;
-//       static const Value NaN;
-
     protected:
       Expr _expr;
@@ -554 +575 @@
       }
 
+      void simplify() const {
+        const_cast<DualExpr*>(this)->simplify();
+      }
+
       ///Removes the coefficients closer to zero than \c tolerance.
       void simplify(double &tolerance) {
@@ -564 +589 @@
       }
 
-
       ///Sets all coefficients to 0.
       void clear() {
@@ -597 +621 @@
     
 
+  private:
+
+    template <typename _Base>
+    class MappedIterator {
+    public:
+
+      typedef _Base Base;
+
+      typedef typename Base::iterator_category iterator_category;
+      typedef typename Base::difference_type difference_type;
+      typedef const std::pair<int, Value> value_type;
+      typedef value_type reference;
+      class pointer {
+      public:
+        pointer(value_type& _value) : value(_value) {}
+        value_type* operator->() { return &value; }
+      private:
+        value_type value;
+      };
+
+      MappedIterator(const Base& _base, const LpSolverBase& _lp) 
+        : base(_base), lp(_lp) {}
+
+      reference operator*() {
+        return std::make_pair(lp._lpId(base->first), base->second);
+      }
+
+      pointer operator->() {
+        return pointer(operator*());
+      }
+
+      MappedIterator& operator++() {
+        ++base;
+        return *this;
+      }
+
+      MappedIterator& operator++(int) {
+        MappedIterator tmp(*this);
+        ++base;
+        return tmp;
+      }
+
+      bool operator==(const MappedIterator& it) const {
+        return base == it.base;
+      }
+
+      bool operator!=(const MappedIterator& it) const {
+        return base != it.base;
+      }
+
+    private:
+      Base base;
+      const LpSolverBase& lp;
+    };
+
   protected:
+
+    /// STL compatible iterator for lp col
+    typedef MappedIterator<Expr::const_iterator> LpRowIterator;
+    /// STL compatible iterator for lp row
+    typedef MappedIterator<DualExpr::const_iterator> LpColIterator;
 
     //Abstract virtual functions
     virtual LpSolverBase &_newLp() = 0;
     virtual LpSolverBase &_copyLp(){
-      ///\todo This should be implemented here, too,  when we have problem retrieving routines. It can be overriden.
+      ///\todo This should be implemented here, too, when we have
+      ///problem retrieving routines. It can be overriden.
 
       //Starting:
@@ -614 +699 @@
     virtual void _eraseCol(int col) = 0;
     virtual void _eraseRow(int row) = 0;
-    virtual void _getColName(int col,       std::string & name) = 0;
+    virtual void _getColName(int col, std::string & name) = 0;
     virtual void _setColName(int col, const std::string & name) = 0;
-    virtual void _setRowCoeffs(int i, 
-                               int length,
-                               int  const * indices, 
-                               Value  const * values ) = 0;
-    virtual void _setColCoeffs(int i, 
-                               int length,
-                               int  const * indices, 
-                               Value  const * values ) = 0;
+    virtual void _setRowCoeffs(int i, LpRowIterator b, LpRowIterator e) = 0;
+    virtual void _setColCoeffs(int i, LpColIterator b, LpColIterator e) = 0;
     virtual void _setCoeff(int row, int col, Value value) = 0;
     virtual void _setColLowerBound(int i, Value value) = 0;
@@ -632 +711 @@
     virtual void _setObjCoeff(int i, Value obj_coef) = 0;
     virtual void _clearObj()=0;
-//     virtual void _setObj(int length,
-//                          int  const * indices, 
-//                          Value  const * values ) = 0;
+
     virtual SolveExitStatus _solve() = 0;
     virtual Value _getPrimal(int i) = 0;
@@ -653 +730 @@
     //Constant component of the objective function
     Value obj_const_comp;
-    
-
-
-    
+        
   public:
 
@@ -745 +819 @@
     ///a better one.
     void col(Col c,const DualExpr &e) {
-      std::vector<int> indices;
-      std::vector<Value> values;
-      indices.push_back(0);
-      values.push_back(0);
-      for(DualExpr::const_iterator i=e.begin(); i!=e.end(); ++i)
-        if((*i).second!=0) {
-          indices.push_back(rows.floatingId((*i).first.id));
-          values.push_back((*i).second);
-        }
-      _setColCoeffs(cols.floatingId(c.id),indices.size()-1,
-                    &indices[0],&values[0]);
+      e.simplify();
+      _setColCoeffs(_lpId(c), LpColIterator(e.begin(), *this), 
+                    LpColIterator(e.end(), *this));
     }
 
@@ -850 +916 @@
     ///added or not.
     void row(Row r, Value l,const Expr &e, Value u) {
-      std::vector<int> indices;
-      std::vector<Value> values;
-      indices.push_back(0);
-      values.push_back(0);
-      for(Expr::const_iterator i=e.begin(); i!=e.end(); ++i)
-        if((*i).second!=0) { ///\bug EPSILON would be necessary here!!!
-          indices.push_back(cols.floatingId((*i).first.id));
-          values.push_back((*i).second);
-        }
-      _setRowCoeffs(rows.floatingId(r.id),indices.size()-1,
-                    &indices[0],&values[0]);
-//       _setRowLowerBound(rows.floatingId(r.id),l-e.constComp());
-//       _setRowUpperBound(rows.floatingId(r.id),u-e.constComp());
-       _setRowBounds(rows.floatingId(r.id),l-e.constComp(),u-e.constComp());
+      e.simplify();
+      _setRowCoeffs(_lpId(r), LpRowIterator(e.begin(), *this),
+                    LpRowIterator(e.end(), *this));
+//       _setRowLowerBound(_lpId(r),l-e.constComp());
+//       _setRowUpperBound(_lpId(r),u-e.constComp());
+       _setRowBounds(_lpId(r),l-e.constComp(),u-e.constComp());
     }
 
@@ -871 +929 @@
     ///\param c is a linear expression (see \ref Constr)
     void row(Row r, const Constr &c) {
-      row(r,
-             c.lowerBounded()?c.lowerBound():-INF,
-             c.expr(),
-             c.upperBounded()?c.upperBound():INF);
+      row(r, c.lowerBounded()?c.lowerBound():-INF,
+          c.expr(), c.upperBounded()?c.upperBound():INF);
     }
 
@@ -905 +961 @@
     ///\todo Please check this
     void eraseCol(Col c) {
-      _eraseCol(cols.floatingId(c.id));
+      _eraseCol(_lpId(c));
       cols.erase(c.id);
     }
@@ -913 +969 @@
     ///\todo Please check this
     void eraseRow(Row r) {
-      _eraseRow(rows.floatingId(r.id));
+      _eraseRow(_lpId(r));
       rows.erase(r.id);
     }
@@ -923 +979 @@
     std::string colName(Col c){
       std::string name;
-      _getColName(cols.floatingId(c.id), name);
+      _getColName(_lpId(c), name);
       return name;
     }
@@ -931 +987 @@
     ///\param c is the coresponding coloumn 
     ///\param name The name to be given
-    void colName(Col c, const std::string & name){
-      _setColName(cols.floatingId(c.id), name);
+    void colName(Col c, const std::string& name){
+      _setColName(_lpId(c), name);
     }
     
@@ -942 +998 @@
 
     void coeff(Row r, Col c, Value val){
-      _setCoeff(rows.floatingId(r.id),cols.floatingId(c.id), val);
+      _setCoeff(_lpId(r),_lpId(c), val);
     }
 
@@ -951 +1007 @@
     /// Value or -\ref INF.
     void colLowerBound(Col c, Value value) {
-      _setColLowerBound(cols.floatingId(c.id),value);
+      _setColLowerBound(_lpId(c),value);
     }
     
@@ -997 +1053 @@
     /// Value or \ref INF.
     void colUpperBound(Col c, Value value) {
-      _setColUpperBound(cols.floatingId(c.id),value);
+      _setColUpperBound(_lpId(c),value);
     };
 
@@ -1044 +1100 @@
     /// Value, -\ref INF or \ref INF.
     void colBounds(Col c, Value lower, Value upper) {
-      _setColLowerBound(cols.floatingId(c.id),lower);
-      _setColUpperBound(cols.floatingId(c.id),upper);
+      _setColLowerBound(_lpId(c),lower);
+      _setColUpperBound(_lpId(c),upper);
     }
     
@@ -1092 +1148 @@
 //     /// Value or -\ref INF.
 //     void rowLowerBound(Row r, Value value) {
-//       _setRowLowerBound(rows.floatingId(r.id),value);
+//       _setRowLowerBound(_lpId(r),value);
 //     };
 //     /// Set the upper bound of a row (i.e a constraint)
@@ -1100 +1156 @@
 //     /// Value or \ref INF.
 //     void rowUpperBound(Row r, Value value) {
-//       _setRowUpperBound(rows.floatingId(r.id),value);
+//       _setRowUpperBound(_lpId(r),value);
 //     };
 
@@ -1110 +1166 @@
     /// Value, -\ref INF or \ref INF.
     void rowBounds(Row c, Value lower, Value upper) {
-      _setRowBounds(rows.floatingId(c.id),lower, upper);
-      // _setRowUpperBound(rows.floatingId(c.id),upper);
+      _setRowBounds(_lpId(c),lower, upper);
+      // _setRowUpperBound(_lpId(c),upper);
     }
     
     ///Set an element of the objective function
-    void objCoeff(Col c, Value v) {_setObjCoeff(cols.floatingId(c.id),v); };
+    void objCoeff(Col c, Value v) {_setObjCoeff(_lpId(c),v); };
     ///Set the objective function
     
@@ -1171 +1227 @@
 
     ///\e
-    Value primal(Col c) { return _getPrimal(cols.floatingId(c.id)); }
+    Value primal(Col c) { return _getPrimal(_lpId(c)); }
 
     ///\e
-    Value dual(Row r) { return _getDual(rows.floatingId(r.id)); }
+    Value dual(Row r) { return _getDual(_lpId(r)); }
 
     ///\e
-    bool isBasicCol(Col c) { return _isBasicCol(cols.floatingId(c.id)); }
+    bool isBasicCol(Col c) { return _isBasicCol(_lpId(c)); }
 
     ///\e
@@ -1214 +1270 @@
     ///Sets the type of the given coloumn to the given type.
     void colType(Col c, ColTypes col_type) {
-      _colType(cols.floatingId(c.id),col_type);
+      _colType(_lpId(c),col_type);
     }
 
@@ -1221 +1277 @@
     ///Gives back the type of the column.
     ColTypes colType(Col c){
-      return _colType(cols.floatingId(c.id));
+      return _colType(_lpId(c));
     }
 
@@ -1441 +1497 @@
   ///
   inline LpSolverBase::DualExpr operator+(const LpSolverBase::DualExpr &a,
-                                      const LpSolverBase::DualExpr &b) 
+                                          const LpSolverBase::DualExpr &b) 
   {
     LpSolverBase::DualExpr tmp(a);
@@ -1452 +1508 @@
   ///
   inline LpSolverBase::DualExpr operator-(const LpSolverBase::DualExpr &a,
-                                      const LpSolverBase::DualExpr &b) 
+                                          const LpSolverBase::DualExpr &b) 
   {
     LpSolverBase::DualExpr tmp(a);
@@ -1463 +1519 @@
   ///
   inline LpSolverBase::DualExpr operator*(const LpSolverBase::DualExpr &a,
-                                      const LpSolverBase::Value &b) 
+                                          const LpSolverBase::Value &b) 
   {
     LpSolverBase::DualExpr tmp(a);
@@ -1475 +1531 @@
   ///
   inline LpSolverBase::DualExpr operator*(const LpSolverBase::Value &a,
-                                      const LpSolverBase::DualExpr &b) 
+                                          const LpSolverBase::DualExpr &b) 
   {
     LpSolverBase::DualExpr tmp(b);
@@ -1486 +1542 @@
   ///
   inline LpSolverBase::DualExpr operator/(const LpSolverBase::DualExpr &a,
-                                      const LpSolverBase::Value &b) 
+                                          const LpSolverBase::Value &b) 
   {
     LpSolverBase::DualExpr tmp(a);