Changeset 1074:4a24a46407db in lemon-0.x for src/work/marci/lp

Timestamp:

01/11/05 18:15:46 (20 years ago)

Author:

marci

Branch:

default

Phase:

public

Convert:

svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@1470

Message:

:-}

Location:

src/work/marci/lp

Files:

• lp_solver_wrapper_3.h (copied) (copied from src/work/marci/lp/lp_solver_wrapper_2.h) (6 diffs)
• min_cost_gen_flow.h (modified) (3 diffs)

src/work/marci/lp/lp_solver_wrapper_3.h

@@ -169 +169 @@
     /// \e
     typedef IterablePartition<int>::ClassIt ColIt;
-  protected:
+  public:
     /// \e
     IterablePartition<int> row_iter_map;
@@ -175 +175 @@
     IterablePartition<int> col_iter_map;
     /// \e
-    const int VALID_ID;
-    /// \e
-    const int INVALID_ID;
+    const int VALID_CLASS;
+    /// \e
+    const int INVALID_CLASS;
   public:
     /// \e
     LPSolverBase() : row_iter_map(2), 
                      col_iter_map(2), 
-                     VALID_ID(0), INVALID_ID(1) { }
+                     VALID_CLASS(0), INVALID_CLASS(1) { }
     /// \e
     virtual ~LPSolverBase() { }
@@ -189 +189 @@
     /// \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, _Value* doubles) = 0;
-    //pair<RowIt, _Value>-bol kell megadni egy std range-et
+  protected:
+    /// \e
+    virtual int _addRow() = 0;
+    /// \e
+    virtual int _addCol() = 0;
+  public:
+    /// \e
+    RowIt addRow() {
+      int i=_addRow(); 
+      RowIt row_it;
+      row_iter_map.first(row_it, INVALID_CLASS);
+      if (row_iter_map.valid(row_it)) { //van hasznalhato hely
+        row_iter_map.set(row_it, INVALID_CLASS, VALID_CLASS);
+        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_CLASS);
+      }
+      return row_it;
+    }
+    /// \e
+    ColIt addCol() {
+      int i=_addCol();  
+      ColIt col_it;
+      col_iter_map.first(col_it, INVALID_CLASS);
+      if (col_iter_map.valid(col_it)) { //van hasznalhato hely
+        col_iter_map.set(col_it, INVALID_CLASS, VALID_CLASS);
+        col_iter_map[col_it]=i;
+      } else { //a cucc vegere kell inzertalni mert nincs szabad hely
+        col_it=col_iter_map.push_back(i, VALID_CLASS);
+      }
+      return col_it;
+    }
+    /// \e
+    virtual void setRowCoeffs(int i, 
+                              std::vector<std::pair<int, double> > coeffs) = 0;
+    /// \e
+    virtual void setColCoeffs(int i, 
+                              std::vector<std::pair<int, double> > coeffs) = 0;
     /// \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];
-      _Value* doubles = new _Value[mem_length];
-      int length=0;
+      std::vector<std::pair<int, double> > coeffs;
       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, _Value* doubles) = 0;
-    //pair<ColIt, _Value>-bol kell megadni egy std range-et
+        coeffs.push_back(std::
+                         make_pair(col_iter_map[begin->first], begin->second));
+      }
+      setRowCoeffs(row_iter_map[row_it], coeffs);
+    }
     /// \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];
-      _Value* doubles = new _Value[mem_length];
-      int length=0;
+      std::vector<std::pair<int, double> > coeffs;
       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;
+        coeffs.push_back(std::
+                         make_pair(row_iter_map[begin->first], begin->second));
+      }
+      setColCoeffs(col_iter_map[col_it], coeffs);
+    }
+    /// temporally, glpk style indexing
+    //virtual void setRowCoeffs(RowIt row_it, int num, 
+    //                int* indices, _Value* doubles) = 0;
+    //pair<RowIt, _Value>-bol kell megadni egy std range-et
+    /// \e
+    //    virtual void seColCoeffs(int i, 
+    //                        std::vector<std::pair<int, double> > coeffs) = 0;
+    /// \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];
+//       _Value* doubles = new _Value[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, _Value* doubles) = 0;
+    //pair<ColIt, _Value>-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];
+//       _Value* doubles = new _Value[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;
+//     }
+  protected:
+    /// \e
+    virtual void _eraseCol(int i) = 0;
+    /// \e
+    virtual void _eraseRow(int i) = 0;
+  public:
+    /// \e
+    void eraseCol(const ColIt& col_it) {
+      col_iter_map.set(col_it, VALID_CLASS, INVALID_CLASS);
+      int cols[2];
+      cols[1]=col_iter_map[col_it];
+      _eraseCol(cols[1]);
+      col_iter_map[col_it]=0; //glpk specifikus, de kell ez??
+      ColIt it;
+      for (col_iter_map.first(it, VALID_CLASS); 
+           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_CLASS, INVALID_CLASS);
+      int rows[2];
+      rows[1]=row_iter_map[row_it];
+      _eraseRow(rows[1]);
+      row_iter_map[row_it]=0; //glpk specifikus, de kell ez??
+      RowIt it;
+      for (row_iter_map.first(it, VALID_CLASS); 
+           row_iter_map.valid(it); row_iter_map.next(it)) {
+        if (row_iter_map[it]>rows[1]) --row_iter_map[it];
+      }
+    }
     /// \e
     virtual void setColBounds(const ColIt& col_it, int bound_type, 
@@ -295 +380 @@
     typedef LPSolverBase<double> 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
@@ -344 +402 @@
       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;
-    }
+  protected:
+    /// \e
+    int _addCol() { 
+      return lpx_add_cols(lp, 1);
+    }
+    /// \e
+    int _addRow() { 
+      return lpx_add_rows(lp, 1);
+    }
+  public:
     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);
-    }
+    /// \e
+    virtual void setRowCoeffs(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=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;
+        std::cout << "  " << indices[length] << " " 
+                  << doubles[length] << std::endl;
+      }
+      std::cout << i << " " << length << std::endl;
+      lpx_set_mat_row(lp, i, length, indices, doubles);
+      delete [] indices;
+      delete [] doubles;
+    }
+    /// \e
+    virtual void setColCoeffs(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=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
+//     /// temporally, glpk style indexing
+//     virtual void setRowCoeffs(RowIt row_it, int num, 
+//                            int* indices, _Value* doubles) = 0;
+//     //pair<RowIt, _Value>-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];
+//       _Value* doubles = new _Value[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;
+//     }
+//     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
@@ -423 +517 @@
     //     }
     /// \e
-    void eraseCol(const ColIt& col_it) {
-      col_iter_map.set(col_it, VALID_ID, INVALID_ID);
+  protected:
+    virtual void _eraseCol(int i) {
       int cols[2];
-      cols[1]=col_iter_map[col_it];
+      cols[1]=i;
       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);
+    }
+    virtual void _eraseRow(int i) {
       int rows[2];
-      rows[1]=row_iter_map[row_it];
+      rows[1]=i;
       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];
-      }
-    }
+    }
+  public:
     /// \e
     void setColBounds(const ColIt& col_it, int bound_type, 

src/work/marci/lp/min_cost_gen_flow.h

@@ -15 +15 @@
 //#include <preflow_res.h>
 #include <work/marci/merge_node_graph_wrapper.h>
-#include <work/marci/lp/lp_solver_wrapper_2.h>
+#include <work/marci/lp/lp_solver_wrapper_3.h>
 
 namespace lemon {
@@ -229 +229 @@
         lp.setObjCoef(col_it, cost[e]);
       }
+      LPSolver::ColIt col_it;
+      for (lp.col_iter_map.first(col_it, lp.VALID_CLASS); 
+           lp.col_iter_map.valid(col_it); 
+           lp.col_iter_map.next(col_it)) {
+        std::cout << "ize " << lp.col_iter_map[col_it] << std::endl;
+      }
       for (typename Graph::NodeIt n(g); n!=INVALID; ++n) {
         typename Graph::template EdgeMap<Num> coeffs(g, 0);
@@ -245 +251 @@
         }
         //std::cout << std::endl;
+        std::cout << " " << g.id(n) << " " << row.size() << std::endl;
         lp.setRowCoeffs(row_it, row.begin(), row.end());
         lp.setRowBounds(row_it, LPX_FX, 0.0, 0.0);