1.1 --- a/src/work/athos/lp/lp_base.h Thu Mar 24 12:19:05 2005 +0000
1.2 +++ b/src/work/athos/lp/lp_base.h Fri Mar 25 08:18:27 2005 +0000
1.3 @@ -18,8 +18,11 @@
1.4 #define LEMON_LP_BASE_H
1.5
1.6 #include<vector>
1.7 +#include<limits>
1.8
1.9 +#include<lemon/utility.h>
1.10 #include<lemon/error.h>
1.11 +#include<lemon/invalid.h>
1.12
1.13 #include"lin_expr.h"
1.14 ///\file
1.15 @@ -65,6 +68,7 @@
1.16 index[first_free]=n;
1.17 first_free=next;
1.18 }
1.19 + return cross[n];
1.20 }
1.21 else throw LogicError(); //floatingId-s must form a continuous range;
1.22 }
1.23 @@ -96,15 +100,56 @@
1.24
1.25 public:
1.26
1.27 - /// \e
1.28 + ///The floating point type used by the solver
1.29 typedef double Value;
1.30 - /// \e
1.31 + ///The infinity constant
1.32 static const Value INF;
1.33
1.34 - ///\e
1.35 - class Col { protected: int id; friend class LpSolverBase; };
1.36 - ///\e
1.37 - class Row { protected: int id; friend class LpSolverBase; };
1.38 + ///Refer to a column of the LP.
1.39 +
1.40 + ///This type is used to refer to a column of the LP.
1.41 + ///
1.42 + ///Its value remains valid and correct even after the addition or erase of
1.43 + ///new column (unless the referred column itself was also deleted,
1.44 + ///of course).
1.45 + ///
1.46 + ///\todo Document what can one do with a Col (INVALID, comparing,
1.47 + ///it is similar to Node/Edge)
1.48 + class Col {
1.49 + protected:
1.50 + int id;
1.51 + friend class LpSolverBase;
1.52 + public:
1.53 + typedef True LpSolverCol;
1.54 + Col() {}
1.55 + Col(const Invalid&) : id(-1) {}
1.56 + bool operator<(Col c) const {return id<c.id;}
1.57 + bool operator==(Col c) const {return id==c.id;}
1.58 + bool operator!=(Col c) const {return id==c.id;}
1.59 + };
1.60 +
1.61 + ///Refer to a row of the LP.
1.62 +
1.63 + ///This type is used to refer to a row of the LP.
1.64 + ///
1.65 + ///Its value remains valid and correct even after the addition or erase of
1.66 + ///new rows (unless the referred row itself was also deleted, of course).
1.67 + ///
1.68 + ///\todo Document what can one do with a Row (INVALID, comparing,
1.69 + ///it is similar to Node/Edge)
1.70 + class Row {
1.71 + protected:
1.72 + int id;
1.73 + friend class LpSolverBase;
1.74 + public:
1.75 + typedef True LpSolverRow;
1.76 + Row() {}
1.77 + Row(const Invalid&) : id(-1) {}
1.78 + typedef True LpSolverRow;
1.79 + bool operator<(Row c) const {return id<c.id;}
1.80 + bool operator==(Row c) const {return id==c.id;}
1.81 + bool operator!=(Row c) const {return id==c.id;}
1.82 + };
1.83
1.84 typedef SparseLinExpr<Col, Value> Expr;
1.85
1.86 @@ -175,6 +220,44 @@
1.87
1.88 ///Add a new empty column (i.e a new variable) to the LP
1.89 Col addCol() { Col c; c.id=cols.insert(_addCol()); return c;}
1.90 + ///\brief Fill the elements of a container with newly created columns
1.91 + ///(i.e a new variables)
1.92 + ///
1.93 + ///This magic function takes container as its argument
1.94 + ///and fills its elements
1.95 + ///with new columns (i.e. variables)
1.96 + ///\param t can be either any standard STL iterable container with
1.97 + ///\ref Col \c values_type or \c mapped_type
1.98 + ///like <tt>std::vector<LpSolverBase::Col></tt>,
1.99 + /// <tt>std::list<LpSolverBase::Col></tt> or
1.100 + /// <tt>std::map<AnyType,LpSolverBase::Col></tt> or
1.101 + ///it can be an iterable lemon map like
1.102 + /// <tt>ListGraph::NodeMap<LpSolverBase::Col></tt>.
1.103 + ///\return The number of the created column.
1.104 + ///\bug Iterable nodemap hasn't been implemented yet.
1.105 +#ifdef DOXYGEN
1.106 + template<class T>
1.107 + int addColSet(T &t) { return 0;}
1.108 +#else
1.109 + template<class T>
1.110 + typename enable_if<typename T::value_type::LpSolverCol,int>::type
1.111 + addColSet(T &t,dummy<0> = 0) {
1.112 + int s=0;
1.113 + for(typename T::iterator i=t.begin();i!=t.end();++i) {*i=addCol();s++;}
1.114 + return s;
1.115 + }
1.116 + template<class T>
1.117 + typename enable_if<typename T::value_type::second_type::LpSolverCol,
1.118 + int>::type
1.119 + addColSet(T &t,dummy<1> = 1) {
1.120 + int s=0;
1.121 + for(typename T::iterator i=t.begin();i!=t.end();++i) {
1.122 + i->second=addCol();
1.123 + s++;
1.124 + }
1.125 + return s;
1.126 + }
1.127 +#endif
1.128 ///Add a new empty row (i.e a new constaint) to the LP
1.129 Row addRow() { Row r; r.id=rows.insert(_addRow()); return r;}
1.130
1.131 @@ -191,14 +274,15 @@
1.132 std::vector<Value> values;
1.133 indices.push_back(0);
1.134 values.push_back(0);
1.135 - for(Expr::iterator i=e.begin(); i!=e.end(); ++i) {
1.136 - indices.push_back(cols.floatingId((*i).first.id));
1.137 - values.push_back((*i).second);
1.138 - }
1.139 + for(Expr::iterator i=e.begin(); i!=e.end(); ++i)
1.140 + if((*i).second!=0) { ///\bug EPSILON would be necessary here!!!
1.141 + indices.push_back(cols.floatingId((*i).first.id));
1.142 + values.push_back((*i).second);
1.143 + }
1.144 _setRowCoeffs(rows.floatingId(r.id),indices.size()-1,
1.145 &indices[0],&values[0]);
1.146 - _setRowLowerBound(rows.floatingId(r.id),l);
1.147 - _setRowUpperBound(rows.floatingId(r.id),l);
1.148 + _setRowLowerBound(rows.floatingId(r.id),l-e.constComp());
1.149 + _setRowUpperBound(rows.floatingId(r.id),u-e.constComp());
1.150 return r;
1.151 }
1.152