1.1 --- a/src/work/marci/lp/lp_solver_base.h	Tue Feb 08 11:27:03 2005 +0000
     1.2 +++ b/src/work/marci/lp/lp_solver_base.h	Tue Feb 08 17:47:19 2005 +0000
     1.3 @@ -171,6 +171,7 @@
     1.4  
     1.5  
     1.6    /*! \e
     1.7 +    \todo kellenene uj iterable structure bele, mert ez nem az igazi
     1.8      \todo A[x,y]-t cserel. Jobboldal, baloldal csere.
     1.9      \todo LEKERDEZESEK!!!
    1.10      \todo DOKSI!!!! Doxygen group!!!
    1.11 @@ -201,6 +202,10 @@
    1.12      /// \e
    1.13      IterablePartition<int> col_iter_map;
    1.14      /// \e
    1.15 +    std::vector<RowIt> int_row_map;
    1.16 +    /// \e
    1.17 +    std::vector<ColIt> int_col_map;
    1.18 +    /// \e
    1.19      const int VALID_CLASS;
    1.20      /// \e
    1.21      const int INVALID_CLASS;
    1.22 @@ -297,8 +302,15 @@
    1.23      virtual void _setRowCoeffs(int i, 
    1.24  			       const std::vector<std::pair<int, _Value> >& coeffs) = 0;
    1.25      /// \e
    1.26 +    /// This routine modifies \c coeffs only by the \c push_back method.
    1.27 +    virtual void _getRowCoeffs(int i, 
    1.28 +			       std::vector<std::pair<int, _Value> >& coeffs) = 0;
    1.29      virtual void _setColCoeffs(int i, 
    1.30  			       const std::vector<std::pair<int, _Value> >& coeffs) = 0;
    1.31 +    /// \e
    1.32 +    /// This routine modifies \c coeffs only by the \c push_back method.
    1.33 +    virtual void _getColCoeffs(int i, 
    1.34 +			       std::vector<std::pair<int, _Value> >& coeffs) = 0;
    1.35    public:
    1.36      /// \e
    1.37      enum Bound { FREE, LOWER, UPPER, DOUBLE, FIXED };
    1.38 @@ -373,6 +385,7 @@
    1.39        } else { //a cucc vegere kell inzertalni mert nincs szabad hely
    1.40  	col_it=col_iter_map.push_back(i, VALID_CLASS);
    1.41        }
    1.42 +      int_col_map.push_back(col_it);
    1.43        return col_it;
    1.44      }
    1.45      /// \e
    1.46 @@ -386,6 +399,7 @@
    1.47        } else { //a cucc vegere kell inzertalni mert nincs szabad hely
    1.48  	row_it=row_iter_map.push_back(i, VALID_CLASS);
    1.49        }
    1.50 +      int_row_map.push_back(row_it);
    1.51        return row_it;
    1.52      }
    1.53      /// \e
    1.54 @@ -400,6 +414,7 @@
    1.55  	   col_iter_map.valid(it); col_iter_map.next(it)) {
    1.56  	if (col_iter_map[it]>cols[1]) --col_iter_map[it];
    1.57        }
    1.58 +      int_col_map.erase(int_col_map.begin()+cols[1]);
    1.59      }
    1.60      /// \e
    1.61      void eraseRow(const RowIt& row_it) {
    1.62 @@ -413,6 +428,7 @@
    1.63  	   row_iter_map.valid(it); row_iter_map.next(it)) {
    1.64  	if (row_iter_map[it]>rows[1]) --row_iter_map[it];
    1.65        }
    1.66 +      int_row_map.erase(int_row_map.begin()+rows[1]);
    1.67      }
    1.68      /// \e
    1.69      template <typename Begin, typename End>
    1.70 @@ -509,6 +525,16 @@
    1.71        _setRowCoeffs(row_iter_map[row_it], row_coeffs);
    1.72      }
    1.73      /// \e
    1.74 +    /// This routine modifies \c expr by only adding to it.
    1.75 +    void getRowCoeffs(RowIt row_it, Expression& expr) {
    1.76 +      std::vector<std::pair<int, _Value> > row_coeffs;
    1.77 +      _getRowCoeffs(row_iter_map[row_it], row_coeffs);
    1.78 +      for(typename std::vector<std::pair<int, _Value> >::const_iterator 
    1.79 + 	    i=row_coeffs.begin(); i!=row_coeffs.end(); ++i) {
    1.80 + 	expr+= (*i).second*int_col_map[(*i).first];
    1.81 +      }
    1.82 +    }
    1.83 +    /// \e
    1.84      void setColCoeffs(ColIt col_it, const DualExpression& expr) {
    1.85        std::vector<std::pair<int, _Value> > col_coeffs;
    1.86        for(typename DualExpression::Data::const_iterator i=expr.data.begin(); 
    1.87 @@ -519,12 +545,28 @@
    1.88        _setColCoeffs(col_iter_map[col_it], col_coeffs);
    1.89      }
    1.90      /// \e
    1.91 +    /// This routine modifies \c expr by only adding to it.
    1.92 +    void getColCoeffs(ColIt col_it, DualExpression& expr) {
    1.93 +      std::vector<std::pair<int, _Value> > col_coeffs;
    1.94 +      _getColCoeffs(col_iter_map[col_it], col_coeffs);
    1.95 +      for(typename std::vector<std::pair<int, _Value> >::const_iterator 
    1.96 + 	    i=col_coeffs.begin(); i!=col_coeffs.end(); ++i) {
    1.97 + 	expr+= (*i).second*int_row_map[(*i).first];
    1.98 +      }
    1.99 +    }
   1.100 +    /// \e
   1.101 +    /// \bug ez igy nem jo
   1.102      void setObjCoeffs(const Expression& expr) {
   1.103        for(typename Expression::Data::const_iterator i=expr.data.begin(); 
   1.104  	  i!=expr.data.end(); ++i) {
   1.105  	setObjCoef((*i).first, (*i).second);
   1.106        }
   1.107      }
   1.108 +    /// \e
   1.109 +    /// This routine modifies \c expr by only adding to it.
   1.110 +    void getObjCoeffs(Expression& expr) {
   1.111 +      /// FIXME not yet implemented
   1.112 +    }
   1.113      //@}
   1.114    };
   1.115    
   1.116 @@ -547,6 +589,8 @@
   1.117      /// \e
   1.118      LPGLPK() : Parent(), 
   1.119  			lp(lpx_create_prob()) {
   1.120 +      int_row_map.push_back(RowIt());
   1.121 +      int_col_map.push_back(ColIt());
   1.122        lpx_set_int_parm(lp, LPX_K_DUAL, 1);
   1.123      }
   1.124      /// \e
   1.125 @@ -592,15 +636,25 @@
   1.126  	++length;
   1.127  	indices[length]=it->first;
   1.128  	doubles[length]=it->second;
   1.129 -// 	std::cout << "  " << indices[length] << " " 
   1.130 -// 		  << doubles[length] << std::endl;
   1.131        }
   1.132 -//      std::cout << i << " " << length << std::endl;
   1.133        lpx_set_mat_row(lp, i, length, indices, doubles);
   1.134        delete [] indices;
   1.135        delete [] doubles;
   1.136      }
   1.137      /// \e
   1.138 +    virtual void _getRowCoeffs(int i, 
   1.139 +			       std::vector<std::pair<int, double> >& coeffs) {
   1.140 +      int mem_length=1+colNum();
   1.141 +      int* indices = new int[mem_length];
   1.142 +      double* doubles = new double[mem_length];
   1.143 +      int length=lpx_get_mat_row(lp, i, indices, doubles);
   1.144 +      for (int i=1; i<=length; ++i) {
   1.145 +	coeffs.push_back(std::make_pair(indices[i], doubles[i]));
   1.146 +      }
   1.147 +      delete [] indices;
   1.148 +      delete [] doubles;
   1.149 +    }
   1.150 +    /// \e
   1.151      virtual void _setColCoeffs(int i, 
   1.152  			       const std::vector<std::pair<int, double> >& coeffs) {
   1.153        int mem_length=1+rowNum();
   1.154 @@ -618,6 +672,19 @@
   1.155        delete [] doubles;
   1.156      }
   1.157      /// \e
   1.158 +    virtual void _getColCoeffs(int i, 
   1.159 +			       std::vector<std::pair<int, double> >& coeffs) {
   1.160 +      int mem_length=1+rowNum();
   1.161 +      int* indices = new int[mem_length];
   1.162 +      double* doubles = new double[mem_length];
   1.163 +      int length=lpx_get_mat_col(lp, i, indices, doubles);
   1.164 +      for (int i=1; i<=length; ++i) {
   1.165 +	coeffs.push_back(std::make_pair(indices[i], doubles[i]));
   1.166 +      }
   1.167 +      delete [] indices;
   1.168 +      delete [] doubles;
   1.169 +    }
   1.170 +    /// \e
   1.171      virtual void _eraseCol(int i) {
   1.172        int cols[2];
   1.173        cols[1]=i;

     2.1 --- a/src/work/marci/lp/max_flow_expression.cc	Tue Feb 08 11:27:03 2005 +0000
     2.2 +++ b/src/work/marci/lp/max_flow_expression.cc	Tue Feb 08 17:47:19 2005 +0000
     2.3 @@ -2,6 +2,7 @@
     2.4  #include <iostream>
     2.5  #include <fstream>
     2.6  
     2.7 +#include <lemon/graph_utils.h>
     2.8  #include <lemon/smart_graph.h>
     2.9  #include <lemon/list_graph.h>
    2.10  #include <lemon/dimacs.h>
    2.11 @@ -48,7 +49,9 @@
    2.12    typedef LPSolver::ColIt ColIt;
    2.13    typedef LPSolver::RowIt RowIt;
    2.14    typedef Graph::EdgeMap<ColIt> EdgeIndexMap;
    2.15 +  typedef Graph::NodeMap<RowIt> NodeIndexMap;
    2.16    EdgeIndexMap edge_index_map(g);
    2.17 +  NodeIndexMap node_index_map(g);
    2.18    PrimalMap<Edge, EdgeIndexMap> flow(lp, edge_index_map);
    2.19  
    2.20    // nonnegativity of flow and capacity function
    2.21 @@ -75,11 +78,41 @@
    2.22      // flow conservation constraints
    2.23      if ((n!=s) && (n!=t)) {
    2.24        RowIt row_it=lp.addRow();
    2.25 +      node_index_map.set(n, row_it);
    2.26        lp.setRowCoeffs(row_it, expr);
    2.27        lp.setRowLowerBound(row_it, 0.0);
    2.28        lp.setRowUpperBound(row_it, 0.0);
    2.29 +//       cout << expr << endl;
    2.30 +//       {
    2.31 +// 	LPSolver::Expression expr;
    2.32 +// 	lp.getRowCoeffs(node_index_map[n], expr);	
    2.33 +// 	cout << expr << endl;
    2.34 +//       }
    2.35      }
    2.36    }
    2.37    lp.solveSimplex();
    2.38 +//   cout << "num of nodes: " << countNodes(g) << endl;
    2.39 +//   cout << "num of edges: " << countEdges(g) << endl;
    2.40 +//   cout << "num of rows: " << lp.rowNum() << endl;
    2.41 +//   cout << "num of rows: " << lp.int_row_map.size() << endl;
    2.42 +//   for (int i=0; i<lp.int_row_map.size(); ++i) {
    2.43 +//     cout << lp.int_row_map[i] << " " << endl;
    2.44 +//   }
    2.45 +//   cout << "num of columns: " << lp.colNum() << endl;
    2.46 +//   cout << "num of columns: " << lp.int_col_map.size() << endl;
    2.47 +//   for (int i=0; i<lp.int_col_map.size(); ++i) {
    2.48 +//     cout << lp.int_col_map[i] << " " << endl;
    2.49 +//   }
    2.50    cout << "elapsed time: " << ts << endl;
    2.51 +//   Graph::NodeIt n(g);
    2.52 +//   ++n;
    2.53 +//   for(Graph::OutEdgeIt e(g, n); e!=INVALID; ++e) {
    2.54 +//     cout << edge_index_map[e] << endl;
    2.55 +//   }
    2.56 +//   for(Graph::InEdgeIt e(g, n); e!=INVALID; ++e) {
    2.57 +//     cout << edge_index_map[e] << endl;
    2.58 +//   }
    2.59 +//   LPSolver::DualExpression expr;
    2.60 +//   lp.getRowCoeffs(node_index_map[n], expr);
    2.61 +//   cout << expr << endl;
    2.62  }