lemon-0.x: comparison lemon/lp

equal deleted inserted replaced

-:696585ab305a
+:d9b7247ed0f9
 ///\file
 ///\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.
 class _FixId
 {
 ///Returns the first (smallest) inserted index
 ///or -1 if no index has been inserted before.
 int firstIndex() {return _first_index;}
 };
 ///Common base class for LP solvers
 ///\todo Much more docs
 ///\ingroup gen_opt_group
 class LpSolverBase {
 enum SolveExitStatus {
 ///This means that the problem has been successfully solved: either
 ///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
 };
 ///\e
 enum SolutionStatus {
 	int fid = _lp->cols.floatingId(id)+1;
 	id = unsigned(fid)<_lp->cols.cross.size() ? _lp->cols.fixId(fid) : -1;
 	return *this;
 }
 };
+static int id(const Col& col) { return col.id; }
 ///Refer to a row of the LP.
 ///This type is used to refer to a row of the LP.
 ///
 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;}
 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
 ///This data structure strores a linear expression of the variables
 ///(\ref Col "Col"s) and also has a constant component.
 	  if ((*i).second==0) Base::erase(i);
 	  i=j;
 	}
 }
+void simplify() const {
+const_cast<Expr*>(this)->simplify();
+}
 ///Removes the coefficients closer to zero than \c tolerance.
 void simplify(double &tolerance) {
 	for (Base::iterator i=Base::begin(); i!=Base::end();) {
 	  Base::iterator j=i;
 	  ++j;
 public:
 typedef LpSolverBase::Expr Expr;
 typedef Expr::Key Key;
 typedef Expr::Value Value;
-//       static const Value INF;
-//       static const Value NaN;
 protected:
 Expr _expr;
 Value _lb,_ub;
 public:
 ///\e
 	  if ((*i).second==0) Base::erase(i);
 	  i=j;
 	}
 }
+void simplify() const {
+const_cast<DualExpr*>(this)->simplify();
+}
 ///Removes the coefficients closer to zero than \c tolerance.
 void simplify(double &tolerance) {
 	for (Base::iterator i=Base::begin(); i!=Base::end();) {
 	  Base::iterator j=i;
 	  ++j;
 	  if (std::fabs((*i).second)<tolerance) Base::erase(i);
 	  i=j;
 	}
 }
 ///Sets all coefficients to 0.
 void clear() {
 	Base::clear();
 }
 	return *this;
 }
 };
+private:
+template <typename _Base>
+class MappedIterator {
+public:
+typedef _Base Base;
+typedef typename Base::iterator_category iterator_category;
+typedef typename Base::difference_type difference_type;
+typedef const std::pair<int, Value> 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<Expr::const_iterator> LpRowIterator;
+/// STL compatible iterator for lp row
+typedef MappedIterator<DualExpr::const_iterator> 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());
 return newlp;
 //return *(LpSolverBase*)0;
 virtual int _addCol() = 0;
 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,
+virtual void _setRowCoeffs(int i, LpRowIterator b, LpRowIterator e) = 0;
-			       int length,
+virtual void _setColCoeffs(int i, LpColIterator b, LpColIterator e) = 0;
-int  const * indices,
-Value  const * values ) = 0;
-virtual void _setColCoeffs(int i,
-			       int length,
-int  const * indices,
-Value  const * values ) = 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;
 //     virtual void _setRowLowerBound(int i, Value value) = 0;
 //     virtual void _setRowUpperBound(int i, Value value) = 0;
 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;
 virtual Value _getPrimalValue() = 0;
 virtual bool _isBasicCol(int i) = 0;
 //Own protected stuff
 //Constant component of the objective function
 Value obj_const_comp;
 public:
 ///\e
 LpSolverBase() : obj_const_comp(0) {}
 ///\param c is the column to be modified
 ///\param e is a dual linear expression (see \ref DualExpr)
 ///a better one.
 void col(Col c,const DualExpr &e) {
-std::vector<int> indices;
+e.simplify();
-std::vector<Value> values;
+_setColCoeffs(_lpId(c), LpColIterator(e.begin(), *this),
-indices.push_back(0);
+LpColIterator(e.end(), *this));
-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]);
 }
 ///Add a new column to the LP
 ///\param e is a dual linear expression (see \ref DualExpr)
 ///\bug This is a temportary function. The interface will change to
 ///a better one.
 ///\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<int> indices;
+e.simplify();
-std::vector<Value> values;
+_setRowCoeffs(_lpId(r), LpRowIterator(e.begin(), *this),
-indices.push_back(0);
+LpRowIterator(e.end(), *this));
-values.push_back(0);
+//       _setRowLowerBound(_lpId(r),l-e.constComp());
-for(Expr::const_iterator i=e.begin(); i!=e.end(); ++i)
+//       _setRowUpperBound(_lpId(r),u-e.constComp());
-	if((*i).second!=0) { ///\bug EPSILON would be necessary here!!!
+_setRowBounds(_lpId(r),l-e.constComp(),u-e.constComp());
-	  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());
 }
 ///Set a row (i.e a constraint) of the LP
 ///\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,
+row(r, c.lowerBounded()?c.lowerBound():-INF,
-	     c.lowerBounded()?c.lowerBound():-INF,
+c.expr(), c.upperBounded()?c.upperBound():INF);
-	     c.expr(),
-	     c.upperBounded()?c.upperBound():INF);
 }
 ///Add a new row (i.e a new constraint) to the LP
 ///\param l is the lower bound (-\ref INF means no bound)
 ///Erase a coloumn (i.e a variable) from the LP
 ///\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
 ///\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);
 }
 /// Get the name of a column
 ///\param c is the coresponding coloumn
 ///\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;
 }
 /// Set the name of a column
 ///\param c is the coresponding coloumn
 ///\param name The name to be given
-void colName(Col c, const std::string & name){
+void colName(Col c, const std::string& name){
-_setColName(cols.floatingId(c.id), name);
+_setColName(_lpId(c), name);
 }
 /// Set an element of the coefficient matrix of the LP
 ///\param r is the row of the element to be modified
 ///\param c is the coloumn of the element to be modified
 ///\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)
 /// The lower bound of a variable (column) has to be given by an
 /// 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
 ///(i.e a variables) at once
 ///
 /// The upper bound of a variable (column) has to be given by an
 /// 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
 ///(i.e a variables) at once
 ///
 /// The lower and the upper bounds of
 /// a variable (column) have to be given by an
 /// 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);
+_setColLowerBound(_lpId(c),lower);
-_setColUpperBound(cols.floatingId(c.id),upper);
+_setColUpperBound(_lpId(c),upper);
 }
 ///\brief Set the lower and the upper bound of several columns
 ///(i.e a variables) at once
 ///
 //     /// The lower bound of a linear expression (row) has to be given by an
 //     /// 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)
 //     /// The upper bound of a linear expression (row) has to be given by an
 //     /// 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)
 /// The lower and the upper bounds of
 /// a constraint (row) have to be given by an
 /// 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);
+_setRowBounds(_lpId(c),lower, upper);
-// _setRowUpperBound(rows.floatingId(c.id),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.
 ///\bug Is should be called obj()
 void setObj(Expr e) {
 ProblemTypes problemType() {
 return _getProblemType();
 }
 ///\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
 ///\return
 ///- \ref INF or -\ref INF means either infeasibility or unboundedness
 ///Sets the type of the given coloumn to the given type
 ///
 ///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.
 ///
 ///Sets the type of the given Col to integer or remove that property.
 ///\e
 ///\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;
 return tmp;
 }
 ///\e
 ///\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;
 return tmp;
 }
 ///\e
 ///\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;
 return tmp;
 }
 ///\e
 ///\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;
 return tmp;
 }
 ///\e
 ///\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;
 return tmp;
 }

changeset 2314	dbbd5c514163
parent 2309	468a525d5b45
child 2324	18fc834761d9