1.1 --- a/src/work/athos/lp/lp_base.h Wed Mar 30 08:28:44 2005 +0000
1.2 +++ b/src/work/athos/lp/lp_base.h Wed Mar 30 10:38:22 2005 +0000
1.3 @@ -20,6 +20,7 @@
1.4 #include<vector>
1.5 #include<map>
1.6 #include<limits>
1.7 +#include<math.h>
1.8
1.9 #include<lemon/utility.h>
1.10 #include<lemon/error.h>
1.11 @@ -72,6 +73,7 @@
1.12 }
1.13 return cross[n];
1.14 }
1.15 + ///\todo Create an own exception type.
1.16 else throw LogicError(); //floatingId-s must form a continuous range;
1.17 }
1.18 ///Remove a fix id.
1.19 @@ -126,8 +128,7 @@
1.20 ///This type is used to refer to a column of the LP.
1.21 ///
1.22 ///Its value remains valid and correct even after the addition or erase of
1.23 - ///new column (unless the referred column itself was also deleted,
1.24 - ///of course).
1.25 + ///other columns.
1.26 ///
1.27 ///\todo Document what can one do with a Col (INVALID, comparing,
1.28 ///it is similar to Node/Edge)
1.29 @@ -150,7 +151,7 @@
1.30 ///This type is used to refer to a row of the LP.
1.31 ///
1.32 ///Its value remains valid and correct even after the addition or erase of
1.33 - ///new rows (unless the referred row itself was also deleted, of course).
1.34 + ///other rows.
1.35 ///
1.36 ///\todo Document what can one do with a Row (INVALID, comparing,
1.37 ///it is similar to Node/Edge)
1.38 @@ -171,34 +172,34 @@
1.39
1.40 ///Linear expression
1.41 // typedef SparseLinExpr<Col> Expr;
1.42 - class Expr : public std::map<Col,Col::ExprValue>
1.43 + class Expr : public std::map<Col,Value>
1.44 {
1.45 public:
1.46 - typedef Col Var;
1.47 - typedef Col::ExprValue Coeff;
1.48 + typedef LpSolverBase::Col Key;
1.49 + typedef LpSolverBase::Value Value;
1.50
1.51 protected:
1.52 - typedef std::map<Col,Col::ExprValue> Base;
1.53 + typedef std::map<Col,Value> Base;
1.54
1.55 - Coeff const_comp;
1.56 + Value const_comp;
1.57 public:
1.58 typedef True IsLinExpression;
1.59 ///\e
1.60 Expr() : Base(), const_comp(0) { }
1.61 ///\e
1.62 - Expr(const Var &v) : const_comp(0) {
1.63 + Expr(const Key &v) : const_comp(0) {
1.64 Base::insert(std::make_pair(v, 1));
1.65 }
1.66 ///\e
1.67 - Expr(const Coeff &v) : const_comp(v) {}
1.68 + Expr(const Value &v) : const_comp(v) {}
1.69 ///\e
1.70 - void set(const Var &v,const Coeff &c) {
1.71 + void set(const Key &v,const Value &c) {
1.72 Base::insert(std::make_pair(v, c));
1.73 }
1.74 ///\e
1.75 - Coeff &constComp() { return const_comp; }
1.76 + Value &constComp() { return const_comp; }
1.77 ///\e
1.78 - const Coeff &constComp() const { return const_comp; }
1.79 + const Value &constComp() const { return const_comp; }
1.80
1.81 ///Removes the components with zero coefficient.
1.82 void simplify() {
1.83 @@ -209,7 +210,13 @@
1.84 j=i;
1.85 }
1.86 }
1.87 -
1.88 +
1.89 + ///Sets all coefficients and the constant component to 0.
1.90 + void clear() {
1.91 + Base::clear();
1.92 + const_comp=0;
1.93 + }
1.94 +
1.95 ///\e
1.96 Expr &operator+=(const Expr &e) {
1.97 for (Base::const_iterator j=e.begin(); j!=e.end(); ++j)
1.98 @@ -226,14 +233,14 @@
1.99 return *this;
1.100 }
1.101 ///\e
1.102 - Expr &operator*=(const Coeff &c) {
1.103 + Expr &operator*=(const Value &c) {
1.104 for (Base::iterator j=Base::begin(); j!=Base::end(); ++j)
1.105 j->second*=c;
1.106 const_comp*=c;
1.107 return *this;
1.108 }
1.109 ///\e
1.110 - Expr &operator/=(const Coeff &c) {
1.111 + Expr &operator/=(const Value &c) {
1.112 for (Base::iterator j=Base::begin(); j!=Base::end(); ++j)
1.113 j->second/=c;
1.114 const_comp/=c;
1.115 @@ -247,26 +254,50 @@
1.116 {
1.117 public:
1.118 typedef LpSolverBase::Expr Expr;
1.119 - typedef Expr::Var Var;
1.120 - typedef Expr::Coeff Coeff;
1.121 + typedef Expr::Key Key;
1.122 + typedef Expr::Value Value;
1.123
1.124 - static const Coeff INF;
1.125 - static const Coeff NaN;
1.126 - // static const Coeff INF=0;
1.127 - // static const Coeff NaN=1;
1.128 + static const Value INF;
1.129 + static const Value NaN;
1.130 + // static const Value INF=0;
1.131 + // static const Value NaN=1;
1.132
1.133 - Expr expr;
1.134 - Coeff lb,ub;
1.135 -
1.136 - Constr() : expr(), lb(NaN), ub(NaN) {}
1.137 - Constr(Coeff _lb,const Expr &e,Coeff _ub) :
1.138 - expr(e), lb(_lb), ub(_ub) {}
1.139 - Constr(const Expr &e,Coeff _ub) :
1.140 - expr(e), lb(NaN), ub(_ub) {}
1.141 - Constr(Coeff _lb,const Expr &e) :
1.142 - expr(e), lb(_lb), ub(NaN) {}
1.143 + protected:
1.144 + Expr _expr;
1.145 + Value _lb,_ub;
1.146 + public:
1.147 + ///\e
1.148 + Constr() : _expr(), _lb(NaN), _ub(NaN) {}
1.149 + ///\e
1.150 + Constr(Value lb,const Expr &e,Value ub) :
1.151 + _expr(e), _lb(lb), _ub(ub) {}
1.152 + ///\e
1.153 + Constr(const Expr &e,Value ub) :
1.154 + _expr(e), _lb(NaN), _ub(ub) {}
1.155 + ///\e
1.156 + Constr(Value lb,const Expr &e) :
1.157 + _expr(e), _lb(lb), _ub(NaN) {}
1.158 + ///\e
1.159 Constr(const Expr &e) :
1.160 - expr(e), lb(NaN), ub(NaN) {}
1.161 + _expr(e), _lb(NaN), _ub(NaN) {}
1.162 + ///\e
1.163 + void clear()
1.164 + {
1.165 + _expr.clear();
1.166 + _lb=_ub=NaN;
1.167 + }
1.168 + ///\e
1.169 + Expr &expr() { return _expr; }
1.170 + ///\e
1.171 + const Expr &expr() const { return _expr; }
1.172 + ///\e
1.173 + Value &lowerBound() { return _lb; }
1.174 + ///\e
1.175 + const Value &lowerBound() const { return _lb; }
1.176 + ///\e
1.177 + Value &upperBound() { return _ub; }
1.178 + ///\e
1.179 + const Value &upperBound() const { return _ub; }
1.180 };
1.181
1.182
1.183 @@ -354,16 +385,28 @@
1.184 ///\brief Fill the elements of a container with newly created columns
1.185 ///(i.e a new variables)
1.186 ///
1.187 - ///This magic function takes container as its argument
1.188 + ///This magic function takes a container as its argument
1.189 ///and fills its elements
1.190 ///with new columns (i.e. variables)
1.191 - ///\param t can be either any standard STL iterable container with
1.192 - ///\ref Col \c values_type or \c mapped_type
1.193 - ///like <tt>std::vector<LpSolverBase::Col></tt>,
1.194 - /// <tt>std::list<LpSolverBase::Col></tt> or
1.195 - /// <tt>std::map<AnyType,LpSolverBase::Col></tt> or
1.196 - ///it can be an iterable lemon map like
1.197 - /// <tt>ListGraph::NodeMap<LpSolverBase::Col></tt>.
1.198 + ///\param t can be
1.199 + ///- a standard STL compatible iterable container with
1.200 + ///\ref Col as its \c values_type
1.201 + ///like
1.202 + ///\code
1.203 + ///std::vector<LpSolverBase::Col>
1.204 + ///std::list<LpSolverBase::Col>
1.205 + ///\endcode
1.206 + ///- a standard STL compatible iterable container with
1.207 + ///\ref Col as its \c mapped_type
1.208 + ///like
1.209 + ///\code
1.210 + ///std::map<AnyType,LpSolverBase::Col>
1.211 + ///\endcode
1.212 + ///- an iterable lemon \ref concept::WriteMap "write map" like
1.213 + ///\code
1.214 + ///ListGraph::NodeMap<LpSolverBase::Col>
1.215 + ///ListGraph::EdgeMap<LpSolverBase::Col>
1.216 + ///\endcode
1.217 ///\return The number of the created column.
1.218 ///\bug Iterable nodemap hasn't been implemented yet.
1.219 #ifdef DOXYGEN
1.220 @@ -440,9 +483,10 @@
1.221 ///\param r is the row to be modified
1.222 ///\param c is a linear expression (see \ref Constr)
1.223 void setRow(Row r, const Constr &c) {
1.224 - Value lb= c.lb==NaN?-INF:lb;
1.225 - Value ub= c.ub==NaN?INF:lb;
1.226 - setRow(r,lb,c.expr,ub);
1.227 + setRow(r,
1.228 + isnan(c.lowerBound())?-INF:c.lowerBound(),
1.229 + c.expr(),
1.230 + isnan(c.upperBound())?INF:c.upperBound());
1.231 }
1.232
1.233 ///Add a new row (i.e a new constaint) to the LP
1.234 @@ -563,7 +607,7 @@
1.235 ///\relates LpSolverBase::Expr
1.236 ///
1.237 inline LpSolverBase::Expr operator*(const LpSolverBase::Expr &a,
1.238 - const LpSolverBase::Expr::Coeff &b)
1.239 + const LpSolverBase::Value &b)
1.240 {
1.241 LpSolverBase::Expr tmp(a);
1.242 tmp*=b; ///\todo Don't STL have some special 'merge' algorithm?
1.243 @@ -574,7 +618,7 @@
1.244
1.245 ///\relates LpSolverBase::Expr
1.246 ///
1.247 - inline LpSolverBase::Expr operator*(const LpSolverBase::Expr::Coeff &a,
1.248 + inline LpSolverBase::Expr operator*(const LpSolverBase::Value &a,
1.249 const LpSolverBase::Expr &b)
1.250 {
1.251 LpSolverBase::Expr tmp(b);
1.252 @@ -586,7 +630,7 @@
1.253 ///\relates LpSolverBase::Expr
1.254 ///
1.255 inline LpSolverBase::Expr operator/(const LpSolverBase::Expr &a,
1.256 - const LpSolverBase::Expr::Coeff &b)
1.257 + const LpSolverBase::Value &b)
1.258 {
1.259 LpSolverBase::Expr tmp(a);
1.260 tmp/=b; ///\todo Don't STL have some special 'merge' algorithm?
1.261 @@ -607,7 +651,7 @@
1.262
1.263 ///\relates LpSolverBase::Constr
1.264 ///
1.265 - inline LpSolverBase::Constr operator<=(const LpSolverBase::Expr::Coeff &e,
1.266 + inline LpSolverBase::Constr operator<=(const LpSolverBase::Value &e,
1.267 const LpSolverBase::Expr &f)
1.268 {
1.269 return LpSolverBase::Constr(e,f);
1.270 @@ -618,7 +662,7 @@
1.271 ///\relates LpSolverBase::Constr
1.272 ///
1.273 inline LpSolverBase::Constr operator<=(const LpSolverBase::Expr &e,
1.274 - const LpSolverBase::Expr::Coeff &f)
1.275 + const LpSolverBase::Value &f)
1.276 {
1.277 return LpSolverBase::Constr(e,f);
1.278 }
1.279 @@ -638,7 +682,7 @@
1.280
1.281 ///\relates LpSolverBase::Constr
1.282 ///
1.283 - inline LpSolverBase::Constr operator>=(const LpSolverBase::Expr::Coeff &e,
1.284 + inline LpSolverBase::Constr operator>=(const LpSolverBase::Value &e,
1.285 const LpSolverBase::Expr &f)
1.286 {
1.287 return LpSolverBase::Constr(f,e);
1.288 @@ -650,7 +694,7 @@
1.289 ///\relates LpSolverBase::Constr
1.290 ///
1.291 inline LpSolverBase::Constr operator>=(const LpSolverBase::Expr &e,
1.292 - const LpSolverBase::Expr::Coeff &f)
1.293 + const LpSolverBase::Value &f)
1.294 {
1.295 return LpSolverBase::Constr(f,e);
1.296 }
1.297 @@ -669,12 +713,13 @@
1.298
1.299 ///\relates LpSolverBase::Constr
1.300 ///
1.301 - inline LpSolverBase::Constr operator<=(const LpSolverBase::Constr::Coeff &n,
1.302 + inline LpSolverBase::Constr operator<=(const LpSolverBase::Value &n,
1.303 const LpSolverBase::Constr&c)
1.304 {
1.305 LpSolverBase::Constr tmp(c);
1.306 - if(tmp.lb!=tmp.NaN) throw LogicError();
1.307 - else tmp.lb=n;
1.308 + ///\todo Create an own exception type.
1.309 + if(!isnan(tmp.lowerBound())) throw LogicError();
1.310 + else tmp.lowerBound()=n;
1.311 return tmp;
1.312 }
1.313 ///\e
1.314 @@ -682,11 +727,12 @@
1.315 ///\relates LpSolverBase::Constr
1.316 ///
1.317 inline LpSolverBase::Constr operator<=(const LpSolverBase::Constr& c,
1.318 - const LpSolverBase::Constr::Coeff &n)
1.319 + const LpSolverBase::Value &n)
1.320 {
1.321 LpSolverBase::Constr tmp(c);
1.322 - if(tmp.ub!=tmp.NaN) throw LogicError();
1.323 - else tmp.ub=n;
1.324 + ///\todo Create an own exception type.
1.325 + if(!isnan(tmp.upperBound())) throw LogicError();
1.326 + else tmp.upperBound()=n;
1.327 return tmp;
1.328 }
1.329
1.330 @@ -694,12 +740,13 @@
1.331
1.332 ///\relates LpSolverBase::Constr
1.333 ///
1.334 - inline LpSolverBase::Constr operator>=(const LpSolverBase::Constr::Coeff &n,
1.335 + inline LpSolverBase::Constr operator>=(const LpSolverBase::Value &n,
1.336 const LpSolverBase::Constr&c)
1.337 {
1.338 LpSolverBase::Constr tmp(c);
1.339 - if(tmp.ub!=tmp.NaN) throw LogicError();
1.340 - else tmp.ub=n;
1.341 + ///\todo Create an own exception type.
1.342 + if(!isnan(tmp.upperBound())) throw LogicError();
1.343 + else tmp.upperBound()=n;
1.344 return tmp;
1.345 }
1.346 ///\e
1.347 @@ -707,11 +754,12 @@
1.348 ///\relates LpSolverBase::Constr
1.349 ///
1.350 inline LpSolverBase::Constr operator>=(const LpSolverBase::Constr& c,
1.351 - const LpSolverBase::Constr::Coeff &n)
1.352 + const LpSolverBase::Value &n)
1.353 {
1.354 LpSolverBase::Constr tmp(c);
1.355 - if(tmp.lb!=tmp.NaN) throw LogicError();
1.356 - else tmp.lb=n;
1.357 + ///\todo Create an own exception type.
1.358 + if(!isnan(tmp.lowerBound())) throw LogicError();
1.359 + else tmp.lowerBound()=n;
1.360 return tmp;
1.361 }
1.362