# HG changeset patch
# User athos
# Date 1111764180 0
# Node ID d8491fce67515037da41497a92a0c24ad7ca9fcd
# Parent  11a09f1319b372d432f9ded505f9289d9b3ae0c9


diff -r 11a09f1319b3 -r d8491fce6751 src/work/athos/lp/lp_solver_glpk.cc
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/src/work/athos/lp/lp_solver_glpk.cc	Fri Mar 25 15:23:00 2005 +0000
@@ -0,0 +1,28 @@
+// -*- c++ -*-
+#ifndef LEMON_LP_SOLVER_GLPK_CC
+#define LEMON_LP_SOLVER_GLPK_CC
+    //LOW LEVEL INTERFACE, MATRIX MANIPULATING FUNCTIONS
+extern "C" {
+#include "glpk.h"
+}
+#include "lp_solver_glpk.h"
+
+namespace lemon {
+
+
+    /// \e
+    int LpGlpk::_addCol() { 
+      int i=lpx_add_cols(lp, 1);
+      _setColLowerBound(i, -INF);
+      _setColUpperBound(i, INF);
+      return i;
+    }
+    /// \e
+    int LpGlpk::_addRow() { 
+      int i=lpx_add_rows(lp, 1);
+      return i;
+    }
+
+} //namespace lemon
+
+#endif //LEMON_LP_SOLVER_GLPK_CC
diff -r 11a09f1319b3 -r d8491fce6751 src/work/athos/lp/lp_solver_glpk.h
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/src/work/athos/lp/lp_solver_glpk.h	Fri Mar 25 15:23:00 2005 +0000
@@ -0,0 +1,565 @@
+// -*- c++ -*-
+#ifndef LEMON_LP_SOLVER_GLPK_H
+#define LEMON_LP_SOLVER_GLPK_H
+
+///\ingroup misc
+///\file
+
+extern "C" {
+#include "glpk.h"
+}
+#include <lp_solver_base.h>
+
+namespace lemon {
+  
+  
+  template <typename Value>
+  const Value LpSolverBase<Value>::INF=std::numeric_limits<Value>::infinity();
+
+
+  /// \brief Wrapper for GLPK solver
+  /// 
+  /// This class implements a lemon wrapper for GLPK.
+  class LpGlpk : public LpSolverBase<double> {
+
+  public:
+
+    typedef LpSolverBase<double> Parent;
+    
+    /// \e
+    LPX* lp;
+
+    /// \e
+    LpGlpk() : Parent(), 
+			lp(lpx_create_prob()) {
+      //int_row_map.push_back(Row());
+      //int_col_map.push_back(Col());
+      lpx_set_int_parm(lp, LPX_K_DUAL, 1);
+    }
+    /// \e
+    ~LpGlpk() {
+      lpx_delete_prob(lp);
+    }
+
+    //MATRIX INDEPEDENT MANIPULATING FUNCTIONS
+
+    /// \e
+    void setMinimize() { 
+      lpx_set_obj_dir(lp, LPX_MIN);
+    }
+    /// \e
+    void setMaximize() { 
+      lpx_set_obj_dir(lp, LPX_MAX);
+    }
+
+    /// \e
+    /// Retrieve number of rows
+    int rowNum() const { return lpx_get_num_rows(lp); }
+    /// \e
+    /// Retrieve number of coloumns
+    int colNum() const { return lpx_get_num_cols(lp); }
+
+  protected:
+    /// \e
+    int LpGlpk::_addCol() { 
+      int i=lpx_add_cols(lp, 1);
+      _setColLowerBound(i, -INF);
+      _setColUpperBound(i, INF);
+      return i;
+    }
+    /// \e
+    int LpGlpk::_addRow() { 
+      int i=lpx_add_rows(lp, 1);
+      return i;
+    }
+    /// \e
+    virtual void _setRowCoeffs(int i, 
+			       const std::vector<std::pair<int, double> >& coeffs) {
+      int mem_length=1+colNum();
+      int* indices = new int[mem_length];
+      double* doubles = new double[mem_length];
+      int length=0;
+      for (std::vector<std::pair<int, double> >::
+	     const_iterator it=coeffs.begin(); it!=coeffs.end(); ++it) {
+	++length;
+	indices[length]=it->first;
+	doubles[length]=it->second;
+      }
+      lpx_set_mat_row(lp, i, length, indices, doubles);
+      delete [] indices;
+      delete [] doubles;
+    }
+    /// \e
+    virtual void _getRowCoeffs(int i, 
+			       std::vector<std::pair<int, double> >& coeffs) {
+      int mem_length=1+colNum();
+      int* indices = new int[mem_length];
+      double* doubles = new double[mem_length];
+      int length=lpx_get_mat_row(lp, i, indices, doubles);
+      for (int i=1; i<=length; ++i) {
+	coeffs.push_back(std::make_pair(indices[i], doubles[i]));
+      }
+      delete [] indices;
+      delete [] doubles;
+    }
+    /// \e
+    virtual void _setColCoeffs(int i, 
+			       const std::vector<std::pair<int, double> >& coeffs) {
+      int mem_length=1+rowNum();
+      int* indices = new int[mem_length];
+      double* doubles = new double[mem_length];
+      int length=0;
+      for (std::vector<std::pair<int, double> >::
+	     const_iterator it=coeffs.begin(); it!=coeffs.end(); ++it) {
+	++length;
+	indices[length]=it->first;
+	doubles[length]=it->second;
+      }
+      lpx_set_mat_col(lp, i, length, indices, doubles);
+      delete [] indices;
+      delete [] doubles;
+    }
+    /// \e
+    virtual void _getColCoeffs(int i, 
+			       std::vector<std::pair<int, double> >& coeffs) {
+      int mem_length=1+rowNum();
+      int* indices = new int[mem_length];
+      double* doubles = new double[mem_length];
+      int length=lpx_get_mat_col(lp, i, indices, doubles);
+      for (int i=1; i<=length; ++i) {
+	coeffs.push_back(std::make_pair(indices[i], doubles[i]));
+      }
+      delete [] indices;
+      delete [] doubles;
+    }
+    /// \e
+    virtual void _eraseCol(int i) {
+      int cols[2];
+      cols[1]=i;
+      lpx_del_cols(lp, 1, cols);
+    }
+    virtual void _eraseRow(int i) {
+      int rows[2];
+      rows[1]=i;
+      lpx_del_rows(lp, 1, rows);
+    }
+
+    void _setCoeff(int row, int col, double value) {
+      ///FIXME Of course this is not efficient at all, but GLPK knows not more.
+      /// First approach: get one row, apply changes and set it again
+
+      int mem_length=1+colNum();
+      int* indices = new int[mem_length];
+      double* doubles = new double[mem_length];
+
+
+      int length=lpx_get_mat_row(lp, i, indices, doubles);
+
+      //The following code does not suppose that the elements of the array indices are sorted
+      int i=1;
+      bool found=false;
+      while (i <= length && !found){
+	if (indices[i]=col){
+	  found = true;
+	  doubles[i]=value;
+	}
+	++i;
+      }
+      if (!found){
+	++length;
+	indices[length]=col;
+	doubles[length]=value;
+      }
+
+// This is a piece of code that assumes that the array 'indices' is sorted. 
+// Not ready, I suppose. 
+//       //We need another arrays to put the data back, anyway
+//       int* new_indices = new int[length+1];
+//       double* new_doubles = new double[length+1];
+//       int offset;
+
+//       int i=1;
+//       while (i <= length && indices[i]<col){
+// 	new_indiced[i]=indices[i];
+// 	new_doubles[i]=doubles[i];
+// 	++i;
+//       }
+//       if (i>length || indices[i]>col){
+// 	//Ha atugrottuk, vagy a vegen van
+// 	new_indices[i]=col;
+// 	new_doubles[i]=value;
+// 	offset = 1;
+//       }
+//       else{
+// 	//I.e.: indices[i]=col
+// 	new_doubles[i]=value;
+// 	offset = 0;
+// 	++i;
+//       }
+//       while (i <= length){
+// 	new_indices[i+offset]=indices[i];
+// 	new_values[i+offset]=values[i];
+//       }
+
+      lpx_set_mat_row(lp, row, length, indices, doubles);
+      delete [] indices;
+      delete [] doubles;
+
+//       lpx_set_mat_row(lp, row, length+offset, new_indices, new_doubles);
+//       delete [] new_indices;
+//       delete [] new_doubles;
+      
+
+    }
+    double _getCoeff(int col, int row) {
+      /// FIXME not yet implemented
+      return 0.0;
+    }
+    virtual void _setColLowerBound(int i, double lo) {
+      if (lo==INF) {
+	//FIXME error
+      }
+      int b=lpx_get_col_type(lp, i);
+      double up=lpx_get_col_ub(lp, i);	
+      if (lo==-INF) {
+	switch (b) {
+	case LPX_FR:
+	case LPX_LO:
+	  lpx_set_col_bnds(lp, i, LPX_FR, lo, up);
+	  break;
+	case LPX_UP:
+	  break;
+	case LPX_DB:
+	case LPX_FX:
+	  lpx_set_col_bnds(lp, i, LPX_UP, lo, up);
+	  break;
+	default: ;
+	  //FIXME error
+	}
+      } else {
+	switch (b) {
+	case LPX_FR:
+	case LPX_LO:
+	  lpx_set_col_bnds(lp, i, LPX_LO, lo, up);
+	  break;
+	case LPX_UP:	  
+	case LPX_DB:
+	case LPX_FX:
+	  if (lo==up) 
+	    lpx_set_col_bnds(lp, i, LPX_FX, lo, up);
+	  else 
+	    lpx_set_col_bnds(lp, i, LPX_DB, lo, up);
+	  break;
+	default: ;
+	  //FIXME error
+	}
+      }
+    }
+    virtual double _getColLowerBound(int i) {
+      int b=lpx_get_col_type(lp, i);
+      switch (b) {
+      case LPX_FR:
+	return -INF;
+      case LPX_LO:
+	return lpx_get_col_lb(lp, i);
+      case LPX_UP:
+	return -INF;
+      case LPX_DB:
+      case LPX_FX:
+	return lpx_get_col_lb(lp, i);
+      default: ;
+	//FIXME error
+	return 0.0;
+      }
+    }
+    virtual void _setColUpperBound(int i, double up) {
+      if (up==-INF) {
+	//FIXME error
+      }
+      int b=lpx_get_col_type(lp, i);
+      double lo=lpx_get_col_lb(lp, i);
+      if (up==INF) {
+	switch (b) {
+	case LPX_FR:
+	case LPX_LO:
+	  break;
+	case LPX_UP:
+	  lpx_set_col_bnds(lp, i, LPX_FR, lo, up);
+	  break;
+	case LPX_DB:
+	case LPX_FX:
+	  lpx_set_col_bnds(lp, i, LPX_LO, lo, up);
+	  break;
+	default: ;
+	  //FIXME error
+	}
+      } else {
+	switch (b) {
+	case LPX_FR:
+	  lpx_set_col_bnds(lp, i, LPX_UP, lo, up);
+	case LPX_LO:
+	  if (lo==up) 
+	    lpx_set_col_bnds(lp, i, LPX_FX, lo, up);
+	  else
+	    lpx_set_col_bnds(lp, i, LPX_DB, lo, up);
+	  break;
+	case LPX_UP:
+	  lpx_set_col_bnds(lp, i, LPX_UP, lo, up);
+	  break;
+	case LPX_DB:
+	case LPX_FX:
+	  if (lo==up) 
+	    lpx_set_col_bnds(lp, i, LPX_FX, lo, up);
+	  else 
+	    lpx_set_col_bnds(lp, i, LPX_DB, lo, up);
+	  break;
+	default: ;
+	  //FIXME error
+	}
+      }
+    }
+    virtual double _getColUpperBound(int i) {
+      int b=lpx_get_col_type(lp, i);
+      switch (b) {
+      case LPX_FR:
+      case LPX_LO:
+	return INF;
+      case LPX_UP:
+      case LPX_DB:
+      case LPX_FX:
+	return lpx_get_col_ub(lp, i);
+      default: ;
+	//FIXME error
+	return 0.0;
+      }
+    }
+    virtual void _setRowLowerBound(int i, double lo) {
+      if (lo==INF) {
+	//FIXME error
+      }
+      int b=lpx_get_row_type(lp, i);
+      double up=lpx_get_row_ub(lp, i);	
+      if (lo==-INF) {
+	switch (b) {
+	case LPX_FR:
+	case LPX_LO:
+	  lpx_set_row_bnds(lp, i, LPX_FR, lo, up);
+	  break;
+	case LPX_UP:
+	  break;
+	case LPX_DB:
+	case LPX_FX:
+	  lpx_set_row_bnds(lp, i, LPX_UP, lo, up);
+	  break;
+	default: ;
+	  //FIXME error
+	}
+      } else {
+	switch (b) {
+	case LPX_FR:
+	case LPX_LO:
+	  lpx_set_row_bnds(lp, i, LPX_LO, lo, up);
+	  break;
+	case LPX_UP:	  
+	case LPX_DB:
+	case LPX_FX:
+	  if (lo==up) 
+	    lpx_set_row_bnds(lp, i, LPX_FX, lo, up);
+	  else 
+	    lpx_set_row_bnds(lp, i, LPX_DB, lo, up);
+	  break;
+	default: ;
+	  //FIXME error
+	}
+      }
+    }
+    virtual double _getRowLowerBound(int i) {
+      int b=lpx_get_row_type(lp, i);
+      switch (b) {
+      case LPX_FR:
+	return -INF;
+      case LPX_LO:
+	return lpx_get_row_lb(lp, i);
+      case LPX_UP:
+	return -INF;
+      case LPX_DB:
+      case LPX_FX:
+	return lpx_get_row_lb(lp, i);
+      default: ;
+	//FIXME error
+	return 0.0;
+      }
+    }
+    virtual void _setRowUpperBound(int i, double up) {
+      if (up==-INF) {
+	//FIXME error
+      }
+      int b=lpx_get_row_type(lp, i);
+      double lo=lpx_get_row_lb(lp, i);
+      if (up==INF) {
+	switch (b) {
+	case LPX_FR:
+	case LPX_LO:
+	  break;
+	case LPX_UP:
+	  lpx_set_row_bnds(lp, i, LPX_FR, lo, up);
+	  break;
+	case LPX_DB:
+	case LPX_FX:
+	  lpx_set_row_bnds(lp, i, LPX_LO, lo, up);
+	  break;
+	default: ;
+	  //FIXME error
+	}
+      } else {
+	switch (b) {
+	case LPX_FR:
+	  lpx_set_row_bnds(lp, i, LPX_UP, lo, up);
+	case LPX_LO:
+	  if (lo==up) 
+	    lpx_set_row_bnds(lp, i, LPX_FX, lo, up);
+	  else
+	    lpx_set_row_bnds(lp, i, LPX_DB, lo, up);
+	  break;
+	case LPX_UP:
+	  lpx_set_row_bnds(lp, i, LPX_UP, lo, up);
+	  break;
+	case LPX_DB:
+	case LPX_FX:
+	  if (lo==up) 
+	    lpx_set_row_bnds(lp, i, LPX_FX, lo, up);
+	  else 
+	    lpx_set_row_bnds(lp, i, LPX_DB, lo, up);
+	  break;
+	default: ;
+	  //FIXME error
+	}
+      }
+    }
+    virtual double _getRowUpperBound(int i) {
+      int b=lpx_get_row_type(lp, i);
+      switch (b) {
+      case LPX_FR:
+      case LPX_LO:
+	return INF;
+      case LPX_UP:
+      case LPX_DB:
+      case LPX_FX:
+	return lpx_get_row_ub(lp, i);
+      default: ;
+	//FIXME error
+	return 0.0;
+      }
+    }
+    /// \e
+    virtual double _getObjCoeff(int i) { 
+      return lpx_get_obj_coef(lp, i);
+    }
+    /// \e
+    virtual void _setObjCoeff(int i, double obj_coef) { 
+      lpx_set_obj_coef(lp, i, obj_coef);
+    }
+
+  protected:
+    virtual double _getPrimal(int i) {
+      return lpx_get_col_prim(lp, i);
+    }
+
+    //MIP
+  protected:
+    /// \e
+    void _setColCont(int i) { lpx_set_col_kind(lp, i, LPX_CV); }
+    /// \e
+    void _setColInt(int i) { lpx_set_col_kind(lp, i, LPX_IV); }
+    /// \e
+    double _getMIPPrimal(int i) { return lpx_mip_col_val(lp, i); }
+
+
+//   public:
+//     /// \e
+//     void solveSimplex() { lpx_simplex(lp); }
+//     /// \e
+//     void solvePrimalSimplex() { lpx_simplex(lp); }
+//     /// \e
+//     void solveDualSimplex() { lpx_simplex(lp); }
+//     /// \e
+//     double getObjVal() { return lpx_get_obj_val(lp); }
+//     /// \e
+//     int warmUp() { return lpx_warm_up(lp); }
+//     /// \e
+//     void printWarmUpStatus(int i) {
+//       switch (i) {
+//       case LPX_E_OK: cout << "LPX_E_OK" << endl; break;
+//       case LPX_E_EMPTY: cout << "LPX_E_EMPTY" << endl; break;	
+//       case LPX_E_BADB: cout << "LPX_E_BADB" << endl; break;
+//       case LPX_E_SING: cout << "LPX_E_SING" << endl; break;
+//       }
+//     }
+//     /// \e
+//     int getPrimalStatus() { return lpx_get_prim_stat(lp); }
+//     /// \e
+//     void printPrimalStatus(int i) {
+//       switch (i) {
+//       case LPX_P_UNDEF: cout << "LPX_P_UNDEF" << endl; break;
+//       case LPX_P_FEAS: cout << "LPX_P_FEAS" << endl; break;	
+//       case LPX_P_INFEAS: cout << "LPX_P_INFEAS" << endl; break;
+//       case LPX_P_NOFEAS: cout << "LPX_P_NOFEAS" << endl; break;
+//       }
+//     }
+//     /// \e
+//     int getDualStatus() { return lpx_get_dual_stat(lp); }
+//     /// \e
+//     void printDualStatus(int i) {
+//       switch (i) {
+//       case LPX_D_UNDEF: cout << "LPX_D_UNDEF" << endl; break;
+//       case LPX_D_FEAS: cout << "LPX_D_FEAS" << endl; break;	
+//       case LPX_D_INFEAS: cout << "LPX_D_INFEAS" << endl; break;
+//       case LPX_D_NOFEAS: cout << "LPX_D_NOFEAS" << endl; break;
+//       }
+//     }
+//     /// Returns the status of the slack variable assigned to row \c row.
+//     int getRowStat(const Row& row) { 
+//       return lpx_get_row_stat(lp, row_iter_map[row]); 
+//     }
+//     /// \e
+//     void printRowStatus(int i) {
+//       switch (i) {
+//       case LPX_BS: cout << "LPX_BS" << endl; break;
+//       case LPX_NL: cout << "LPX_NL" << endl; break;	
+//       case LPX_NU: cout << "LPX_NU" << endl; break;
+//       case LPX_NF: cout << "LPX_NF" << endl; break;
+//       case LPX_NS: cout << "LPX_NS" << endl; break;
+//       }
+//     }
+//     /// Returns the status of the variable assigned to column \c col.
+//     int getColStat(const Col& col) { 
+//       return lpx_get_col_stat(lp, col_iter_map[col]); 
+//     }
+//     /// \e
+//     void printColStatus(int i) {
+//       switch (i) {
+//       case LPX_BS: cout << "LPX_BS" << endl; break;
+//       case LPX_NL: cout << "LPX_NL" << endl; break;	
+//       case LPX_NU: cout << "LPX_NU" << endl; break;
+//       case LPX_NF: cout << "LPX_NF" << endl; break;
+//       case LPX_NS: cout << "LPX_NS" << endl; break;
+//       }
+//     }
+
+//     // MIP
+//     /// \e
+//     void solveBandB() { lpx_integer(lp); }
+//     /// \e
+//     void setLP() { lpx_set_class(lp, LPX_LP); }
+//     /// \e
+//     void setMIP() { lpx_set_class(lp, LPX_MIP); }
+
+
+
+  };
+  
+  /// @}
+
+} //namespace lemon
+
+#endif //LEMON_LP_SOLVER_GLPK_H