alpar@1253: /* -*- C++ -*-
alpar@1253:  * src/lemon/lin_expr.h - Part of LEMON, a generic C++ optimization library
alpar@1253:  *
alpar@1253:  * Copyright (C) 2005 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
alpar@1253:  * (Egervary Combinatorial Optimization Research Group, EGRES).
alpar@1253:  *
alpar@1253:  * Permission to use, modify and distribute this software is granted
alpar@1253:  * provided that this copyright notice appears in all copies. For
alpar@1253:  * precise terms see the accompanying LICENSE file.
alpar@1253:  *
alpar@1253:  * This software is provided "AS IS" with no warranty of any kind,
alpar@1253:  * express or implied, and with no claim as to its suitability for any
alpar@1253:  * purpose.
alpar@1253:  *
alpar@1253:  */
alpar@1253: 
alpar@1253: #ifndef LEMON_LIN_EXPR_H
alpar@1253: #define LEMON_LIN_EXPR_H
alpar@1253: 
alpar@1253: #include<vector>
alpar@1253: #include<map>
alpar@1264: #include<lemon/utility.h>
alpar@1253: ///\file
alpar@1253: ///\brief Classes to handle linear expressions
alpar@1253: namespace lemon {
alpar@1253:   
alpar@1253:   /// Class to handle sparse linear expressions
alpar@1259:   template <class _V>
alpar@1259:   class SparseLinExpr : public std::map<_V, typename _V::ExprValue>
alpar@1253:   {
alpar@1253:   public:
alpar@1253:     typedef _V Var; 
alpar@1259:     typedef typename _V::ExprValue Coeff;
alpar@1253:     
alpar@1253:   protected:
alpar@1259:     typedef typename std::map<_V, typename _V::ExprValue> Base;
alpar@1253: 
alpar@1253:     Coeff const_comp;
alpar@1253:   public:
alpar@1264:     typedef True IsLinExpression;
alpar@1259:     ///\e
alpar@1259:     SparseLinExpr() : Base(), const_comp(0) { }
alpar@1259:     ///\e
alpar@1259:     SparseLinExpr(const Var &v) : const_comp(0) {
alpar@1253:       Base::insert(std::make_pair(v, 1));
alpar@1253:     }
alpar@1259:     ///\e
alpar@1253:     SparseLinExpr(const Coeff &v) : const_comp(v) {}
alpar@1253:     
alpar@1259:     ///\e
alpar@1253:     void set(const Var &v,const Coeff &c) {
alpar@1253:       return Base::insert(std::make_pair(v, c));
alpar@1253:     }
alpar@1253: //     Coeff &operator[](const Var &v) { return data[v]; }
alpar@1253: //     const Coeff &operator[](const Var &v) const { return data[v]; }
alpar@1253: 
alpar@1259:     ///\e
alpar@1253:     Coeff &constComp() { return const_comp; }
alpar@1259:     ///\e
alpar@1253:     const Coeff &constComp() const { return const_comp; }
alpar@1253: 
alpar@1253:     ///Removes the components with zero coefficient.
alpar@1253:     void simplify() {
alpar@1253:       for (typename Base::iterator i=Base::begin(); i!=Base::end();) {
alpar@1253: 	typename Base::iterator j=i;
alpar@1253: 	++j;
alpar@1253: 	if ((*i).second==0) Base::erase(i);
alpar@1253: 	j=i;
alpar@1253:       }
alpar@1253:     }
alpar@1253:    
alpar@1259:     ///\e
alpar@1259:     SparseLinExpr &operator+=(const SparseLinExpr &e) {
alpar@1259:       for (typename Base::const_iterator j=e.begin(); j!=e.end(); ++j)
alpar@1259: 	(*this)[j->first]+=j->second;
alpar@1259:       ///\todo it might be speeded up using "hints"
alpar@1259:       const_comp+=e.const_comp;
alpar@1259:       return *this;
alpar@1259:     }
alpar@1259:     ///\e
alpar@1259:     SparseLinExpr &operator-=(const SparseLinExpr &e) {
alpar@1259:       for (typename Base::const_iterator j=e.begin(); j!=e.end(); ++j)
alpar@1259: 	(*this)[j->first]-=j->second;
alpar@1259:       const_comp-=e.const_comp;
alpar@1259:       return *this;
alpar@1259:     }
alpar@1259:     ///\e
alpar@1259:     SparseLinExpr &operator*=(const Coeff &c) {
alpar@1259:       for (typename Base::iterator j=Base::begin(); j!=Base::end(); ++j)
alpar@1259: 	j->second*=c;
alpar@1259:       const_comp*=c;
alpar@1259:       return *this;
alpar@1259:     }
alpar@1259:     ///\e
alpar@1259:     SparseLinExpr &operator/=(const Coeff &c) {
alpar@1259:       for (typename Base::iterator j=Base::begin(); j!=Base::end(); ++j)
alpar@1259: 	j->second/=c;
alpar@1259:       const_comp/=c;
alpar@1259:       return *this;
alpar@1259:     }
alpar@1259:     
alpar@1253:   };
alpar@1253: 
alpar@1259:   ///\e
alpar@1259:   
alpar@1259:   ///\relates SparseLinExpr
alpar@1259:   ///
alpar@1259:   template <class V>
alpar@1259:   SparseLinExpr<V> operator+(const SparseLinExpr<V> &a,
alpar@1259: 				const SparseLinExpr<V> &b) {
alpar@1259:     SparseLinExpr<V> tmp(a);
alpar@1259:     tmp+=b; ///\todo Don't STL have some special 'merge' algorithm?
alpar@1259:     return tmp;
alpar@1259:   }
alpar@1259:   
alpar@1259:   ///\e
alpar@1259:   
alpar@1259:   ///\relates SparseLinExpr
alpar@1259:   ///
alpar@1259:   template <class V>
alpar@1259:   SparseLinExpr<V> operator-(const SparseLinExpr<V> &a,
alpar@1259: 				const SparseLinExpr<V> &b) {
alpar@1259:     SparseLinExpr<V> tmp(a);
alpar@1259:     tmp-=b; ///\todo Don't STL have some special 'merge' algorithm?
alpar@1259:     return tmp;
alpar@1259:   }
alpar@1259:   
alpar@1259:   ///\e
alpar@1259:   
alpar@1259:   ///\relates SparseLinExpr
alpar@1259:   ///
alpar@1259:   template <class V>
alpar@1259:   SparseLinExpr<V> operator*(const typename V::ExprValue &c,
alpar@1259: 			       const SparseLinExpr<V> &e) {
alpar@1259:     SparseLinExpr<V> tmp(e);
alpar@1259:     tmp*=c;
alpar@1259:     return tmp;
alpar@1259:   }
alpar@1259:   
alpar@1259:   ///\e
alpar@1259:   
alpar@1259:   ///\relates SparseLinExpr
alpar@1259:   ///
alpar@1259:   template <class V>
alpar@1259:   SparseLinExpr<V> operator*(const SparseLinExpr<V> &e,
alpar@1259: 			       const typename V::ExprValue &c) {
alpar@1259:     SparseLinExpr<V> tmp(e);
alpar@1259:     tmp*=c;
alpar@1259:     return tmp;
alpar@1259:   }
alpar@1259:   
alpar@1259:   
alpar@1259:   ///\e
alpar@1259:   
alpar@1259:   ///\relates SparseLinExpr
alpar@1259:   ///
alpar@1259:   template <class V>
alpar@1259:   SparseLinExpr<V> operator/(const SparseLinExpr<V> &e,
alpar@1259: 			       const typename V::ExprValue &c) {
alpar@1259:     SparseLinExpr<V> tmp(e);
alpar@1259:     tmp/=c;
alpar@1259:     return tmp;
alpar@1259:   }
alpar@1259:   
alpar@1259:   ///\e
alpar@1259:   
alpar@1259:   ///\relates SparseLinExpr
alpar@1259:   ///
alpar@1259:   template <class V>
alpar@1259:   SparseLinExpr<V> operator+(const typename V::ExprValue &c,
alpar@1259: 			     const SparseLinExpr<V> &e) {
alpar@1259:     SparseLinExpr<V> tmp(e);
alpar@1259:     tmp.constComp()+=c;
alpar@1259:     return tmp;
alpar@1259:   }
alpar@1259: 
alpar@1259:   ///\e
alpar@1259:   
alpar@1259:   ///\relates SparseLinExpr
alpar@1259:   ///
alpar@1259:   template <class V>
alpar@1259:   SparseLinExpr<V> operator+(const SparseLinExpr<V> &e,
alpar@1259: 			     const typename V::ExprValue &c) {
alpar@1259:     SparseLinExpr<V> tmp(e);
alpar@1259:     tmp.constComp()+=c;
alpar@1259:     return tmp;
alpar@1259:   }
alpar@1259: 
alpar@1259:   ///\e
alpar@1259:   
alpar@1259:   ///\relates SparseLinExpr
alpar@1259:   ///
alpar@1259:   template <class V>
alpar@1259:   SparseLinExpr<V> operator+(const V &v,const SparseLinExpr<V> &e) {
alpar@1259:     SparseLinExpr<V> tmp(e);
alpar@1259:     tmp[v]+=1;
alpar@1259:     return tmp;
alpar@1259:   }
alpar@1259: 
alpar@1259:   ///\e
alpar@1259:   
alpar@1259:   ///\relates SparseLinExpr
alpar@1259:   ///
alpar@1259:   template <class V>
alpar@1259:   SparseLinExpr<V> operator+(const SparseLinExpr<V> &e,const V &v) {
alpar@1259:     SparseLinExpr<V> tmp(e);
alpar@1259:     tmp[v]+=1;
alpar@1259:     return tmp;
alpar@1259:   }
alpar@1259: 
alpar@1259:   ///\e
alpar@1259:   
alpar@1259:   ///\relates SparseLinExpr
alpar@1259:   ///
alpar@1259:   template <class V>
alpar@1259:   SparseLinExpr<V> operator-(const typename V::ExprValue &c,
alpar@1259: 			     const SparseLinExpr<V> &e) {
alpar@1259:     SparseLinExpr<V> tmp(e);
alpar@1259:     tmp*=-1;
alpar@1259:     tmp.constComp()+=c;
alpar@1259:     return tmp;
alpar@1259:   }
alpar@1259: 
alpar@1259:   ///\e
alpar@1259:   
alpar@1259:   ///\relates SparseLinExpr
alpar@1259:   ///
alpar@1259:   template <class V>
alpar@1259:   SparseLinExpr<V> operator-(const SparseLinExpr<V> &e,
alpar@1259: 			     const typename V::ExprValue &c) {
alpar@1259:     SparseLinExpr<V> tmp(e);
alpar@1259:     tmp.constComp()-=c;
alpar@1259:     return tmp;
alpar@1259:   }
alpar@1259: 
alpar@1259:   ///\e
alpar@1259:   
alpar@1259:   ///\relates SparseLinExpr
alpar@1259:   ///
alpar@1259:   template <class V>
alpar@1259:   SparseLinExpr<V> operator-(const V &v,const SparseLinExpr<V> &e) {
alpar@1259:     SparseLinExpr<V> tmp(e);
alpar@1259:     tmp*=-1;
alpar@1259:     tmp[v]+=1;
alpar@1259:     return tmp;
alpar@1259:   }
alpar@1259: 
alpar@1259:   ///\e
alpar@1259:   
alpar@1259:   ///\relates SparseLinExpr
alpar@1259:   ///
alpar@1259:   template <class V>
alpar@1259:   SparseLinExpr<V> operator-(const SparseLinExpr<V> &e,const V &v) {
alpar@1259:     SparseLinExpr<V> tmp(e);
alpar@1259:     tmp[v]-=1;
alpar@1259:     return tmp;
alpar@1259:   }
alpar@1259: 
alpar@1259:   ///\e
alpar@1259:   
alpar@1259:   ///\relates SparseLinExpr
alpar@1259:   ///
alpar@1259:   template <class V>
alpar@1264:   SparseLinExpr<V> operator+(const V &v,const typename V::ExprValue &c) {
alpar@1264:     SparseLinExpr<V> tmp(v);
alpar@1264:     tmp.constComp()=c;
alpar@1264:     return tmp;
alpar@1264:   }
alpar@1264: 
alpar@1264:   ///\e
alpar@1264:   
alpar@1264:   ///\relates SparseLinExpr
alpar@1264:   ///
alpar@1264:   template <class V>
alpar@1264:   SparseLinExpr<V> operator-(const V &v,const typename V::ExprValue &c) {
alpar@1264:     SparseLinExpr<V> tmp(v);
alpar@1264:     tmp.constComp()=-c;
alpar@1264:     return tmp;
alpar@1264:   }
alpar@1264: 
alpar@1264:   ///\e
alpar@1264:   
alpar@1264:   ///\relates SparseLinExpr
alpar@1264:   ///
alpar@1264:   template <class V>
alpar@1264:   SparseLinExpr<V> operator+(const typename V::ExprValue &c,const V &v) {
alpar@1264:     SparseLinExpr<V> tmp(v);
alpar@1264:     tmp.constComp()=c;
alpar@1264:     return tmp;
alpar@1264:   }
alpar@1264: 
alpar@1264:   ///\e
alpar@1264:   
alpar@1264:   ///\relates SparseLinExpr
alpar@1264:   ///
alpar@1264:   template <class V>
alpar@1264:   SparseLinExpr<V> operator-(const typename V::ExprValue &c,const V &v) {
alpar@1264:     SparseLinExpr<V> tmp(c);
alpar@1264:     tmp[v]=-1;
alpar@1264:     return tmp;
alpar@1264:   }
alpar@1264: 
alpar@1264:   ///\e
alpar@1264:   
alpar@1264:   ///\relates SparseLinExpr
alpar@1264:   ///
alpar@1264:   template <class V>
alpar@1259:   SparseLinExpr<V> operator+(const V &v1,const V &v2) {
alpar@1259:     SparseLinExpr<V> tmp(v1);
alpar@1259:     tmp[v2]+=1;
alpar@1259:     return tmp;
alpar@1259:   }
alpar@1259: 
alpar@1259:   ///\e
alpar@1259:   
alpar@1259:   ///\relates SparseLinExpr
alpar@1259:   ///
alpar@1259:   template <class V>
alpar@1259:   SparseLinExpr<V> operator*(const V &v,const typename V::ExprValue &c) {
alpar@1259:     SparseLinExpr<V> tmp;
alpar@1259:     tmp[v]=c;
alpar@1259:     return tmp;
alpar@1259:   }
alpar@1259: 
alpar@1259:   ///\e
alpar@1259:   
alpar@1259:   ///\relates SparseLinExpr
alpar@1259:   ///
alpar@1259:   template <class V>
alpar@1259:   SparseLinExpr<V> operator*(const typename V::ExprValue &c,const V &v) {
alpar@1259:     SparseLinExpr<V> tmp;
alpar@1259:     tmp[v]=c;
alpar@1259:     return tmp;
alpar@1259:   }
alpar@1259: 
alpar@1259:   ///\e
alpar@1259:   
alpar@1259:   ///\relates SparseLinExpr
alpar@1259:   ///
alpar@1259:   template <class V>
alpar@1259:   SparseLinExpr<V> operator/(const V &v,const typename V::ExprValue &c) {
alpar@1259:     SparseLinExpr<V> tmp;
alpar@1259:     tmp[v]=1/c;
alpar@1259:     return tmp;
alpar@1259:   }
alpar@1259: 
alpar@1259: 
alpar@1264:   //////////////////////////////////////////////////////////////////////
alpar@1264:   /// Constraints
alpar@1264:   //////////////////////////////////////////////////////////////////////
alpar@1264:   
alpar@1264:   template <class E>
alpar@1264:   class LinConstr
alpar@1264:   {
alpar@1264:   public:
alpar@1264:     typedef E Expr;
alpar@1264:     typedef typename E::Var Var;
alpar@1264:     typedef typename E::Coeff Coeff;
alpar@1264:     
alpar@1264:     static const Coeff INF;
alpar@1264:     static const Coeff NaN;
alpar@1264: //     static const Coeff INF=0;
alpar@1264: //     static const Coeff NaN=1;
alpar@1264: 
alpar@1264:     Expr expr;
alpar@1264:     Coeff lb,ub;
alpar@1264:     
alpar@1264:     LinConstr() : expr(), lb(NaN), ub(NaN) {}
alpar@1264:     LinConstr(Coeff _lb,const Expr &e,Coeff _ub) :
alpar@1264:       expr(e), lb(_lb), ub(_ub) {}
alpar@1264:     LinConstr(const Expr &e,Coeff _ub) : 
alpar@1264:       expr(e), lb(NaN), ub(_ub) {}
alpar@1264:     LinConstr(Coeff _lb,const Expr &e) :
alpar@1264:       expr(e), lb(_lb), ub(NaN) {}
alpar@1264:   };
alpar@1264: 
alpar@1264:   template<class E>
alpar@1264:   const typename LinConstr<E>::Coeff LinConstr<E>::INF=
alpar@1264:     std::numeric_limits<Coeff>::infinity();
alpar@1264:   template<class E>
alpar@1264:   const typename LinConstr<E>::Coeff LinConstr<E>::NaN=
alpar@1264:     std::numeric_limits<Coeff>::quiet_NaN();
alpar@1264: 
alpar@1264:   
alpar@1264:   template<class E>
alpar@1264:   typename enable_if<typename E::IsLinExpression, LinConstr<E> >::type
alpar@1264:   operator<=(const E &e,const E &f) 
alpar@1264:   {
alpar@1264:     return LinConstr<E>(-LinConstr<E>::INF,e-f,0);
alpar@1264:   }
alpar@1264: 
alpar@1264:   template<class E>
alpar@1264:   typename enable_if<typename E::IsLinExpression, LinConstr<E> >::type
alpar@1264:   operator>=(const E &e,const E &f) 
alpar@1264:   {
alpar@1264:     return LinConstr<E>(-LinConstr<E>::INF,f-e,0);
alpar@1264:   }
alpar@1264: 
alpar@1264:   template<class E>
alpar@1264:   typename enable_if<typename E::IsLinExpression, LinConstr<E> >::type
alpar@1264:   operator==(const E &e,const E &f) 
alpar@1264:   {
alpar@1264:     return LinConstr<E>(0,e-f,0);
alpar@1264:   }
alpar@1264:   
alpar@1264:   //////////////////////////////
alpar@1264: 
alpar@1264:   template<class E>
alpar@1264:   typename enable_if<typename E::IsLinExpression, LinConstr<E> >::type
alpar@1264:   operator<=(const E &e,const typename E::Coeff &n) 
alpar@1264:   {
alpar@1264:     return LinConstr<E>(e,n);
alpar@1264:   }
alpar@1264: 
alpar@1264:   template<class E>
alpar@1264:   typename enable_if<typename E::IsLinExpression, LinConstr<E> >::type
alpar@1264:   operator>=(const E &e,const typename E::Coeff &n) 
alpar@1264:   {
alpar@1264:     return LinConstr<E>(n,e);
alpar@1264:   }
alpar@1264: 
alpar@1264:   template<class E>
alpar@1264:   typename enable_if<typename E::IsLinExpression, LinConstr<E> >::type
alpar@1264:   operator==(const E &e,const typename E::Coeff &n) 
alpar@1264:   {
alpar@1264:     return LinConstr<E>(n,e,n);
alpar@1264:   }
alpar@1264: 
alpar@1264:   //////////////////////////////
alpar@1264: 
alpar@1264:   template<class E>
alpar@1264:   typename enable_if<typename E::IsLinExpression, LinConstr<E> >::type
alpar@1264:   operator<=(const typename E::Coeff &n,const E &e) 
alpar@1264:   {
alpar@1264:     return LinConstr<E>(n,e);
alpar@1264:   }
alpar@1264: 
alpar@1264:   template<class E>
alpar@1264:   typename enable_if<typename E::IsLinExpression, LinConstr<E> >::type
alpar@1264:   operator>=(const typename E::Coeff &n,const E &e) 
alpar@1264:   {
alpar@1264:     return LinConstr<E>(e,n);
alpar@1264:   }
alpar@1264: 
alpar@1264:   template<class E>
alpar@1264:   typename enable_if<typename E::IsLinExpression, LinConstr<E> >::type
alpar@1264:   operator==(const typename E::Coeff &n,const E &e) 
alpar@1264:   {
alpar@1264:     return LinConstr<E>(n,e,n);
alpar@1264:   }
alpar@1264: 
alpar@1264:   //////////////////////////////
alpar@1264: 
alpar@1264:   template<class E>
alpar@1264:   typename enable_if<typename E::IsLinExpression, LinConstr<E> >::type
alpar@1264:   operator<=(const typename E::Coeff &n,const LinConstr<E> &c) 
alpar@1264:   {
alpar@1264:     LinConstr<E> tmp(c);
alpar@1264:     if(tmp.lb!=tmp.NaN) throw LogicError();
alpar@1264:     else tmp.lb=n;
alpar@1264:     return tmp;
alpar@1264:   }
alpar@1264: 
alpar@1264:   template<class E>
alpar@1264:   typename enable_if<typename E::IsLinExpression, LinConstr<E> >::type
alpar@1264:   operator>=(const typename E::Coeff &n,const LinConstr<E> &c) 
alpar@1264:   {
alpar@1264:     LinConstr<E> tmp(c);
alpar@1264:     if(tmp.ub!=tmp.NaN) throw LogicError();
alpar@1264:     else tmp.ub=n;
alpar@1264:     return tmp;
alpar@1264:   }
alpar@1264: 
alpar@1264:   template<class E>
alpar@1264:   typename enable_if<typename E::IsLinExpression, LinConstr<E> >::type
alpar@1264:   operator<=(const LinConstr<E> &c,const typename E::Coeff &n) 
alpar@1264:   {
alpar@1264:     LinConstr<E> tmp(c);
alpar@1264:     if(tmp.ub!=tmp.NaN) throw LogicError();
alpar@1264:     else tmp.ub=n;
alpar@1264:     return tmp;
alpar@1264:   }
alpar@1264: 
alpar@1264:   template<class E>
alpar@1264:   typename enable_if<typename E::IsLinExpression, LinConstr<E> >::type
alpar@1264:   operator>=(const LinConstr<E> &c,const typename E::Coeff &n) 
alpar@1264:   {
alpar@1264:     LinConstr<E> tmp(c);
alpar@1264:     if(tmp.lb!=tmp.NaN) throw LogicError();
alpar@1264:     else tmp.lb=n;
alpar@1264:     return tmp;
alpar@1264:   }
alpar@1264: 
alpar@1264:   
alpar@1264: 
alpar@1253: } //namespace lemon
alpar@1253: 
alpar@1253: #endif //LEMON_LIN_EXPR_H