Changeset 1273:2b2ffa625775 in lemon-0.x for src/work/athos/lp

Timestamp:

03/30/05 12:38:22 (20 years ago)

Author:

Alpar Juttner

Branch:

default

Phase:

public

Convert:

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

Message:

• Better (but still incomplete) doc
• lp_test runs correctly

Location:

src/work/athos/lp

Files:

• lp_base.cc (modified) (1 diff)
• lp_base.h (modified) (22 diffs)
• lp_solver_skeleton.cc (modified) (1 diff)
• lp_solver_skeleton.h (modified) (2 diffs)
• lp_test.cc (modified) (4 diffs)

src/work/athos/lp/lp_base.cc

@@ -26 +26 @@
   LpSolverBase::NaN = std::numeric_limits<Value>::quiet_NaN();
 
-  const LpSolverBase::Constr::Coeff
+  const LpSolverBase::Constr::Value
   LpSolverBase::Constr::INF = std::numeric_limits<Value>::infinity();
-  const LpSolverBase::Constr::Coeff
+  const LpSolverBase::Constr::Value
   LpSolverBase::Constr::NaN = std::numeric_limits<Value>::quiet_NaN();
   

src/work/athos/lp/lp_base.h

@@ -21 +21 @@
 #include<map>
 #include<limits>
+#include<math.h>
 
 #include<lemon/utility.h>
@@ -73 +74 @@
         return cross[n];
       }
+      ///\todo Create an own exception type.
       else throw LogicError(); //floatingId-s must form a continuous range;
     }
@@ -127 +129 @@
     ///
     ///Its value remains valid and correct even after the addition or erase of
-    ///new column (unless the referred column itself was also deleted,
-    ///of course).
+    ///other columns.
     ///
     ///\todo Document what can one do with a Col (INVALID, comparing,
@@ -151 +152 @@
     ///
     ///Its value remains valid and correct even after the addition or erase of
-    ///new rows (unless the referred row itself was also deleted, of course).
+    ///other rows.
     ///
     ///\todo Document what can one do with a Row (INVALID, comparing,
@@ -172 +173 @@
     ///Linear expression
     //    typedef SparseLinExpr<Col> Expr;
-    class Expr : public std::map<Col,Col::ExprValue>
+    class Expr : public std::map<Col,Value>
     {
     public:
-      typedef Col Var; 
-      typedef Col::ExprValue Coeff;
+      typedef LpSolverBase::Col Key; 
+      typedef LpSolverBase::Value Value;
       
     protected:
-      typedef std::map<Col,Col::ExprValue> Base;
+      typedef std::map<Col,Value> Base;
       
-      Coeff const_comp;
+      Value const_comp;
   public:
       typedef True IsLinExpression;
@@ -187 +188 @@
       Expr() : Base(), const_comp(0) { }
       ///\e
-      Expr(const Var &v) : const_comp(0) {
+      Expr(const Key &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) {
+      Expr(const Value &v) : const_comp(v) {}
+      ///\e
+      void set(const Key &v,const Value &c) {
         Base::insert(std::make_pair(v, c));
       }
       ///\e
-      Coeff &constComp() { return const_comp; }
-      ///\e
-      const Coeff &constComp() const { return const_comp; }
+      Value &constComp() { return const_comp; }
+      ///\e
+      const Value &constComp() const { return const_comp; }
       
       ///Removes the components with zero coefficient.
@@ -210 +211 @@
         }
       }
-      
+
+      ///Sets all coefficients and the constant component to 0.
+      void clear() {
+        Base::clear();
+        const_comp=0;
+      }
+
       ///\e
       Expr &operator+=(const Expr &e) {
@@ -227 +234 @@
       }
       ///\e
-      Expr &operator*=(const Coeff &c) {
+      Expr &operator*=(const Value &c) {
         for (Base::iterator j=Base::begin(); j!=Base::end(); ++j)
           j->second*=c;
@@ -234 +241 @@
       }
       ///\e
-      Expr &operator/=(const Coeff &c) {
+      Expr &operator/=(const Value &c) {
         for (Base::iterator j=Base::begin(); j!=Base::end(); ++j)
           j->second/=c;
@@ -248 +255 @@
     public:
       typedef LpSolverBase::Expr Expr;
-      typedef Expr::Var Var;
-      typedef Expr::Coeff Coeff;
+      typedef Expr::Key Key;
+      typedef Expr::Value Value;
       
-      static const Coeff INF;
-      static const Coeff NaN;
-      //     static const Coeff INF=0;
-      //     static const Coeff NaN=1;
+      static const Value INF;
+      static const Value NaN;
+      //     static const Value INF=0;
+      //     static const Value 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) {}
+    protected:
+      Expr _expr;
+      Value _lb,_ub;
+    public:
+      ///\e
+      Constr() : _expr(), _lb(NaN), _ub(NaN) {}
+      ///\e
+      Constr(Value lb,const Expr &e,Value ub) :
+        _expr(e), _lb(lb), _ub(ub) {}
+      ///\e
+      Constr(const Expr &e,Value ub) : 
+        _expr(e), _lb(NaN), _ub(ub) {}
+      ///\e
+      Constr(Value lb,const Expr &e) :
+        _expr(e), _lb(lb), _ub(NaN) {}
+      ///\e
       Constr(const Expr &e) : 
-        expr(e), lb(NaN), ub(NaN) {}
+        _expr(e), _lb(NaN), _ub(NaN) {}
+      ///\e
+      void clear() 
+      {
+        _expr.clear();
+        _lb=_ub=NaN;
+      }
+      ///\e
+      Expr &expr() { return _expr; }
+      ///\e
+      const Expr &expr() const { return _expr; }
+      ///\e
+      Value &lowerBound() { return _lb; }
+      ///\e
+      const Value &lowerBound() const { return _lb; }
+      ///\e
+      Value &upperBound() { return _ub; }
+      ///\e
+      const Value &upperBound() const { return _ub; }
     };
     
@@ -355 +386 @@
     ///(i.e a new variables)
     ///
-    ///This magic function takes container as its argument
+    ///This magic function takes a container as its argument
     ///and fills its elements
     ///with new columns (i.e. variables)
-    ///\param t can be either any standard STL iterable container with
-    ///\ref Col \c values_type or \c mapped_type
-    ///like <tt>std::vector<LpSolverBase::Col></tt>,
-    /// <tt>std::list<LpSolverBase::Col></tt> or
-    /// <tt>std::map<AnyType,LpSolverBase::Col></tt> or
-    ///it can be an iterable lemon map like 
-    /// <tt>ListGraph::NodeMap<LpSolverBase::Col></tt>.
+    ///\param t can be
+    ///- a standard STL compatible iterable container with
+    ///\ref Col as its \c values_type
+    ///like
+    ///\code
+    ///std::vector<LpSolverBase::Col>
+    ///std::list<LpSolverBase::Col>
+    ///\endcode
+    ///- a standard STL compatible iterable container with
+    ///\ref Col as its \c mapped_type
+    ///like
+    ///\code
+    ///std::map<AnyType,LpSolverBase::Col>
+    ///\endcode
+    ///- an iterable lemon \ref concept::WriteMap "write map" like 
+    ///\code
+    ///ListGraph::NodeMap<LpSolverBase::Col>
+    ///ListGraph::EdgeMap<LpSolverBase::Col>
+    ///\endcode
     ///\return The number of the created column.
     ///\bug Iterable nodemap hasn't been implemented yet.
@@ -441 +484 @@
     ///\param c is a linear expression (see \ref Constr)
     void setRow(Row r, const Constr &c) {
-      Value lb= c.lb==NaN?-INF:lb;
-      Value ub= c.ub==NaN?INF:lb;
-      setRow(r,lb,c.expr,ub);
+      setRow(r,
+             isnan(c.lowerBound())?-INF:c.lowerBound(),
+             c.expr(),
+             isnan(c.upperBound())?INF:c.upperBound());
     }
 
@@ -564 +608 @@
   ///
   inline LpSolverBase::Expr operator*(const LpSolverBase::Expr &a,
-                                      const LpSolverBase::Expr::Coeff &b) 
+                                      const LpSolverBase::Value &b) 
   {
     LpSolverBase::Expr tmp(a);
@@ -575 +619 @@
   ///\relates LpSolverBase::Expr
   ///
-  inline LpSolverBase::Expr operator*(const LpSolverBase::Expr::Coeff &a,
+  inline LpSolverBase::Expr operator*(const LpSolverBase::Value &a,
                                       const LpSolverBase::Expr &b) 
   {
@@ -587 +631 @@
   ///
   inline LpSolverBase::Expr operator/(const LpSolverBase::Expr &a,
-                                      const LpSolverBase::Expr::Coeff &b) 
+                                      const LpSolverBase::Value &b) 
   {
     LpSolverBase::Expr tmp(a);
@@ -608 +652 @@
   ///\relates LpSolverBase::Constr
   ///
-  inline LpSolverBase::Constr operator<=(const LpSolverBase::Expr::Coeff &e,
+  inline LpSolverBase::Constr operator<=(const LpSolverBase::Value &e,
                                          const LpSolverBase::Expr &f) 
   {
@@ -619 +663 @@
   ///
   inline LpSolverBase::Constr operator<=(const LpSolverBase::Expr &e,
-                                         const LpSolverBase::Expr::Coeff &f) 
+                                         const LpSolverBase::Value &f) 
   {
     return LpSolverBase::Constr(e,f);
@@ -639 +683 @@
   ///\relates LpSolverBase::Constr
   ///
-  inline LpSolverBase::Constr operator>=(const LpSolverBase::Expr::Coeff &e,
+  inline LpSolverBase::Constr operator>=(const LpSolverBase::Value &e,
                                          const LpSolverBase::Expr &f) 
   {
@@ -651 +695 @@
   ///
   inline LpSolverBase::Constr operator>=(const LpSolverBase::Expr &e,
-                                         const LpSolverBase::Expr::Coeff &f) 
+                                         const LpSolverBase::Value &f) 
   {
     return LpSolverBase::Constr(f,e);
@@ -670 +714 @@
   ///\relates LpSolverBase::Constr
   ///
-  inline LpSolverBase::Constr operator<=(const LpSolverBase::Constr::Coeff &n,
+  inline LpSolverBase::Constr operator<=(const LpSolverBase::Value &n,
                                          const LpSolverBase::Constr&c) 
   {
     LpSolverBase::Constr tmp(c);
-    if(tmp.lb!=tmp.NaN) throw LogicError();
-    else tmp.lb=n;
+    ///\todo Create an own exception type.
+    if(!isnan(tmp.lowerBound())) throw LogicError();
+    else tmp.lowerBound()=n;
     return tmp;
   }
@@ -683 +728 @@
   ///
   inline LpSolverBase::Constr operator<=(const LpSolverBase::Constr& c,
-                                         const LpSolverBase::Constr::Coeff &n)
+                                         const LpSolverBase::Value &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,
+    ///\todo Create an own exception type.
+    if(!isnan(tmp.upperBound())) throw LogicError();
+    else tmp.upperBound()=n;
+    return tmp;
+  }
+
+  ///\e
+  
+  ///\relates LpSolverBase::Constr
+  ///
+  inline LpSolverBase::Constr operator>=(const LpSolverBase::Value &n,
                                          const LpSolverBase::Constr&c) 
   {
     LpSolverBase::Constr tmp(c);
-    if(tmp.ub!=tmp.NaN) throw LogicError();
-    else tmp.ub=n;
+    ///\todo Create an own exception type.
+    if(!isnan(tmp.upperBound())) throw LogicError();
+    else tmp.upperBound()=n;
     return tmp;
   }
@@ -708 +755 @@
   ///
   inline LpSolverBase::Constr operator>=(const LpSolverBase::Constr& c,
-                                         const LpSolverBase::Constr::Coeff &n)
+                                         const LpSolverBase::Value &n)
   {
     LpSolverBase::Constr tmp(c);
-    if(tmp.lb!=tmp.NaN) throw LogicError();
-    else tmp.lb=n;
+    ///\todo Create an own exception type.
+    if(!isnan(tmp.lowerBound())) throw LogicError();
+    else tmp.lowerBound()=n;
     return tmp;
   }

src/work/athos/lp/lp_solver_skeleton.cc

@@ -24 +24 @@
   int LpSolverSkeleton::_addCol()
   {
-    return 1;
+    return ++col_num;
   }
   
   int LpSolverSkeleton::_addRow() 
   {
-    return 1;
+    return ++row_num;
   }
   

src/work/athos/lp/lp_solver_skeleton.h

@@ -27 +27 @@
   ///A skeleton class to implement LP solver interfaces
   class LpSolverSkeleton :public LpSolverBase {
-
+    int col_num,row_num;
+    
   protected:
     virtual int _addCol();
@@ -46 +47 @@
     virtual SolutionType _solve();
     virtual Value _getSolution(int i);
-
+  public:
+    LpSolverSkeleton() : LpSolverBase(), col_num(0), row_num(0) {}
   };  
 

src/work/athos/lp/lp_test.cc

@@ -117 +117 @@
   
   lp.addRow(LP::INF,e,23);
-  lp.addRow(LP::INF,3.0*(p1+p2)-p3,23);
   lp.addRow(LP::INF,3.0*(x[1]+x[2]/2)-x[3],23);
-  lp.addRow(LP::INF,3.0*(p1+p2*2-5*p3+12-p4/3)+2*p4-4,23);
   lp.addRow(LP::INF,3.0*(x[1]+x[2]*2-5*x[3]+12-x[4]/3)+2*x[4]-4,23);
 
   lp.addRow(x[1]+x[3]<=x[5]-3);
   lp.addRow(-7<=x[1]+x[3]-12<=3);
-  //lp.addRow(x[1]<=x[5]);
+  lp.addRow(x[1]<=x[5]);
 
 }
@@ -144 +142 @@
   typename G::EdgeMap<LpGlpk::Col> x(g);
   lp.addColSet(x);
-   //for(EdgeIt e(g);e!=INVALID;++e) x[e]=lp.addCol();
   
   for(EdgeIt e(g);e!=INVALID;++e) {
@@ -155 +152 @@
     for(InEdgeIt  e(g,n);e!=INVALID;++e) ex+=x[e];
     for(OutEdgeIt e(g,n);e!=INVALID;++e) ex-=x[e];
-    lp.addRow(0,ex,0);
+    lp.addRow(ex==0);
   }
   {
@@ -178 +175 @@
 
   ListGraph g;
+  ListGraph::Node s=g.addNode();
+  ListGraph::Node t=g.addNode();
+
   ListGraph::EdgeMap<double> cap(g);
   
-  maxFlow(g,cap,ListGraph::NodeIt(g),ListGraph::NodeIt(g));
+  maxFlow(g,cap,s,t);
 
 }