1.1 --- a/src/work/athos/lp/lin_expr.h Thu Apr 07 15:22:03 2005 +0000
1.2 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000
1.3 @@ -1,498 +0,0 @@
1.4 -/* -*- C++ -*-
1.5 - * src/lemon/lin_expr.h - Part of LEMON, a generic C++ optimization library
1.6 - *
1.7 - * Copyright (C) 2005 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
1.8 - * (Egervary Combinatorial Optimization Research Group, EGRES).
1.9 - *
1.10 - * Permission to use, modify and distribute this software is granted
1.11 - * provided that this copyright notice appears in all copies. For
1.12 - * precise terms see the accompanying LICENSE file.
1.13 - *
1.14 - * This software is provided "AS IS" with no warranty of any kind,
1.15 - * express or implied, and with no claim as to its suitability for any
1.16 - * purpose.
1.17 - *
1.18 - */
1.19 -
1.20 -#ifndef LEMON_LIN_EXPR_H
1.21 -#define LEMON_LIN_EXPR_H
1.22 -
1.23 -#include<vector>
1.24 -#include<map>
1.25 -#include<lemon/utility.h>
1.26 -///\file
1.27 -///\brief Classes to handle linear expressions
1.28 -namespace lemon {
1.29 -
1.30 - /// Class to handle sparse linear expressions
1.31 - template <class _V>
1.32 - class SparseLinExpr : public std::map<_V, typename _V::ExprValue>
1.33 - {
1.34 - public:
1.35 - typedef _V Var;
1.36 - typedef typename _V::ExprValue Coeff;
1.37 -
1.38 - protected:
1.39 - typedef typename std::map<_V, typename _V::ExprValue> Base;
1.40 -
1.41 - Coeff const_comp;
1.42 - public:
1.43 - typedef True IsLinExpression;
1.44 - ///\e
1.45 - SparseLinExpr() : Base(), const_comp(0) { }
1.46 - ///\e
1.47 - SparseLinExpr(const Var &v) : const_comp(0) {
1.48 - Base::insert(std::make_pair(v, 1));
1.49 - }
1.50 - ///\e
1.51 - SparseLinExpr(const Coeff &v) : const_comp(v) {}
1.52 -
1.53 - ///\e
1.54 - void set(const Var &v,const Coeff &c) {
1.55 - return Base::insert(std::make_pair(v, c));
1.56 - }
1.57 -// Coeff &operator[](const Var &v) { return data[v]; }
1.58 -// const Coeff &operator[](const Var &v) const { return data[v]; }
1.59 -
1.60 - ///\e
1.61 - Coeff &constComp() { return const_comp; }
1.62 - ///\e
1.63 - const Coeff &constComp() const { return const_comp; }
1.64 -
1.65 - ///Removes the components with zero coefficient.
1.66 - void simplify() {
1.67 - for (typename Base::iterator i=Base::begin(); i!=Base::end();) {
1.68 - typename Base::iterator j=i;
1.69 - ++j;
1.70 - if ((*i).second==0) Base::erase(i);
1.71 - j=i;
1.72 - }
1.73 - }
1.74 -
1.75 - ///\e
1.76 - SparseLinExpr &operator+=(const SparseLinExpr &e) {
1.77 - for (typename Base::const_iterator j=e.begin(); j!=e.end(); ++j)
1.78 - (*this)[j->first]+=j->second;
1.79 - ///\todo it might be speeded up using "hints"
1.80 - const_comp+=e.const_comp;
1.81 - return *this;
1.82 - }
1.83 - ///\e
1.84 - SparseLinExpr &operator-=(const SparseLinExpr &e) {
1.85 - for (typename Base::const_iterator j=e.begin(); j!=e.end(); ++j)
1.86 - (*this)[j->first]-=j->second;
1.87 - const_comp-=e.const_comp;
1.88 - return *this;
1.89 - }
1.90 - ///\e
1.91 - SparseLinExpr &operator*=(const Coeff &c) {
1.92 - for (typename Base::iterator j=Base::begin(); j!=Base::end(); ++j)
1.93 - j->second*=c;
1.94 - const_comp*=c;
1.95 - return *this;
1.96 - }
1.97 - ///\e
1.98 - SparseLinExpr &operator/=(const Coeff &c) {
1.99 - for (typename Base::iterator j=Base::begin(); j!=Base::end(); ++j)
1.100 - j->second/=c;
1.101 - const_comp/=c;
1.102 - return *this;
1.103 - }
1.104 -
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 SparseLinExpr<V> &a,
1.113 - const SparseLinExpr<V> &b) {
1.114 - SparseLinExpr<V> tmp(a);
1.115 - tmp+=b; ///\todo Don't STL have some special 'merge' algorithm?
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> &a,
1.125 - const SparseLinExpr<V> &b) {
1.126 - SparseLinExpr<V> tmp(a);
1.127 - tmp-=b; ///\todo Don't STL have some special 'merge' algorithm?
1.128 - return tmp;
1.129 - }
1.130 -
1.131 - ///\e
1.132 -
1.133 - ///\relates SparseLinExpr
1.134 - ///
1.135 - template <class V>
1.136 - SparseLinExpr<V> operator*(const typename V::ExprValue &c,
1.137 - const SparseLinExpr<V> &e) {
1.138 - SparseLinExpr<V> tmp(e);
1.139 - tmp*=c;
1.140 - return tmp;
1.141 - }
1.142 -
1.143 - ///\e
1.144 -
1.145 - ///\relates SparseLinExpr
1.146 - ///
1.147 - template <class V>
1.148 - SparseLinExpr<V> operator*(const SparseLinExpr<V> &e,
1.149 - const typename V::ExprValue &c) {
1.150 - SparseLinExpr<V> tmp(e);
1.151 - tmp*=c;
1.152 - return tmp;
1.153 - }
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/=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 typename V::ExprValue &c,
1.174 - const SparseLinExpr<V> &e) {
1.175 - SparseLinExpr<V> tmp(e);
1.176 - tmp.constComp()+=c;
1.177 - return tmp;
1.178 - }
1.179 -
1.180 - ///\e
1.181 -
1.182 - ///\relates SparseLinExpr
1.183 - ///
1.184 - template <class V>
1.185 - SparseLinExpr<V> operator+(const SparseLinExpr<V> &e,
1.186 - const typename V::ExprValue &c) {
1.187 - SparseLinExpr<V> tmp(e);
1.188 - tmp.constComp()+=c;
1.189 - return tmp;
1.190 - }
1.191 -
1.192 - ///\e
1.193 -
1.194 - ///\relates SparseLinExpr
1.195 - ///
1.196 - template <class V>
1.197 - SparseLinExpr<V> operator+(const V &v,const SparseLinExpr<V> &e) {
1.198 - SparseLinExpr<V> tmp(e);
1.199 - tmp[v]+=1;
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,const V &v) {
1.209 - SparseLinExpr<V> tmp(e);
1.210 - tmp[v]+=1;
1.211 - return tmp;
1.212 - }
1.213 -
1.214 - ///\e
1.215 -
1.216 - ///\relates SparseLinExpr
1.217 - ///
1.218 - template <class V>
1.219 - SparseLinExpr<V> operator-(const typename V::ExprValue &c,
1.220 - const SparseLinExpr<V> &e) {
1.221 - SparseLinExpr<V> tmp(e);
1.222 - tmp*=-1;
1.223 - tmp.constComp()+=c;
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,
1.233 - const typename V::ExprValue &c) {
1.234 - SparseLinExpr<V> tmp(e);
1.235 - tmp.constComp()-=c;
1.236 - return tmp;
1.237 - }
1.238 -
1.239 - ///\e
1.240 -
1.241 - ///\relates SparseLinExpr
1.242 - ///
1.243 - template <class V>
1.244 - SparseLinExpr<V> operator-(const V &v,const SparseLinExpr<V> &e) {
1.245 - SparseLinExpr<V> tmp(e);
1.246 - tmp*=-1;
1.247 - tmp[v]+=1;
1.248 - return tmp;
1.249 - }
1.250 -
1.251 - ///\e
1.252 -
1.253 - ///\relates SparseLinExpr
1.254 - ///
1.255 - template <class V>
1.256 - SparseLinExpr<V> operator-(const SparseLinExpr<V> &e,const V &v) {
1.257 - SparseLinExpr<V> tmp(e);
1.258 - tmp[v]-=1;
1.259 - return tmp;
1.260 - }
1.261 -
1.262 - ///\e
1.263 -
1.264 - ///\relates SparseLinExpr
1.265 - ///
1.266 - template <class V>
1.267 - SparseLinExpr<V> operator+(const V &v,const typename V::ExprValue &c) {
1.268 - SparseLinExpr<V> tmp(v);
1.269 - tmp.constComp()=c;
1.270 - return tmp;
1.271 - }
1.272 -
1.273 - ///\e
1.274 -
1.275 - ///\relates SparseLinExpr
1.276 - ///
1.277 - template <class V>
1.278 - SparseLinExpr<V> operator-(const V &v,const typename V::ExprValue &c) {
1.279 - SparseLinExpr<V> tmp(v);
1.280 - tmp.constComp()=-c;
1.281 - return tmp;
1.282 - }
1.283 -
1.284 - ///\e
1.285 -
1.286 - ///\relates SparseLinExpr
1.287 - ///
1.288 - template <class V>
1.289 - SparseLinExpr<V> operator+(const typename V::ExprValue &c,const V &v) {
1.290 - SparseLinExpr<V> tmp(v);
1.291 - tmp.constComp()=c;
1.292 - return tmp;
1.293 - }
1.294 -
1.295 - ///\e
1.296 -
1.297 - ///\relates SparseLinExpr
1.298 - ///
1.299 - template <class V>
1.300 - SparseLinExpr<V> operator-(const typename V::ExprValue &c,const V &v) {
1.301 - SparseLinExpr<V> tmp(c);
1.302 - tmp[v]=-1;
1.303 - return tmp;
1.304 - }
1.305 -
1.306 - ///\e
1.307 -
1.308 - ///\relates SparseLinExpr
1.309 - ///
1.310 - template <class V>
1.311 - SparseLinExpr<V> operator+(const V &v1,const V &v2) {
1.312 - SparseLinExpr<V> tmp(v1);
1.313 - tmp[v2]+=1;
1.314 - return tmp;
1.315 - }
1.316 -
1.317 - ///\e
1.318 -
1.319 - ///\relates SparseLinExpr
1.320 - ///
1.321 - template <class V>
1.322 - SparseLinExpr<V> operator*(const V &v,const typename V::ExprValue &c) {
1.323 - SparseLinExpr<V> tmp;
1.324 - tmp[v]=c;
1.325 - return tmp;
1.326 - }
1.327 -
1.328 - ///\e
1.329 -
1.330 - ///\relates SparseLinExpr
1.331 - ///
1.332 - template <class V>
1.333 - SparseLinExpr<V> operator*(const typename V::ExprValue &c,const V &v) {
1.334 - SparseLinExpr<V> tmp;
1.335 - tmp[v]=c;
1.336 - return tmp;
1.337 - }
1.338 -
1.339 - ///\e
1.340 -
1.341 - ///\relates SparseLinExpr
1.342 - ///
1.343 - template <class V>
1.344 - SparseLinExpr<V> operator/(const V &v,const typename V::ExprValue &c) {
1.345 - SparseLinExpr<V> tmp;
1.346 - tmp[v]=1/c;
1.347 - return tmp;
1.348 - }
1.349 -
1.350 -
1.351 - //////////////////////////////////////////////////////////////////////
1.352 - /// Constraints
1.353 - //////////////////////////////////////////////////////////////////////
1.354 -
1.355 - template <class E>
1.356 - class LinConstr
1.357 - {
1.358 - public:
1.359 - typedef E Expr;
1.360 - typedef typename E::Var Var;
1.361 - typedef typename E::Coeff Coeff;
1.362 -
1.363 - static const Coeff INF;
1.364 - static const Coeff NaN;
1.365 -// static const Coeff INF=0;
1.366 -// static const Coeff NaN=1;
1.367 -
1.368 - Expr expr;
1.369 - Coeff lb,ub;
1.370 -
1.371 - LinConstr() : expr(), lb(NaN), ub(NaN) {}
1.372 - LinConstr(Coeff _lb,const Expr &e,Coeff _ub) :
1.373 - expr(e), lb(_lb), ub(_ub) {}
1.374 - LinConstr(const Expr &e,Coeff _ub) :
1.375 - expr(e), lb(NaN), ub(_ub) {}
1.376 - LinConstr(Coeff _lb,const Expr &e) :
1.377 - expr(e), lb(_lb), ub(NaN) {}
1.378 - };
1.379 -
1.380 - template<class E>
1.381 - const typename LinConstr<E>::Coeff LinConstr<E>::INF=
1.382 - std::numeric_limits<Coeff>::infinity();
1.383 - template<class E>
1.384 - const typename LinConstr<E>::Coeff LinConstr<E>::NaN=
1.385 - std::numeric_limits<Coeff>::quiet_NaN();
1.386 -
1.387 -
1.388 - template<class E>
1.389 - typename enable_if<typename E::IsLinExpression, LinConstr<E> >::type
1.390 - operator<=(const E &e,const E &f)
1.391 - {
1.392 - return LinConstr<E>(-LinConstr<E>::INF,e-f,0);
1.393 - }
1.394 -
1.395 - template<class E>
1.396 - typename enable_if<typename E::IsLinExpression, LinConstr<E> >::type
1.397 - operator>=(const E &e,const E &f)
1.398 - {
1.399 - return LinConstr<E>(-LinConstr<E>::INF,f-e,0);
1.400 - }
1.401 -
1.402 - template<class E>
1.403 - typename enable_if<typename E::IsLinExpression, LinConstr<E> >::type
1.404 - operator==(const E &e,const E &f)
1.405 - {
1.406 - return LinConstr<E>(0,e-f,0);
1.407 - }
1.408 -
1.409 - //////////////////////////////
1.410 -
1.411 - template<class E>
1.412 - typename enable_if<typename E::IsLinExpression, LinConstr<E> >::type
1.413 - operator<=(const E &e,const typename E::Coeff &n)
1.414 - {
1.415 - return LinConstr<E>(e,n);
1.416 - }
1.417 -
1.418 - template<class E>
1.419 - typename enable_if<typename E::IsLinExpression, LinConstr<E> >::type
1.420 - operator>=(const E &e,const typename E::Coeff &n)
1.421 - {
1.422 - return LinConstr<E>(n,e);
1.423 - }
1.424 -
1.425 - template<class E>
1.426 - typename enable_if<typename E::IsLinExpression, LinConstr<E> >::type
1.427 - operator==(const E &e,const typename E::Coeff &n)
1.428 - {
1.429 - return LinConstr<E>(n,e,n);
1.430 - }
1.431 -
1.432 - //////////////////////////////
1.433 -
1.434 - template<class E>
1.435 - typename enable_if<typename E::IsLinExpression, LinConstr<E> >::type
1.436 - operator<=(const typename E::Coeff &n,const E &e)
1.437 - {
1.438 - return LinConstr<E>(n,e);
1.439 - }
1.440 -
1.441 - template<class E>
1.442 - typename enable_if<typename E::IsLinExpression, LinConstr<E> >::type
1.443 - operator>=(const typename E::Coeff &n,const E &e)
1.444 - {
1.445 - return LinConstr<E>(e,n);
1.446 - }
1.447 -
1.448 - template<class E>
1.449 - typename enable_if<typename E::IsLinExpression, LinConstr<E> >::type
1.450 - operator==(const typename E::Coeff &n,const E &e)
1.451 - {
1.452 - return LinConstr<E>(n,e,n);
1.453 - }
1.454 -
1.455 - //////////////////////////////
1.456 -
1.457 - template<class E>
1.458 - typename enable_if<typename E::IsLinExpression, LinConstr<E> >::type
1.459 - operator<=(const typename E::Coeff &n,const LinConstr<E> &c)
1.460 - {
1.461 - LinConstr<E> tmp(c);
1.462 - if(tmp.lb!=tmp.NaN) throw LogicError();
1.463 - else tmp.lb=n;
1.464 - return tmp;
1.465 - }
1.466 -
1.467 - template<class E>
1.468 - typename enable_if<typename E::IsLinExpression, LinConstr<E> >::type
1.469 - operator>=(const typename E::Coeff &n,const LinConstr<E> &c)
1.470 - {
1.471 - LinConstr<E> tmp(c);
1.472 - if(tmp.ub!=tmp.NaN) throw LogicError();
1.473 - else tmp.ub=n;
1.474 - return tmp;
1.475 - }
1.476 -
1.477 - template<class E>
1.478 - typename enable_if<typename E::IsLinExpression, LinConstr<E> >::type
1.479 - operator<=(const LinConstr<E> &c,const typename E::Coeff &n)
1.480 - {
1.481 - LinConstr<E> tmp(c);
1.482 - if(tmp.ub!=tmp.NaN) throw LogicError();
1.483 - else tmp.ub=n;
1.484 - return tmp;
1.485 - }
1.486 -
1.487 - template<class E>
1.488 - typename enable_if<typename E::IsLinExpression, LinConstr<E> >::type
1.489 - operator>=(const LinConstr<E> &c,const typename E::Coeff &n)
1.490 - {
1.491 - LinConstr<E> tmp(c);
1.492 - if(tmp.lb!=tmp.NaN) throw LogicError();
1.493 - else tmp.lb=n;
1.494 - return tmp;
1.495 - }
1.496 -
1.497 -
1.498 -
1.499 -} //namespace lemon
1.500 -
1.501 -#endif //LEMON_LIN_EXPR_H