1.1 --- a/src/work/athos/lp/lp_base.cc Wed Mar 30 08:28:44 2005 +0000
1.2 +++ b/src/work/athos/lp/lp_base.cc Wed Mar 30 10:38:22 2005 +0000
1.3 @@ -25,9 +25,9 @@
1.4 const LpSolverBase::Value
1.5 LpSolverBase::NaN = std::numeric_limits<Value>::quiet_NaN();
1.6
1.7 - const LpSolverBase::Constr::Coeff
1.8 + const LpSolverBase::Constr::Value
1.9 LpSolverBase::Constr::INF = std::numeric_limits<Value>::infinity();
1.10 - const LpSolverBase::Constr::Coeff
1.11 + const LpSolverBase::Constr::Value
1.12 LpSolverBase::Constr::NaN = std::numeric_limits<Value>::quiet_NaN();
1.13
1.14 } //namespace lemon
2.1 --- a/src/work/athos/lp/lp_base.h Wed Mar 30 08:28:44 2005 +0000
2.2 +++ b/src/work/athos/lp/lp_base.h Wed Mar 30 10:38:22 2005 +0000
2.3 @@ -20,6 +20,7 @@
2.4 #include<vector>
2.5 #include<map>
2.6 #include<limits>
2.7 +#include<math.h>
2.8
2.9 #include<lemon/utility.h>
2.10 #include<lemon/error.h>
2.11 @@ -72,6 +73,7 @@
2.12 }
2.13 return cross[n];
2.14 }
2.15 + ///\todo Create an own exception type.
2.16 else throw LogicError(); //floatingId-s must form a continuous range;
2.17 }
2.18 ///Remove a fix id.
2.19 @@ -126,8 +128,7 @@
2.20 ///This type is used to refer to a column of the LP.
2.21 ///
2.22 ///Its value remains valid and correct even after the addition or erase of
2.23 - ///new column (unless the referred column itself was also deleted,
2.24 - ///of course).
2.25 + ///other columns.
2.26 ///
2.27 ///\todo Document what can one do with a Col (INVALID, comparing,
2.28 ///it is similar to Node/Edge)
2.29 @@ -150,7 +151,7 @@
2.30 ///This type is used to refer to a row of the LP.
2.31 ///
2.32 ///Its value remains valid and correct even after the addition or erase of
2.33 - ///new rows (unless the referred row itself was also deleted, of course).
2.34 + ///other rows.
2.35 ///
2.36 ///\todo Document what can one do with a Row (INVALID, comparing,
2.37 ///it is similar to Node/Edge)
2.38 @@ -171,34 +172,34 @@
2.39
2.40 ///Linear expression
2.41 // typedef SparseLinExpr<Col> Expr;
2.42 - class Expr : public std::map<Col,Col::ExprValue>
2.43 + class Expr : public std::map<Col,Value>
2.44 {
2.45 public:
2.46 - typedef Col Var;
2.47 - typedef Col::ExprValue Coeff;
2.48 + typedef LpSolverBase::Col Key;
2.49 + typedef LpSolverBase::Value Value;
2.50
2.51 protected:
2.52 - typedef std::map<Col,Col::ExprValue> Base;
2.53 + typedef std::map<Col,Value> Base;
2.54
2.55 - Coeff const_comp;
2.56 + Value const_comp;
2.57 public:
2.58 typedef True IsLinExpression;
2.59 ///\e
2.60 Expr() : Base(), const_comp(0) { }
2.61 ///\e
2.62 - Expr(const Var &v) : const_comp(0) {
2.63 + Expr(const Key &v) : const_comp(0) {
2.64 Base::insert(std::make_pair(v, 1));
2.65 }
2.66 ///\e
2.67 - Expr(const Coeff &v) : const_comp(v) {}
2.68 + Expr(const Value &v) : const_comp(v) {}
2.69 ///\e
2.70 - void set(const Var &v,const Coeff &c) {
2.71 + void set(const Key &v,const Value &c) {
2.72 Base::insert(std::make_pair(v, c));
2.73 }
2.74 ///\e
2.75 - Coeff &constComp() { return const_comp; }
2.76 + Value &constComp() { return const_comp; }
2.77 ///\e
2.78 - const Coeff &constComp() const { return const_comp; }
2.79 + const Value &constComp() const { return const_comp; }
2.80
2.81 ///Removes the components with zero coefficient.
2.82 void simplify() {
2.83 @@ -209,7 +210,13 @@
2.84 j=i;
2.85 }
2.86 }
2.87 -
2.88 +
2.89 + ///Sets all coefficients and the constant component to 0.
2.90 + void clear() {
2.91 + Base::clear();
2.92 + const_comp=0;
2.93 + }
2.94 +
2.95 ///\e
2.96 Expr &operator+=(const Expr &e) {
2.97 for (Base::const_iterator j=e.begin(); j!=e.end(); ++j)
2.98 @@ -226,14 +233,14 @@
2.99 return *this;
2.100 }
2.101 ///\e
2.102 - Expr &operator*=(const Coeff &c) {
2.103 + Expr &operator*=(const Value &c) {
2.104 for (Base::iterator j=Base::begin(); j!=Base::end(); ++j)
2.105 j->second*=c;
2.106 const_comp*=c;
2.107 return *this;
2.108 }
2.109 ///\e
2.110 - Expr &operator/=(const Coeff &c) {
2.111 + Expr &operator/=(const Value &c) {
2.112 for (Base::iterator j=Base::begin(); j!=Base::end(); ++j)
2.113 j->second/=c;
2.114 const_comp/=c;
2.115 @@ -247,26 +254,50 @@
2.116 {
2.117 public:
2.118 typedef LpSolverBase::Expr Expr;
2.119 - typedef Expr::Var Var;
2.120 - typedef Expr::Coeff Coeff;
2.121 + typedef Expr::Key Key;
2.122 + typedef Expr::Value Value;
2.123
2.124 - static const Coeff INF;
2.125 - static const Coeff NaN;
2.126 - // static const Coeff INF=0;
2.127 - // static const Coeff NaN=1;
2.128 + static const Value INF;
2.129 + static const Value NaN;
2.130 + // static const Value INF=0;
2.131 + // static const Value NaN=1;
2.132
2.133 - Expr expr;
2.134 - Coeff lb,ub;
2.135 -
2.136 - Constr() : expr(), lb(NaN), ub(NaN) {}
2.137 - Constr(Coeff _lb,const Expr &e,Coeff _ub) :
2.138 - expr(e), lb(_lb), ub(_ub) {}
2.139 - Constr(const Expr &e,Coeff _ub) :
2.140 - expr(e), lb(NaN), ub(_ub) {}
2.141 - Constr(Coeff _lb,const Expr &e) :
2.142 - expr(e), lb(_lb), ub(NaN) {}
2.143 + protected:
2.144 + Expr _expr;
2.145 + Value _lb,_ub;
2.146 + public:
2.147 + ///\e
2.148 + Constr() : _expr(), _lb(NaN), _ub(NaN) {}
2.149 + ///\e
2.150 + Constr(Value lb,const Expr &e,Value ub) :
2.151 + _expr(e), _lb(lb), _ub(ub) {}
2.152 + ///\e
2.153 + Constr(const Expr &e,Value ub) :
2.154 + _expr(e), _lb(NaN), _ub(ub) {}
2.155 + ///\e
2.156 + Constr(Value lb,const Expr &e) :
2.157 + _expr(e), _lb(lb), _ub(NaN) {}
2.158 + ///\e
2.159 Constr(const Expr &e) :
2.160 - expr(e), lb(NaN), ub(NaN) {}
2.161 + _expr(e), _lb(NaN), _ub(NaN) {}
2.162 + ///\e
2.163 + void clear()
2.164 + {
2.165 + _expr.clear();
2.166 + _lb=_ub=NaN;
2.167 + }
2.168 + ///\e
2.169 + Expr &expr() { return _expr; }
2.170 + ///\e
2.171 + const Expr &expr() const { return _expr; }
2.172 + ///\e
2.173 + Value &lowerBound() { return _lb; }
2.174 + ///\e
2.175 + const Value &lowerBound() const { return _lb; }
2.176 + ///\e
2.177 + Value &upperBound() { return _ub; }
2.178 + ///\e
2.179 + const Value &upperBound() const { return _ub; }
2.180 };
2.181
2.182
2.183 @@ -354,16 +385,28 @@
2.184 ///\brief Fill the elements of a container with newly created columns
2.185 ///(i.e a new variables)
2.186 ///
2.187 - ///This magic function takes container as its argument
2.188 + ///This magic function takes a container as its argument
2.189 ///and fills its elements
2.190 ///with new columns (i.e. variables)
2.191 - ///\param t can be either any standard STL iterable container with
2.192 - ///\ref Col \c values_type or \c mapped_type
2.193 - ///like <tt>std::vector<LpSolverBase::Col></tt>,
2.194 - /// <tt>std::list<LpSolverBase::Col></tt> or
2.195 - /// <tt>std::map<AnyType,LpSolverBase::Col></tt> or
2.196 - ///it can be an iterable lemon map like
2.197 - /// <tt>ListGraph::NodeMap<LpSolverBase::Col></tt>.
2.198 + ///\param t can be
2.199 + ///- a standard STL compatible iterable container with
2.200 + ///\ref Col as its \c values_type
2.201 + ///like
2.202 + ///\code
2.203 + ///std::vector<LpSolverBase::Col>
2.204 + ///std::list<LpSolverBase::Col>
2.205 + ///\endcode
2.206 + ///- a standard STL compatible iterable container with
2.207 + ///\ref Col as its \c mapped_type
2.208 + ///like
2.209 + ///\code
2.210 + ///std::map<AnyType,LpSolverBase::Col>
2.211 + ///\endcode
2.212 + ///- an iterable lemon \ref concept::WriteMap "write map" like
2.213 + ///\code
2.214 + ///ListGraph::NodeMap<LpSolverBase::Col>
2.215 + ///ListGraph::EdgeMap<LpSolverBase::Col>
2.216 + ///\endcode
2.217 ///\return The number of the created column.
2.218 ///\bug Iterable nodemap hasn't been implemented yet.
2.219 #ifdef DOXYGEN
2.220 @@ -440,9 +483,10 @@
2.221 ///\param r is the row to be modified
2.222 ///\param c is a linear expression (see \ref Constr)
2.223 void setRow(Row r, const Constr &c) {
2.224 - Value lb= c.lb==NaN?-INF:lb;
2.225 - Value ub= c.ub==NaN?INF:lb;
2.226 - setRow(r,lb,c.expr,ub);
2.227 + setRow(r,
2.228 + isnan(c.lowerBound())?-INF:c.lowerBound(),
2.229 + c.expr(),
2.230 + isnan(c.upperBound())?INF:c.upperBound());
2.231 }
2.232
2.233 ///Add a new row (i.e a new constaint) to the LP
2.234 @@ -563,7 +607,7 @@
2.235 ///\relates LpSolverBase::Expr
2.236 ///
2.237 inline LpSolverBase::Expr operator*(const LpSolverBase::Expr &a,
2.238 - const LpSolverBase::Expr::Coeff &b)
2.239 + const LpSolverBase::Value &b)
2.240 {
2.241 LpSolverBase::Expr tmp(a);
2.242 tmp*=b; ///\todo Don't STL have some special 'merge' algorithm?
2.243 @@ -574,7 +618,7 @@
2.244
2.245 ///\relates LpSolverBase::Expr
2.246 ///
2.247 - inline LpSolverBase::Expr operator*(const LpSolverBase::Expr::Coeff &a,
2.248 + inline LpSolverBase::Expr operator*(const LpSolverBase::Value &a,
2.249 const LpSolverBase::Expr &b)
2.250 {
2.251 LpSolverBase::Expr tmp(b);
2.252 @@ -586,7 +630,7 @@
2.253 ///\relates LpSolverBase::Expr
2.254 ///
2.255 inline LpSolverBase::Expr operator/(const LpSolverBase::Expr &a,
2.256 - const LpSolverBase::Expr::Coeff &b)
2.257 + const LpSolverBase::Value &b)
2.258 {
2.259 LpSolverBase::Expr tmp(a);
2.260 tmp/=b; ///\todo Don't STL have some special 'merge' algorithm?
2.261 @@ -607,7 +651,7 @@
2.262
2.263 ///\relates LpSolverBase::Constr
2.264 ///
2.265 - inline LpSolverBase::Constr operator<=(const LpSolverBase::Expr::Coeff &e,
2.266 + inline LpSolverBase::Constr operator<=(const LpSolverBase::Value &e,
2.267 const LpSolverBase::Expr &f)
2.268 {
2.269 return LpSolverBase::Constr(e,f);
2.270 @@ -618,7 +662,7 @@
2.271 ///\relates LpSolverBase::Constr
2.272 ///
2.273 inline LpSolverBase::Constr operator<=(const LpSolverBase::Expr &e,
2.274 - const LpSolverBase::Expr::Coeff &f)
2.275 + const LpSolverBase::Value &f)
2.276 {
2.277 return LpSolverBase::Constr(e,f);
2.278 }
2.279 @@ -638,7 +682,7 @@
2.280
2.281 ///\relates LpSolverBase::Constr
2.282 ///
2.283 - inline LpSolverBase::Constr operator>=(const LpSolverBase::Expr::Coeff &e,
2.284 + inline LpSolverBase::Constr operator>=(const LpSolverBase::Value &e,
2.285 const LpSolverBase::Expr &f)
2.286 {
2.287 return LpSolverBase::Constr(f,e);
2.288 @@ -650,7 +694,7 @@
2.289 ///\relates LpSolverBase::Constr
2.290 ///
2.291 inline LpSolverBase::Constr operator>=(const LpSolverBase::Expr &e,
2.292 - const LpSolverBase::Expr::Coeff &f)
2.293 + const LpSolverBase::Value &f)
2.294 {
2.295 return LpSolverBase::Constr(f,e);
2.296 }
2.297 @@ -669,12 +713,13 @@
2.298
2.299 ///\relates LpSolverBase::Constr
2.300 ///
2.301 - inline LpSolverBase::Constr operator<=(const LpSolverBase::Constr::Coeff &n,
2.302 + inline LpSolverBase::Constr operator<=(const LpSolverBase::Value &n,
2.303 const LpSolverBase::Constr&c)
2.304 {
2.305 LpSolverBase::Constr tmp(c);
2.306 - if(tmp.lb!=tmp.NaN) throw LogicError();
2.307 - else tmp.lb=n;
2.308 + ///\todo Create an own exception type.
2.309 + if(!isnan(tmp.lowerBound())) throw LogicError();
2.310 + else tmp.lowerBound()=n;
2.311 return tmp;
2.312 }
2.313 ///\e
2.314 @@ -682,11 +727,12 @@
2.315 ///\relates LpSolverBase::Constr
2.316 ///
2.317 inline LpSolverBase::Constr operator<=(const LpSolverBase::Constr& c,
2.318 - const LpSolverBase::Constr::Coeff &n)
2.319 + const LpSolverBase::Value &n)
2.320 {
2.321 LpSolverBase::Constr tmp(c);
2.322 - if(tmp.ub!=tmp.NaN) throw LogicError();
2.323 - else tmp.ub=n;
2.324 + ///\todo Create an own exception type.
2.325 + if(!isnan(tmp.upperBound())) throw LogicError();
2.326 + else tmp.upperBound()=n;
2.327 return tmp;
2.328 }
2.329
2.330 @@ -694,12 +740,13 @@
2.331
2.332 ///\relates LpSolverBase::Constr
2.333 ///
2.334 - inline LpSolverBase::Constr operator>=(const LpSolverBase::Constr::Coeff &n,
2.335 + inline LpSolverBase::Constr operator>=(const LpSolverBase::Value &n,
2.336 const LpSolverBase::Constr&c)
2.337 {
2.338 LpSolverBase::Constr tmp(c);
2.339 - if(tmp.ub!=tmp.NaN) throw LogicError();
2.340 - else tmp.ub=n;
2.341 + ///\todo Create an own exception type.
2.342 + if(!isnan(tmp.upperBound())) throw LogicError();
2.343 + else tmp.upperBound()=n;
2.344 return tmp;
2.345 }
2.346 ///\e
2.347 @@ -707,11 +754,12 @@
2.348 ///\relates LpSolverBase::Constr
2.349 ///
2.350 inline LpSolverBase::Constr operator>=(const LpSolverBase::Constr& c,
2.351 - const LpSolverBase::Constr::Coeff &n)
2.352 + const LpSolverBase::Value &n)
2.353 {
2.354 LpSolverBase::Constr tmp(c);
2.355 - if(tmp.lb!=tmp.NaN) throw LogicError();
2.356 - else tmp.lb=n;
2.357 + ///\todo Create an own exception type.
2.358 + if(!isnan(tmp.lowerBound())) throw LogicError();
2.359 + else tmp.lowerBound()=n;
2.360 return tmp;
2.361 }
2.362
3.1 --- a/src/work/athos/lp/lp_solver_skeleton.cc Wed Mar 30 08:28:44 2005 +0000
3.2 +++ b/src/work/athos/lp/lp_solver_skeleton.cc Wed Mar 30 10:38:22 2005 +0000
3.3 @@ -23,12 +23,12 @@
3.4
3.5 int LpSolverSkeleton::_addCol()
3.6 {
3.7 - return 1;
3.8 + return ++col_num;
3.9 }
3.10
3.11 int LpSolverSkeleton::_addRow()
3.12 {
3.13 - return 1;
3.14 + return ++row_num;
3.15 }
3.16
3.17 void LpSolverSkeleton::_setRowCoeffs(int i,
4.1 --- a/src/work/athos/lp/lp_solver_skeleton.h Wed Mar 30 08:28:44 2005 +0000
4.2 +++ b/src/work/athos/lp/lp_solver_skeleton.h Wed Mar 30 10:38:22 2005 +0000
4.3 @@ -26,7 +26,8 @@
4.4
4.5 ///A skeleton class to implement LP solver interfaces
4.6 class LpSolverSkeleton :public LpSolverBase {
4.7 -
4.8 + int col_num,row_num;
4.9 +
4.10 protected:
4.11 virtual int _addCol();
4.12 virtual int _addRow();
4.13 @@ -45,7 +46,8 @@
4.14 virtual void _setObjCoeff(int i, Value obj_coef);
4.15 virtual SolutionType _solve();
4.16 virtual Value _getSolution(int i);
4.17 -
4.18 + public:
4.19 + LpSolverSkeleton() : LpSolverBase(), col_num(0), row_num(0) {}
4.20 };
4.21
4.22 } //namespace lemon
5.1 --- a/src/work/athos/lp/lp_test.cc Wed Mar 30 08:28:44 2005 +0000
5.2 +++ b/src/work/athos/lp/lp_test.cc Wed Mar 30 10:38:22 2005 +0000
5.3 @@ -116,14 +116,12 @@
5.4 e.constComp()=12;
5.5
5.6 lp.addRow(LP::INF,e,23);
5.7 - lp.addRow(LP::INF,3.0*(p1+p2)-p3,23);
5.8 lp.addRow(LP::INF,3.0*(x[1]+x[2]/2)-x[3],23);
5.9 - lp.addRow(LP::INF,3.0*(p1+p2*2-5*p3+12-p4/3)+2*p4-4,23);
5.10 lp.addRow(LP::INF,3.0*(x[1]+x[2]*2-5*x[3]+12-x[4]/3)+2*x[4]-4,23);
5.11
5.12 lp.addRow(x[1]+x[3]<=x[5]-3);
5.13 lp.addRow(-7<=x[1]+x[3]-12<=3);
5.14 - //lp.addRow(x[1]<=x[5]);
5.15 + lp.addRow(x[1]<=x[5]);
5.16
5.17 }
5.18
5.19 @@ -143,7 +141,6 @@
5.20
5.21 typename G::EdgeMap<LpGlpk::Col> x(g);
5.22 lp.addColSet(x);
5.23 - //for(EdgeIt e(g);e!=INVALID;++e) x[e]=lp.addCol();
5.24
5.25 for(EdgeIt e(g);e!=INVALID;++e) {
5.26 lp.setColUpperBound(x[e],cap[e]);
5.27 @@ -154,7 +151,7 @@
5.28 LpGlpk::Expr ex;
5.29 for(InEdgeIt e(g,n);e!=INVALID;++e) ex+=x[e];
5.30 for(OutEdgeIt e(g,n);e!=INVALID;++e) ex-=x[e];
5.31 - lp.addRow(0,ex,0);
5.32 + lp.addRow(ex==0);
5.33 }
5.34 {
5.35 LpGlpk::Expr ex;
5.36 @@ -177,8 +174,11 @@
5.37 lpTest(lp_glpk);
5.38
5.39 ListGraph g;
5.40 + ListGraph::Node s=g.addNode();
5.41 + ListGraph::Node t=g.addNode();
5.42 +
5.43 ListGraph::EdgeMap<double> cap(g);
5.44
5.45 - maxFlow(g,cap,ListGraph::NodeIt(g),ListGraph::NodeIt(g));
5.46 + maxFlow(g,cap,s,t);
5.47
5.48 }