COIN-OR::LEMON - Graph Library

Changeset 1273:2b2ffa625775 in lemon-0.x


Ignore:
Timestamp:
03/30/05 12:38:22 (15 years ago)
Author:
Alpar Juttner
Branch:
default
Phase:
public
Convert:
svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@1703
Message:
  • Better (but still incomplete) doc
  • lp_test runs correctly
Location:
src/work/athos/lp
Files:
5 edited

Legend:

Unmodified
Added
Removed
  • src/work/athos/lp/lp_base.cc

    r1272 r1273  
    2626  LpSolverBase::NaN = std::numeric_limits<Value>::quiet_NaN();
    2727
    28   const LpSolverBase::Constr::Coeff
     28  const LpSolverBase::Constr::Value
    2929  LpSolverBase::Constr::INF = std::numeric_limits<Value>::infinity();
    30   const LpSolverBase::Constr::Coeff
     30  const LpSolverBase::Constr::Value
    3131  LpSolverBase::Constr::NaN = std::numeric_limits<Value>::quiet_NaN();
    3232 
  • src/work/athos/lp/lp_base.h

    r1272 r1273  
    2121#include<map>
    2222#include<limits>
     23#include<math.h>
    2324
    2425#include<lemon/utility.h>
     
    7374        return cross[n];
    7475      }
     76      ///\todo Create an own exception type.
    7577      else throw LogicError(); //floatingId-s must form a continuous range;
    7678    }
     
    127129    ///
    128130    ///Its value remains valid and correct even after the addition or erase of
    129     ///new column (unless the referred column itself was also deleted,
    130     ///of course).
     131    ///other columns.
    131132    ///
    132133    ///\todo Document what can one do with a Col (INVALID, comparing,
     
    151152    ///
    152153    ///Its value remains valid and correct even after the addition or erase of
    153     ///new rows (unless the referred row itself was also deleted, of course).
     154    ///other rows.
    154155    ///
    155156    ///\todo Document what can one do with a Row (INVALID, comparing,
     
    172173    ///Linear expression
    173174    //    typedef SparseLinExpr<Col> Expr;
    174     class Expr : public std::map<Col,Col::ExprValue>
     175    class Expr : public std::map<Col,Value>
    175176    {
    176177    public:
    177       typedef Col Var;
    178       typedef Col::ExprValue Coeff;
     178      typedef LpSolverBase::Col Key;
     179      typedef LpSolverBase::Value Value;
    179180     
    180181    protected:
    181       typedef std::map<Col,Col::ExprValue> Base;
     182      typedef std::map<Col,Value> Base;
    182183     
    183       Coeff const_comp;
     184      Value const_comp;
    184185  public:
    185186      typedef True IsLinExpression;
     
    187188      Expr() : Base(), const_comp(0) { }
    188189      ///\e
    189       Expr(const Var &v) : const_comp(0) {
     190      Expr(const Key &v) : const_comp(0) {
    190191        Base::insert(std::make_pair(v, 1));
    191192      }
    192193      ///\e
    193       Expr(const Coeff &v) : const_comp(v) {}
    194       ///\e
    195       void set(const Var &v,const Coeff &c) {
     194      Expr(const Value &v) : const_comp(v) {}
     195      ///\e
     196      void set(const Key &v,const Value &c) {
    196197        Base::insert(std::make_pair(v, c));
    197198      }
    198199      ///\e
    199       Coeff &constComp() { return const_comp; }
    200       ///\e
    201       const Coeff &constComp() const { return const_comp; }
     200      Value &constComp() { return const_comp; }
     201      ///\e
     202      const Value &constComp() const { return const_comp; }
    202203     
    203204      ///Removes the components with zero coefficient.
     
    210211        }
    211212      }
    212      
     213
     214      ///Sets all coefficients and the constant component to 0.
     215      void clear() {
     216        Base::clear();
     217        const_comp=0;
     218      }
     219
    213220      ///\e
    214221      Expr &operator+=(const Expr &e) {
     
    227234      }
    228235      ///\e
    229       Expr &operator*=(const Coeff &c) {
     236      Expr &operator*=(const Value &c) {
    230237        for (Base::iterator j=Base::begin(); j!=Base::end(); ++j)
    231238          j->second*=c;
     
    234241      }
    235242      ///\e
    236       Expr &operator/=(const Coeff &c) {
     243      Expr &operator/=(const Value &c) {
    237244        for (Base::iterator j=Base::begin(); j!=Base::end(); ++j)
    238245          j->second/=c;
     
    248255    public:
    249256      typedef LpSolverBase::Expr Expr;
    250       typedef Expr::Var Var;
    251       typedef Expr::Coeff Coeff;
     257      typedef Expr::Key Key;
     258      typedef Expr::Value Value;
    252259     
    253       static const Coeff INF;
    254       static const Coeff NaN;
    255       //     static const Coeff INF=0;
    256       //     static const Coeff NaN=1;
     260      static const Value INF;
     261      static const Value NaN;
     262      //     static const Value INF=0;
     263      //     static const Value NaN=1;
    257264     
    258       Expr expr;
    259       Coeff lb,ub;
    260      
    261       Constr() : expr(), lb(NaN), ub(NaN) {}
    262       Constr(Coeff _lb,const Expr &e,Coeff _ub) :
    263         expr(e), lb(_lb), ub(_ub) {}
    264       Constr(const Expr &e,Coeff _ub) :
    265         expr(e), lb(NaN), ub(_ub) {}
    266       Constr(Coeff _lb,const Expr &e) :
    267         expr(e), lb(_lb), ub(NaN) {}
     265    protected:
     266      Expr _expr;
     267      Value _lb,_ub;
     268    public:
     269      ///\e
     270      Constr() : _expr(), _lb(NaN), _ub(NaN) {}
     271      ///\e
     272      Constr(Value lb,const Expr &e,Value ub) :
     273        _expr(e), _lb(lb), _ub(ub) {}
     274      ///\e
     275      Constr(const Expr &e,Value ub) :
     276        _expr(e), _lb(NaN), _ub(ub) {}
     277      ///\e
     278      Constr(Value lb,const Expr &e) :
     279        _expr(e), _lb(lb), _ub(NaN) {}
     280      ///\e
    268281      Constr(const Expr &e) :
    269         expr(e), lb(NaN), ub(NaN) {}
     282        _expr(e), _lb(NaN), _ub(NaN) {}
     283      ///\e
     284      void clear()
     285      {
     286        _expr.clear();
     287        _lb=_ub=NaN;
     288      }
     289      ///\e
     290      Expr &expr() { return _expr; }
     291      ///\e
     292      const Expr &expr() const { return _expr; }
     293      ///\e
     294      Value &lowerBound() { return _lb; }
     295      ///\e
     296      const Value &lowerBound() const { return _lb; }
     297      ///\e
     298      Value &upperBound() { return _ub; }
     299      ///\e
     300      const Value &upperBound() const { return _ub; }
    270301    };
    271302   
     
    355386    ///(i.e a new variables)
    356387    ///
    357     ///This magic function takes container as its argument
     388    ///This magic function takes a container as its argument
    358389    ///and fills its elements
    359390    ///with new columns (i.e. variables)
    360     ///\param t can be either any standard STL iterable container with
    361     ///\ref Col \c values_type or \c mapped_type
    362     ///like <tt>std::vector<LpSolverBase::Col></tt>,
    363     /// <tt>std::list<LpSolverBase::Col></tt> or
    364     /// <tt>std::map<AnyType,LpSolverBase::Col></tt> or
    365     ///it can be an iterable lemon map like
    366     /// <tt>ListGraph::NodeMap<LpSolverBase::Col></tt>.
     391    ///\param t can be
     392    ///- a standard STL compatible iterable container with
     393    ///\ref Col as its \c values_type
     394    ///like
     395    ///\code
     396    ///std::vector<LpSolverBase::Col>
     397    ///std::list<LpSolverBase::Col>
     398    ///\endcode
     399    ///- a standard STL compatible iterable container with
     400    ///\ref Col as its \c mapped_type
     401    ///like
     402    ///\code
     403    ///std::map<AnyType,LpSolverBase::Col>
     404    ///\endcode
     405    ///- an iterable lemon \ref concept::WriteMap "write map" like
     406    ///\code
     407    ///ListGraph::NodeMap<LpSolverBase::Col>
     408    ///ListGraph::EdgeMap<LpSolverBase::Col>
     409    ///\endcode
    367410    ///\return The number of the created column.
    368411    ///\bug Iterable nodemap hasn't been implemented yet.
     
    441484    ///\param c is a linear expression (see \ref Constr)
    442485    void setRow(Row r, const Constr &c) {
    443       Value lb= c.lb==NaN?-INF:lb;
    444       Value ub= c.ub==NaN?INF:lb;
    445       setRow(r,lb,c.expr,ub);
     486      setRow(r,
     487             isnan(c.lowerBound())?-INF:c.lowerBound(),
     488             c.expr(),
     489             isnan(c.upperBound())?INF:c.upperBound());
    446490    }
    447491
     
    564608  ///
    565609  inline LpSolverBase::Expr operator*(const LpSolverBase::Expr &a,
    566                                       const LpSolverBase::Expr::Coeff &b)
     610                                      const LpSolverBase::Value &b)
    567611  {
    568612    LpSolverBase::Expr tmp(a);
     
    575619  ///\relates LpSolverBase::Expr
    576620  ///
    577   inline LpSolverBase::Expr operator*(const LpSolverBase::Expr::Coeff &a,
     621  inline LpSolverBase::Expr operator*(const LpSolverBase::Value &a,
    578622                                      const LpSolverBase::Expr &b)
    579623  {
     
    587631  ///
    588632  inline LpSolverBase::Expr operator/(const LpSolverBase::Expr &a,
    589                                       const LpSolverBase::Expr::Coeff &b)
     633                                      const LpSolverBase::Value &b)
    590634  {
    591635    LpSolverBase::Expr tmp(a);
     
    608652  ///\relates LpSolverBase::Constr
    609653  ///
    610   inline LpSolverBase::Constr operator<=(const LpSolverBase::Expr::Coeff &e,
     654  inline LpSolverBase::Constr operator<=(const LpSolverBase::Value &e,
    611655                                         const LpSolverBase::Expr &f)
    612656  {
     
    619663  ///
    620664  inline LpSolverBase::Constr operator<=(const LpSolverBase::Expr &e,
    621                                          const LpSolverBase::Expr::Coeff &f)
     665                                         const LpSolverBase::Value &f)
    622666  {
    623667    return LpSolverBase::Constr(e,f);
     
    639683  ///\relates LpSolverBase::Constr
    640684  ///
    641   inline LpSolverBase::Constr operator>=(const LpSolverBase::Expr::Coeff &e,
     685  inline LpSolverBase::Constr operator>=(const LpSolverBase::Value &e,
    642686                                         const LpSolverBase::Expr &f)
    643687  {
     
    651695  ///
    652696  inline LpSolverBase::Constr operator>=(const LpSolverBase::Expr &e,
    653                                          const LpSolverBase::Expr::Coeff &f)
     697                                         const LpSolverBase::Value &f)
    654698  {
    655699    return LpSolverBase::Constr(f,e);
     
    670714  ///\relates LpSolverBase::Constr
    671715  ///
    672   inline LpSolverBase::Constr operator<=(const LpSolverBase::Constr::Coeff &n,
     716  inline LpSolverBase::Constr operator<=(const LpSolverBase::Value &n,
    673717                                         const LpSolverBase::Constr&c)
    674718  {
    675719    LpSolverBase::Constr tmp(c);
    676     if(tmp.lb!=tmp.NaN) throw LogicError();
    677     else tmp.lb=n;
     720    ///\todo Create an own exception type.
     721    if(!isnan(tmp.lowerBound())) throw LogicError();
     722    else tmp.lowerBound()=n;
    678723    return tmp;
    679724  }
     
    683728  ///
    684729  inline LpSolverBase::Constr operator<=(const LpSolverBase::Constr& c,
    685                                          const LpSolverBase::Constr::Coeff &n)
     730                                         const LpSolverBase::Value &n)
    686731  {
    687732    LpSolverBase::Constr tmp(c);
    688     if(tmp.ub!=tmp.NaN) throw LogicError();
    689     else tmp.ub=n;
    690     return tmp;
    691   }
    692 
    693   ///\e
    694  
    695   ///\relates LpSolverBase::Constr
    696   ///
    697   inline LpSolverBase::Constr operator>=(const LpSolverBase::Constr::Coeff &n,
     733    ///\todo Create an own exception type.
     734    if(!isnan(tmp.upperBound())) throw LogicError();
     735    else tmp.upperBound()=n;
     736    return tmp;
     737  }
     738
     739  ///\e
     740 
     741  ///\relates LpSolverBase::Constr
     742  ///
     743  inline LpSolverBase::Constr operator>=(const LpSolverBase::Value &n,
    698744                                         const LpSolverBase::Constr&c)
    699745  {
    700746    LpSolverBase::Constr tmp(c);
    701     if(tmp.ub!=tmp.NaN) throw LogicError();
    702     else tmp.ub=n;
     747    ///\todo Create an own exception type.
     748    if(!isnan(tmp.upperBound())) throw LogicError();
     749    else tmp.upperBound()=n;
    703750    return tmp;
    704751  }
     
    708755  ///
    709756  inline LpSolverBase::Constr operator>=(const LpSolverBase::Constr& c,
    710                                          const LpSolverBase::Constr::Coeff &n)
     757                                         const LpSolverBase::Value &n)
    711758  {
    712759    LpSolverBase::Constr tmp(c);
    713     if(tmp.lb!=tmp.NaN) throw LogicError();
    714     else tmp.lb=n;
     760    ///\todo Create an own exception type.
     761    if(!isnan(tmp.lowerBound())) throw LogicError();
     762    else tmp.lowerBound()=n;
    715763    return tmp;
    716764  }
  • src/work/athos/lp/lp_solver_skeleton.cc

    r1263 r1273  
    2424  int LpSolverSkeleton::_addCol()
    2525  {
    26     return 1;
     26    return ++col_num;
    2727  }
    2828 
    2929  int LpSolverSkeleton::_addRow()
    3030  {
    31     return 1;
     31    return ++row_num;
    3232  }
    3333 
  • src/work/athos/lp/lp_solver_skeleton.h

    r1263 r1273  
    2727  ///A skeleton class to implement LP solver interfaces
    2828  class LpSolverSkeleton :public LpSolverBase {
    29 
     29    int col_num,row_num;
     30   
    3031  protected:
    3132    virtual int _addCol();
     
    4647    virtual SolutionType _solve();
    4748    virtual Value _getSolution(int i);
    48 
     49  public:
     50    LpSolverSkeleton() : LpSolverBase(), col_num(0), row_num(0) {}
    4951  }; 
    5052
  • src/work/athos/lp/lp_test.cc

    r1272 r1273  
    117117 
    118118  lp.addRow(LP::INF,e,23);
    119   lp.addRow(LP::INF,3.0*(p1+p2)-p3,23);
    120119  lp.addRow(LP::INF,3.0*(x[1]+x[2]/2)-x[3],23);
    121   lp.addRow(LP::INF,3.0*(p1+p2*2-5*p3+12-p4/3)+2*p4-4,23);
    122120  lp.addRow(LP::INF,3.0*(x[1]+x[2]*2-5*x[3]+12-x[4]/3)+2*x[4]-4,23);
    123121
    124122  lp.addRow(x[1]+x[3]<=x[5]-3);
    125123  lp.addRow(-7<=x[1]+x[3]-12<=3);
    126   //lp.addRow(x[1]<=x[5]);
     124  lp.addRow(x[1]<=x[5]);
    127125
    128126}
     
    144142  typename G::EdgeMap<LpGlpk::Col> x(g);
    145143  lp.addColSet(x);
    146    //for(EdgeIt e(g);e!=INVALID;++e) x[e]=lp.addCol();
    147144 
    148145  for(EdgeIt e(g);e!=INVALID;++e) {
     
    155152    for(InEdgeIt  e(g,n);e!=INVALID;++e) ex+=x[e];
    156153    for(OutEdgeIt e(g,n);e!=INVALID;++e) ex-=x[e];
    157     lp.addRow(0,ex,0);
     154    lp.addRow(ex==0);
    158155  }
    159156  {
     
    178175
    179176  ListGraph g;
     177  ListGraph::Node s=g.addNode();
     178  ListGraph::Node t=g.addNode();
     179
    180180  ListGraph::EdgeMap<double> cap(g);
    181181 
    182   maxFlow(g,cap,ListGraph::NodeIt(g),ListGraph::NodeIt(g));
     182  maxFlow(g,cap,s,t);
    183183
    184184}
Note: See TracChangeset for help on using the changeset viewer.