One more thing to do...
2 #ifndef HUGO_LP_SOLVER_WRAPPER_H
3 #define HUGO_LP_SOLVER_WRAPPER
7 ///\brief Dijkstra algorithm.
22 //#include <sage_graph.h>
23 //#include <hugo/list_graph.h>
24 //#include <hugo/graph_wrapper.h>
25 #include <hugo/invalid.h>
26 //#include <bfs_dfs.h>
28 //#include <hugo/max_flow.h>
29 //#include <augmenting_flow.h>
30 //#include <iter_map.h>
42 /// \brief A partitioned vector with iterable classes.
44 /// This class implements a container in which the data is stored in an
45 /// stl vector, the range is partitioned into sets and each set is
46 /// doubly linked in a list.
47 /// That is, each class is iterable by hugo iterators, and any member of
48 /// the vector can bo moved to an other class.
50 class IterablePartition {
54 int prev; //invalid az -1
57 std::vector<Node> nodes;
62 std::vector<Tip> tips;
64 /// The classes are indexed by integers from \c 0 to \c classNum()-1.
65 int classNum() const { return tips.size(); }
66 /// This hugo style iterator iterates through a class.
68 /// Constructor. The number of classes is to be given which is fixed
69 /// over the life of the container.
70 /// The partition classes are indexed from 0 to class_num-1.
71 IterablePartition(int class_num) {
72 for (int i=0; i<class_num; ++i) {
79 void befuz(ClassIt it, int class_id) {
80 if (tips[class_id].first==-1) {
81 if (tips[class_id].last==-1) {
82 nodes[it.i].prev=nodes[it.i].next=-1;
83 tips[class_id].first=tips[class_id].last=it.i;
86 nodes[it.i].prev=tips[class_id].last;
88 nodes[tips[class_id].last].next=it.i;
89 tips[class_id].last=it.i;
92 void kifuz(ClassIt it, int class_id) {
93 if (tips[class_id].first==it.i) {
94 if (tips[class_id].last==it.i) {
95 tips[class_id].first=tips[class_id].last=-1;
97 tips[class_id].first=nodes[it.i].next;
98 nodes[nodes[it.i].next].prev=-1;
101 if (tips[class_id].last==it.i) {
102 tips[class_id].last=nodes[it.i].prev;
103 nodes[nodes[it.i].prev].next=-1;
105 nodes[nodes[it.i].next].prev=nodes[it.i].prev;
106 nodes[nodes[it.i].prev].next=nodes[it.i].next;
111 /// A new element with data \c t is pushed into the vector and into class
113 ClassIt push_back(const T& t, int class_id) {
117 int i=nodes.size()-1;
121 /// A member is moved to an other class.
122 void set(ClassIt it, int old_class_id, int new_class_id) {
123 kifuz(it.i, old_class_id);
124 befuz(it.i, new_class_id);
126 /// Returns the data pointed by \c it.
127 T& operator[](ClassIt it) { return nodes[it.i].data; }
128 /// Returns the data pointed by \c it.
129 const T& operator[](ClassIt it) const { return nodes[it.i].data; }
132 friend class IterablePartition;
136 /// Default constructor.
138 /// This constructor constructs an iterator which points
139 /// to the member of th container indexed by the integer _i.
140 ClassIt(const int& _i) : i(_i) { }
141 /// Invalid constructor.
142 ClassIt(const Invalid&) : i(-1) { }
144 /// First member of class \c class_id.
145 ClassIt& first(ClassIt& it, int class_id) const {
146 it.i=tips[class_id].first;
150 ClassIt& next(ClassIt& it) const {
151 it.i=nodes[it.i].next;
154 /// True iff the iterator is valid.
155 bool valid(const ClassIt& it) const { return it.i!=-1; }
158 /// \brief Wrappers for LP solvers
160 /// This class implements a hugo wrapper for glpk.
161 /// Later other LP-solvers will be wrapped into hugo.
162 /// The aim of this class is to give a general surface to different
163 /// solvers, i.e. it makes possible to write algorithms using LP's,
164 /// in which the solver can be changed to an other one easily.
165 class LPSolverWrapper {
173 // Row(const Invalid&) : i(0) { }
174 // Row(const int& _i) : i(_i) { }
175 // operator int() const { return i; }
177 // class RowIt : public Row {
179 // RowIt(const Row& row) : Row(row) { }
187 // Col(const Invalid&) : i(0) { }
188 // Col(const int& _i) : i(_i) { }
189 // operator int() const { return i; }
191 // class ColIt : public Col {
192 // ColIt(const Col& col) : Col(col) { }
199 typedef IterablePartition<int>::ClassIt RowIt;
201 IterablePartition<int> row_iter_map;
203 typedef IterablePartition<int>::ClassIt ColIt;
205 IterablePartition<int> col_iter_map;
206 //std::vector<int> row_id_to_lp_row_id;
207 //std::vector<int> col_id_to_lp_col_id;
211 const int INVALID_ID;
215 LPSolverWrapper() : lp(lpx_create_prob()),
218 //row_id_to_lp_row_id(), col_id_to_lp_col_id(),
219 VALID_ID(0), INVALID_ID(1) {
220 lpx_set_int_parm(lp, LPX_K_DUAL, 1);
228 lpx_set_obj_dir(lp, LPX_MIN);
232 lpx_set_obj_dir(lp, LPX_MAX);
236 int i=lpx_add_cols(lp, 1);
238 col_iter_map.first(col_it, INVALID_ID);
239 if (col_iter_map.valid(col_it)) { //van hasznalhato hely
240 col_iter_map.set(col_it, INVALID_ID, VALID_ID);
241 col_iter_map[col_it]=i;
242 //col_id_to_lp_col_id[col_iter_map[col_it]]=i;
243 } else { //a cucc vegere kell inzertalni mert nincs szabad hely
244 //col_id_to_lp_col_id.push_back(i);
245 //int j=col_id_to_lp_col_id.size()-1;
246 col_it=col_iter_map.push_back(i, VALID_ID);
248 // edge_index_map.set(e, i);
249 // lpx_set_col_bnds(lp, i, LPX_DB, 0.0, 1.0);
250 // lpx_set_obj_coef(lp, i, cost[e]);
255 int i=lpx_add_rows(lp, 1);
257 row_iter_map.first(row_it, INVALID_ID);
258 if (row_iter_map.valid(row_it)) { //van hasznalhato hely
259 row_iter_map.set(row_it, INVALID_ID, VALID_ID);
260 row_iter_map[row_it]=i;
261 } else { //a cucc vegere kell inzertalni mert nincs szabad hely
262 row_it=row_iter_map.push_back(i, VALID_ID);
266 //pair<RowIt, double>-bol kell megadni egy std range-et
268 template <typename Begin, typename End>
269 void setColCoeffs(const ColIt& col_it,
270 Begin begin, End end) {
271 int mem_length=1+lpx_get_num_rows(lp);
272 int* indices = new int[mem_length];
273 double* doubles = new double[mem_length];
275 for ( ; begin!=end; ++begin) {
277 indices[length]=row_iter_map[begin->first];
278 doubles[length]=begin->second;
280 lpx_set_mat_col(lp, col_iter_map[col_it], length, indices, doubles);
284 //pair<ColIt, double>-bol kell megadni egy std range-et
286 template <typename Begin, typename End>
287 void setRowCoeffs(const RowIt& row_it,
288 Begin begin, End end) {
289 int mem_length=1+lpx_get_num_cols(lp);
290 int* indices = new int[mem_length];
291 double* doubles = new double[mem_length];
293 for ( ; begin!=end; ++begin) {
295 indices[length]=col_iter_map[begin->first];
296 doubles[length]=begin->second;
298 lpx_set_mat_row(lp, row_iter_map[row_it], length, indices, doubles);
303 void eraseCol(const ColIt& col_it) {
304 col_iter_map.set(col_it, VALID_ID, INVALID_ID);
306 cols[1]=col_iter_map[col_it];
307 lpx_del_cols(lp, 1, cols);
308 col_iter_map[col_it]=0; //glpk specifikus
310 for (col_iter_map.first(it, VALID_ID);
311 col_iter_map.valid(it); col_iter_map.next(it)) {
312 if (col_iter_map[it]>cols[1]) --col_iter_map[it];
316 void eraseRow(const RowIt& row_it) {
317 row_iter_map.set(row_it, VALID_ID, INVALID_ID);
319 rows[1]=row_iter_map[row_it];
320 lpx_del_rows(lp, 1, rows);
321 row_iter_map[row_it]=0; //glpk specifikus
323 for (row_iter_map.first(it, VALID_ID);
324 row_iter_map.valid(it); row_iter_map.next(it)) {
325 if (row_iter_map[it]>rows[1]) --row_iter_map[it];
329 void setColBounds(const ColIt& col_it, int bound_type,
330 double lo, double up) {
331 lpx_set_col_bnds(lp, col_iter_map[col_it], bound_type, lo, up);
334 double getObjCoef(const ColIt& col_it) {
335 return lpx_get_obj_coef(lp, col_iter_map[col_it]);
338 void setRowBounds(const RowIt& row_it, int bound_type,
339 double lo, double up) {
340 lpx_set_row_bnds(lp, row_iter_map[row_it], bound_type, lo, up);
342 // void setObjCoef(const RowIt& row_it, double obj_coef) {
343 // lpx_set_obj_coef(lp, row_iter_map[row_it], obj_coef);
346 void solveSimplex() { lpx_simplex(lp); }
348 void solvePrimalSimplex() { lpx_simplex(lp); }
350 void solveDualSimplex() { lpx_simplex(lp); }
352 double getPrimal(const ColIt& col_it) {
353 return lpx_get_col_prim(lp, col_iter_map[col_it]);
356 double getObjVal() { return lpx_get_obj_val(lp); }
358 int rowNum() const { return lpx_get_num_rows(lp); }
360 int colNum() const { return lpx_get_num_cols(lp); }
362 int warmUp() { return lpx_warm_up(lp); }
364 void printWarmUpStatus(int i) {
366 case LPX_E_OK: cout << "LPX_E_OK" << endl; break;
367 case LPX_E_EMPTY: cout << "LPX_E_EMPTY" << endl; break;
368 case LPX_E_BADB: cout << "LPX_E_BADB" << endl; break;
369 case LPX_E_SING: cout << "LPX_E_SING" << endl; break;
373 int getPrimalStatus() { return lpx_get_prim_stat(lp); }
375 void printPrimalStatus(int i) {
377 case LPX_P_UNDEF: cout << "LPX_P_UNDEF" << endl; break;
378 case LPX_P_FEAS: cout << "LPX_P_FEAS" << endl; break;
379 case LPX_P_INFEAS: cout << "LPX_P_INFEAS" << endl; break;
380 case LPX_P_NOFEAS: cout << "LPX_P_NOFEAS" << endl; break;
384 int getDualStatus() { return lpx_get_dual_stat(lp); }
386 void printDualStatus(int i) {
388 case LPX_D_UNDEF: cout << "LPX_D_UNDEF" << endl; break;
389 case LPX_D_FEAS: cout << "LPX_D_FEAS" << endl; break;
390 case LPX_D_INFEAS: cout << "LPX_D_INFEAS" << endl; break;
391 case LPX_D_NOFEAS: cout << "LPX_D_NOFEAS" << endl; break;
394 /// Returns the status of the slack variable assigned to row \c row_it.
395 int getRowStat(const RowIt& row_it) {
396 return lpx_get_row_stat(lp, row_iter_map[row_it]);
399 void printRowStatus(int i) {
401 case LPX_BS: cout << "LPX_BS" << endl; break;
402 case LPX_NL: cout << "LPX_NL" << endl; break;
403 case LPX_NU: cout << "LPX_NU" << endl; break;
404 case LPX_NF: cout << "LPX_NF" << endl; break;
405 case LPX_NS: cout << "LPX_NS" << endl; break;
408 /// Returns the status of the variable assigned to column \c col_it.
409 int getColStat(const ColIt& col_it) {
410 return lpx_get_col_stat(lp, col_iter_map[col_it]);
413 void printColStatus(int i) {
415 case LPX_BS: cout << "LPX_BS" << endl; break;
416 case LPX_NL: cout << "LPX_NL" << endl; break;
417 case LPX_NU: cout << "LPX_NU" << endl; break;
418 case LPX_NF: cout << "LPX_NF" << endl; break;
419 case LPX_NS: cout << "LPX_NS" << endl; break;
428 #endif //HUGO_LP_SOLVER_WRAPPER_H