Changeset 1272:17be4c5bc6c6 in lemon-0.x for src/work/athos/lp/lp_base.h

Timestamp:

03/30/05 10:28:44 (19 years ago)

Author:

Alpar Juttner

Branch:

default

Phase:

public

Convert:

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

Message:

• Non-template expressions and constraints (lin_expr.h isn't used)

File:

• src/work/athos/lp/lp_base.h (modified) (7 diffs)

src/work/athos/lp/lp_base.h

@@ -19 +19 @@
 
 #include<vector>
+#include<map>
 #include<limits>
 
@@ -25 +26 @@
 #include<lemon/invalid.h>
 
-#include"lin_expr.h"
+//#include"lin_expr.h"
+
 ///\file
 ///\brief The interface of the LP solver interface.
@@ -169 +171 @@
     
     ///Linear expression
-    typedef SparseLinExpr<Col> Expr;
+    //    typedef SparseLinExpr<Col> Expr;
+    class Expr : public std::map<Col,Col::ExprValue>
+    {
+    public:
+      typedef Col Var; 
+      typedef Col::ExprValue Coeff;
+      
+    protected:
+      typedef std::map<Col,Col::ExprValue> Base;
+      
+      Coeff const_comp;
+  public:
+      typedef True IsLinExpression;
+      ///\e
+      Expr() : Base(), const_comp(0) { }
+      ///\e
+      Expr(const Var &v) : const_comp(0) {
+        Base::insert(std::make_pair(v, 1));
+      }
+      ///\e
+      Expr(const Coeff &v) : const_comp(v) {}
+      ///\e
+      void set(const Var &v,const Coeff &c) {
+        Base::insert(std::make_pair(v, c));
+      }
+      ///\e
+      Coeff &constComp() { return const_comp; }
+      ///\e
+      const Coeff &constComp() const { return const_comp; }
+      
+      ///Removes the components with zero coefficient.
+      void simplify() {
+        for (Base::iterator i=Base::begin(); i!=Base::end();) {
+          Base::iterator j=i;
+          ++j;
+          if ((*i).second==0) Base::erase(i);
+          j=i;
+        }
+      }
+      
+      ///\e
+      Expr &operator+=(const Expr &e) {
+        for (Base::const_iterator j=e.begin(); j!=e.end(); ++j)
+          (*this)[j->first]+=j->second;
+        ///\todo it might be speeded up using "hints"
+        const_comp+=e.const_comp;
+        return *this;
+      }
+      ///\e
+      Expr &operator-=(const Expr &e) {
+        for (Base::const_iterator j=e.begin(); j!=e.end(); ++j)
+          (*this)[j->first]-=j->second;
+        const_comp-=e.const_comp;
+        return *this;
+      }
+      ///\e
+      Expr &operator*=(const Coeff &c) {
+        for (Base::iterator j=Base::begin(); j!=Base::end(); ++j)
+          j->second*=c;
+        const_comp*=c;
+        return *this;
+      }
+      ///\e
+      Expr &operator/=(const Coeff &c) {
+        for (Base::iterator j=Base::begin(); j!=Base::end(); ++j)
+          j->second/=c;
+        const_comp/=c;
+        return *this;
+      }
+    };
+    
     ///Linear constraint
-    typedef LinConstr<Expr> Constr;
+    //typedef LinConstr<Expr> Constr;
+    class Constr
+    {
+    public:
+      typedef LpSolverBase::Expr Expr;
+      typedef Expr::Var Var;
+      typedef Expr::Coeff Coeff;
+      
+      static const Coeff INF;
+      static const Coeff NaN;
+      //     static const Coeff INF=0;
+      //     static const Coeff NaN=1;
+      
+      Expr expr;
+      Coeff lb,ub;
+      
+      Constr() : expr(), lb(NaN), ub(NaN) {}
+      Constr(Coeff _lb,const Expr &e,Coeff _ub) :
+        expr(e), lb(_lb), ub(_ub) {}
+      Constr(const Expr &e,Coeff _ub) : 
+        expr(e), lb(NaN), ub(_ub) {}
+      Constr(Coeff _lb,const Expr &e) :
+        expr(e), lb(_lb), ub(NaN) {}
+      Constr(const Expr &e) : 
+        expr(e), lb(NaN), ub(NaN) {}
+    };
+    
 
   protected:
@@ -291 +389 @@
       return s;
     }
+    template<class T>
+    typename enable_if<typename T::ValueSet::value_type::LpSolverCol,
+                       int>::type
+    addColSet(T &t,dummy<2> = 2) { 
+      ///\bug <tt>return addColSet(t.valueSet());</tt> should also work.
+      int s=0;
+      for(typename T::ValueSet::iterator i=t.valueSet().begin();
+          i!=t.valueSet().end();
+          ++i)
+        {
+          *i=addCol();
+          s++;
+        }
+      return s;
+    }
 #endif
 
@@ -327 +440 @@
     ///\param r is the row to be modified
     ///\param c is a linear expression (see \ref Constr)
-    ///\bug This is a temportary function. The interface will change to
-    ///a better one.
     void setRow(Row r, const Constr &c) {
       Value lb= c.lb==NaN?-INF:lb;
@@ -353 +464 @@
     ///\param c is a linear expression (see \ref Constr)
     ///\return The created row.
-    ///\bug This is a temportary function. The interface will change to
-    ///a better one.
     Row addRow(const Constr &c) {
       Row r=addRow();
@@ -428 +537 @@
   };  
 
+  ///\e
+  
+  ///\relates LpSolverBase::Expr
+  ///
+  inline LpSolverBase::Expr operator+(const LpSolverBase::Expr &a,
+                                      const LpSolverBase::Expr &b) 
+  {
+    LpSolverBase::Expr tmp(a);
+    tmp+=b; ///\todo Don't STL have some special 'merge' algorithm?
+    return tmp;
+  }
+  ///\e
+  
+  ///\relates LpSolverBase::Expr
+  ///
+  inline LpSolverBase::Expr operator-(const LpSolverBase::Expr &a,
+                                      const LpSolverBase::Expr &b) 
+  {
+    LpSolverBase::Expr tmp(a);
+    tmp-=b; ///\todo Don't STL have some special 'merge' algorithm?
+    return tmp;
+  }
+  ///\e
+  
+  ///\relates LpSolverBase::Expr
+  ///
+  inline LpSolverBase::Expr operator*(const LpSolverBase::Expr &a,
+                                      const LpSolverBase::Expr::Coeff &b) 
+  {
+    LpSolverBase::Expr tmp(a);
+    tmp*=b; ///\todo Don't STL have some special 'merge' algorithm?
+    return tmp;
+  }
+  
+  ///\e
+  
+  ///\relates LpSolverBase::Expr
+  ///
+  inline LpSolverBase::Expr operator*(const LpSolverBase::Expr::Coeff &a,
+                                      const LpSolverBase::Expr &b) 
+  {
+    LpSolverBase::Expr tmp(b);
+    tmp*=a; ///\todo Don't STL have some special 'merge' algorithm?
+    return tmp;
+  }
+  ///\e
+  
+  ///\relates LpSolverBase::Expr
+  ///
+  inline LpSolverBase::Expr operator/(const LpSolverBase::Expr &a,
+                                      const LpSolverBase::Expr::Coeff &b) 
+  {
+    LpSolverBase::Expr tmp(a);
+    tmp/=b; ///\todo Don't STL have some special 'merge' algorithm?
+    return tmp;
+  }
+  
+  ///\e
+  
+  ///\relates LpSolverBase::Constr
+  ///
+  inline LpSolverBase::Constr operator<=(const LpSolverBase::Expr &e,
+                                         const LpSolverBase::Expr &f) 
+  {
+    return LpSolverBase::Constr(-LpSolverBase::INF,e-f,0);
+  }
+
+  ///\e
+  
+  ///\relates LpSolverBase::Constr
+  ///
+  inline LpSolverBase::Constr operator<=(const LpSolverBase::Expr::Coeff &e,
+                                         const LpSolverBase::Expr &f) 
+  {
+    return LpSolverBase::Constr(e,f);
+  }
+
+  ///\e
+  
+  ///\relates LpSolverBase::Constr
+  ///
+  inline LpSolverBase::Constr operator<=(const LpSolverBase::Expr &e,
+                                         const LpSolverBase::Expr::Coeff &f) 
+  {
+    return LpSolverBase::Constr(e,f);
+  }
+
+  ///\e
+  
+  ///\relates LpSolverBase::Constr
+  ///
+  inline LpSolverBase::Constr operator>=(const LpSolverBase::Expr &e,
+                                         const LpSolverBase::Expr &f) 
+  {
+    return LpSolverBase::Constr(-LpSolverBase::INF,f-e,0);
+  }
+
+
+  ///\e
+  
+  ///\relates LpSolverBase::Constr
+  ///
+  inline LpSolverBase::Constr operator>=(const LpSolverBase::Expr::Coeff &e,
+                                         const LpSolverBase::Expr &f) 
+  {
+    return LpSolverBase::Constr(f,e);
+  }
+
+
+  ///\e
+  
+  ///\relates LpSolverBase::Constr
+  ///
+  inline LpSolverBase::Constr operator>=(const LpSolverBase::Expr &e,
+                                         const LpSolverBase::Expr::Coeff &f) 
+  {
+    return LpSolverBase::Constr(f,e);
+  }
+
+  ///\e
+  
+  ///\relates LpSolverBase::Constr
+  ///
+  inline LpSolverBase::Constr operator==(const LpSolverBase::Expr &e,
+                                         const LpSolverBase::Expr &f) 
+  {
+    return LpSolverBase::Constr(0,e-f,0);
+  }
+
+  ///\e
+  
+  ///\relates LpSolverBase::Constr
+  ///
+  inline LpSolverBase::Constr operator<=(const LpSolverBase::Constr::Coeff &n,
+                                         const LpSolverBase::Constr&c) 
+  {
+    LpSolverBase::Constr tmp(c);
+    if(tmp.lb!=tmp.NaN) throw LogicError();
+    else tmp.lb=n;
+    return tmp;
+  }
+  ///\e
+  
+  ///\relates LpSolverBase::Constr
+  ///
+  inline LpSolverBase::Constr operator<=(const LpSolverBase::Constr& c,
+                                         const LpSolverBase::Constr::Coeff &n)
+  {
+    LpSolverBase::Constr tmp(c);
+    if(tmp.ub!=tmp.NaN) throw LogicError();
+    else tmp.ub=n;
+    return tmp;
+  }
+
+  ///\e
+  
+  ///\relates LpSolverBase::Constr
+  ///
+  inline LpSolverBase::Constr operator>=(const LpSolverBase::Constr::Coeff &n,
+                                         const LpSolverBase::Constr&c) 
+  {
+    LpSolverBase::Constr tmp(c);
+    if(tmp.ub!=tmp.NaN) throw LogicError();
+    else tmp.ub=n;
+    return tmp;
+  }
+  ///\e
+  
+  ///\relates LpSolverBase::Constr
+  ///
+  inline LpSolverBase::Constr operator>=(const LpSolverBase::Constr& c,
+                                         const LpSolverBase::Constr::Coeff &n)
+  {
+    LpSolverBase::Constr tmp(c);
+    if(tmp.lb!=tmp.NaN) throw LogicError();
+    else tmp.lb=n;
+    return tmp;
+  }
+
+
 } //namespace lemon