# HG changeset patch
# User marci
# Date 1102334170 0
# Node ID 0b7169db694f83f5d9f191c64829f24439b9c387
# Parent  c8a41699e613032cbf95ec4f6dd17c3ab6bdaccd
:-(

diff -r c8a41699e613 -r 0b7169db694f src/work/marci/lp/lp_solver_wrapper_2.h
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/src/work/marci/lp/lp_solver_wrapper_2.h	Mon Dec 06 11:56:10 2004 +0000
@@ -0,0 +1,547 @@
+// -*- c++ -*-
+#ifndef LEMON_LP_SOLVER_WRAPPER_H
+#define LEMON_LP_SOLVER_WRAPPER_H
+
+///\ingroup misc
+///\file
+///\brief Dijkstra algorithm.
+
+// #include <stdio.h>
+#include <stdlib.h>
+// #include <stdio>
+//#include <stdlib>
+extern "C" {
+#include "glpk.h"
+}
+
+#include <iostream>
+#include <vector>
+#include <string>
+#include <list>
+#include <memory>
+#include <utility>
+
+//#include <sage_graph.h>
+//#include <lemon/list_graph.h>
+//#include <lemon/graph_wrapper.h>
+#include <lemon/invalid.h>
+//#include <bfs_dfs.h>
+//#include <stp.h>
+//#include <lemon/max_flow.h>
+//#include <augmenting_flow.h>
+//#include <iter_map.h>
+
+using std::cout;
+using std::cin;
+using std::endl;
+
+namespace lemon {
+
+  
+  /// \addtogroup misc
+  /// @{
+
+  /// \brief A partitioned vector with iterable classes.
+  ///
+  /// This class implements a container in which the data is stored in an 
+  /// stl vector, the range is partitioned into sets and each set is 
+  /// doubly linked in a list. 
+  /// That is, each class is iterable by lemon iterators, and any member of 
+  /// the vector can bo moved to an other class.
+  template <typename T>
+  class IterablePartition {
+  protected:
+    struct Node {
+      T data;
+      int prev; //invalid az -1
+      int next; 
+    };
+    std::vector<Node> nodes;
+    struct Tip {
+      int first;
+      int last;
+    };
+    std::vector<Tip> tips;
+  public:
+    /// The classes are indexed by integers from \c 0 to \c classNum()-1.
+    int classNum() const { return tips.size(); }
+    /// This lemon style iterator iterates through a class. 
+    class ClassIt;
+    /// Constructor. The number of classes is to be given which is fixed 
+    /// over the life of the container. 
+    /// The partition classes are indexed from 0 to class_num-1. 
+    IterablePartition(int class_num) { 
+      for (int i=0; i<class_num; ++i) {
+	Tip t;
+	t.first=t.last=-1;
+	tips.push_back(t);
+      }
+    }
+  protected:
+    void befuz(ClassIt it, int class_id) {
+      if (tips[class_id].first==-1) {
+	if (tips[class_id].last==-1) {
+	  nodes[it.i].prev=nodes[it.i].next=-1;
+	  tips[class_id].first=tips[class_id].last=it.i;
+	}
+      } else {
+	nodes[it.i].prev=tips[class_id].last;
+	nodes[it.i].next=-1;
+	nodes[tips[class_id].last].next=it.i;
+	tips[class_id].last=it.i;
+      }
+    }
+    void kifuz(ClassIt it, int class_id) {
+      if (tips[class_id].first==it.i) {
+	if (tips[class_id].last==it.i) {
+	  tips[class_id].first=tips[class_id].last=-1;
+	} else {
+	  tips[class_id].first=nodes[it.i].next;
+	  nodes[nodes[it.i].next].prev=-1;
+	}
+      } else {
+	if (tips[class_id].last==it.i) {
+	  tips[class_id].last=nodes[it.i].prev;
+	  nodes[nodes[it.i].prev].next=-1;
+	} else {
+	  nodes[nodes[it.i].next].prev=nodes[it.i].prev;
+	  nodes[nodes[it.i].prev].next=nodes[it.i].next;
+	}
+      }
+    }
+  public:
+    /// A new element with data \c t is pushed into the vector and into class 
+    /// \c class_id.
+    ClassIt push_back(const T& t, int class_id) { 
+      Node n;
+      n.data=t;
+      nodes.push_back(n);
+      int i=nodes.size()-1;
+      befuz(i, class_id);
+      return i;
+    }
+    /// A member is moved to an other class.
+    void set(ClassIt it, int old_class_id, int new_class_id) {
+      kifuz(it.i, old_class_id);
+      befuz(it.i, new_class_id);
+    }
+    /// Returns the data pointed by \c it.
+    T& operator[](ClassIt it) { return nodes[it.i].data; }
+    /// Returns the data pointed by \c it.
+    const T& operator[](ClassIt it) const { return nodes[it.i].data; }
+    ///.
+    class ClassIt {
+      friend class IterablePartition;
+    protected:
+      int i;
+    public:
+      /// Default constructor.
+      ClassIt() { }
+      /// This constructor constructs an iterator which points
+      /// to the member of th container indexed by the integer _i.
+      ClassIt(const int& _i) : i(_i) { }
+      /// Invalid constructor.
+      ClassIt(const Invalid&) : i(-1) { }
+    };
+    /// First member of class \c class_id.
+    ClassIt& first(ClassIt& it, int class_id) const {
+      it.i=tips[class_id].first;
+      return it;
+    }
+    /// Next member.
+    ClassIt& next(ClassIt& it) const {
+      it.i=nodes[it.i].next;
+      return it;
+    }
+    /// True iff the iterator is valid.
+    bool valid(const ClassIt& it) const { return it.i!=-1; }
+  };
+
+  /*! \e
+   */
+  class LPSolverBase {
+  public:
+    /// \e
+    typedef IterablePartition<int>::ClassIt RowIt;
+    /// \e
+    typedef IterablePartition<int>::ClassIt ColIt;
+  protected:
+    /// \e
+    IterablePartition<int> row_iter_map;
+    /// \e
+    IterablePartition<int> col_iter_map;
+    /// \e
+    const int VALID_ID;
+    /// \e
+    const int INVALID_ID;
+  public:
+    /// \e
+    LPSolverBase() : row_iter_map(2), 
+		     col_iter_map(2), 
+		     VALID_ID(0), INVALID_ID(1) { }
+    /// \e
+    virtual ~LPSolverBase() { }
+    /// \e
+    virtual void setMinimize() = 0;
+    /// \e
+    virtual void setMaximize() = 0;
+    /// \e
+    virtual RowIt addRow() = 0;
+    /// \e
+    virtual ColIt addCol() = 0;
+    /// temporally, glpk style indexing
+    virtual void setRowCoeffs(RowIt row_it, int num, 
+			      int* indices, double* doubles) = 0;
+    //pair<RowIt, double>-bol kell megadni egy std range-et
+    /// \e
+    template <typename Begin, typename End>
+    void setRowCoeffs(RowIt row_it, Begin begin, End end) {
+      int mem_length=1+colNum();
+      int* indices = new int[mem_length];
+      double* doubles = new double[mem_length];
+      int length=0;
+      for ( ; begin!=end; ++begin) {
+	++length;
+	indices[length]=col_iter_map[begin->first];
+	doubles[length]=begin->second;
+      }
+      setRowCoeffs(row_it, length, indices, doubles);
+      delete [] indices;
+      delete [] doubles;
+    }
+    /// temporally, glpk style indexing
+    virtual void setColCoeffs(ColIt col_it, int num, 
+			      int* indices, double* doubles) = 0;
+    //pair<ColIt, double>-bol kell megadni egy std range-et
+    /// \e
+    template <typename Begin, typename End>
+    void setColCoeffs(ColIt col_it, Begin begin, End end) {
+      int mem_length=1+rowNum();
+      int* indices = new int[mem_length];
+      double* doubles = new double[mem_length];
+      int length=0;
+      for ( ; begin!=end; ++begin) {
+	++length;
+	indices[length]=row_iter_map[begin->first];
+	doubles[length]=begin->second;
+      }
+      setColCoeffs(col_it, length, indices, doubles);
+      delete [] indices;
+      delete [] doubles;
+    }
+    /// \e
+    virtual void eraseCol(const ColIt& col_it) = 0;
+    /// \e
+    virtual void eraseRow(const RowIt& row_it) = 0;
+    /// \e
+    virtual void setColBounds(const ColIt& col_it, int bound_type, 
+			      double lo, double up) =0; 
+    /// \e
+    virtual double getObjCoef(const ColIt& col_it) = 0;
+    /// \e
+    virtual void setRowBounds(const RowIt& row_it, int bound_type, 
+			      double lo, double up) = 0;
+    /// \e
+    virtual void setObjCoef(const ColIt& col_it, double obj_coef) = 0;
+    /// \e
+    virtual void solveSimplex() = 0;
+    /// \e
+    virtual void solvePrimalSimplex() = 0;
+    /// \e
+    virtual void solveDualSimplex() = 0;
+    /// \e
+    virtual double getPrimal(const ColIt& col_it) = 0;
+    /// \e
+    virtual double getObjVal() = 0;
+    /// \e
+    virtual int rowNum() const = 0;
+    /// \e
+    virtual int colNum() const = 0;
+    /// \e
+    virtual int warmUp() = 0;
+    /// \e
+    virtual void printWarmUpStatus(int i) = 0;
+    /// \e
+    virtual int getPrimalStatus() = 0;
+    /// \e
+    virtual void printPrimalStatus(int i) = 0;
+    /// \e
+    virtual int getDualStatus() = 0;
+    /// \e
+    virtual void printDualStatus(int i) = 0;
+    /// Returns the status of the slack variable assigned to row \c row_it.
+    virtual int getRowStat(const RowIt& row_it) = 0;
+    /// \e
+    virtual void printRowStatus(int i) = 0;
+    /// Returns the status of the variable assigned to column \c col_it.
+    virtual int getColStat(const ColIt& col_it) = 0;
+    /// \e
+    virtual void printColStatus(int i) = 0;
+  };
+  
+  /// \brief Wrappers for LP solvers
+  /// 
+  /// This class implements a lemon wrapper for glpk.
+  /// Later other LP-solvers will be wrapped into lemon.
+  /// The aim of this class is to give a general surface to different 
+  /// solvers, i.e. it makes possible to write algorithms using LP's, 
+  /// in which the solver can be changed to an other one easily.
+  class LPSolverWrapper : public LPSolverBase {
+  public:
+    typedef LPSolverBase Parent;
+
+    //   class Row {
+    //   protected:
+    //     int i;
+    //   public:
+    //     Row() { }
+    //     Row(const Invalid&) : i(0) { }
+    //     Row(const int& _i) : i(_i) { }
+    //     operator int() const { return i; }
+    //   };
+    //   class RowIt : public Row {
+    //   public:
+    //     RowIt(const Row& row) : Row(row) { }
+    //   };
+
+    //   class Col {
+    //   protected:
+    //     int i;
+    //   public:
+    //     Col() { }
+    //     Col(const Invalid&) : i(0) { }
+    //     Col(const int& _i) : i(_i) { }
+    //     operator int() const { return i; }
+    //   };
+    //   class ColIt : public Col {
+    //     ColIt(const Col& col) : Col(col) { }
+    //   };
+
+  public:
+    /// \e
+    LPX* lp;
+
+  public:
+    /// \e
+    LPSolverWrapper() : LPSolverBase(), 
+			lp(lpx_create_prob()) {
+      lpx_set_int_parm(lp, LPX_K_DUAL, 1);
+    }
+    /// \e
+    ~LPSolverWrapper() {
+      lpx_delete_prob(lp);
+    }
+    /// \e
+    void setMinimize() { 
+      lpx_set_obj_dir(lp, LPX_MIN);
+    }
+    /// \e
+    void setMaximize() { 
+      lpx_set_obj_dir(lp, LPX_MAX);
+    }
+    /// \e
+    ColIt addCol() {
+      int i=lpx_add_cols(lp, 1);  
+      ColIt col_it;
+      col_iter_map.first(col_it, INVALID_ID);
+      if (col_iter_map.valid(col_it)) { //van hasznalhato hely
+	col_iter_map.set(col_it, INVALID_ID, VALID_ID);
+	col_iter_map[col_it]=i;
+	//col_id_to_lp_col_id[col_iter_map[col_it]]=i;
+      } else { //a cucc vegere kell inzertalni mert nincs szabad hely
+	//col_id_to_lp_col_id.push_back(i);
+	//int j=col_id_to_lp_col_id.size()-1;
+	col_it=col_iter_map.push_back(i, VALID_ID);
+      }
+      //    edge_index_map.set(e, i);
+      //    lpx_set_col_bnds(lp, i, LPX_DB, 0.0, 1.0);
+      //    lpx_set_obj_coef(lp, i, cost[e]);    
+      return col_it;
+    }
+    /// \e
+    RowIt addRow() {
+      int i=lpx_add_rows(lp, 1);  
+      RowIt row_it;
+      row_iter_map.first(row_it, INVALID_ID);
+      if (row_iter_map.valid(row_it)) { //van hasznalhato hely
+	row_iter_map.set(row_it, INVALID_ID, VALID_ID);
+	row_iter_map[row_it]=i;
+      } else { //a cucc vegere kell inzertalni mert nincs szabad hely
+	row_it=row_iter_map.push_back(i, VALID_ID);
+      }
+      return row_it;
+    }
+    using Parent::setRowCoeffs;
+    void setRowCoeffs(RowIt row_it, int length, 
+		      int* indices, double* doubles) {
+      lpx_set_mat_row(lp, row_iter_map[row_it], length, indices, doubles);
+    }
+    using Parent::setColCoeffs;
+    void setColCoeffs(ColIt col_it, int length, 
+		      int* indices, double* doubles) {
+      lpx_set_mat_col(lp, col_iter_map[col_it], length, indices, doubles);
+    }
+    //     //pair<RowIt, double>-bol kell megadni egy std range-et
+    //     /// \e
+    //     template <typename Begin, typename End>
+    //     void setColCoeffs(const ColIt& col_it, 
+    // 		      Begin begin, End end) {
+    //       int mem_length=1+lpx_get_num_rows(lp);
+    //       int* indices = new int[mem_length];
+    //       double* doubles = new double[mem_length];
+    //       int length=0;
+    //       for ( ; begin!=end; ++begin) {
+    // 	++length;
+    // 	indices[length]=row_iter_map[begin->first];
+    // 	doubles[length]=begin->second;
+    //       }
+    //       lpx_set_mat_col(lp, col_iter_map[col_it], length, indices, doubles);
+    //       delete [] indices;
+    //       delete [] doubles;
+    //     }
+    //     //pair<ColIt, double>-bol kell megadni egy std range-et
+    //     /// \e
+    //     template <typename Begin, typename End>
+    //     void setRowCoeffs(const RowIt& row_it, 
+    // 		      Begin begin, End end) {
+    //       int mem_length=1+lpx_get_num_cols(lp);
+    //       int* indices = new int[mem_length];
+    //       double* doubles = new double[mem_length];
+    //       int length=0;
+    //       for ( ; begin!=end; ++begin) {
+    // 	++length;
+    // 	indices[length]=col_iter_map[begin->first];
+    // 	doubles[length]=begin->second;
+    //       }
+    //       lpx_set_mat_row(lp, row_iter_map[row_it], length, indices, doubles);
+    //       delete [] indices;
+    //       delete [] doubles;
+    //     }
+    /// \e
+    void eraseCol(const ColIt& col_it) {
+      col_iter_map.set(col_it, VALID_ID, INVALID_ID);
+      int cols[2];
+      cols[1]=col_iter_map[col_it];
+      lpx_del_cols(lp, 1, cols);
+      col_iter_map[col_it]=0; //glpk specifikus
+      ColIt it;
+      for (col_iter_map.first(it, VALID_ID); 
+	   col_iter_map.valid(it); col_iter_map.next(it)) {
+	if (col_iter_map[it]>cols[1]) --col_iter_map[it];
+      }
+    }
+    /// \e
+    void eraseRow(const RowIt& row_it) {
+      row_iter_map.set(row_it, VALID_ID, INVALID_ID);
+      int rows[2];
+      rows[1]=row_iter_map[row_it];
+      lpx_del_rows(lp, 1, rows);
+      row_iter_map[row_it]=0; //glpk specifikus
+      RowIt it;
+      for (row_iter_map.first(it, VALID_ID); 
+	   row_iter_map.valid(it); row_iter_map.next(it)) {
+	if (row_iter_map[it]>rows[1]) --row_iter_map[it];
+      }
+    }
+    /// \e
+    void setColBounds(const ColIt& col_it, int bound_type, 
+		      double lo, double up) {
+      lpx_set_col_bnds(lp, col_iter_map[col_it], bound_type, lo, up);
+    }
+    /// \e
+    double getObjCoef(const ColIt& col_it) { 
+      return lpx_get_obj_coef(lp, col_iter_map[col_it]);
+    }
+    /// \e
+    void setRowBounds(const RowIt& row_it, int bound_type, 
+		      double lo, double up) {
+      lpx_set_row_bnds(lp, row_iter_map[row_it], bound_type, lo, up);
+    }
+    /// \e
+    void setObjCoef(const ColIt& col_it, double obj_coef) { 
+      lpx_set_obj_coef(lp, col_iter_map[col_it], obj_coef);
+    }
+    /// \e
+    void solveSimplex() { lpx_simplex(lp); }
+    /// \e
+    void solvePrimalSimplex() { lpx_simplex(lp); }
+    /// \e
+    void solveDualSimplex() { lpx_simplex(lp); }
+    /// \e
+    double getPrimal(const ColIt& col_it) {
+      return lpx_get_col_prim(lp, col_iter_map[col_it]);
+    }
+    /// \e
+    double getObjVal() { return lpx_get_obj_val(lp); }
+    /// \e
+    int rowNum() const { return lpx_get_num_rows(lp); }
+    /// \e
+    int colNum() const { return lpx_get_num_cols(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_it.
+    int getRowStat(const RowIt& row_it) { 
+      return lpx_get_row_stat(lp, row_iter_map[row_it]); 
+    }
+    /// \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_it.
+    int getColStat(const ColIt& col_it) { 
+      return lpx_get_col_stat(lp, col_iter_map[col_it]); 
+    }
+    /// \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;
+      }
+    }
+  };
+  
+  /// @}
+
+} //namespace lemon
+
+#endif //LEMON_LP_SOLVER_WRAPPER_H
diff -r c8a41699e613 -r 0b7169db694f src/work/marci/lp/max_flow_by_lp.cc
--- a/src/work/marci/lp/max_flow_by_lp.cc	Mon Dec 06 00:30:44 2004 +0000
+++ b/src/work/marci/lp/max_flow_by_lp.cc	Mon Dec 06 11:56:10 2004 +0000
@@ -10,7 +10,7 @@
 #include <lemon/preflow.h>
 #include <augmenting_flow.h>
 //#include <preflow_res.h>
-#include <lp_solver_wrapper.h>
+//#include <lp_solver_wrapper_2.h>
 #include <min_cost_gen_flow.h>
 
 // Use a DIMACS max flow file as stdin.
@@ -179,7 +179,7 @@
   MinCostGenFlow<Graph, int, Excess, LCap> 
     min_cost(g, excess, lcap, cap, flow, cost); 
   min_cost.feasible();
-  min_cost.run();
+  min_cost.runByLP();
 
   std::cout << "elapsed time: " << ts << std::endl;
   std::cout << "flow value: "<< flow[e] << std::endl;
diff -r c8a41699e613 -r 0b7169db694f src/work/marci/lp/min_cost_gen_flow.h
--- a/src/work/marci/lp/min_cost_gen_flow.h	Mon Dec 06 00:30:44 2004 +0000
+++ b/src/work/marci/lp/min_cost_gen_flow.h	Mon Dec 06 11:56:10 2004 +0000
@@ -14,7 +14,7 @@
 //#include <augmenting_flow.h>
 //#include <preflow_res.h>
 #include <work/marci/merge_node_graph_wrapper.h>
-#include <work/marci/lp/lp_solver_wrapper.h>
+#include <work/marci/lp/lp_solver_wrapper_2.h>
 
 namespace lemon {
 
@@ -211,10 +211,11 @@
       return (expected>=min_cost_flow.flowValue());
     }
     void runByLP() {
-      LPSolverWrapper lp;
+      typedef LPSolverWrapper LPSolver;
+      LPSolver lp;
       lp.setMinimize();
-      typedef LPSolverWrapper::ColIt ColIt;
-      typedef LPSolverWrapper::RowIt RowIt;
+      typedef LPSolver::ColIt ColIt;
+      typedef LPSolver::RowIt RowIt;
       typedef typename Graph::template EdgeMap<ColIt> EdgeIndexMap;
       EdgeIndexMap edge_index_map(g);
       PrimalMap<typename Graph::Edge, EdgeIndexMap> lp_flow(lp, edge_index_map);