1.1 --- a/src/work/athos/lp/lin_expr.h Fri Mar 25 11:03:49 2005 +0000
1.2 +++ b/src/work/athos/lp/lin_expr.h Fri Mar 25 12:58:52 2005 +0000
1.3 @@ -27,31 +27,37 @@
1.4 namespace lemon {
1.5
1.6 /// Class to handle sparse linear expressions
1.7 - template <class _V,class _C>
1.8 - class SparseLinExpr : public std::map<_V, _C>
1.9 + template <class _V>
1.10 + class SparseLinExpr : public std::map<_V, typename _V::ExprValue>
1.11 {
1.12 public:
1.13 typedef _V Var;
1.14 - typedef _C Coeff;
1.15 + typedef typename _V::ExprValue Coeff;
1.16
1.17 protected:
1.18 - typedef typename std::map<_V, _C> Base;
1.19 + typedef typename std::map<_V, typename _V::ExprValue> Base;
1.20
1.21 Coeff const_comp;
1.22 public:
1.23 - SparseLinExpr() { }
1.24 - SparseLinExpr(const Var &v) : const_comp(v) {
1.25 + ///\e
1.26 + SparseLinExpr() : Base(), const_comp(0) { }
1.27 + ///\e
1.28 + SparseLinExpr(const Var &v) : const_comp(0) {
1.29 Base::insert(std::make_pair(v, 1));
1.30 }
1.31 + ///\e
1.32 SparseLinExpr(const Coeff &v) : const_comp(v) {}
1.33
1.34 + ///\e
1.35 void set(const Var &v,const Coeff &c) {
1.36 return Base::insert(std::make_pair(v, c));
1.37 }
1.38 // Coeff &operator[](const Var &v) { return data[v]; }
1.39 // const Coeff &operator[](const Var &v) const { return data[v]; }
1.40
1.41 + ///\e
1.42 Coeff &constComp() { return const_comp; }
1.43 + ///\e
1.44 const Coeff &constComp() const { return const_comp; }
1.45
1.46 ///Removes the components with zero coefficient.
1.47 @@ -64,8 +70,238 @@
1.48 }
1.49 }
1.50
1.51 + ///\e
1.52 + SparseLinExpr &operator+=(const SparseLinExpr &e) {
1.53 + for (typename Base::const_iterator j=e.begin(); j!=e.end(); ++j)
1.54 + (*this)[j->first]+=j->second;
1.55 + ///\todo it might be speeded up using "hints"
1.56 + const_comp+=e.const_comp;
1.57 + return *this;
1.58 + }
1.59 + ///\e
1.60 + SparseLinExpr &operator-=(const SparseLinExpr &e) {
1.61 + for (typename Base::const_iterator j=e.begin(); j!=e.end(); ++j)
1.62 + (*this)[j->first]-=j->second;
1.63 + const_comp-=e.const_comp;
1.64 + return *this;
1.65 + }
1.66 + ///\e
1.67 + SparseLinExpr &operator*=(const Coeff &c) {
1.68 + for (typename Base::iterator j=Base::begin(); j!=Base::end(); ++j)
1.69 + j->second*=c;
1.70 + const_comp*=c;
1.71 + return *this;
1.72 + }
1.73 + ///\e
1.74 + SparseLinExpr &operator/=(const Coeff &c) {
1.75 + for (typename Base::iterator j=Base::begin(); j!=Base::end(); ++j)
1.76 + j->second/=c;
1.77 + const_comp/=c;
1.78 + return *this;
1.79 + }
1.80 +
1.81 };
1.82
1.83 + ///\e
1.84 +
1.85 + ///\relates SparseLinExpr
1.86 + ///
1.87 + template <class V>
1.88 + SparseLinExpr<V> operator+(const SparseLinExpr<V> &a,
1.89 + const SparseLinExpr<V> &b) {
1.90 + SparseLinExpr<V> tmp(a);
1.91 + tmp+=b; ///\todo Don't STL have some special 'merge' algorithm?
1.92 + return tmp;
1.93 + }
1.94 +
1.95 + ///\e
1.96 +
1.97 + ///\relates SparseLinExpr
1.98 + ///
1.99 + template <class V>
1.100 + SparseLinExpr<V> operator-(const SparseLinExpr<V> &a,
1.101 + const SparseLinExpr<V> &b) {
1.102 + SparseLinExpr<V> tmp(a);
1.103 + tmp-=b; ///\todo Don't STL have some special 'merge' algorithm?
1.104 + return tmp;
1.105 + }
1.106 +
1.107 + ///\e
1.108 +
1.109 + ///\relates SparseLinExpr
1.110 + ///
1.111 + template <class V>
1.112 + SparseLinExpr<V> operator*(const typename V::ExprValue &c,
1.113 + const SparseLinExpr<V> &e) {
1.114 + SparseLinExpr<V> tmp(e);
1.115 + tmp*=c;
1.116 + return tmp;
1.117 + }
1.118 +
1.119 + ///\e
1.120 +
1.121 + ///\relates SparseLinExpr
1.122 + ///
1.123 + template <class V>
1.124 + SparseLinExpr<V> operator*(const SparseLinExpr<V> &e,
1.125 + const typename V::ExprValue &c) {
1.126 + SparseLinExpr<V> tmp(e);
1.127 + tmp*=c;
1.128 + return tmp;
1.129 + }
1.130 +
1.131 +
1.132 + ///\e
1.133 +
1.134 + ///\relates SparseLinExpr
1.135 + ///
1.136 + template <class V>
1.137 + SparseLinExpr<V> operator/(const SparseLinExpr<V> &e,
1.138 + const typename V::ExprValue &c) {
1.139 + SparseLinExpr<V> tmp(e);
1.140 + tmp/=c;
1.141 + return tmp;
1.142 + }
1.143 +
1.144 + ///\e
1.145 +
1.146 + ///\relates SparseLinExpr
1.147 + ///
1.148 + template <class V>
1.149 + SparseLinExpr<V> operator+(const typename V::ExprValue &c,
1.150 + const SparseLinExpr<V> &e) {
1.151 + SparseLinExpr<V> tmp(e);
1.152 + tmp.constComp()+=c;
1.153 + return tmp;
1.154 + }
1.155 +
1.156 + ///\e
1.157 +
1.158 + ///\relates SparseLinExpr
1.159 + ///
1.160 + template <class V>
1.161 + SparseLinExpr<V> operator+(const SparseLinExpr<V> &e,
1.162 + const typename V::ExprValue &c) {
1.163 + SparseLinExpr<V> tmp(e);
1.164 + tmp.constComp()+=c;
1.165 + return tmp;
1.166 + }
1.167 +
1.168 + ///\e
1.169 +
1.170 + ///\relates SparseLinExpr
1.171 + ///
1.172 + template <class V>
1.173 + SparseLinExpr<V> operator+(const V &v,const SparseLinExpr<V> &e) {
1.174 + SparseLinExpr<V> tmp(e);
1.175 + tmp[v]+=1;
1.176 + return tmp;
1.177 + }
1.178 +
1.179 + ///\e
1.180 +
1.181 + ///\relates SparseLinExpr
1.182 + ///
1.183 + template <class V>
1.184 + SparseLinExpr<V> operator+(const SparseLinExpr<V> &e,const V &v) {
1.185 + SparseLinExpr<V> tmp(e);
1.186 + tmp[v]+=1;
1.187 + return tmp;
1.188 + }
1.189 +
1.190 + ///\e
1.191 +
1.192 + ///\relates SparseLinExpr
1.193 + ///
1.194 + template <class V>
1.195 + SparseLinExpr<V> operator-(const typename V::ExprValue &c,
1.196 + const SparseLinExpr<V> &e) {
1.197 + SparseLinExpr<V> tmp(e);
1.198 + tmp*=-1;
1.199 + tmp.constComp()+=c;
1.200 + return tmp;
1.201 + }
1.202 +
1.203 + ///\e
1.204 +
1.205 + ///\relates SparseLinExpr
1.206 + ///
1.207 + template <class V>
1.208 + SparseLinExpr<V> operator-(const SparseLinExpr<V> &e,
1.209 + const typename V::ExprValue &c) {
1.210 + SparseLinExpr<V> tmp(e);
1.211 + tmp.constComp()-=c;
1.212 + return tmp;
1.213 + }
1.214 +
1.215 + ///\e
1.216 +
1.217 + ///\relates SparseLinExpr
1.218 + ///
1.219 + template <class V>
1.220 + SparseLinExpr<V> operator-(const V &v,const SparseLinExpr<V> &e) {
1.221 + SparseLinExpr<V> tmp(e);
1.222 + tmp*=-1;
1.223 + tmp[v]+=1;
1.224 + return tmp;
1.225 + }
1.226 +
1.227 + ///\e
1.228 +
1.229 + ///\relates SparseLinExpr
1.230 + ///
1.231 + template <class V>
1.232 + SparseLinExpr<V> operator-(const SparseLinExpr<V> &e,const V &v) {
1.233 + SparseLinExpr<V> tmp(e);
1.234 + tmp[v]-=1;
1.235 + return tmp;
1.236 + }
1.237 +
1.238 + ///\e
1.239 +
1.240 + ///\relates SparseLinExpr
1.241 + ///
1.242 + template <class V>
1.243 + SparseLinExpr<V> operator+(const V &v1,const V &v2) {
1.244 + SparseLinExpr<V> tmp(v1);
1.245 + tmp[v2]+=1;
1.246 + return tmp;
1.247 + }
1.248 +
1.249 + ///\e
1.250 +
1.251 + ///\relates SparseLinExpr
1.252 + ///
1.253 + template <class V>
1.254 + SparseLinExpr<V> operator*(const V &v,const typename V::ExprValue &c) {
1.255 + SparseLinExpr<V> tmp;
1.256 + tmp[v]=c;
1.257 + return tmp;
1.258 + }
1.259 +
1.260 + ///\e
1.261 +
1.262 + ///\relates SparseLinExpr
1.263 + ///
1.264 + template <class V>
1.265 + SparseLinExpr<V> operator*(const typename V::ExprValue &c,const V &v) {
1.266 + SparseLinExpr<V> tmp;
1.267 + tmp[v]=c;
1.268 + return tmp;
1.269 + }
1.270 +
1.271 + ///\e
1.272 +
1.273 + ///\relates SparseLinExpr
1.274 + ///
1.275 + template <class V>
1.276 + SparseLinExpr<V> operator/(const V &v,const typename V::ExprValue &c) {
1.277 + SparseLinExpr<V> tmp;
1.278 + tmp[v]=1/c;
1.279 + return tmp;
1.280 + }
1.281 +
1.282 +
1.283 } //namespace lemon
1.284
1.285 #endif //LEMON_LIN_EXPR_H
2.1 --- a/src/work/athos/lp/lp_base.h Fri Mar 25 11:03:49 2005 +0000
2.2 +++ b/src/work/athos/lp/lp_base.h Fri Mar 25 12:58:52 2005 +0000
2.3 @@ -120,6 +120,7 @@
2.4 int id;
2.5 friend class LpSolverBase;
2.6 public:
2.7 + typedef Value ExprValue;
2.8 typedef True LpSolverCol;
2.9 Col() {}
2.10 Col(const Invalid&) : id(-1) {}
2.11 @@ -142,6 +143,7 @@
2.12 int id;
2.13 friend class LpSolverBase;
2.14 public:
2.15 + typedef Value ExprValue;
2.16 typedef True LpSolverRow;
2.17 Row() {}
2.18 Row(const Invalid&) : id(-1) {}
2.19 @@ -150,8 +152,9 @@
2.20 bool operator==(Row c) const {return id==c.id;}
2.21 bool operator!=(Row c) const {return id==c.id;}
2.22 };
2.23 -
2.24 - typedef SparseLinExpr<Col, Value> Expr;
2.25 +
2.26 + ///Linear expression
2.27 + typedef SparseLinExpr<Col> Expr;
2.28
2.29 protected:
2.30 _FixId rows;
2.31 @@ -184,25 +187,25 @@
2.32
2.33 /// The lower bound of a variable (column) have to be given by an
2.34 /// extended number of type Value, i.e. a finite number of type
2.35 - /// Value or -INF.
2.36 + /// Value or -\ref INF.
2.37 virtual void _setColLowerBound(int i, Value value) = 0;
2.38 /// \e
2.39
2.40 /// The upper bound of a variable (column) have to be given by an
2.41 /// extended number of type Value, i.e. a finite number of type
2.42 - /// Value or INF.
2.43 + /// Value or \ref INF.
2.44 virtual void _setColUpperBound(int i, Value value) = 0;
2.45 /// \e
2.46
2.47 /// The lower bound of a linear expression (row) have to be given by an
2.48 /// extended number of type Value, i.e. a finite number of type
2.49 - /// Value or -INF.
2.50 + /// Value or -\ref INF.
2.51 virtual void _setRowLowerBound(int i, Value value) = 0;
2.52 /// \e
2.53
2.54 /// The upper bound of a linear expression (row) have to be given by an
2.55 /// extended number of type Value, i.e. a finite number of type
2.56 - /// Value or INF.
2.57 + /// Value or \ref INF.
2.58 virtual void _setRowUpperBound(int i, Value value) = 0;
2.59
2.60 /// \e
2.61 @@ -267,9 +270,9 @@
2.62 ///Set a row (i.e a constaint) of the LP
2.63
2.64 ///\param r is the row to be modified
2.65 - ///\param l is lower bound (-INF means no bound)
2.66 + ///\param l is lower bound (-\ref INF means no bound)
2.67 ///\param e is a linear expression (see \ref Expr)
2.68 - ///\param u is the upper bound (INF means no bound)
2.69 + ///\param u is the upper bound (\ref INF means no bound)
2.70 ///\bug This is a temportary function. The interface will change to
2.71 ///a better one.
2.72 void setRow(Row r, Value l,const Expr &e, Value u) {
2.73 @@ -290,9 +293,9 @@
2.74
2.75 ///Add a new row (i.e a new constaint) to the LP
2.76
2.77 - ///\param l is the lower bound (-INF means no bound)
2.78 + ///\param l is the lower bound (-\ref INF means no bound)
2.79 ///\param e is a linear expression (see \ref Expr)
2.80 - ///\param u is the upper bound (INF means no bound)
2.81 + ///\param u is the upper bound (\ref INF means no bound)
2.82 ///\return The created row.
2.83 ///\bug This is a temportary function. The interface will change to
2.84 ///a better one.
2.85 @@ -306,7 +309,7 @@
2.86
2.87 /// The upper bound of a variable (column) have to be given by an
2.88 /// extended number of type Value, i.e. a finite number of type
2.89 - /// Value or -INF.
2.90 + /// Value or -\ref INF.
2.91 virtual void setColLowerBound(Col c, Value value) {
2.92 _setColLowerBound(cols.floatingId(c.id),value);
2.93 }
2.94 @@ -314,7 +317,7 @@
2.95
2.96 /// The upper bound of a variable (column) have to be given by an
2.97 /// extended number of type Value, i.e. a finite number of type
2.98 - /// Value or INF.
2.99 + /// Value or \ref INF.
2.100 virtual void setColUpperBound(Col c, Value value) {
2.101 _setColUpperBound(cols.floatingId(c.id),value);
2.102 };
2.103 @@ -322,7 +325,7 @@
2.104
2.105 /// The lower bound of a linear expression (row) have to be given by an
2.106 /// extended number of type Value, i.e. a finite number of type
2.107 - /// Value or -INF.
2.108 + /// Value or -\ref INF.
2.109 virtual void setRowLowerBound(Row r, Value value) {
2.110 _setRowLowerBound(rows.floatingId(r.id),value);
2.111 };
2.112 @@ -330,7 +333,7 @@
2.113
2.114 /// The upper bound of a linear expression (row) have to be given by an
2.115 /// extended number of type Value, i.e. a finite number of type
2.116 - /// Value or INF.
2.117 + /// Value or \ref INF.
2.118 virtual void setRowUpperBound(Row r, Value value) {
2.119 _setRowUpperBound(rows.floatingId(r.id),value);
2.120 };
3.1 --- a/src/work/athos/lp/lp_test.cc Fri Mar 25 11:03:49 2005 +0000
3.2 +++ b/src/work/athos/lp/lp_test.cc Fri Mar 25 12:58:52 2005 +0000
3.3 @@ -28,6 +28,12 @@
3.4 e[x[3]]=4;
3.5 e[x[3]]=1;
3.6 e.constComp()=12;
3.7 +
3.8 + LP::Col p1,p2,p3,p4,p5;
3.9 +
3.10 lp.addRow(LP::INF,e,23);
3.11 -
3.12 + lp.addRow(LP::INF,3.0*(p1+p2)-p3,23);
3.13 + lp.addRow(LP::INF,3.0*(x[1]+x[2]/2)-x[3],23);
3.14 + lp.addRow(LP::INF,3.0*(p1+p2*2-5*p3+12-p4/3)+2*p4-4,23);
3.15 + lp.addRow(LP::INF,3.0*(x[1]+x[2]*2-5*x[3]+12-x[4]/3)+2*x[4]-4,23);
3.16 }