1.1 --- a/src/lemon/utility.h Thu Mar 24 12:19:05 2005 +0000
1.2 +++ b/src/lemon/utility.h Fri Mar 25 08:18:27 2005 +0000
1.3 @@ -56,7 +56,9 @@
1.4 Wrap(const T &t) : value(t) {}
1.5 };
1.6
1.7 + /**************** dummy class to avoid ambiguity ****************/
1.8
1.9 + template<int T> struct dummy { dummy(int) {} };
1.10
1.11 /**************** enable_if from BOOST ****************/
1.12
2.1 --- a/src/work/athos/lp/Makefile Thu Mar 24 12:19:05 2005 +0000
2.2 +++ b/src/work/athos/lp/Makefile Fri Mar 25 08:18:27 2005 +0000
2.3 @@ -2,6 +2,9 @@
2.4
2.5 all: lp_test
2.6
2.7 +clean:
2.8 + rm lp_test *.o
2.9 +
2.10 lp_base.o: lp_base.cc lp_base.h lin_expr.h
2.11 lp_solver_skeleton.o: lp_solver_skeleton.cc lp_solver_skeleton.h lp_base.h \
2.12 lin_expr.h
3.1 --- a/src/work/athos/lp/lp_base.cc Thu Mar 24 12:19:05 2005 +0000
3.2 +++ b/src/work/athos/lp/lp_base.cc Fri Mar 25 08:18:27 2005 +0000
3.3 @@ -19,7 +19,9 @@
3.4
3.5 #include "lp_base.h"
3.6 namespace lemon {
3.7 -
3.8 +
3.9 + const LpSolverBase::Value
3.10 + LpSolverBase::INF = std::numeric_limits<Value>::infinity();
3.11
3.12
3.13 } //namespace lemon
4.1 --- a/src/work/athos/lp/lp_base.h Thu Mar 24 12:19:05 2005 +0000
4.2 +++ b/src/work/athos/lp/lp_base.h Fri Mar 25 08:18:27 2005 +0000
4.3 @@ -18,8 +18,11 @@
4.4 #define LEMON_LP_BASE_H
4.5
4.6 #include<vector>
4.7 +#include<limits>
4.8
4.9 +#include<lemon/utility.h>
4.10 #include<lemon/error.h>
4.11 +#include<lemon/invalid.h>
4.12
4.13 #include"lin_expr.h"
4.14 ///\file
4.15 @@ -65,6 +68,7 @@
4.16 index[first_free]=n;
4.17 first_free=next;
4.18 }
4.19 + return cross[n];
4.20 }
4.21 else throw LogicError(); //floatingId-s must form a continuous range;
4.22 }
4.23 @@ -96,15 +100,56 @@
4.24
4.25 public:
4.26
4.27 - /// \e
4.28 + ///The floating point type used by the solver
4.29 typedef double Value;
4.30 - /// \e
4.31 + ///The infinity constant
4.32 static const Value INF;
4.33
4.34 - ///\e
4.35 - class Col { protected: int id; friend class LpSolverBase; };
4.36 - ///\e
4.37 - class Row { protected: int id; friend class LpSolverBase; };
4.38 + ///Refer to a column of the LP.
4.39 +
4.40 + ///This type is used to refer to a column of the LP.
4.41 + ///
4.42 + ///Its value remains valid and correct even after the addition or erase of
4.43 + ///new column (unless the referred column itself was also deleted,
4.44 + ///of course).
4.45 + ///
4.46 + ///\todo Document what can one do with a Col (INVALID, comparing,
4.47 + ///it is similar to Node/Edge)
4.48 + class Col {
4.49 + protected:
4.50 + int id;
4.51 + friend class LpSolverBase;
4.52 + public:
4.53 + typedef True LpSolverCol;
4.54 + Col() {}
4.55 + Col(const Invalid&) : id(-1) {}
4.56 + bool operator<(Col c) const {return id<c.id;}
4.57 + bool operator==(Col c) const {return id==c.id;}
4.58 + bool operator!=(Col c) const {return id==c.id;}
4.59 + };
4.60 +
4.61 + ///Refer to a row of the LP.
4.62 +
4.63 + ///This type is used to refer to a row of the LP.
4.64 + ///
4.65 + ///Its value remains valid and correct even after the addition or erase of
4.66 + ///new rows (unless the referred row itself was also deleted, of course).
4.67 + ///
4.68 + ///\todo Document what can one do with a Row (INVALID, comparing,
4.69 + ///it is similar to Node/Edge)
4.70 + class Row {
4.71 + protected:
4.72 + int id;
4.73 + friend class LpSolverBase;
4.74 + public:
4.75 + typedef True LpSolverRow;
4.76 + Row() {}
4.77 + Row(const Invalid&) : id(-1) {}
4.78 + typedef True LpSolverRow;
4.79 + bool operator<(Row c) const {return id<c.id;}
4.80 + bool operator==(Row c) const {return id==c.id;}
4.81 + bool operator!=(Row c) const {return id==c.id;}
4.82 + };
4.83
4.84 typedef SparseLinExpr<Col, Value> Expr;
4.85
4.86 @@ -175,6 +220,44 @@
4.87
4.88 ///Add a new empty column (i.e a new variable) to the LP
4.89 Col addCol() { Col c; c.id=cols.insert(_addCol()); return c;}
4.90 + ///\brief Fill the elements of a container with newly created columns
4.91 + ///(i.e a new variables)
4.92 + ///
4.93 + ///This magic function takes container as its argument
4.94 + ///and fills its elements
4.95 + ///with new columns (i.e. variables)
4.96 + ///\param t can be either any standard STL iterable container with
4.97 + ///\ref Col \c values_type or \c mapped_type
4.98 + ///like <tt>std::vector<LpSolverBase::Col></tt>,
4.99 + /// <tt>std::list<LpSolverBase::Col></tt> or
4.100 + /// <tt>std::map<AnyType,LpSolverBase::Col></tt> or
4.101 + ///it can be an iterable lemon map like
4.102 + /// <tt>ListGraph::NodeMap<LpSolverBase::Col></tt>.
4.103 + ///\return The number of the created column.
4.104 + ///\bug Iterable nodemap hasn't been implemented yet.
4.105 +#ifdef DOXYGEN
4.106 + template<class T>
4.107 + int addColSet(T &t) { return 0;}
4.108 +#else
4.109 + template<class T>
4.110 + typename enable_if<typename T::value_type::LpSolverCol,int>::type
4.111 + addColSet(T &t,dummy<0> = 0) {
4.112 + int s=0;
4.113 + for(typename T::iterator i=t.begin();i!=t.end();++i) {*i=addCol();s++;}
4.114 + return s;
4.115 + }
4.116 + template<class T>
4.117 + typename enable_if<typename T::value_type::second_type::LpSolverCol,
4.118 + int>::type
4.119 + addColSet(T &t,dummy<1> = 1) {
4.120 + int s=0;
4.121 + for(typename T::iterator i=t.begin();i!=t.end();++i) {
4.122 + i->second=addCol();
4.123 + s++;
4.124 + }
4.125 + return s;
4.126 + }
4.127 +#endif
4.128 ///Add a new empty row (i.e a new constaint) to the LP
4.129 Row addRow() { Row r; r.id=rows.insert(_addRow()); return r;}
4.130
4.131 @@ -191,14 +274,15 @@
4.132 std::vector<Value> values;
4.133 indices.push_back(0);
4.134 values.push_back(0);
4.135 - for(Expr::iterator i=e.begin(); i!=e.end(); ++i) {
4.136 - indices.push_back(cols.floatingId((*i).first.id));
4.137 - values.push_back((*i).second);
4.138 - }
4.139 + for(Expr::iterator i=e.begin(); i!=e.end(); ++i)
4.140 + if((*i).second!=0) { ///\bug EPSILON would be necessary here!!!
4.141 + indices.push_back(cols.floatingId((*i).first.id));
4.142 + values.push_back((*i).second);
4.143 + }
4.144 _setRowCoeffs(rows.floatingId(r.id),indices.size()-1,
4.145 &indices[0],&values[0]);
4.146 - _setRowLowerBound(rows.floatingId(r.id),l);
4.147 - _setRowUpperBound(rows.floatingId(r.id),l);
4.148 + _setRowLowerBound(rows.floatingId(r.id),l-e.constComp());
4.149 + _setRowUpperBound(rows.floatingId(r.id),u-e.constComp());
4.150 return r;
4.151 }
4.152
5.1 --- a/src/work/athos/lp/lp_test.cc Thu Mar 24 12:19:05 2005 +0000
5.2 +++ b/src/work/athos/lp/lp_test.cc Fri Mar 25 08:18:27 2005 +0000
5.3 @@ -4,5 +4,30 @@
5.4
5.5 int main()
5.6 {
5.7 - LpSolverSkeleton lp;
5.8 + typedef LpSolverSkeleton LP;
5.9 + LP lp;
5.10 +
5.11 + std::vector<LP::Col> x;
5.12 + for(int i=0;i<10;i++) x.push_back(lp.addCol());
5.13 +
5.14 + std::vector<LP::Col> y(10);
5.15 + lp.addColSet(y);
5.16 +
5.17 + std::map<int,LP::Col> z;
5.18 +
5.19 + z.insert(std::make_pair(12,INVALID));
5.20 + z.insert(std::make_pair(2,INVALID));
5.21 + z.insert(std::make_pair(7,INVALID));
5.22 + z.insert(std::make_pair(5,INVALID));
5.23 +
5.24 + lp.addColSet(z);
5.25 +
5.26 +
5.27 + LP::Expr e;
5.28 + e[x[3]]=2;
5.29 + e[x[3]]=4;
5.30 + e[x[3]]=1;
5.31 + e.constComp()=12;
5.32 + lp.addRow(LP::INF,e,23);
5.33 +
5.34 }