COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/work/athos/lp/lin_expr.h @ 1259:11a09f1319b3

Last change on this file since 1259:11a09f1319b3 was 1259:11a09f1319b3, checked in by Alpar Juttner, 18 years ago
  • Largely extended linear expressions
  • Better docs
File size: 6.5 KB
Line 
1/* -*- C++ -*-
2 * src/lemon/lin_expr.h - Part of LEMON, a generic C++ optimization library
3 *
4 * Copyright (C) 2005 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
5 * (Egervary Combinatorial Optimization Research Group, EGRES).
6 *
7 * Permission to use, modify and distribute this software is granted
8 * provided that this copyright notice appears in all copies. For
9 * precise terms see the accompanying LICENSE file.
10 *
11 * This software is provided "AS IS" with no warranty of any kind,
12 * express or implied, and with no claim as to its suitability for any
13 * purpose.
14 *
15 */
16
17#ifndef LEMON_LIN_EXPR_H
18#define LEMON_LIN_EXPR_H
19
20#include<vector>
21
22
23#include<map>
24
25///\file
26///\brief Classes to handle linear expressions
27namespace lemon {
28 
29  /// Class to handle sparse linear expressions
30  template <class _V>
31  class SparseLinExpr : public std::map<_V, typename _V::ExprValue>
32  {
33  public:
34    typedef _V Var;
35    typedef typename _V::ExprValue Coeff;
36   
37  protected:
38    typedef typename std::map<_V, typename _V::ExprValue> Base;
39
40    Coeff const_comp;
41  public:
42    ///\e
43    SparseLinExpr() : Base(), const_comp(0) { }
44    ///\e
45    SparseLinExpr(const Var &v) : const_comp(0) {
46      Base::insert(std::make_pair(v, 1));
47    }
48    ///\e
49    SparseLinExpr(const Coeff &v) : const_comp(v) {}
50   
51    ///\e
52    void set(const Var &v,const Coeff &c) {
53      return Base::insert(std::make_pair(v, c));
54    }
55//     Coeff &operator[](const Var &v) { return data[v]; }
56//     const Coeff &operator[](const Var &v) const { return data[v]; }
57
58    ///\e
59    Coeff &constComp() { return const_comp; }
60    ///\e
61    const Coeff &constComp() const { return const_comp; }
62
63    ///Removes the components with zero coefficient.
64    void simplify() {
65      for (typename Base::iterator i=Base::begin(); i!=Base::end();) {
66        typename Base::iterator j=i;
67        ++j;
68        if ((*i).second==0) Base::erase(i);
69        j=i;
70      }
71    }
72   
73    ///\e
74    SparseLinExpr &operator+=(const SparseLinExpr &e) {
75      for (typename Base::const_iterator j=e.begin(); j!=e.end(); ++j)
76        (*this)[j->first]+=j->second;
77      ///\todo it might be speeded up using "hints"
78      const_comp+=e.const_comp;
79      return *this;
80    }
81    ///\e
82    SparseLinExpr &operator-=(const SparseLinExpr &e) {
83      for (typename Base::const_iterator j=e.begin(); j!=e.end(); ++j)
84        (*this)[j->first]-=j->second;
85      const_comp-=e.const_comp;
86      return *this;
87    }
88    ///\e
89    SparseLinExpr &operator*=(const Coeff &c) {
90      for (typename Base::iterator j=Base::begin(); j!=Base::end(); ++j)
91        j->second*=c;
92      const_comp*=c;
93      return *this;
94    }
95    ///\e
96    SparseLinExpr &operator/=(const Coeff &c) {
97      for (typename Base::iterator j=Base::begin(); j!=Base::end(); ++j)
98        j->second/=c;
99      const_comp/=c;
100      return *this;
101    }
102   
103  };
104
105  ///\e
106 
107  ///\relates SparseLinExpr
108  ///
109  template <class V>
110  SparseLinExpr<V> operator+(const SparseLinExpr<V> &a,
111                                const SparseLinExpr<V> &b) {
112    SparseLinExpr<V> tmp(a);
113    tmp+=b; ///\todo Don't STL have some special 'merge' algorithm?
114    return tmp;
115  }
116 
117  ///\e
118 
119  ///\relates SparseLinExpr
120  ///
121  template <class V>
122  SparseLinExpr<V> operator-(const SparseLinExpr<V> &a,
123                                const SparseLinExpr<V> &b) {
124    SparseLinExpr<V> tmp(a);
125    tmp-=b; ///\todo Don't STL have some special 'merge' algorithm?
126    return tmp;
127  }
128 
129  ///\e
130 
131  ///\relates SparseLinExpr
132  ///
133  template <class V>
134  SparseLinExpr<V> operator*(const typename V::ExprValue &c,
135                               const SparseLinExpr<V> &e) {
136    SparseLinExpr<V> tmp(e);
137    tmp*=c;
138    return tmp;
139  }
140 
141  ///\e
142 
143  ///\relates SparseLinExpr
144  ///
145  template <class V>
146  SparseLinExpr<V> operator*(const SparseLinExpr<V> &e,
147                               const typename V::ExprValue &c) {
148    SparseLinExpr<V> tmp(e);
149    tmp*=c;
150    return tmp;
151  }
152 
153 
154  ///\e
155 
156  ///\relates SparseLinExpr
157  ///
158  template <class V>
159  SparseLinExpr<V> operator/(const SparseLinExpr<V> &e,
160                               const typename V::ExprValue &c) {
161    SparseLinExpr<V> tmp(e);
162    tmp/=c;
163    return tmp;
164  }
165 
166  ///\e
167 
168  ///\relates SparseLinExpr
169  ///
170  template <class V>
171  SparseLinExpr<V> operator+(const typename V::ExprValue &c,
172                             const SparseLinExpr<V> &e) {
173    SparseLinExpr<V> tmp(e);
174    tmp.constComp()+=c;
175    return tmp;
176  }
177
178  ///\e
179 
180  ///\relates SparseLinExpr
181  ///
182  template <class V>
183  SparseLinExpr<V> operator+(const SparseLinExpr<V> &e,
184                             const typename V::ExprValue &c) {
185    SparseLinExpr<V> tmp(e);
186    tmp.constComp()+=c;
187    return tmp;
188  }
189
190  ///\e
191 
192  ///\relates SparseLinExpr
193  ///
194  template <class V>
195  SparseLinExpr<V> operator+(const V &v,const SparseLinExpr<V> &e) {
196    SparseLinExpr<V> tmp(e);
197    tmp[v]+=1;
198    return tmp;
199  }
200
201  ///\e
202 
203  ///\relates SparseLinExpr
204  ///
205  template <class V>
206  SparseLinExpr<V> operator+(const SparseLinExpr<V> &e,const V &v) {
207    SparseLinExpr<V> tmp(e);
208    tmp[v]+=1;
209    return tmp;
210  }
211
212  ///\e
213 
214  ///\relates SparseLinExpr
215  ///
216  template <class V>
217  SparseLinExpr<V> operator-(const typename V::ExprValue &c,
218                             const SparseLinExpr<V> &e) {
219    SparseLinExpr<V> tmp(e);
220    tmp*=-1;
221    tmp.constComp()+=c;
222    return tmp;
223  }
224
225  ///\e
226 
227  ///\relates SparseLinExpr
228  ///
229  template <class V>
230  SparseLinExpr<V> operator-(const SparseLinExpr<V> &e,
231                             const typename V::ExprValue &c) {
232    SparseLinExpr<V> tmp(e);
233    tmp.constComp()-=c;
234    return tmp;
235  }
236
237  ///\e
238 
239  ///\relates SparseLinExpr
240  ///
241  template <class V>
242  SparseLinExpr<V> operator-(const V &v,const SparseLinExpr<V> &e) {
243    SparseLinExpr<V> tmp(e);
244    tmp*=-1;
245    tmp[v]+=1;
246    return tmp;
247  }
248
249  ///\e
250 
251  ///\relates SparseLinExpr
252  ///
253  template <class V>
254  SparseLinExpr<V> operator-(const SparseLinExpr<V> &e,const V &v) {
255    SparseLinExpr<V> tmp(e);
256    tmp[v]-=1;
257    return tmp;
258  }
259
260  ///\e
261 
262  ///\relates SparseLinExpr
263  ///
264  template <class V>
265  SparseLinExpr<V> operator+(const V &v1,const V &v2) {
266    SparseLinExpr<V> tmp(v1);
267    tmp[v2]+=1;
268    return tmp;
269  }
270
271  ///\e
272 
273  ///\relates SparseLinExpr
274  ///
275  template <class V>
276  SparseLinExpr<V> operator*(const V &v,const typename V::ExprValue &c) {
277    SparseLinExpr<V> tmp;
278    tmp[v]=c;
279    return tmp;
280  }
281
282  ///\e
283 
284  ///\relates SparseLinExpr
285  ///
286  template <class V>
287  SparseLinExpr<V> operator*(const typename V::ExprValue &c,const V &v) {
288    SparseLinExpr<V> tmp;
289    tmp[v]=c;
290    return tmp;
291  }
292
293  ///\e
294 
295  ///\relates SparseLinExpr
296  ///
297  template <class V>
298  SparseLinExpr<V> operator/(const V &v,const typename V::ExprValue &c) {
299    SparseLinExpr<V> tmp;
300    tmp[v]=1/c;
301    return tmp;
302  }
303
304
305} //namespace lemon
306
307#endif //LEMON_LIN_EXPR_H
Note: See TracBrowser for help on using the repository browser.