source:lemon-0.x/src/work/marci/lp/expression.h@1153:4b0468de3a31

Last change on this file since 1153:4b0468de3a31 was 1144:1cfabf245433, checked in by marci, 16 years ago

trying to add constraints of kind 1 <= x[2]+x[3] <= 4

File size: 5.1 KB
Line
1// -*- c++ -*-
2#ifndef LEMON_EXPRESSION_H
3#define LEMON_EXPRESSION_H
4
5#include <iostream>
6#include <map>
7#include <limits>
8
9namespace lemon {
10
11  /*! \brief Linear expression
12
13    \c Expr<_Col,_Value> implements a class of linear expressions with the
14    operations of addition and multiplication with scalar.
15
16    \author Marton Makai
17   */
18  template <typename _Col, typename _Value>
19  class Expr;
20
21  template <typename _Col, typename _Value>
22  class Expr {
23//  protected:
24  public:
25    typedef
26    typename std::map<_Col, _Value> Data;
27    Data data;
28  public:
29    void simplify() {
30      for (typename Data::iterator i=data.begin();
31           i!=data.end(); ++i) {
32        if ((*i).second==0) data.erase(i);
33      }
34    }
35    Expr() { }
36    Expr(_Col _col) {
37      data.insert(std::make_pair(_col, 1));
38    }
39    Expr& operator*=(_Value _value) {
40      for (typename Data::iterator i=data.begin();
41           i!=data.end(); ++i) {
42        (*i).second *= _value;
43      }
44      simplify();
45      return *this;
46    }
47    Expr& operator+=(const Expr<_Col, _Value>& expr) {
48      for (typename Data::const_iterator j=expr.data.begin();
49           j!=expr.data.end(); ++j) {
50        typename Data::iterator i=data.find((*j).first);
51        if (i==data.end()) {
52          data.insert(std::make_pair((*j).first, (*j).second));
53        } else {
54          (*i).second+=(*j).second;
55        }
56      }
57      simplify();
58      return *this;
59    }
60    Expr& operator-=(const Expr<_Col, _Value>& expr) {
61      for (typename Data::const_iterator j=expr.data.begin();
62           j!=expr.data.end(); ++j) {
63        typename Data::iterator i=data.find((*j).first);
64        if (i==data.end()) {
65          data.insert(std::make_pair((*j).first, -(*j).second));
66        } else {
67          (*i).second+=-(*j).second;
68        }
69      }
70      simplify();
71      return *this;
72    }
73    template <typename _C, typename _V>
74    friend std::ostream& operator<<(std::ostream& os,
75                                    const Expr<_C, _V>& expr);
76  };
77
78  template <typename _Col, typename _Value>
79  Expr<_Col, _Value> operator*(_Value _value, _Col _col) {
80    Expr<_Col, _Value> tmp(_col);
81    tmp*=_value;
82    tmp.simplify();
83    return tmp;
84  }
85
86  template <typename _Col, typename _Value>
87  Expr<_Col, _Value> operator*(_Value _value,
88                               const Expr<_Col, _Value>& expr) {
89    Expr<_Col, _Value> tmp(expr);
90    tmp*=_value;
91    tmp.simplify();
92    return tmp;
93  }
94
95  template <typename _Col, typename _Value>
96  Expr<_Col, _Value> operator+(const Expr<_Col, _Value>& expr1,
97                               const Expr<_Col, _Value>& expr2) {
98    Expr<_Col, _Value> tmp(expr1);
99    tmp+=expr2;
100    tmp.simplify();
101    return tmp;
102  }
103
104  template <typename _Col, typename _Value>
105  Expr<_Col, _Value> operator-(const Expr<_Col, _Value>& expr1,
106                               const Expr<_Col, _Value>& expr2) {
107    Expr<_Col, _Value> tmp(expr1);
108    tmp-=expr2;
109    tmp.simplify();
110    return tmp;
111  }
112
113  template <typename _Col, typename _Value>
114  std::ostream& operator<<(std::ostream& os,
115                           const Expr<_Col, _Value>& expr) {
116    for (typename Expr<_Col, _Value>::Data::const_iterator i=
117           expr.data.begin();
118         i!=expr.data.end(); ++i) {
119      os << (*i).second << "*" << (*i).first << " ";
120    }
121    return os;
122  }
123
124  template <typename _Col, typename _Value>
125  class LConstr {
126    //  protected:
127  public:
128    Expr<_Col, _Value> expr;
129    _Value lo;
130  public:
131    LConstr(const Expr<_Col, _Value>& _expr, _Value _lo) :
132      expr(_expr), lo(_lo) { }
133  };
134
135  template <typename _Col, typename _Value>
136  LConstr<_Col, _Value>
137  operator<=(_Value lo, const Expr<_Col, _Value>& expr) {
138    return LConstr<_Col, _Value>(expr, lo);
139  }
140
141  template <typename _Col, typename _Value>
142  class UConstr {
143    //  protected:
144  public:
145    Expr<_Col, _Value> expr;
146    _Value up;
147  public:
148    UConstr(const Expr<_Col, _Value>& _expr, _Value _up) :
149      expr(_expr), up(_up) { }
150  };
151
152  template <typename _Col, typename _Value>
153  UConstr<_Col, _Value>
154  operator<=(const Expr<_Col, _Value>& expr, _Value up) {
155    return UConstr<_Col, _Value>(expr, up);
156  }
157
158  template <typename _Col, typename _Value>
159  class Constr {
160    //  protected:
161  public:
162    Expr<_Col, _Value> expr;
163    _Value lo, up;
164  public:
165    Constr(const Expr<_Col, _Value>& _expr, _Value _lo, _Value _up) :
166      expr(_expr), lo(_lo), up(_up) { }
167    Constr(const LConstr<_Col, _Value>& _lconstr) :
168      expr(_lconstr.expr),
169      lo(_lconstr.lo),
170      up(std::numeric_limits<_Value>::infinity()) { }
171    Constr(const UConstr<_Col, _Value>& _uconstr) :
172      expr(_uconstr.expr),
173      lo(-std::numeric_limits<_Value>::infinity()),
174      up(_uconstr.up) { }
175  };
176
177  template <typename _Col, typename _Value>
178  Constr<_Col, _Value>
179  operator<=(const LConstr<_Col, _Value>& lconstr, _Value up) {
180    return Constr<_Col, _Value>(lconstr.expr, lconstr.lo, up);
181  }
182
183  template <typename _Col, typename _Value>
184  Constr<_Col, _Value>
185  operator<=(_Value lo, const UConstr<_Col, _Value>& uconstr) {
186    return Constr<_Col, _Value>(uconstr.expr, lo, uconstr.up);
187  }
188
189  template <typename _Col, typename _Value>
190  Constr<_Col, _Value>
191  operator==(const Expr<_Col, _Value>& expr, _Value value) {
192    return Constr<_Col, _Value>(expr, value, value);
193  }
194
195} //namespace lemon
196
197#endif //LEMON_EXPRESSION_H
Note: See TracBrowser for help on using the repository browser.