25 ///\file |
25 ///\file |
26 ///\brief Classes to handle linear expressions |
26 ///\brief Classes to handle linear expressions |
27 namespace lemon { |
27 namespace lemon { |
28 |
28 |
29 /// Class to handle sparse linear expressions |
29 /// Class to handle sparse linear expressions |
30 template <class _V,class _C> |
30 template <class _V> |
31 class SparseLinExpr : public std::map<_V, _C> |
31 class SparseLinExpr : public std::map<_V, typename _V::ExprValue> |
32 { |
32 { |
33 public: |
33 public: |
34 typedef _V Var; |
34 typedef _V Var; |
35 typedef _C Coeff; |
35 typedef typename _V::ExprValue Coeff; |
36 |
36 |
37 protected: |
37 protected: |
38 typedef typename std::map<_V, _C> Base; |
38 typedef typename std::map<_V, typename _V::ExprValue> Base; |
39 |
39 |
40 Coeff const_comp; |
40 Coeff const_comp; |
41 public: |
41 public: |
42 SparseLinExpr() { } |
42 ///\e |
43 SparseLinExpr(const Var &v) : const_comp(v) { |
43 SparseLinExpr() : Base(), const_comp(0) { } |
|
44 ///\e |
|
45 SparseLinExpr(const Var &v) : const_comp(0) { |
44 Base::insert(std::make_pair(v, 1)); |
46 Base::insert(std::make_pair(v, 1)); |
45 } |
47 } |
|
48 ///\e |
46 SparseLinExpr(const Coeff &v) : const_comp(v) {} |
49 SparseLinExpr(const Coeff &v) : const_comp(v) {} |
47 |
50 |
|
51 ///\e |
48 void set(const Var &v,const Coeff &c) { |
52 void set(const Var &v,const Coeff &c) { |
49 return Base::insert(std::make_pair(v, c)); |
53 return Base::insert(std::make_pair(v, c)); |
50 } |
54 } |
51 // Coeff &operator[](const Var &v) { return data[v]; } |
55 // Coeff &operator[](const Var &v) { return data[v]; } |
52 // const Coeff &operator[](const Var &v) const { return data[v]; } |
56 // const Coeff &operator[](const Var &v) const { return data[v]; } |
53 |
57 |
|
58 ///\e |
54 Coeff &constComp() { return const_comp; } |
59 Coeff &constComp() { return const_comp; } |
|
60 ///\e |
55 const Coeff &constComp() const { return const_comp; } |
61 const Coeff &constComp() const { return const_comp; } |
56 |
62 |
57 ///Removes the components with zero coefficient. |
63 ///Removes the components with zero coefficient. |
58 void simplify() { |
64 void simplify() { |
59 for (typename Base::iterator i=Base::begin(); i!=Base::end();) { |
65 for (typename Base::iterator i=Base::begin(); i!=Base::end();) { |
62 if ((*i).second==0) Base::erase(i); |
68 if ((*i).second==0) Base::erase(i); |
63 j=i; |
69 j=i; |
64 } |
70 } |
65 } |
71 } |
66 |
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 |
67 }; |
103 }; |
68 |
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 |
69 } //namespace lemon |
305 } //namespace lemon |
70 |
306 |
71 #endif //LEMON_LIN_EXPR_H |
307 #endif //LEMON_LIN_EXPR_H |