COIN-OR::LEMON - Graph Library

Changeset 1152:1765ff9fefa1 in lemon-0.x for src/work


Ignore:
Timestamp:
02/16/05 22:40:16 (19 years ago)
Author:
marci
Branch:
default
Phase:
public
Convert:
svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@1553
Message:

small changes

Location:
src/work/marci/lp
Files:
2 edited

Legend:

Unmodified
Added
Removed
  • src/work/marci/lp/lp_solver_base.h

    r1144 r1152  
    11// -*- c++ -*-
    2 #ifndef LEMON_LP_SOLVER_WRAPPER_H
    3 #define LEMON_LP_SOLVER_WRAPPER_H
     2#ifndef LEMON_LP_SOLVER_BASE_H
     3#define LEMON_LP_SOLVER_BASE_H
    44
    55///\ingroup misc
    66///\file
    7 ///\brief Dijkstra algorithm.
    87
    98// #include <stdio.h>
     
    2524#include <utility>
    2625
    27 //#include <lemon/list_graph.h>
    2826#include <lemon/invalid.h>
    2927#include <expression.h>
    30 //#include <bfs_dfs.h>
    3128//#include <stp.h>
    3229//#include <lemon/max_flow.h>
     
    6865    int classNum() const { return tips.size(); }
    6966    /// This lemon style iterator iterates through a class.
    70     class ClassIt;
     67    class Class;
    7168    /// Constructor. The number of classes is to be given which is fixed
    7269    /// over the life of the container.
     
    8077    }
    8178  protected:
    82     void befuz(ClassIt it, int class_id) {
     79    void befuz(Class it, int class_id) {
    8380      if (tips[class_id].first==-1) {
    8481        if (tips[class_id].last==-1) {
     
    9390      }
    9491    }
    95     void kifuz(ClassIt it, int class_id) {
     92    void kifuz(Class it, int class_id) {
    9693      if (tips[class_id].first==it.i) {
    9794        if (tips[class_id].last==it.i) {
     
    114111    /// A new element with data \c t is pushed into the vector and into class
    115112    /// \c class_id.
    116     ClassIt push_back(const T& t, int class_id) {
     113    Class push_back(const T& t, int class_id) {
    117114      Node n;
    118115      n.data=t;
     
    123120    }
    124121    /// A member is moved to an other class.
    125     void set(ClassIt it, int old_class_id, int new_class_id) {
     122    void set(Class it, int old_class_id, int new_class_id) {
    126123      kifuz(it.i, old_class_id);
    127124      befuz(it.i, new_class_id);
    128125    }
    129126    /// Returns the data pointed by \c it.
    130     T& operator[](ClassIt it) { return nodes[it.i].data; }
     127    T& operator[](Class it) { return nodes[it.i].data; }
    131128    /// Returns the data pointed by \c it.
    132     const T& operator[](ClassIt it) const { return nodes[it.i].data; }
     129    const T& operator[](Class it) const { return nodes[it.i].data; }
    133130    ///.
    134     class ClassIt {
     131    class Class {
    135132      friend class IterablePartition;
    136133    protected:
     
    138135    public:
    139136      /// Default constructor.
    140       ClassIt() { }
     137      Class() { }
    141138      /// This constructor constructs an iterator which points
    142139      /// to the member of th container indexed by the integer _i.
    143       ClassIt(const int& _i) : i(_i) { }
     140      Class(const int& _i) : i(_i) { }
    144141      /// Invalid constructor.
    145       ClassIt(const Invalid&) : i(-1) { }
    146       friend bool operator<(const ClassIt& x, const ClassIt& y);
     142      Class(const Invalid&) : i(-1) { }
     143      friend bool operator<(const Class& x, const Class& y);
    147144      friend std::ostream& operator<<(std::ostream& os,
    148                                       const ClassIt& it);
     145                                      const Class& it);
     146      bool operator==(const Class& node) const {return i == node.i;}
     147      bool operator!=(const Class& node) const {return i != node.i;}
    149148    };
    150     friend bool operator<(const ClassIt& x, const ClassIt& y) {
     149    friend bool operator<(const Class& x, const Class& y) {
    151150      return (x.i < y.i);
    152151    }
    153152    friend std::ostream& operator<<(std::ostream& os,
    154                                     const ClassIt& it) {
     153                                    const Class& it) {
    155154      os << it.i;
    156155      return os;
    157156    }
    158157    /// First member of class \c class_id.
    159     ClassIt& first(ClassIt& it, int class_id) const {
     158    Class& first(Class& it, int class_id) const {
    160159      it.i=tips[class_id].first;
    161160      return it;
    162161    }
    163162    /// Next member.
    164     ClassIt& next(ClassIt& it) const {
     163    Class& next(Class& it) const {
    165164      it.i=nodes[it.i].next;
    166165      return it;
    167166    }
    168167    /// True iff the iterator is valid.
    169     bool valid(const ClassIt& it) const { return it.i!=-1; }
     168    bool valid(const Class& it) const { return it.i!=-1; }
     169
     170    class ClassIt : public Class {
     171      const IterablePartition* iterable_partition;
     172    public:
     173      ClassIt() { }
     174      ClassIt(Invalid i) : Class(i) { }
     175      ClassIt(const IterablePartition& _iterable_partition,
     176              const int& i) : iterable_partition(&_iterable_partition) {
     177        _iterable_partition.first(*this, i);
     178      }
     179      ClassIt(const IterablePartition& _iterable_partition,
     180              const Class& _class) :
     181        Class(_class), iterable_partition(&_iterable_partition) { }
     182      ClassIt& operator++() {
     183        iterable_partition->next(*this);
     184        return *this;
     185      }
     186    };
     187
    170188  };
    171189
     
    192210
    193211    /// \e
     212    typedef IterablePartition<int> Rows;
     213    /// \e
     214    typedef IterablePartition<int> Cols;
     215    /// \e
    194216    typedef _Value Value;
    195217    /// \e
    196     typedef IterablePartition<int>::ClassIt Row;
    197     /// \e
    198     typedef IterablePartition<int>::ClassIt Col;
     218    typedef Rows::Class Row;
     219    /// \e
     220    typedef Cols::Class Col;
    199221  public:
    200222    /// \e
     
    247269    /// \e
    248270    virtual void solveDualSimplex() = 0;
    249     /// \e
    250271
    251272    //SOLUTION RETRIEVING
     
    306327    virtual void _getRowCoeffs(int i,
    307328                               std::vector<std::pair<int, _Value> >& coeffs) = 0;
     329    /// \e
    308330    virtual void _setColCoeffs(int i,
    309331                               const std::vector<std::pair<int, _Value> >& coeffs) = 0;
     
    312334    virtual void _getColCoeffs(int i,
    313335                               std::vector<std::pair<int, _Value> >& coeffs) = 0;
    314   public:
    315     /// \e
    316     enum Bound { FREE, LOWER, UPPER, DOUBLE, FIXED };
     336    /// \e
     337    virtual void _setCoeff(int col, int row, _Value value) = 0;
     338    /// \e
     339    virtual _Value _getCoeff(int col, int row) = 0;
     340    //  public:
     341    //    /// \e
     342    //    enum Bound { FREE, LOWER, UPPER, DOUBLE, FIXED };
    317343  protected:
    318344    /// \e
     
    357383    virtual _Value _getRowUpperBound(int i) = 0;
    358384    /// \e
    359     virtual void _setObjCoef(int i, _Value obj_coef) = 0;
    360     /// \e
    361     virtual _Value _getObjCoef(int i) = 0;
     385    virtual void _setObjCoeff(int i, _Value obj_coef) = 0;
     386    /// \e
     387    virtual _Value _getObjCoeff(int i) = 0;
    362388   
    363389    //SOLUTION RETRIEVING
     
    432458    }
    433459    /// \e
     460    void setCoeff(Col col, Row row, _Value value) {
     461      _setCoeff(col_iter_map[col], row_iter_map[row], value);
     462    }
     463    /// \e
     464    _Value getCoeff(Col col, Row row) {
     465      return _getCoeff(col_iter_map[col], row_iter_map[row], value);
     466    }
     467    /// \e
    434468    void setColLowerBound(Col col, _Value lo) {
    435469      _setColLowerBound(col_iter_map[col], lo);
     
    464498    }
    465499    /// \e
    466     void setObjCoef(const Col& col, _Value obj_coef) {
    467       _setObjCoef(col_iter_map[col], obj_coef);
    468     }
    469     /// \e
    470     _Value getObjCoef(const Col& col) {
    471       return _getObjCoef(col_iter_map[col]);
     500    void setObjCoeff(const Col& col, _Value obj_coef) {
     501      _setObjCoeff(col_iter_map[col], obj_coef);
     502    }
     503    /// \e
     504    _Value getObjCoeff(const Col& col) {
     505      return _getObjCoeff(col_iter_map[col]);
    472506    }
    473507
     
    552586    }
    553587    /// \e
    554     /// \bug ez igy nem jo
    555588    void setObjCoeffs(const Expression& expr) {
     589      // writing zero everywhere
     590      for(Cols::ClassIt it(col_iter_map, VALID_CLASS); it!=INVALID; ++it)
     591        setObjCoeff(it, 0.0);
     592      // writing the data needed
    556593      for(typename Expression::Data::const_iterator i=expr.data.begin();
    557594          i!=expr.data.end(); ++i) {
    558         setObjCoef((*i).first, (*i).second);
     595        setObjCoeff((*i).first, (*i).second);
    559596      }
    560597    }
     
    562599    /// This routine modifies \c expr by only adding to it.
    563600    void getObjCoeffs(Expression& expr) {
    564       /// FIXME not yet implemented
     601      for(Cols::ClassIt it(col_iter_map, VALID_CLASS); it!=INVALID; ++it)
     602        expr+=getObjCoeff(it)*it;
     603    }
     604    //@}
     605
     606
     607    /*! @name MIP functions and types (public members)
     608    */
     609    //@{
     610  public:
     611    /// \e
     612    virtual void solveBandB() = 0;
     613    /// \e
     614    virtual void setLP() = 0;
     615    /// \e
     616    virtual void setMIP() = 0;
     617  protected:
     618   /// \e
     619    virtual void _setColCont(int i) = 0;
     620    /// \e
     621    virtual void _setColInt(int i) = 0;
     622  public:
     623    /// \e
     624    void setColCont(Col col) {
     625      _setColCont(col_iter_map[col]);
     626    }
     627    /// \e
     628    void setColInt(Col col) {
     629      _setColInt(col_iter_map[col]);
    565630    }
    566631    //@}
     
    691756      rows[1]=i;
    692757      lpx_del_rows(lp, 1, rows);
     758    }
     759    void _setCoeff(int col, int row, double value) {
     760      /// FIXME not yet implemented
     761    }
     762    double _getCoeff(int col, int row) {
     763      /// FIXME not yet implemented
     764      return 0.0;
    693765    }
    694766    virtual void _setColLowerBound(int i, double lo) {
     
    9291001    }
    9301002    /// \e
    931     virtual double _getObjCoef(int i) {
     1003    virtual double _getObjCoeff(int i) {
    9321004      return lpx_get_obj_coef(lp, i);
    9331005    }
    9341006    /// \e
    935     virtual void _setObjCoef(int i, double obj_coef) {
     1007    virtual void _setObjCoeff(int i, double obj_coef) {
    9361008      lpx_set_obj_coef(lp, i, obj_coef);
    9371009    }
     
    9431015    /// \e
    9441016    void solveDualSimplex() { lpx_simplex(lp); }
    945     /// \e
    9461017  protected:
    9471018    virtual double _getPrimal(int i) {
     
    10161087      }
    10171088    }
     1089
     1090    // MIP
     1091    /// \e
     1092    void solveBandB() { lpx_integer(lp); }
     1093    /// \e
     1094    void setLP() { lpx_set_class(lp, LPX_LP); }
     1095    /// \e
     1096    void setMIP() { lpx_set_class(lp, LPX_MIP); }
     1097  protected:
     1098    /// \e
     1099    void _setColCont(int i) {lpx_set_col_kind(lp, i, LPX_CV); }
     1100    /// \e
     1101    void _setColInt(int i) {lpx_set_col_kind(lp, i, LPX_IV); }
    10181102  };
    10191103 
     
    10221106} //namespace lemon
    10231107
    1024 #endif //LEMON_LP_SOLVER_WRAPPER_H
     1108#endif //LEMON_LP_SOLVER_BASE_H
  • src/work/marci/lp/max_flow_expression.cc

    r1144 r1152  
    8383  lp.solveSimplex();
    8484  cout << "elapsed time: " << ts << endl;
     85//   cout << "rows:" << endl;
     86//   for (
     87//        LPSolver::Rows::ClassIt i(lp.row_iter_map, 0);
     88//        i!=INVALID;
     89//        ++i) {
     90//     cout << i << " ";
     91//   }
     92//   cout << endl;
     93//   cout << "cols:" << endl;
     94//   for (
     95//        LPSolver::Cols::ClassIt i(lp.col_iter_map, 0);
     96//        i!=INVALID;
     97//        ++i) {
     98//     cout << i << " ";
     99//   }
     100//   cout << endl;
     101  lp.setMIP();
     102  cout << "elapsed time: " << ts << endl;
     103  for (LPSolver::Cols::ClassIt it(lp.col_iter_map ,1); it!=INVALID; ++it) {
     104    lp.setColInt(it);
     105  }
     106  cout << "elapsed time: " << ts << endl;
     107  lp.solveBandB();
     108  cout << "elapsed time: " << ts << endl;
    85109}
Note: See TracChangeset for help on using the changeset viewer.