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

Timestamp:

02/16/05 22:40:16 (20 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:

• lp_solver_base.h (modified) (22 diffs)
• max_flow_expression.cc (modified) (1 diff)

src/work/marci/lp/lp_solver_base.h

@@ -1 +1 @@
 // -*- c++ -*-
-#ifndef LEMON_LP_SOLVER_WRAPPER_H
-#define LEMON_LP_SOLVER_WRAPPER_H
+#ifndef LEMON_LP_SOLVER_BASE_H
+#define LEMON_LP_SOLVER_BASE_H
 
 ///\ingroup misc
 ///\file
-///\brief Dijkstra algorithm.
 
 // #include <stdio.h>
@@ -25 +24 @@
 #include <utility>
 
-//#include <lemon/list_graph.h>
 #include <lemon/invalid.h>
 #include <expression.h>
-//#include <bfs_dfs.h>
 //#include <stp.h>
 //#include <lemon/max_flow.h>
@@ -68 +65 @@
     int classNum() const { return tips.size(); }
     /// This lemon style iterator iterates through a class. 
-    class ClassIt;
+    class Class;
     /// Constructor. The number of classes is to be given which is fixed 
     /// over the life of the container. 
@@ -80 +77 @@
     }
   protected:
-    void befuz(ClassIt it, int class_id) {
+    void befuz(Class it, int class_id) {
       if (tips[class_id].first==-1) {
         if (tips[class_id].last==-1) {
@@ -93 +90 @@
       }
     }
-    void kifuz(ClassIt it, int class_id) {
+    void kifuz(Class it, int class_id) {
       if (tips[class_id].first==it.i) {
         if (tips[class_id].last==it.i) {
@@ -114 +111 @@
     /// A new element with data \c t is pushed into the vector and into class 
     /// \c class_id.
-    ClassIt push_back(const T& t, int class_id) { 
+    Class push_back(const T& t, int class_id) { 
       Node n;
       n.data=t;
@@ -123 +120 @@
     }
     /// A member is moved to an other class.
-    void set(ClassIt it, int old_class_id, int new_class_id) {
+    void set(Class it, int old_class_id, int new_class_id) {
       kifuz(it.i, old_class_id);
       befuz(it.i, new_class_id);
     }
     /// Returns the data pointed by \c it.
-    T& operator[](ClassIt it) { return nodes[it.i].data; }
+    T& operator[](Class it) { return nodes[it.i].data; }
     /// Returns the data pointed by \c it.
-    const T& operator[](ClassIt it) const { return nodes[it.i].data; }
+    const T& operator[](Class it) const { return nodes[it.i].data; }
     ///.
-    class ClassIt {
+    class Class {
       friend class IterablePartition;
     protected:
@@ -138 +135 @@
     public:
       /// Default constructor.
-      ClassIt() { }
+      Class() { }
       /// This constructor constructs an iterator which points
       /// to the member of th container indexed by the integer _i.
-      ClassIt(const int& _i) : i(_i) { }
+      Class(const int& _i) : i(_i) { }
       /// Invalid constructor.
-      ClassIt(const Invalid&) : i(-1) { }
-      friend bool operator<(const ClassIt& x, const ClassIt& y);
+      Class(const Invalid&) : i(-1) { }
+      friend bool operator<(const Class& x, const Class& y);
       friend std::ostream& operator<<(std::ostream& os, 
-                                      const ClassIt& it);
+                                      const Class& it);
+      bool operator==(const Class& node) const {return i == node.i;}
+      bool operator!=(const Class& node) const {return i != node.i;}
     };
-    friend bool operator<(const ClassIt& x, const ClassIt& y) {
+    friend bool operator<(const Class& x, const Class& y) {
       return (x.i < y.i);
     }
     friend std::ostream& operator<<(std::ostream& os, 
-                                    const ClassIt& it) {
+                                    const Class& it) {
       os << it.i;
       return os;
     }
     /// First member of class \c class_id.
-    ClassIt& first(ClassIt& it, int class_id) const {
+    Class& first(Class& it, int class_id) const {
       it.i=tips[class_id].first;
       return it;
     }
     /// Next member.
-    ClassIt& next(ClassIt& it) const {
+    Class& next(Class& it) const {
       it.i=nodes[it.i].next;
       return it;
     }
     /// True iff the iterator is valid.
-    bool valid(const ClassIt& it) const { return it.i!=-1; }
+    bool valid(const Class& it) const { return it.i!=-1; }
+
+    class ClassIt : public Class {
+      const IterablePartition* iterable_partition;
+    public:
+      ClassIt() { }
+      ClassIt(Invalid i) : Class(i) { }
+      ClassIt(const IterablePartition& _iterable_partition, 
+              const int& i) : iterable_partition(&_iterable_partition) {
+        _iterable_partition.first(*this, i);
+      }
+      ClassIt(const IterablePartition& _iterable_partition, 
+              const Class& _class) : 
+        Class(_class), iterable_partition(&_iterable_partition) { }
+      ClassIt& operator++() {
+        iterable_partition->next(*this);
+        return *this;
+      }
+    };
+
   };
 
@@ -192 +210 @@
 
     /// \e
+    typedef IterablePartition<int> Rows;
+    /// \e
+    typedef IterablePartition<int> Cols;
+    /// \e
     typedef _Value Value;
     /// \e
-    typedef IterablePartition<int>::ClassIt Row;
-    /// \e
-    typedef IterablePartition<int>::ClassIt Col;
+    typedef Rows::Class Row;
+    /// \e
+    typedef Cols::Class Col;
   public:
     /// \e
@@ -247 +269 @@
     /// \e
     virtual void solveDualSimplex() = 0;
-    /// \e
 
     //SOLUTION RETRIEVING
@@ -306 +327 @@
     virtual void _getRowCoeffs(int i, 
                                std::vector<std::pair<int, _Value> >& coeffs) = 0;
+    /// \e
     virtual void _setColCoeffs(int i, 
                                const std::vector<std::pair<int, _Value> >& coeffs) = 0;
@@ -312 +334 @@
     virtual void _getColCoeffs(int i, 
                                std::vector<std::pair<int, _Value> >& coeffs) = 0;
-  public:
-    /// \e
-    enum Bound { FREE, LOWER, UPPER, DOUBLE, FIXED };
+    /// \e
+    virtual void _setCoeff(int col, int row, _Value value) = 0;
+    /// \e
+    virtual _Value _getCoeff(int col, int row) = 0;
+    //  public:
+    //    /// \e
+    //    enum Bound { FREE, LOWER, UPPER, DOUBLE, FIXED };
   protected:
     /// \e
@@ -357 +383 @@
     virtual _Value _getRowUpperBound(int i) = 0;
     /// \e
-    virtual void _setObjCoef(int i, _Value obj_coef) = 0;
-    /// \e
-    virtual _Value _getObjCoef(int i) = 0;
+    virtual void _setObjCoeff(int i, _Value obj_coef) = 0;
+    /// \e
+    virtual _Value _getObjCoeff(int i) = 0;
     
     //SOLUTION RETRIEVING
@@ -432 +458 @@
     }
     /// \e
+    void setCoeff(Col col, Row row, _Value value) {
+      _setCoeff(col_iter_map[col], row_iter_map[row], value);
+    }
+    /// \e
+    _Value getCoeff(Col col, Row row) {
+      return _getCoeff(col_iter_map[col], row_iter_map[row], value);
+    }
+    /// \e
     void setColLowerBound(Col col, _Value lo) {
       _setColLowerBound(col_iter_map[col], lo);
@@ -464 +498 @@
     }
     /// \e
-    void setObjCoef(const Col& col, _Value obj_coef) {
-      _setObjCoef(col_iter_map[col], obj_coef);
-    }
-    /// \e
-    _Value getObjCoef(const Col& col) {
-      return _getObjCoef(col_iter_map[col]);
+    void setObjCoeff(const Col& col, _Value obj_coef) {
+      _setObjCoeff(col_iter_map[col], obj_coef);
+    }
+    /// \e
+    _Value getObjCoeff(const Col& col) {
+      return _getObjCoeff(col_iter_map[col]);
     }
 
@@ -552 +586 @@
     }
     /// \e
-    /// \bug ez igy nem jo
     void setObjCoeffs(const Expression& expr) {
+      // writing zero everywhere
+      for(Cols::ClassIt it(col_iter_map, VALID_CLASS); it!=INVALID; ++it)
+        setObjCoeff(it, 0.0);
+      // writing the data needed
       for(typename Expression::Data::const_iterator i=expr.data.begin(); 
           i!=expr.data.end(); ++i) {
-        setObjCoef((*i).first, (*i).second);
+        setObjCoeff((*i).first, (*i).second);
       }
     }
@@ -562 +599 @@
     /// This routine modifies \c expr by only adding to it.
     void getObjCoeffs(Expression& expr) {
-      /// FIXME not yet implemented
+      for(Cols::ClassIt it(col_iter_map, VALID_CLASS); it!=INVALID; ++it)
+        expr+=getObjCoeff(it)*it;
+    }
+    //@}
+
+
+    /*! @name MIP functions and types (public members)
+    */
+    //@{
+  public:
+    /// \e
+    virtual void solveBandB() = 0;
+    /// \e
+    virtual void setLP() = 0;
+    /// \e
+    virtual void setMIP() = 0;
+  protected:
+   /// \e
+    virtual void _setColCont(int i) = 0;
+    /// \e
+    virtual void _setColInt(int i) = 0;
+  public:
+    /// \e
+    void setColCont(Col col) {
+      _setColCont(col_iter_map[col]);
+    }
+    /// \e
+    void setColInt(Col col) {
+      _setColInt(col_iter_map[col]);
     }
     //@}
@@ -691 +756 @@
       rows[1]=i;
       lpx_del_rows(lp, 1, rows);
+    }
+    void _setCoeff(int col, int row, double value) {
+      /// FIXME not yet implemented
+    }
+    double _getCoeff(int col, int row) {
+      /// FIXME not yet implemented
+      return 0.0;
     }
     virtual void _setColLowerBound(int i, double lo) {
@@ -929 +1001 @@
     }
     /// \e
-    virtual double _getObjCoef(int i) { 
+    virtual double _getObjCoeff(int i) { 
       return lpx_get_obj_coef(lp, i);
     }
     /// \e
-    virtual void _setObjCoef(int i, double obj_coef) { 
+    virtual void _setObjCoeff(int i, double obj_coef) { 
       lpx_set_obj_coef(lp, i, obj_coef);
     }
@@ -943 +1015 @@
     /// \e
     void solveDualSimplex() { lpx_simplex(lp); }
-    /// \e
   protected:
     virtual double _getPrimal(int i) {
@@ -1016 +1087 @@
       }
     }
+
+    // MIP
+    /// \e
+    void solveBandB() { lpx_integer(lp); }
+    /// \e
+    void setLP() { lpx_set_class(lp, LPX_LP); }
+    /// \e
+    void setMIP() { lpx_set_class(lp, LPX_MIP); }
+  protected:
+    /// \e
+    void _setColCont(int i) {lpx_set_col_kind(lp, i, LPX_CV); }
+    /// \e
+    void _setColInt(int i) {lpx_set_col_kind(lp, i, LPX_IV); }
   };
   
@@ -1022 +1106 @@
 } //namespace lemon
 
-#endif //LEMON_LP_SOLVER_WRAPPER_H
+#endif //LEMON_LP_SOLVER_BASE_H

src/work/marci/lp/max_flow_expression.cc

@@ -83 +83 @@
   lp.solveSimplex();
   cout << "elapsed time: " << ts << endl;
+//   cout << "rows:" << endl;
+//   for (
+//        LPSolver::Rows::ClassIt i(lp.row_iter_map, 0);
+//        i!=INVALID;
+//        ++i) { 
+//     cout << i << " ";
+//   }
+//   cout << endl;
+//   cout << "cols:" << endl;
+//   for (
+//        LPSolver::Cols::ClassIt i(lp.col_iter_map, 0);
+//        i!=INVALID;
+//        ++i) { 
+//     cout << i << " ";
+//   }
+//   cout << endl;
+  lp.setMIP();
+  cout << "elapsed time: " << ts << endl;
+  for (LPSolver::Cols::ClassIt it(lp.col_iter_map ,1); it!=INVALID; ++it) {
+    lp.setColInt(it);
+  }
+  cout << "elapsed time: " << ts << endl;
+  lp.solveBandB();
+  cout << "elapsed time: " << ts << endl;
 }