marci@764: // -*- c++ -*-
alpar@921: #ifndef LEMON_LP_SOLVER_WRAPPER_H
marci@1015: #define LEMON_LP_SOLVER_WRAPPER_H
marci@764: 
alpar@765: ///\ingroup misc
alpar@765: ///\file
alpar@765: ///\brief Dijkstra algorithm.
alpar@765: 
marci@764: // #include <stdio.h>
marci@764: #include <stdlib.h>
marci@764: // #include <stdio>
marci@764: //#include <stdlib>
marci@1014: extern "C" {
marci@764: #include "glpk.h"
marci@1014: }
marci@764: 
marci@764: #include <iostream>
marci@764: #include <vector>
marci@764: #include <string>
marci@764: #include <list>
marci@764: #include <memory>
marci@764: #include <utility>
marci@764: 
marci@764: //#include <sage_graph.h>
alpar@921: //#include <lemon/list_graph.h>
alpar@921: //#include <lemon/graph_wrapper.h>
alpar@921: #include <lemon/invalid.h>
marci@764: //#include <bfs_dfs.h>
marci@764: //#include <stp.h>
alpar@921: //#include <lemon/max_flow.h>
marci@764: //#include <augmenting_flow.h>
marci@764: //#include <iter_map.h>
marci@764: 
marci@764: using std::cout;
marci@764: using std::cin;
marci@764: using std::endl;
marci@764: 
alpar@921: namespace lemon {
marci@764: 
alpar@765:   
alpar@765:   /// \addtogroup misc
alpar@765:   /// @{
alpar@765: 
marci@764:   /// \brief A partitioned vector with iterable classes.
marci@764:   ///
marci@764:   /// This class implements a container in which the data is stored in an 
marci@764:   /// stl vector, the range is partitioned into sets and each set is 
marci@764:   /// doubly linked in a list. 
alpar@921:   /// That is, each class is iterable by lemon iterators, and any member of 
marci@764:   /// the vector can bo moved to an other class.
marci@764:   template <typename T>
marci@764:   class IterablePartition {
marci@764:   protected:
marci@764:     struct Node {
marci@764:       T data;
marci@764:       int prev; //invalid az -1
marci@764:       int next; 
marci@764:     };
marci@764:     std::vector<Node> nodes;
marci@764:     struct Tip {
marci@764:       int first;
marci@764:       int last;
marci@764:     };
marci@764:     std::vector<Tip> tips;
marci@764:   public:
marci@764:     /// The classes are indexed by integers from \c 0 to \c classNum()-1.
marci@764:     int classNum() const { return tips.size(); }
alpar@921:     /// This lemon style iterator iterates through a class. 
marci@764:     class ClassIt;
marci@764:     /// Constructor. The number of classes is to be given which is fixed 
marci@764:     /// over the life of the container. 
marci@764:     /// The partition classes are indexed from 0 to class_num-1. 
marci@764:     IterablePartition(int class_num) { 
marci@764:       for (int i=0; i<class_num; ++i) {
marci@764: 	Tip t;
marci@764: 	t.first=t.last=-1;
marci@764: 	tips.push_back(t);
marci@764:       }
marci@764:     }
marci@764:   protected:
marci@764:     void befuz(ClassIt it, int class_id) {
marci@764:       if (tips[class_id].first==-1) {
marci@764: 	if (tips[class_id].last==-1) {
marci@764: 	  nodes[it.i].prev=nodes[it.i].next=-1;
marci@764: 	  tips[class_id].first=tips[class_id].last=it.i;
marci@764: 	}
marci@764:       } else {
marci@764: 	nodes[it.i].prev=tips[class_id].last;
marci@764: 	nodes[it.i].next=-1;
marci@764: 	nodes[tips[class_id].last].next=it.i;
marci@764: 	tips[class_id].last=it.i;
marci@764:       }
marci@764:     }
marci@764:     void kifuz(ClassIt it, int class_id) {
marci@764:       if (tips[class_id].first==it.i) {
marci@764: 	if (tips[class_id].last==it.i) {
marci@764: 	  tips[class_id].first=tips[class_id].last=-1;
marci@764: 	} else {
marci@764: 	  tips[class_id].first=nodes[it.i].next;
marci@764: 	  nodes[nodes[it.i].next].prev=-1;
marci@764: 	}
marci@764:       } else {
marci@764: 	if (tips[class_id].last==it.i) {
marci@764: 	  tips[class_id].last=nodes[it.i].prev;
marci@764: 	  nodes[nodes[it.i].prev].next=-1;
marci@764: 	} else {
marci@764: 	  nodes[nodes[it.i].next].prev=nodes[it.i].prev;
marci@764: 	  nodes[nodes[it.i].prev].next=nodes[it.i].next;
marci@764: 	}
marci@764:       }
marci@764:     }
marci@764:   public:
marci@764:     /// A new element with data \c t is pushed into the vector and into class 
marci@764:     /// \c class_id.
marci@764:     ClassIt push_back(const T& t, int class_id) { 
marci@764:       Node n;
marci@764:       n.data=t;
marci@764:       nodes.push_back(n);
marci@764:       int i=nodes.size()-1;
marci@764:       befuz(i, class_id);
marci@764:       return i;
marci@764:     }
marci@764:     /// A member is moved to an other class.
marci@764:     void set(ClassIt it, int old_class_id, int new_class_id) {
marci@764:       kifuz(it.i, old_class_id);
marci@764:       befuz(it.i, new_class_id);
marci@764:     }
marci@764:     /// Returns the data pointed by \c it.
marci@764:     T& operator[](ClassIt it) { return nodes[it.i].data; }
marci@764:     /// Returns the data pointed by \c it.
marci@764:     const T& operator[](ClassIt it) const { return nodes[it.i].data; }
alpar@765:     ///.
marci@764:     class ClassIt {
marci@764:       friend class IterablePartition;
marci@764:     protected:
marci@764:       int i;
marci@764:     public:
marci@764:       /// Default constructor.
marci@764:       ClassIt() { }
marci@764:       /// This constructor constructs an iterator which points
marci@764:       /// to the member of th container indexed by the integer _i.
marci@764:       ClassIt(const int& _i) : i(_i) { }
marci@764:       /// Invalid constructor.
marci@764:       ClassIt(const Invalid&) : i(-1) { }
marci@764:     };
marci@764:     /// First member of class \c class_id.
marci@764:     ClassIt& first(ClassIt& it, int class_id) const {
marci@764:       it.i=tips[class_id].first;
marci@764:       return it;
marci@764:     }
marci@764:     /// Next member.
marci@764:     ClassIt& next(ClassIt& it) const {
marci@764:       it.i=nodes[it.i].next;
marci@764:       return it;
marci@764:     }
marci@764:     /// True iff the iterator is valid.
marci@764:     bool valid(const ClassIt& it) const { return it.i!=-1; }
marci@764:   };
marci@764:   
marci@764:   /// \brief Wrappers for LP solvers
marci@764:   /// 
alpar@921:   /// This class implements a lemon wrapper for glpk.
alpar@921:   /// Later other LP-solvers will be wrapped into lemon.
marci@764:   /// The aim of this class is to give a general surface to different 
marci@764:   /// solvers, i.e. it makes possible to write algorithms using LP's, 
marci@764:   /// in which the solver can be changed to an other one easily.
marci@764:   class LPSolverWrapper {
marci@764:   public:
marci@764: 
marci@764: //   class Row {
marci@764: //   protected:
marci@764: //     int i;
marci@764: //   public:
marci@764: //     Row() { }
marci@764: //     Row(const Invalid&) : i(0) { }
marci@764: //     Row(const int& _i) : i(_i) { }
marci@764: //     operator int() const { return i; }
marci@764: //   };
marci@764: //   class RowIt : public Row {
marci@764: //   public:
marci@764: //     RowIt(const Row& row) : Row(row) { }
marci@764: //   };
marci@764: 
marci@764: //   class Col {
marci@764: //   protected:
marci@764: //     int i;
marci@764: //   public:
marci@764: //     Col() { }
marci@764: //     Col(const Invalid&) : i(0) { }
marci@764: //     Col(const int& _i) : i(_i) { }
marci@764: //     operator int() const { return i; }
marci@764: //   };
marci@764: //   class ColIt : public Col {
marci@764: //     ColIt(const Col& col) : Col(col) { }
marci@764: //   };
marci@764: 
marci@764:   public:
alpar@765:     ///.
marci@764:     LPX* lp;
alpar@765:     ///.
marci@764:     typedef IterablePartition<int>::ClassIt RowIt;
alpar@765:     ///.
marci@764:     IterablePartition<int> row_iter_map;
alpar@765:     ///.
marci@764:     typedef IterablePartition<int>::ClassIt ColIt;
alpar@765:     ///.
marci@764:     IterablePartition<int> col_iter_map;
marci@764:     //std::vector<int> row_id_to_lp_row_id;
marci@764:     //std::vector<int> col_id_to_lp_col_id;
alpar@765:     ///.
marci@764:     const int VALID_ID;
alpar@765:     ///.
marci@764:     const int INVALID_ID;
marci@764: 
marci@764:   public:
alpar@765:     ///.
marci@764:     LPSolverWrapper() : lp(lpx_create_prob()), 
marci@764: 			row_iter_map(2), 
marci@764: 			col_iter_map(2), 
marci@764: 			//row_id_to_lp_row_id(), col_id_to_lp_col_id(), 
marci@764: 			VALID_ID(0), INVALID_ID(1) {
marci@764:       lpx_set_int_parm(lp, LPX_K_DUAL, 1);
marci@764:     }
alpar@765:     ///.
marci@764:     ~LPSolverWrapper() {
marci@764:       lpx_delete_prob(lp);
marci@764:     }
alpar@765:     ///.
marci@764:     void setMinimize() { 
marci@764:       lpx_set_obj_dir(lp, LPX_MIN);
marci@764:     }
alpar@765:     ///.
marci@764:     void setMaximize() { 
marci@764:       lpx_set_obj_dir(lp, LPX_MAX);
marci@764:     }
alpar@765:     ///.
marci@764:     ColIt addCol() {
marci@764:       int i=lpx_add_cols(lp, 1);  
marci@764:       ColIt col_it;
marci@764:       col_iter_map.first(col_it, INVALID_ID);
marci@764:       if (col_iter_map.valid(col_it)) { //van hasznalhato hely
marci@764: 	col_iter_map.set(col_it, INVALID_ID, VALID_ID);
marci@764: 	col_iter_map[col_it]=i;
marci@764: 	//col_id_to_lp_col_id[col_iter_map[col_it]]=i;
marci@764:       } else { //a cucc vegere kell inzertalni mert nincs szabad hely
marci@764: 	//col_id_to_lp_col_id.push_back(i);
marci@764: 	//int j=col_id_to_lp_col_id.size()-1;
marci@764: 	col_it=col_iter_map.push_back(i, VALID_ID);
marci@764:       }
marci@764: //    edge_index_map.set(e, i);
marci@764: //    lpx_set_col_bnds(lp, i, LPX_DB, 0.0, 1.0);
marci@764: //    lpx_set_obj_coef(lp, i, cost[e]);    
marci@764:       return col_it;
marci@764:     }
alpar@765:     ///.
marci@764:     RowIt addRow() {
marci@764:       int i=lpx_add_rows(lp, 1);  
marci@764:       RowIt row_it;
marci@764:       row_iter_map.first(row_it, INVALID_ID);
marci@764:       if (row_iter_map.valid(row_it)) { //van hasznalhato hely
marci@764: 	row_iter_map.set(row_it, INVALID_ID, VALID_ID);
marci@764: 	row_iter_map[row_it]=i;
marci@764:       } else { //a cucc vegere kell inzertalni mert nincs szabad hely
marci@764: 	row_it=row_iter_map.push_back(i, VALID_ID);
marci@764:       }
marci@764:       return row_it;
marci@764:     }
marci@764:     //pair<RowIt, double>-bol kell megadni egy std range-et
alpar@765:     ///.
marci@764:     template <typename Begin, typename End>
marci@764:     void setColCoeffs(const ColIt& col_it, 
marci@764: 		      Begin begin, End end) {
marci@764:       int mem_length=1+lpx_get_num_rows(lp);
marci@764:       int* indices = new int[mem_length];
marci@764:       double* doubles = new double[mem_length];
marci@764:       int length=0;
marci@764:       for ( ; begin!=end; ++begin) {
marci@764: 	++length;
marci@764: 	indices[length]=row_iter_map[begin->first];
marci@764: 	doubles[length]=begin->second;
marci@764:       }
marci@764:       lpx_set_mat_col(lp, col_iter_map[col_it], length, indices, doubles);
marci@764:       delete [] indices;
marci@764:       delete [] doubles;
marci@764:     }
marci@764:     //pair<ColIt, double>-bol kell megadni egy std range-et
alpar@765:     ///.
marci@764:     template <typename Begin, typename End>
marci@764:     void setRowCoeffs(const RowIt& row_it, 
marci@764: 		      Begin begin, End end) {
marci@764:       int mem_length=1+lpx_get_num_cols(lp);
marci@764:       int* indices = new int[mem_length];
marci@764:       double* doubles = new double[mem_length];
marci@764:       int length=0;
marci@764:       for ( ; begin!=end; ++begin) {
marci@764: 	++length;
marci@764: 	indices[length]=col_iter_map[begin->first];
marci@764: 	doubles[length]=begin->second;
marci@764:       }
marci@764:       lpx_set_mat_row(lp, row_iter_map[row_it], length, indices, doubles);
marci@764:       delete [] indices;
marci@764:       delete [] doubles;
marci@764:     }
alpar@765:     ///.
marci@764:     void eraseCol(const ColIt& col_it) {
marci@764:       col_iter_map.set(col_it, VALID_ID, INVALID_ID);
marci@764:       int cols[2];
marci@764:       cols[1]=col_iter_map[col_it];
marci@764:       lpx_del_cols(lp, 1, cols);
marci@764:       col_iter_map[col_it]=0; //glpk specifikus
marci@764:       ColIt it;
marci@764:       for (col_iter_map.first(it, VALID_ID); 
marci@764: 	   col_iter_map.valid(it); col_iter_map.next(it)) {
marci@764: 	if (col_iter_map[it]>cols[1]) --col_iter_map[it];
marci@764:       }
marci@764:     }
alpar@765:     ///.
marci@764:     void eraseRow(const RowIt& row_it) {
marci@764:       row_iter_map.set(row_it, VALID_ID, INVALID_ID);
marci@764:       int rows[2];
marci@764:       rows[1]=row_iter_map[row_it];
marci@764:       lpx_del_rows(lp, 1, rows);
marci@764:       row_iter_map[row_it]=0; //glpk specifikus
marci@764:       RowIt it;
marci@764:       for (row_iter_map.first(it, VALID_ID); 
marci@764: 	   row_iter_map.valid(it); row_iter_map.next(it)) {
marci@764: 	if (row_iter_map[it]>rows[1]) --row_iter_map[it];
marci@764:       }
marci@764:     }
alpar@765:     ///.
marci@764:     void setColBounds(const ColIt& col_it, int bound_type, 
marci@764: 		      double lo, double up) {
marci@764:       lpx_set_col_bnds(lp, col_iter_map[col_it], bound_type, lo, up);
marci@764:     }
alpar@765:     ///.
marci@768:     double getObjCoef(const ColIt& col_it) { 
marci@768:       return lpx_get_obj_coef(lp, col_iter_map[col_it]);
marci@764:     }
alpar@765:     ///.
marci@764:     void setRowBounds(const RowIt& row_it, int bound_type, 
marci@764: 		      double lo, double up) {
marci@764:       lpx_set_row_bnds(lp, row_iter_map[row_it], bound_type, lo, up);
marci@764:     }
marci@888:     ///.
marci@888:     void setObjCoef(const ColIt& col_it, double obj_coef) { 
marci@888:       lpx_set_obj_coef(lp, col_iter_map[col_it], obj_coef);
marci@888:     }
alpar@765:     ///.
marci@764:     void solveSimplex() { lpx_simplex(lp); }
alpar@765:     ///.
marci@764:     void solvePrimalSimplex() { lpx_simplex(lp); }
alpar@765:     ///.
marci@764:     void solveDualSimplex() { lpx_simplex(lp); }
alpar@765:     ///.
marci@764:     double getPrimal(const ColIt& col_it) {
marci@764:       return lpx_get_col_prim(lp, col_iter_map[col_it]);
marci@764:     }
alpar@765:     ///.
marci@764:     double getObjVal() { return lpx_get_obj_val(lp); }
alpar@765:     ///.
marci@764:     int rowNum() const { return lpx_get_num_rows(lp); }
alpar@765:     ///.
marci@764:     int colNum() const { return lpx_get_num_cols(lp); }
alpar@765:     ///.
marci@764:     int warmUp() { return lpx_warm_up(lp); }
alpar@765:     ///.
marci@764:     void printWarmUpStatus(int i) {
marci@764:       switch (i) {
marci@764: 	case LPX_E_OK: cout << "LPX_E_OK" << endl; break;
marci@764: 	case LPX_E_EMPTY: cout << "LPX_E_EMPTY" << endl; break;	
marci@764: 	case LPX_E_BADB: cout << "LPX_E_BADB" << endl; break;
marci@764: 	case LPX_E_SING: cout << "LPX_E_SING" << endl; break;
marci@764:       }
marci@764:     }
alpar@765:     ///.
marci@764:     int getPrimalStatus() { return lpx_get_prim_stat(lp); }
alpar@765:     ///.
marci@764:     void printPrimalStatus(int i) {
marci@764:       switch (i) {
marci@764: 	case LPX_P_UNDEF: cout << "LPX_P_UNDEF" << endl; break;
marci@764: 	case LPX_P_FEAS: cout << "LPX_P_FEAS" << endl; break;	
marci@764: 	case LPX_P_INFEAS: cout << "LPX_P_INFEAS" << endl; break;
marci@764: 	case LPX_P_NOFEAS: cout << "LPX_P_NOFEAS" << endl; break;
marci@764:       }
marci@764:     }
alpar@765:     ///.
marci@764:     int getDualStatus() { return lpx_get_dual_stat(lp); }
alpar@765:     ///.
marci@764:     void printDualStatus(int i) {
marci@764:       switch (i) {
marci@764: 	case LPX_D_UNDEF: cout << "LPX_D_UNDEF" << endl; break;
marci@764: 	case LPX_D_FEAS: cout << "LPX_D_FEAS" << endl; break;	
marci@764: 	case LPX_D_INFEAS: cout << "LPX_D_INFEAS" << endl; break;
marci@764: 	case LPX_D_NOFEAS: cout << "LPX_D_NOFEAS" << endl; break;
marci@764:       }
marci@764:     }
marci@764:     /// Returns the status of the slack variable assigned to row \c row_it.
marci@764:     int getRowStat(const RowIt& row_it) { 
marci@764:       return lpx_get_row_stat(lp, row_iter_map[row_it]); 
marci@764:     }
alpar@765:     ///.
marci@764:     void printRowStatus(int i) {
marci@764:       switch (i) {
marci@764: 	case LPX_BS: cout << "LPX_BS" << endl; break;
marci@764: 	case LPX_NL: cout << "LPX_NL" << endl; break;	
marci@764: 	case LPX_NU: cout << "LPX_NU" << endl; break;
marci@764: 	case LPX_NF: cout << "LPX_NF" << endl; break;
marci@764: 	case LPX_NS: cout << "LPX_NS" << endl; break;
marci@764:       }
marci@764:     }
marci@764:     /// Returns the status of the variable assigned to column \c col_it.
marci@764:     int getColStat(const ColIt& col_it) { 
marci@764:       return lpx_get_col_stat(lp, col_iter_map[col_it]); 
marci@764:     }
alpar@765:     ///.
marci@764:     void printColStatus(int i) {
marci@764:       switch (i) {
marci@764: 	case LPX_BS: cout << "LPX_BS" << endl; break;
marci@764: 	case LPX_NL: cout << "LPX_NL" << endl; break;	
marci@764: 	case LPX_NU: cout << "LPX_NU" << endl; break;
marci@764: 	case LPX_NF: cout << "LPX_NF" << endl; break;
marci@764: 	case LPX_NS: cout << "LPX_NS" << endl; break;
marci@764:       }
marci@764:     }
marci@764:   };
alpar@765:   
alpar@765:   /// @}
marci@764: 
alpar@921: } //namespace lemon
marci@764: 
alpar@921: #endif //LEMON_LP_SOLVER_WRAPPER_H