124 ///Refer to a column of the LP. |
126 ///Refer to a column of the LP. |
125 |
127 |
126 ///This type is used to refer to a column of the LP. |
128 ///This type is used to refer to a column of the LP. |
127 /// |
129 /// |
128 ///Its value remains valid and correct even after the addition or erase of |
130 ///Its value remains valid and correct even after the addition or erase of |
129 ///new column (unless the referred column itself was also deleted, |
131 ///other columns. |
130 ///of course). |
|
131 /// |
132 /// |
132 ///\todo Document what can one do with a Col (INVALID, comparing, |
133 ///\todo Document what can one do with a Col (INVALID, comparing, |
133 ///it is similar to Node/Edge) |
134 ///it is similar to Node/Edge) |
134 class Col { |
135 class Col { |
135 protected: |
136 protected: |
148 ///Refer to a row of the LP. |
149 ///Refer to a row of the LP. |
149 |
150 |
150 ///This type is used to refer to a row of the LP. |
151 ///This type is used to refer to a row of the LP. |
151 /// |
152 /// |
152 ///Its value remains valid and correct even after the addition or erase of |
153 ///Its value remains valid and correct even after the addition or erase of |
153 ///new rows (unless the referred row itself was also deleted, of course). |
154 ///other rows. |
154 /// |
155 /// |
155 ///\todo Document what can one do with a Row (INVALID, comparing, |
156 ///\todo Document what can one do with a Row (INVALID, comparing, |
156 ///it is similar to Node/Edge) |
157 ///it is similar to Node/Edge) |
157 class Row { |
158 class Row { |
158 protected: |
159 protected: |
169 bool operator!=(Row c) const {return id==c.id;} |
170 bool operator!=(Row c) const {return id==c.id;} |
170 }; |
171 }; |
171 |
172 |
172 ///Linear expression |
173 ///Linear expression |
173 // typedef SparseLinExpr<Col> Expr; |
174 // typedef SparseLinExpr<Col> Expr; |
174 class Expr : public std::map<Col,Col::ExprValue> |
175 class Expr : public std::map<Col,Value> |
175 { |
176 { |
176 public: |
177 public: |
177 typedef Col Var; |
178 typedef LpSolverBase::Col Key; |
178 typedef Col::ExprValue Coeff; |
179 typedef LpSolverBase::Value Value; |
179 |
180 |
180 protected: |
181 protected: |
181 typedef std::map<Col,Col::ExprValue> Base; |
182 typedef std::map<Col,Value> Base; |
182 |
183 |
183 Coeff const_comp; |
184 Value const_comp; |
184 public: |
185 public: |
185 typedef True IsLinExpression; |
186 typedef True IsLinExpression; |
186 ///\e |
187 ///\e |
187 Expr() : Base(), const_comp(0) { } |
188 Expr() : Base(), const_comp(0) { } |
188 ///\e |
189 ///\e |
189 Expr(const Var &v) : const_comp(0) { |
190 Expr(const Key &v) : const_comp(0) { |
190 Base::insert(std::make_pair(v, 1)); |
191 Base::insert(std::make_pair(v, 1)); |
191 } |
192 } |
192 ///\e |
193 ///\e |
193 Expr(const Coeff &v) : const_comp(v) {} |
194 Expr(const Value &v) : const_comp(v) {} |
194 ///\e |
195 ///\e |
195 void set(const Var &v,const Coeff &c) { |
196 void set(const Key &v,const Value &c) { |
196 Base::insert(std::make_pair(v, c)); |
197 Base::insert(std::make_pair(v, c)); |
197 } |
198 } |
198 ///\e |
199 ///\e |
199 Coeff &constComp() { return const_comp; } |
200 Value &constComp() { return const_comp; } |
200 ///\e |
201 ///\e |
201 const Coeff &constComp() const { return const_comp; } |
202 const Value &constComp() const { return const_comp; } |
202 |
203 |
203 ///Removes the components with zero coefficient. |
204 ///Removes the components with zero coefficient. |
204 void simplify() { |
205 void simplify() { |
205 for (Base::iterator i=Base::begin(); i!=Base::end();) { |
206 for (Base::iterator i=Base::begin(); i!=Base::end();) { |
206 Base::iterator j=i; |
207 Base::iterator j=i; |
207 ++j; |
208 ++j; |
208 if ((*i).second==0) Base::erase(i); |
209 if ((*i).second==0) Base::erase(i); |
209 j=i; |
210 j=i; |
210 } |
211 } |
211 } |
212 } |
212 |
213 |
|
214 ///Sets all coefficients and the constant component to 0. |
|
215 void clear() { |
|
216 Base::clear(); |
|
217 const_comp=0; |
|
218 } |
|
219 |
213 ///\e |
220 ///\e |
214 Expr &operator+=(const Expr &e) { |
221 Expr &operator+=(const Expr &e) { |
215 for (Base::const_iterator j=e.begin(); j!=e.end(); ++j) |
222 for (Base::const_iterator j=e.begin(); j!=e.end(); ++j) |
216 (*this)[j->first]+=j->second; |
223 (*this)[j->first]+=j->second; |
217 ///\todo it might be speeded up using "hints" |
224 ///\todo it might be speeded up using "hints" |
224 (*this)[j->first]-=j->second; |
231 (*this)[j->first]-=j->second; |
225 const_comp-=e.const_comp; |
232 const_comp-=e.const_comp; |
226 return *this; |
233 return *this; |
227 } |
234 } |
228 ///\e |
235 ///\e |
229 Expr &operator*=(const Coeff &c) { |
236 Expr &operator*=(const Value &c) { |
230 for (Base::iterator j=Base::begin(); j!=Base::end(); ++j) |
237 for (Base::iterator j=Base::begin(); j!=Base::end(); ++j) |
231 j->second*=c; |
238 j->second*=c; |
232 const_comp*=c; |
239 const_comp*=c; |
233 return *this; |
240 return *this; |
234 } |
241 } |
235 ///\e |
242 ///\e |
236 Expr &operator/=(const Coeff &c) { |
243 Expr &operator/=(const Value &c) { |
237 for (Base::iterator j=Base::begin(); j!=Base::end(); ++j) |
244 for (Base::iterator j=Base::begin(); j!=Base::end(); ++j) |
238 j->second/=c; |
245 j->second/=c; |
239 const_comp/=c; |
246 const_comp/=c; |
240 return *this; |
247 return *this; |
241 } |
248 } |
245 //typedef LinConstr<Expr> Constr; |
252 //typedef LinConstr<Expr> Constr; |
246 class Constr |
253 class Constr |
247 { |
254 { |
248 public: |
255 public: |
249 typedef LpSolverBase::Expr Expr; |
256 typedef LpSolverBase::Expr Expr; |
250 typedef Expr::Var Var; |
257 typedef Expr::Key Key; |
251 typedef Expr::Coeff Coeff; |
258 typedef Expr::Value Value; |
252 |
259 |
253 static const Coeff INF; |
260 static const Value INF; |
254 static const Coeff NaN; |
261 static const Value NaN; |
255 // static const Coeff INF=0; |
262 // static const Value INF=0; |
256 // static const Coeff NaN=1; |
263 // static const Value NaN=1; |
257 |
264 |
258 Expr expr; |
265 protected: |
259 Coeff lb,ub; |
266 Expr _expr; |
260 |
267 Value _lb,_ub; |
261 Constr() : expr(), lb(NaN), ub(NaN) {} |
268 public: |
262 Constr(Coeff _lb,const Expr &e,Coeff _ub) : |
269 ///\e |
263 expr(e), lb(_lb), ub(_ub) {} |
270 Constr() : _expr(), _lb(NaN), _ub(NaN) {} |
264 Constr(const Expr &e,Coeff _ub) : |
271 ///\e |
265 expr(e), lb(NaN), ub(_ub) {} |
272 Constr(Value lb,const Expr &e,Value ub) : |
266 Constr(Coeff _lb,const Expr &e) : |
273 _expr(e), _lb(lb), _ub(ub) {} |
267 expr(e), lb(_lb), ub(NaN) {} |
274 ///\e |
|
275 Constr(const Expr &e,Value ub) : |
|
276 _expr(e), _lb(NaN), _ub(ub) {} |
|
277 ///\e |
|
278 Constr(Value lb,const Expr &e) : |
|
279 _expr(e), _lb(lb), _ub(NaN) {} |
|
280 ///\e |
268 Constr(const Expr &e) : |
281 Constr(const Expr &e) : |
269 expr(e), lb(NaN), ub(NaN) {} |
282 _expr(e), _lb(NaN), _ub(NaN) {} |
|
283 ///\e |
|
284 void clear() |
|
285 { |
|
286 _expr.clear(); |
|
287 _lb=_ub=NaN; |
|
288 } |
|
289 ///\e |
|
290 Expr &expr() { return _expr; } |
|
291 ///\e |
|
292 const Expr &expr() const { return _expr; } |
|
293 ///\e |
|
294 Value &lowerBound() { return _lb; } |
|
295 ///\e |
|
296 const Value &lowerBound() const { return _lb; } |
|
297 ///\e |
|
298 Value &upperBound() { return _ub; } |
|
299 ///\e |
|
300 const Value &upperBound() const { return _ub; } |
270 }; |
301 }; |
271 |
302 |
272 |
303 |
273 protected: |
304 protected: |
274 _FixId rows; |
305 _FixId rows; |
352 Col addCol() { Col c; c.id=cols.insert(_addCol()); return c;} |
383 Col addCol() { Col c; c.id=cols.insert(_addCol()); return c;} |
353 |
384 |
354 ///\brief Fill the elements of a container with newly created columns |
385 ///\brief Fill the elements of a container with newly created columns |
355 ///(i.e a new variables) |
386 ///(i.e a new variables) |
356 /// |
387 /// |
357 ///This magic function takes container as its argument |
388 ///This magic function takes a container as its argument |
358 ///and fills its elements |
389 ///and fills its elements |
359 ///with new columns (i.e. variables) |
390 ///with new columns (i.e. variables) |
360 ///\param t can be either any standard STL iterable container with |
391 ///\param t can be |
361 ///\ref Col \c values_type or \c mapped_type |
392 ///- a standard STL compatible iterable container with |
362 ///like <tt>std::vector<LpSolverBase::Col></tt>, |
393 ///\ref Col as its \c values_type |
363 /// <tt>std::list<LpSolverBase::Col></tt> or |
394 ///like |
364 /// <tt>std::map<AnyType,LpSolverBase::Col></tt> or |
395 ///\code |
365 ///it can be an iterable lemon map like |
396 ///std::vector<LpSolverBase::Col> |
366 /// <tt>ListGraph::NodeMap<LpSolverBase::Col></tt>. |
397 ///std::list<LpSolverBase::Col> |
|
398 ///\endcode |
|
399 ///- a standard STL compatible iterable container with |
|
400 ///\ref Col as its \c mapped_type |
|
401 ///like |
|
402 ///\code |
|
403 ///std::map<AnyType,LpSolverBase::Col> |
|
404 ///\endcode |
|
405 ///- an iterable lemon \ref concept::WriteMap "write map" like |
|
406 ///\code |
|
407 ///ListGraph::NodeMap<LpSolverBase::Col> |
|
408 ///ListGraph::EdgeMap<LpSolverBase::Col> |
|
409 ///\endcode |
367 ///\return The number of the created column. |
410 ///\return The number of the created column. |
368 ///\bug Iterable nodemap hasn't been implemented yet. |
411 ///\bug Iterable nodemap hasn't been implemented yet. |
369 #ifdef DOXYGEN |
412 #ifdef DOXYGEN |
370 template<class T> |
413 template<class T> |
371 int addColSet(T &t) { return 0;} |
414 int addColSet(T &t) { return 0;} |
438 ///Set a row (i.e a constaint) of the LP |
481 ///Set a row (i.e a constaint) of the LP |
439 |
482 |
440 ///\param r is the row to be modified |
483 ///\param r is the row to be modified |
441 ///\param c is a linear expression (see \ref Constr) |
484 ///\param c is a linear expression (see \ref Constr) |
442 void setRow(Row r, const Constr &c) { |
485 void setRow(Row r, const Constr &c) { |
443 Value lb= c.lb==NaN?-INF:lb; |
486 setRow(r, |
444 Value ub= c.ub==NaN?INF:lb; |
487 isnan(c.lowerBound())?-INF:c.lowerBound(), |
445 setRow(r,lb,c.expr,ub); |
488 c.expr(), |
|
489 isnan(c.upperBound())?INF:c.upperBound()); |
446 } |
490 } |
447 |
491 |
448 ///Add a new row (i.e a new constaint) to the LP |
492 ///Add a new row (i.e a new constaint) to the LP |
449 |
493 |
450 ///\param l is the lower bound (-\ref INF means no bound) |
494 ///\param l is the lower bound (-\ref INF means no bound) |
561 ///\e |
605 ///\e |
562 |
606 |
563 ///\relates LpSolverBase::Expr |
607 ///\relates LpSolverBase::Expr |
564 /// |
608 /// |
565 inline LpSolverBase::Expr operator*(const LpSolverBase::Expr &a, |
609 inline LpSolverBase::Expr operator*(const LpSolverBase::Expr &a, |
566 const LpSolverBase::Expr::Coeff &b) |
610 const LpSolverBase::Value &b) |
567 { |
611 { |
568 LpSolverBase::Expr tmp(a); |
612 LpSolverBase::Expr tmp(a); |
569 tmp*=b; ///\todo Don't STL have some special 'merge' algorithm? |
613 tmp*=b; ///\todo Don't STL have some special 'merge' algorithm? |
570 return tmp; |
614 return tmp; |
571 } |
615 } |
572 |
616 |
573 ///\e |
617 ///\e |
574 |
618 |
575 ///\relates LpSolverBase::Expr |
619 ///\relates LpSolverBase::Expr |
576 /// |
620 /// |
577 inline LpSolverBase::Expr operator*(const LpSolverBase::Expr::Coeff &a, |
621 inline LpSolverBase::Expr operator*(const LpSolverBase::Value &a, |
578 const LpSolverBase::Expr &b) |
622 const LpSolverBase::Expr &b) |
579 { |
623 { |
580 LpSolverBase::Expr tmp(b); |
624 LpSolverBase::Expr tmp(b); |
581 tmp*=a; ///\todo Don't STL have some special 'merge' algorithm? |
625 tmp*=a; ///\todo Don't STL have some special 'merge' algorithm? |
582 return tmp; |
626 return tmp; |
584 ///\e |
628 ///\e |
585 |
629 |
586 ///\relates LpSolverBase::Expr |
630 ///\relates LpSolverBase::Expr |
587 /// |
631 /// |
588 inline LpSolverBase::Expr operator/(const LpSolverBase::Expr &a, |
632 inline LpSolverBase::Expr operator/(const LpSolverBase::Expr &a, |
589 const LpSolverBase::Expr::Coeff &b) |
633 const LpSolverBase::Value &b) |
590 { |
634 { |
591 LpSolverBase::Expr tmp(a); |
635 LpSolverBase::Expr tmp(a); |
592 tmp/=b; ///\todo Don't STL have some special 'merge' algorithm? |
636 tmp/=b; ///\todo Don't STL have some special 'merge' algorithm? |
593 return tmp; |
637 return tmp; |
594 } |
638 } |
605 |
649 |
606 ///\e |
650 ///\e |
607 |
651 |
608 ///\relates LpSolverBase::Constr |
652 ///\relates LpSolverBase::Constr |
609 /// |
653 /// |
610 inline LpSolverBase::Constr operator<=(const LpSolverBase::Expr::Coeff &e, |
654 inline LpSolverBase::Constr operator<=(const LpSolverBase::Value &e, |
611 const LpSolverBase::Expr &f) |
655 const LpSolverBase::Expr &f) |
612 { |
656 { |
613 return LpSolverBase::Constr(e,f); |
657 return LpSolverBase::Constr(e,f); |
614 } |
658 } |
615 |
659 |
616 ///\e |
660 ///\e |
617 |
661 |
618 ///\relates LpSolverBase::Constr |
662 ///\relates LpSolverBase::Constr |
619 /// |
663 /// |
620 inline LpSolverBase::Constr operator<=(const LpSolverBase::Expr &e, |
664 inline LpSolverBase::Constr operator<=(const LpSolverBase::Expr &e, |
621 const LpSolverBase::Expr::Coeff &f) |
665 const LpSolverBase::Value &f) |
622 { |
666 { |
623 return LpSolverBase::Constr(e,f); |
667 return LpSolverBase::Constr(e,f); |
624 } |
668 } |
625 |
669 |
626 ///\e |
670 ///\e |
667 |
711 |
668 ///\e |
712 ///\e |
669 |
713 |
670 ///\relates LpSolverBase::Constr |
714 ///\relates LpSolverBase::Constr |
671 /// |
715 /// |
672 inline LpSolverBase::Constr operator<=(const LpSolverBase::Constr::Coeff &n, |
716 inline LpSolverBase::Constr operator<=(const LpSolverBase::Value &n, |
673 const LpSolverBase::Constr&c) |
717 const LpSolverBase::Constr&c) |
674 { |
718 { |
675 LpSolverBase::Constr tmp(c); |
719 LpSolverBase::Constr tmp(c); |
676 if(tmp.lb!=tmp.NaN) throw LogicError(); |
720 ///\todo Create an own exception type. |
677 else tmp.lb=n; |
721 if(!isnan(tmp.lowerBound())) throw LogicError(); |
|
722 else tmp.lowerBound()=n; |
678 return tmp; |
723 return tmp; |
679 } |
724 } |
680 ///\e |
725 ///\e |
681 |
726 |
682 ///\relates LpSolverBase::Constr |
727 ///\relates LpSolverBase::Constr |
683 /// |
728 /// |
684 inline LpSolverBase::Constr operator<=(const LpSolverBase::Constr& c, |
729 inline LpSolverBase::Constr operator<=(const LpSolverBase::Constr& c, |
685 const LpSolverBase::Constr::Coeff &n) |
730 const LpSolverBase::Value &n) |
686 { |
731 { |
687 LpSolverBase::Constr tmp(c); |
732 LpSolverBase::Constr tmp(c); |
688 if(tmp.ub!=tmp.NaN) throw LogicError(); |
733 ///\todo Create an own exception type. |
689 else tmp.ub=n; |
734 if(!isnan(tmp.upperBound())) throw LogicError(); |
690 return tmp; |
735 else tmp.upperBound()=n; |
691 } |
736 return tmp; |
692 |
737 } |
693 ///\e |
738 |
694 |
739 ///\e |
695 ///\relates LpSolverBase::Constr |
740 |
696 /// |
741 ///\relates LpSolverBase::Constr |
697 inline LpSolverBase::Constr operator>=(const LpSolverBase::Constr::Coeff &n, |
742 /// |
|
743 inline LpSolverBase::Constr operator>=(const LpSolverBase::Value &n, |
698 const LpSolverBase::Constr&c) |
744 const LpSolverBase::Constr&c) |
699 { |
745 { |
700 LpSolverBase::Constr tmp(c); |
746 LpSolverBase::Constr tmp(c); |
701 if(tmp.ub!=tmp.NaN) throw LogicError(); |
747 ///\todo Create an own exception type. |
702 else tmp.ub=n; |
748 if(!isnan(tmp.upperBound())) throw LogicError(); |
|
749 else tmp.upperBound()=n; |
703 return tmp; |
750 return tmp; |
704 } |
751 } |
705 ///\e |
752 ///\e |
706 |
753 |
707 ///\relates LpSolverBase::Constr |
754 ///\relates LpSolverBase::Constr |
708 /// |
755 /// |
709 inline LpSolverBase::Constr operator>=(const LpSolverBase::Constr& c, |
756 inline LpSolverBase::Constr operator>=(const LpSolverBase::Constr& c, |
710 const LpSolverBase::Constr::Coeff &n) |
757 const LpSolverBase::Value &n) |
711 { |
758 { |
712 LpSolverBase::Constr tmp(c); |
759 LpSolverBase::Constr tmp(c); |
713 if(tmp.lb!=tmp.NaN) throw LogicError(); |
760 ///\todo Create an own exception type. |
714 else tmp.lb=n; |
761 if(!isnan(tmp.lowerBound())) throw LogicError(); |
|
762 else tmp.lowerBound()=n; |
715 return tmp; |
763 return tmp; |
716 } |
764 } |
717 |
765 |
718 |
766 |
719 } //namespace lemon |
767 } //namespace lemon |