16 |
16 |
17 #ifndef LEMON_LP_BASE_H |
17 #ifndef LEMON_LP_BASE_H |
18 #define LEMON_LP_BASE_H |
18 #define LEMON_LP_BASE_H |
19 |
19 |
20 #include<vector> |
20 #include<vector> |
21 |
21 #include<limits> |
|
22 |
|
23 #include<lemon/utility.h> |
22 #include<lemon/error.h> |
24 #include<lemon/error.h> |
|
25 #include<lemon/invalid.h> |
23 |
26 |
24 #include"lin_expr.h" |
27 #include"lin_expr.h" |
25 ///\file |
28 ///\file |
26 ///\brief The interface of the LP solver interface. |
29 ///\brief The interface of the LP solver interface. |
27 namespace lemon { |
30 namespace lemon { |
94 ///Common base class for LP solvers |
98 ///Common base class for LP solvers |
95 class LpSolverBase { |
99 class LpSolverBase { |
96 |
100 |
97 public: |
101 public: |
98 |
102 |
99 /// \e |
103 ///The floating point type used by the solver |
100 typedef double Value; |
104 typedef double Value; |
101 /// \e |
105 ///The infinity constant |
102 static const Value INF; |
106 static const Value INF; |
103 |
107 |
104 ///\e |
108 ///Refer to a column of the LP. |
105 class Col { protected: int id; friend class LpSolverBase; }; |
109 |
106 ///\e |
110 ///This type is used to refer to a column of the LP. |
107 class Row { protected: int id; friend class LpSolverBase; }; |
111 /// |
|
112 ///Its value remains valid and correct even after the addition or erase of |
|
113 ///new column (unless the referred column itself was also deleted, |
|
114 ///of course). |
|
115 /// |
|
116 ///\todo Document what can one do with a Col (INVALID, comparing, |
|
117 ///it is similar to Node/Edge) |
|
118 class Col { |
|
119 protected: |
|
120 int id; |
|
121 friend class LpSolverBase; |
|
122 public: |
|
123 typedef True LpSolverCol; |
|
124 Col() {} |
|
125 Col(const Invalid&) : id(-1) {} |
|
126 bool operator<(Col c) const {return id<c.id;} |
|
127 bool operator==(Col c) const {return id==c.id;} |
|
128 bool operator!=(Col c) const {return id==c.id;} |
|
129 }; |
|
130 |
|
131 ///Refer to a row of the LP. |
|
132 |
|
133 ///This type is used to refer to a row of the LP. |
|
134 /// |
|
135 ///Its value remains valid and correct even after the addition or erase of |
|
136 ///new rows (unless the referred row itself was also deleted, of course). |
|
137 /// |
|
138 ///\todo Document what can one do with a Row (INVALID, comparing, |
|
139 ///it is similar to Node/Edge) |
|
140 class Row { |
|
141 protected: |
|
142 int id; |
|
143 friend class LpSolverBase; |
|
144 public: |
|
145 typedef True LpSolverRow; |
|
146 Row() {} |
|
147 Row(const Invalid&) : id(-1) {} |
|
148 typedef True LpSolverRow; |
|
149 bool operator<(Row c) const {return id<c.id;} |
|
150 bool operator==(Row c) const {return id==c.id;} |
|
151 bool operator!=(Row c) const {return id==c.id;} |
|
152 }; |
108 |
153 |
109 typedef SparseLinExpr<Col, Value> Expr; |
154 typedef SparseLinExpr<Col, Value> Expr; |
110 |
155 |
111 protected: |
156 protected: |
112 _FixId rows; |
157 _FixId rows; |
173 ///\e |
218 ///\e |
174 virtual ~LpSolverBase() {} |
219 virtual ~LpSolverBase() {} |
175 |
220 |
176 ///Add a new empty column (i.e a new variable) to the LP |
221 ///Add a new empty column (i.e a new variable) to the LP |
177 Col addCol() { Col c; c.id=cols.insert(_addCol()); return c;} |
222 Col addCol() { Col c; c.id=cols.insert(_addCol()); return c;} |
|
223 ///\brief Fill the elements of a container with newly created columns |
|
224 ///(i.e a new variables) |
|
225 /// |
|
226 ///This magic function takes container as its argument |
|
227 ///and fills its elements |
|
228 ///with new columns (i.e. variables) |
|
229 ///\param t can be either any standard STL iterable container with |
|
230 ///\ref Col \c values_type or \c mapped_type |
|
231 ///like <tt>std::vector<LpSolverBase::Col></tt>, |
|
232 /// <tt>std::list<LpSolverBase::Col></tt> or |
|
233 /// <tt>std::map<AnyType,LpSolverBase::Col></tt> or |
|
234 ///it can be an iterable lemon map like |
|
235 /// <tt>ListGraph::NodeMap<LpSolverBase::Col></tt>. |
|
236 ///\return The number of the created column. |
|
237 ///\bug Iterable nodemap hasn't been implemented yet. |
|
238 #ifdef DOXYGEN |
|
239 template<class T> |
|
240 int addColSet(T &t) { return 0;} |
|
241 #else |
|
242 template<class T> |
|
243 typename enable_if<typename T::value_type::LpSolverCol,int>::type |
|
244 addColSet(T &t,dummy<0> = 0) { |
|
245 int s=0; |
|
246 for(typename T::iterator i=t.begin();i!=t.end();++i) {*i=addCol();s++;} |
|
247 return s; |
|
248 } |
|
249 template<class T> |
|
250 typename enable_if<typename T::value_type::second_type::LpSolverCol, |
|
251 int>::type |
|
252 addColSet(T &t,dummy<1> = 1) { |
|
253 int s=0; |
|
254 for(typename T::iterator i=t.begin();i!=t.end();++i) { |
|
255 i->second=addCol(); |
|
256 s++; |
|
257 } |
|
258 return s; |
|
259 } |
|
260 #endif |
178 ///Add a new empty row (i.e a new constaint) to the LP |
261 ///Add a new empty row (i.e a new constaint) to the LP |
179 Row addRow() { Row r; r.id=rows.insert(_addRow()); return r;} |
262 Row addRow() { Row r; r.id=rows.insert(_addRow()); return r;} |
180 |
263 |
181 ///Add a new row (i.e a new constaint) to the LP |
264 ///Add a new row (i.e a new constaint) to the LP |
182 |
265 |
189 Row r=addRow(); |
272 Row r=addRow(); |
190 std::vector<int> indices; |
273 std::vector<int> indices; |
191 std::vector<Value> values; |
274 std::vector<Value> values; |
192 indices.push_back(0); |
275 indices.push_back(0); |
193 values.push_back(0); |
276 values.push_back(0); |
194 for(Expr::iterator i=e.begin(); i!=e.end(); ++i) { |
277 for(Expr::iterator i=e.begin(); i!=e.end(); ++i) |
195 indices.push_back(cols.floatingId((*i).first.id)); |
278 if((*i).second!=0) { ///\bug EPSILON would be necessary here!!! |
196 values.push_back((*i).second); |
279 indices.push_back(cols.floatingId((*i).first.id)); |
197 } |
280 values.push_back((*i).second); |
|
281 } |
198 _setRowCoeffs(rows.floatingId(r.id),indices.size()-1, |
282 _setRowCoeffs(rows.floatingId(r.id),indices.size()-1, |
199 &indices[0],&values[0]); |
283 &indices[0],&values[0]); |
200 _setRowLowerBound(rows.floatingId(r.id),l); |
284 _setRowLowerBound(rows.floatingId(r.id),l-e.constComp()); |
201 _setRowUpperBound(rows.floatingId(r.id),l); |
285 _setRowUpperBound(rows.floatingId(r.id),u-e.constComp()); |
202 return r; |
286 return r; |
203 } |
287 } |
204 |
288 |
205 /// Set the lower bound of a column (i.e a variable) |
289 /// Set the lower bound of a column (i.e a variable) |
206 |
290 |