diff -r 2c17006ec9c3 -r 07e46cbb7d85 lemon/lp_base.h --- a/lemon/lp_base.h Tue Nov 28 17:25:22 2006 +0000 +++ b/lemon/lp_base.h Wed Nov 29 15:01:13 2006 +0000 @@ -32,7 +32,8 @@ ///\brief The interface of the LP solver interface. ///\ingroup gen_opt_group namespace lemon { - + + ///Internal data structure to convert floating id's to fix one's ///\todo This might be implemented to be also usable in other places. @@ -109,7 +110,7 @@ ///or -1 if no index has been inserted before. int firstIndex() {return _first_index;} }; - + ///Common base class for LP solvers ///\todo Much more docs @@ -128,7 +129,8 @@ ///an optimal solution has been found or infeasibility/unboundedness ///has been proved. SOLVED = 0, - ///Any other case (including the case when some user specified limit has been exceeded) + ///Any other case (including the case when some user specified + ///limit has been exceeded) UNSOLVED = 1 }; @@ -221,6 +223,9 @@ return *this; } }; + + static int id(const Col& col) { return col.id; } + ///Refer to a row of the LP. @@ -245,7 +250,22 @@ bool operator> (Row c) const {return id> c.id;} bool operator==(Row c) const {return id==c.id;} bool operator!=(Row c) const {return id!=c.id;} - }; + }; + + static int id(const Row& row) { return row.id; } + + protected: + + int _lpId(const Col& col) const { + return cols.floatingId(id(col)); + } + + int _lpId(const Row& row) const { + return rows.floatingId(id(row)); + } + + + public: ///Linear expression of variables and a constant component @@ -336,6 +356,10 @@ } } + void simplify() const { + const_cast(this)->simplify(); + } + ///Removes the coefficients closer to zero than \c tolerance. void simplify(double &tolerance) { for (Base::iterator i=Base::begin(); i!=Base::end();) { @@ -415,9 +439,6 @@ typedef Expr::Key Key; typedef Expr::Value Value; -// static const Value INF; -// static const Value NaN; - protected: Expr _expr; Value _lb,_ub; @@ -553,6 +574,10 @@ } } + void simplify() const { + const_cast(this)->simplify(); + } + ///Removes the coefficients closer to zero than \c tolerance. void simplify(double &tolerance) { for (Base::iterator i=Base::begin(); i!=Base::end();) { @@ -563,7 +588,6 @@ } } - ///Sets all coefficients to 0. void clear() { Base::clear(); @@ -596,12 +620,73 @@ }; + private: + + template + class MappedIterator { + public: + + typedef _Base Base; + + typedef typename Base::iterator_category iterator_category; + typedef typename Base::difference_type difference_type; + typedef const std::pair value_type; + typedef value_type reference; + class pointer { + public: + pointer(value_type& _value) : value(_value) {} + value_type* operator->() { return &value; } + private: + value_type value; + }; + + MappedIterator(const Base& _base, const LpSolverBase& _lp) + : base(_base), lp(_lp) {} + + reference operator*() { + return std::make_pair(lp._lpId(base->first), base->second); + } + + pointer operator->() { + return pointer(operator*()); + } + + MappedIterator& operator++() { + ++base; + return *this; + } + + MappedIterator& operator++(int) { + MappedIterator tmp(*this); + ++base; + return tmp; + } + + bool operator==(const MappedIterator& it) const { + return base == it.base; + } + + bool operator!=(const MappedIterator& it) const { + return base != it.base; + } + + private: + Base base; + const LpSolverBase& lp; + }; + protected: + /// STL compatible iterator for lp col + typedef MappedIterator LpRowIterator; + /// STL compatible iterator for lp row + typedef MappedIterator LpColIterator; + //Abstract virtual functions virtual LpSolverBase &_newLp() = 0; virtual LpSolverBase &_copyLp(){ - ///\todo This should be implemented here, too, when we have problem retrieving routines. It can be overriden. + ///\todo This should be implemented here, too, when we have + ///problem retrieving routines. It can be overriden. //Starting: LpSolverBase & newlp(_newLp()); @@ -613,16 +698,10 @@ virtual int _addRow() = 0; virtual void _eraseCol(int col) = 0; virtual void _eraseRow(int row) = 0; - virtual void _getColName(int col, std::string & name) = 0; + virtual void _getColName(int col, std::string & name) = 0; virtual void _setColName(int col, const std::string & name) = 0; - virtual void _setRowCoeffs(int i, - int length, - int const * indices, - Value const * values ) = 0; - virtual void _setColCoeffs(int i, - int length, - int const * indices, - Value const * values ) = 0; + virtual void _setRowCoeffs(int i, LpRowIterator b, LpRowIterator e) = 0; + virtual void _setColCoeffs(int i, LpColIterator b, LpColIterator e) = 0; virtual void _setCoeff(int row, int col, Value value) = 0; virtual void _setColLowerBound(int i, Value value) = 0; virtual void _setColUpperBound(int i, Value value) = 0; @@ -631,9 +710,7 @@ virtual void _setRowBounds(int i, Value lower, Value upper) = 0; virtual void _setObjCoeff(int i, Value obj_coef) = 0; virtual void _clearObj()=0; -// virtual void _setObj(int length, -// int const * indices, -// Value const * values ) = 0; + virtual SolveExitStatus _solve() = 0; virtual Value _getPrimal(int i) = 0; virtual Value _getDual(int i) = 0; @@ -652,10 +729,7 @@ //Constant component of the objective function Value obj_const_comp; - - - - + public: ///\e @@ -744,17 +818,9 @@ ///\param e is a dual linear expression (see \ref DualExpr) ///a better one. void col(Col c,const DualExpr &e) { - std::vector indices; - std::vector values; - indices.push_back(0); - values.push_back(0); - for(DualExpr::const_iterator i=e.begin(); i!=e.end(); ++i) - if((*i).second!=0) { - indices.push_back(rows.floatingId((*i).first.id)); - values.push_back((*i).second); - } - _setColCoeffs(cols.floatingId(c.id),indices.size()-1, - &indices[0],&values[0]); + e.simplify(); + _setColCoeffs(_lpId(c), LpColIterator(e.begin(), *this), + LpColIterator(e.end(), *this)); } ///Add a new column to the LP @@ -849,20 +915,12 @@ ///\todo Option to control whether a constraint with a single variable is ///added or not. void row(Row r, Value l,const Expr &e, Value u) { - std::vector indices; - std::vector values; - indices.push_back(0); - values.push_back(0); - for(Expr::const_iterator i=e.begin(); i!=e.end(); ++i) - if((*i).second!=0) { ///\bug EPSILON would be necessary here!!! - indices.push_back(cols.floatingId((*i).first.id)); - values.push_back((*i).second); - } - _setRowCoeffs(rows.floatingId(r.id),indices.size()-1, - &indices[0],&values[0]); -// _setRowLowerBound(rows.floatingId(r.id),l-e.constComp()); -// _setRowUpperBound(rows.floatingId(r.id),u-e.constComp()); - _setRowBounds(rows.floatingId(r.id),l-e.constComp(),u-e.constComp()); + e.simplify(); + _setRowCoeffs(_lpId(r), LpRowIterator(e.begin(), *this), + LpRowIterator(e.end(), *this)); +// _setRowLowerBound(_lpId(r),l-e.constComp()); +// _setRowUpperBound(_lpId(r),u-e.constComp()); + _setRowBounds(_lpId(r),l-e.constComp(),u-e.constComp()); } ///Set a row (i.e a constraint) of the LP @@ -870,10 +928,8 @@ ///\param r is the row to be modified ///\param c is a linear expression (see \ref Constr) void row(Row r, const Constr &c) { - row(r, - c.lowerBounded()?c.lowerBound():-INF, - c.expr(), - c.upperBounded()?c.upperBound():INF); + row(r, c.lowerBounded()?c.lowerBound():-INF, + c.expr(), c.upperBounded()?c.upperBound():INF); } ///Add a new row (i.e a new constraint) to the LP @@ -904,7 +960,7 @@ ///\param c is the coloumn to be deleted ///\todo Please check this void eraseCol(Col c) { - _eraseCol(cols.floatingId(c.id)); + _eraseCol(_lpId(c)); cols.erase(c.id); } ///Erase a row (i.e a constraint) from the LP @@ -912,7 +968,7 @@ ///\param r is the row to be deleted ///\todo Please check this void eraseRow(Row r) { - _eraseRow(rows.floatingId(r.id)); + _eraseRow(_lpId(r)); rows.erase(r.id); } @@ -922,7 +978,7 @@ ///\return The name of the colunm std::string colName(Col c){ std::string name; - _getColName(cols.floatingId(c.id), name); + _getColName(_lpId(c), name); return name; } @@ -930,8 +986,8 @@ ///\param c is the coresponding coloumn ///\param name The name to be given - void colName(Col c, const std::string & name){ - _setColName(cols.floatingId(c.id), name); + void colName(Col c, const std::string& name){ + _setColName(_lpId(c), name); } /// Set an element of the coefficient matrix of the LP @@ -941,7 +997,7 @@ ///\param val is the new value of the coefficient void coeff(Row r, Col c, Value val){ - _setCoeff(rows.floatingId(r.id),cols.floatingId(c.id), val); + _setCoeff(_lpId(r),_lpId(c), val); } /// Set the lower bound of a column (i.e a variable) @@ -950,7 +1006,7 @@ /// extended number of type Value, i.e. a finite number of type /// Value or -\ref INF. void colLowerBound(Col c, Value value) { - _setColLowerBound(cols.floatingId(c.id),value); + _setColLowerBound(_lpId(c),value); } ///\brief Set the lower bound of several columns @@ -996,7 +1052,7 @@ /// extended number of type Value, i.e. a finite number of type /// Value or \ref INF. void colUpperBound(Col c, Value value) { - _setColUpperBound(cols.floatingId(c.id),value); + _setColUpperBound(_lpId(c),value); }; ///\brief Set the lower bound of several columns @@ -1043,8 +1099,8 @@ /// extended number of type Value, i.e. a finite number of type /// Value, -\ref INF or \ref INF. void colBounds(Col c, Value lower, Value upper) { - _setColLowerBound(cols.floatingId(c.id),lower); - _setColUpperBound(cols.floatingId(c.id),upper); + _setColLowerBound(_lpId(c),lower); + _setColUpperBound(_lpId(c),upper); } ///\brief Set the lower and the upper bound of several columns @@ -1091,7 +1147,7 @@ // /// extended number of type Value, i.e. a finite number of type // /// Value or -\ref INF. // void rowLowerBound(Row r, Value value) { -// _setRowLowerBound(rows.floatingId(r.id),value); +// _setRowLowerBound(_lpId(r),value); // }; // /// Set the upper bound of a row (i.e a constraint) @@ -1099,7 +1155,7 @@ // /// extended number of type Value, i.e. a finite number of type // /// Value or \ref INF. // void rowUpperBound(Row r, Value value) { -// _setRowUpperBound(rows.floatingId(r.id),value); +// _setRowUpperBound(_lpId(r),value); // }; /// Set the lower and the upper bounds of a row (i.e a constraint) @@ -1109,12 +1165,12 @@ /// extended number of type Value, i.e. a finite number of type /// Value, -\ref INF or \ref INF. void rowBounds(Row c, Value lower, Value upper) { - _setRowBounds(rows.floatingId(c.id),lower, upper); - // _setRowUpperBound(rows.floatingId(c.id),upper); + _setRowBounds(_lpId(c),lower, upper); + // _setRowUpperBound(_lpId(c),upper); } ///Set an element of the objective function - void objCoeff(Col c, Value v) {_setObjCoeff(cols.floatingId(c.id),v); }; + void objCoeff(Col c, Value v) {_setObjCoeff(_lpId(c),v); }; ///Set the objective function ///\param e is a linear expression of type \ref Expr. @@ -1170,13 +1226,13 @@ } ///\e - Value primal(Col c) { return _getPrimal(cols.floatingId(c.id)); } + Value primal(Col c) { return _getPrimal(_lpId(c)); } ///\e - Value dual(Row r) { return _getDual(rows.floatingId(r.id)); } + Value dual(Row r) { return _getDual(_lpId(r)); } ///\e - bool isBasicCol(Col c) { return _isBasicCol(cols.floatingId(c.id)); } + bool isBasicCol(Col c) { return _isBasicCol(_lpId(c)); } ///\e @@ -1213,14 +1269,14 @@ /// ///Sets the type of the given coloumn to the given type. void colType(Col c, ColTypes col_type) { - _colType(cols.floatingId(c.id),col_type); + _colType(_lpId(c),col_type); } ///Gives back the type of the column. /// ///Gives back the type of the column. ColTypes colType(Col c){ - return _colType(cols.floatingId(c.id)); + return _colType(_lpId(c)); } ///Sets the type of the given Col to integer or remove that property. @@ -1440,7 +1496,7 @@ ///\relates LpSolverBase::DualExpr /// inline LpSolverBase::DualExpr operator+(const LpSolverBase::DualExpr &a, - const LpSolverBase::DualExpr &b) + const LpSolverBase::DualExpr &b) { LpSolverBase::DualExpr tmp(a); tmp+=b; @@ -1451,7 +1507,7 @@ ///\relates LpSolverBase::DualExpr /// inline LpSolverBase::DualExpr operator-(const LpSolverBase::DualExpr &a, - const LpSolverBase::DualExpr &b) + const LpSolverBase::DualExpr &b) { LpSolverBase::DualExpr tmp(a); tmp-=b; @@ -1462,7 +1518,7 @@ ///\relates LpSolverBase::DualExpr /// inline LpSolverBase::DualExpr operator*(const LpSolverBase::DualExpr &a, - const LpSolverBase::Value &b) + const LpSolverBase::Value &b) { LpSolverBase::DualExpr tmp(a); tmp*=b; @@ -1474,7 +1530,7 @@ ///\relates LpSolverBase::DualExpr /// inline LpSolverBase::DualExpr operator*(const LpSolverBase::Value &a, - const LpSolverBase::DualExpr &b) + const LpSolverBase::DualExpr &b) { LpSolverBase::DualExpr tmp(b); tmp*=a; @@ -1485,7 +1541,7 @@ ///\relates LpSolverBase::DualExpr /// inline LpSolverBase::DualExpr operator/(const LpSolverBase::DualExpr &a, - const LpSolverBase::Value &b) + const LpSolverBase::Value &b) { LpSolverBase::DualExpr tmp(a); tmp/=b;