COIN-OR::LEMON - Graph Library

Changeset 1081:c0ad2673b11f in lemon-0.x for src/work


Ignore:
Timestamp:
01/14/05 14:17:16 (20 years ago)
Author:
marci
Branch:
default
Phase:
public
Convert:
svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@1477
Message:

more precise distinction 'tween low and high level lp interfaces

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

Legend:

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

    r1074 r1081  
    3737
    3838namespace lemon {
    39 
    4039 
    4140  /// \addtogroup misc
     
    185184    /// \e
    186185    virtual ~LPSolverBase() { }
     186
     187    //MATRIX INDEPEDENT MANIPULATING FUNCTIONS
     188
     189  public:
    187190    /// \e
    188191    virtual void setMinimize() = 0;
    189192    /// \e
    190193    virtual void setMaximize() = 0;
     194
     195    //LOW LEVEL INTERFACE, MATRIX MANIPULATING FUNCTIONS
     196
    191197  protected:
    192198    /// \e
     
    194200    /// \e
    195201    virtual int _addCol() = 0;
     202    /// \e
     203    virtual void _setRowCoeffs(int i,
     204                               std::vector<std::pair<int, double> > coeffs) = 0;
     205    /// \e
     206    virtual void _setColCoeffs(int i,
     207                               std::vector<std::pair<int, double> > coeffs) = 0;
     208    /// \e
     209    virtual void _eraseCol(int i) = 0;
     210    /// \e
     211    virtual void _eraseRow(int i) = 0;
     212  public:
     213    /// \e
     214    enum Bound { FREE, LOWER, UPPER, DOUBLE, FIXED };
     215  protected:
     216    /// \e
     217    virtual void _setColBounds(int i, Bound bound,
     218                               _Value lo, _Value up) = 0;
     219    /// \e
     220    virtual void _setRowBounds(int i, Bound bound,
     221                               _Value lo, _Value up) = 0;
     222    /// \e
     223    virtual void _setObjCoef(int i, _Value obj_coef) = 0;
     224    /// \e
     225    virtual _Value _getObjCoef(int i) = 0;
     226
     227    //LOW LEVEL, SOLUTION RETRIEVING FUNCTIONS
     228
     229  protected:
     230    virtual _Value _getPrimal(int i) = 0;
     231
     232    //HIGH LEVEL INTERFACE, MATRIX MANIPULATING FUNTIONS
     233
    196234  public:
    197235    /// \e
     
    222260    }
    223261    /// \e
    224     virtual void setRowCoeffs(int i,
    225                               std::vector<std::pair<int, double> > coeffs) = 0;
    226     /// \e
    227     virtual void setColCoeffs(int i,
    228                               std::vector<std::pair<int, double> > coeffs) = 0;
    229     /// \e
    230262    template <typename Begin, typename End>
    231263    void setRowCoeffs(RowIt row_it, Begin begin, End end) {
     
    235267                         make_pair(col_iter_map[begin->first], begin->second));
    236268      }
    237       setRowCoeffs(row_iter_map[row_it], coeffs);
     269      _setRowCoeffs(row_iter_map[row_it], coeffs);
    238270    }
    239271    /// \e
     
    245277                         make_pair(row_iter_map[begin->first], begin->second));
    246278      }
    247       setColCoeffs(col_iter_map[col_it], coeffs);
    248     }
    249     /// temporally, glpk style indexing
    250     //virtual void setRowCoeffs(RowIt row_it, int num,
    251     //                int* indices, _Value* doubles) = 0;
    252     //pair<RowIt, _Value>-bol kell megadni egy std range-et
    253     /// \e
    254     //    virtual void seColCoeffs(int i,
    255     //                        std::vector<std::pair<int, double> > coeffs) = 0;
    256     /// \e
    257 //     template <typename Begin, typename End>
    258 //     void setRowCoeffs(RowIt row_it, Begin begin, End end) {
    259 //       int mem_length=1+colNum();
    260 //       int* indices = new int[mem_length];
    261 //       _Value* doubles = new _Value[mem_length];
    262 //       int length=0;
    263 //       for ( ; begin!=end; ++begin) {
    264 //      ++length;
    265 //      indices[length]=col_iter_map[begin->first];
    266 //      doubles[length]=begin->second;
    267 //       }
    268 //       setRowCoeffs(row_it, length, indices, doubles);
    269 //       delete [] indices;
    270 //       delete [] doubles;
    271 //     }
    272     /// temporally, glpk style indexing
    273     //virtual void setColCoeffs(ColIt col_it, int num,
    274     //                        int* indices, _Value* doubles) = 0;
    275     //pair<ColIt, _Value>-bol kell megadni egy std range-et
    276     /// \e
    277 //     template <typename Begin, typename End>
    278 //     void setColCoeffs(ColIt col_it, Begin begin, End end) {
    279 //       int mem_length=1+rowNum();
    280 //       int* indices = new int[mem_length];
    281 //       _Value* doubles = new _Value[mem_length];
    282 //       int length=0;
    283 //       for ( ; begin!=end; ++begin) {
    284 //      ++length;
    285 //      indices[length]=row_iter_map[begin->first];
    286 //      doubles[length]=begin->second;
    287 //       }
    288 //       setColCoeffs(col_it, length, indices, doubles);
    289 //       delete [] indices;
    290 //       delete [] doubles;
    291 //     }
    292   protected:
    293     /// \e
    294     virtual void _eraseCol(int i) = 0;
    295     /// \e
    296     virtual void _eraseRow(int i) = 0;
    297   public:
     279      _setColCoeffs(col_iter_map[col_it], coeffs);
     280    }
    298281    /// \e
    299282    void eraseCol(const ColIt& col_it) {
     
    323306    }
    324307    /// \e
    325     virtual void setColBounds(const ColIt& col_it, int bound_type,
    326                               _Value lo, _Value up) =0;
    327     /// \e
    328     virtual _Value getObjCoef(const ColIt& col_it) = 0;
    329     /// \e
    330     virtual void setRowBounds(const RowIt& row_it, int bound_type,
    331                               _Value lo, _Value up) = 0;
    332     /// \e
    333     virtual void setObjCoef(const ColIt& col_it, _Value obj_coef) = 0;
     308    void setColBounds(const ColIt& col_it, Bound bound,
     309                      _Value lo, _Value up) {
     310      _setColBounds(col_iter_map[col_it], bound, lo, up);
     311    }
     312    /// \e
     313    void setRowBounds(const RowIt& row_it, Bound bound,
     314                      _Value lo, _Value up) {
     315      _setRowBounds(row_iter_map[row_it], bound, lo, up);
     316    }
     317    /// \e
     318    void setObjCoef(const ColIt& col_it, _Value obj_coef) {
     319      _setObjCoef(col_iter_map[col_it], obj_coef);
     320    }
     321    /// \e
     322    _Value getObjCoef(const ColIt& col_it) {
     323      return _getObjCoef(col_iter_map[col_it]);
     324    }
     325
     326    //SOLVER FUNCTIONS
     327
    334328    /// \e
    335329    virtual void solveSimplex() = 0;
     
    339333    virtual void solveDualSimplex() = 0;
    340334    /// \e
    341     virtual _Value getPrimal(const ColIt& col_it) = 0;
     335
     336    //HIGH LEVEL, SOLUTION RETRIEVING FUNCTIONS
     337
     338  public:
     339    _Value getPrimal(const ColIt& col_it) {
     340      return _getPrimal(col_iter_map[col_it]);
     341    }
    342342    /// \e
    343343    virtual _Value getObjVal() = 0;
     344
     345    //OTHER FUNCTIONS
     346
    344347    /// \e
    345348    virtual int rowNum() const = 0;
     
    376379  /// solvers, i.e. it makes possible to write algorithms using LP's,
    377380  /// in which the solver can be changed to an other one easily.
    378   class LPSolverWrapper : public LPSolverBase<double> {
     381  class LPGLPK : public LPSolverBase<double> {
    379382  public:
    380383    typedef LPSolverBase<double> Parent;
     
    386389  public:
    387390    /// \e
    388     LPSolverWrapper() : Parent(),
     391    LPGLPK() : Parent(),
    389392                        lp(lpx_create_prob()) {
    390393      lpx_set_int_parm(lp, LPX_K_DUAL, 1);
    391394    }
    392395    /// \e
    393     ~LPSolverWrapper() {
     396    ~LPGLPK() {
    394397      lpx_delete_prob(lp);
    395398    }
     399
     400    //MATRIX INDEPEDENT MANIPULATING FUNCTIONS
     401
    396402    /// \e
    397403    void setMinimize() {
     
    402408      lpx_set_obj_dir(lp, LPX_MAX);
    403409    }
     410
     411    //LOW LEVEL INTERFACE, MATRIX MANIPULATING FUNCTIONS
     412
    404413  protected:
    405414    /// \e
     
    411420      return lpx_add_rows(lp, 1);
    412421    }
    413   public:
    414     using Parent::setRowCoeffs;
    415     /// \e
    416     virtual void setRowCoeffs(int i,
    417                               std::vector<std::pair<int, double> > coeffs) {
     422    /// \e
     423    virtual void _setRowCoeffs(int i,
     424                               std::vector<std::pair<int, double> > coeffs) {
    418425      int mem_length=1+colNum();
    419426      int* indices = new int[mem_length];
     
    425432        indices[length]=it->first;
    426433        doubles[length]=it->second;
    427         std::cout << "  " << indices[length] << " "
    428                   << doubles[length] << std::endl;
    429       }
    430       std::cout << i << " " << length << std::endl;
     434//      std::cout << "  " << indices[length] << " "
     435//                << doubles[length] << std::endl;
     436      }
     437//      std::cout << i << " " << length << std::endl;
    431438      lpx_set_mat_row(lp, i, length, indices, doubles);
    432439      delete [] indices;
     
    434441    }
    435442    /// \e
    436     virtual void setColCoeffs(int i,
    437                               std::vector<std::pair<int, double> > coeffs) {
     443    virtual void _setColCoeffs(int i,
     444                               std::vector<std::pair<int, double> > coeffs) {
    438445      int mem_length=1+rowNum();
    439446      int* indices = new int[mem_length];
     
    450457      delete [] doubles;
    451458    }
    452 //     /// \e
    453 //     /// temporally, glpk style indexing
    454 //     virtual void setRowCoeffs(RowIt row_it, int num,
    455 //                            int* indices, _Value* doubles) = 0;
    456 //     //pair<RowIt, _Value>-bol kell megadni egy std range-et
    457 //     /// \e
    458 //     template <typename Begin, typename End>
    459 //     void setRowCoeffs(RowIt row_it, Begin begin, End end) {
    460 //       int mem_length=1+colNum();
    461 //       int* indices = new int[mem_length];
    462 //       _Value* doubles = new _Value[mem_length];
    463 //       int length=0;
    464 //       for ( ; begin!=end; ++begin) {
    465 //      ++length;
    466 //      indices[length]=col_iter_map[begin->first];
    467 //      doubles[length]=begin->second;
    468 //       }
    469 //       setRowCoeffs(row_it, length, indices, doubles);
    470 //       delete [] indices;
    471 //       delete [] doubles;
    472 //     }
    473 //     void setRowCoeffs(RowIt row_it, int length,
    474 //                    int* indices, double* doubles) {
    475 //       lpx_set_mat_row(lp, row_iter_map[row_it], length, indices, doubles);
    476 //     }
    477 //     using Parent::setColCoeffs;
    478 //     void setColCoeffs(ColIt col_it, int length,
    479 //                    int* indices, double* doubles) {
    480 //       lpx_set_mat_col(lp, col_iter_map[col_it], length, indices, doubles);
    481 //     }
    482     //     //pair<RowIt, double>-bol kell megadni egy std range-et
    483     //     /// \e
    484     //     template <typename Begin, typename End>
    485     //     void setColCoeffs(const ColIt& col_it,
    486     //                Begin begin, End end) {
    487     //       int mem_length=1+lpx_get_num_rows(lp);
    488     //       int* indices = new int[mem_length];
    489     //       double* doubles = new double[mem_length];
    490     //       int length=0;
    491     //       for ( ; begin!=end; ++begin) {
    492     //  ++length;
    493     //  indices[length]=row_iter_map[begin->first];
    494     //  doubles[length]=begin->second;
    495     //       }
    496     //       lpx_set_mat_col(lp, col_iter_map[col_it], length, indices, doubles);
    497     //       delete [] indices;
    498     //       delete [] doubles;
    499     //     }
    500     //     //pair<ColIt, double>-bol kell megadni egy std range-et
    501     //     /// \e
    502     //     template <typename Begin, typename End>
    503     //     void setRowCoeffs(const RowIt& row_it,
    504     //                Begin begin, End end) {
    505     //       int mem_length=1+lpx_get_num_cols(lp);
    506     //       int* indices = new int[mem_length];
    507     //       double* doubles = new double[mem_length];
    508     //       int length=0;
    509     //       for ( ; begin!=end; ++begin) {
    510     //  ++length;
    511     //  indices[length]=col_iter_map[begin->first];
    512     //  doubles[length]=begin->second;
    513     //       }
    514     //       lpx_set_mat_row(lp, row_iter_map[row_it], length, indices, doubles);
    515     //       delete [] indices;
    516     //       delete [] doubles;
    517     //     }
    518     /// \e
    519   protected:
     459    /// \e
    520460    virtual void _eraseCol(int i) {
    521461      int cols[2];
     
    528468      lpx_del_rows(lp, 1, rows);
    529469    }
    530   public:
    531     /// \e
    532     void setColBounds(const ColIt& col_it, int bound_type,
    533                       double lo, double up) {
    534       lpx_set_col_bnds(lp, col_iter_map[col_it], bound_type, lo, up);
    535     }
    536     /// \e
    537     double getObjCoef(const ColIt& col_it) {
    538       return lpx_get_obj_coef(lp, col_iter_map[col_it]);
    539     }
    540     /// \e
    541     void setRowBounds(const RowIt& row_it, int bound_type,
    542                       double lo, double up) {
    543       lpx_set_row_bnds(lp, row_iter_map[row_it], bound_type, lo, up);
    544     }
    545     /// \e
    546     void setObjCoef(const ColIt& col_it, double obj_coef) {
    547       lpx_set_obj_coef(lp, col_iter_map[col_it], obj_coef);
    548     }
     470    virtual void _setColBounds(int i, Bound bound,
     471                               double lo, double up) {
     472      switch (bound) {
     473      case FREE:
     474        lpx_set_col_bnds(lp, i, LPX_FR, lo, up);
     475        break;
     476      case LOWER:
     477        lpx_set_col_bnds(lp, i, LPX_LO, lo, up);
     478        break;
     479      case UPPER:
     480        lpx_set_col_bnds(lp, i, LPX_UP, lo, up);
     481        break;
     482      case DOUBLE:
     483        lpx_set_col_bnds(lp, i, LPX_DB, lo, up);
     484        break;
     485      case FIXED:
     486        lpx_set_col_bnds(lp, i, LPX_FX, lo, up);
     487        break;
     488      }
     489    }
     490    virtual void _setRowBounds(int i, Bound bound,
     491                               double lo, double up) {
     492      switch (bound) {
     493      case FREE:
     494        lpx_set_row_bnds(lp, i, LPX_FR, lo, up);
     495        break;
     496      case LOWER:
     497        lpx_set_row_bnds(lp, i, LPX_LO, lo, up);
     498        break;
     499      case UPPER:
     500        lpx_set_row_bnds(lp, i, LPX_UP, lo, up);
     501        break;
     502      case DOUBLE:
     503        lpx_set_row_bnds(lp, i, LPX_DB, lo, up);
     504        break;
     505      case FIXED:
     506        lpx_set_row_bnds(lp, i, LPX_FX, lo, up);
     507        break;
     508      }
     509    }
     510  protected:
     511    /// \e
     512    virtual double _getObjCoef(int i) {
     513      return lpx_get_obj_coef(lp, i);
     514    }
     515    /// \e
     516    virtual void _setObjCoef(int i, double obj_coef) {
     517      lpx_set_obj_coef(lp, i, obj_coef);
     518    }
     519  public:
    549520    /// \e
    550521    void solveSimplex() { lpx_simplex(lp); }
     
    554525    void solveDualSimplex() { lpx_simplex(lp); }
    555526    /// \e
    556     double getPrimal(const ColIt& col_it) {
    557       return lpx_get_col_prim(lp, col_iter_map[col_it]);
    558     }
     527  protected:
     528    virtual double _getPrimal(int i) {
     529      return lpx_get_col_prim(lp, i);
     530    }
     531  public:
    559532    /// \e
    560533    double getObjVal() { return lpx_get_obj_val(lp); }
  • src/work/marci/lp/min_cost_gen_flow.h

    r1074 r1081  
    2222  class PrimalMap {
    2323  protected:
    24     LPSolverWrapper* lp;
     24    LPGLPK* lp;
    2525    EdgeIndexMap* edge_index_map;
    2626  public:
    27     PrimalMap(LPSolverWrapper& _lp, EdgeIndexMap& _edge_index_map) :
     27    PrimalMap(LPGLPK& _lp, EdgeIndexMap& _edge_index_map) :
    2828      lp(&_lp), edge_index_map(&_edge_index_map) { }
    2929    double operator[](Edge e) const {
     
    212212    }
    213213    void runByLP() {
    214       typedef LPSolverWrapper LPSolver;
     214      typedef LPGLPK LPSolver;
    215215      LPSolver lp;
    216216      lp.setMinimize();
     
    224224        edge_index_map.set(e, col_it);
    225225        if (lcapacity[e]==capacity[e])
    226           lp.setColBounds(col_it, LPX_FX, lcapacity[e], capacity[e]);
     226          lp.setColBounds(col_it, LPSolver::FIXED, lcapacity[e], capacity[e]);
    227227        else
    228           lp.setColBounds(col_it, LPX_DB, lcapacity[e], capacity[e]);
     228          lp.setColBounds(col_it, LPSolver::DOUBLE, lcapacity[e], capacity[e]);
    229229        lp.setObjCoef(col_it, cost[e]);
    230230      }
     
    233233           lp.col_iter_map.valid(col_it);
    234234           lp.col_iter_map.next(col_it)) {
    235         std::cout << "ize " << lp.col_iter_map[col_it] << std::endl;
     235//      std::cout << "ize " << lp.col_iter_map[col_it] << std::endl;
    236236      }
    237237      for (typename Graph::NodeIt n(g); n!=INVALID; ++n) {
     
    251251        }
    252252        //std::cout << std::endl;
    253         std::cout << " " << g.id(n) << " " << row.size() << std::endl;
     253        //std::cout << " " << g.id(n) << " " << row.size() << std::endl;
    254254        lp.setRowCoeffs(row_it, row.begin(), row.end());
    255         lp.setRowBounds(row_it, LPX_FX, 0.0, 0.0);
     255        lp.setRowBounds(row_it, LPSolver::FIXED, 0.0, 0.0);
    256256      }
    257257      lp.solveSimplex();
Note: See TracChangeset for help on using the changeset viewer.