Changeset 1256:3bb4ed285c39 in lemon-0.x for src/work/athos/lp

Timestamp:

03/25/05 09:18:27 (20 years ago)

Author:

Alpar Juttner

Branch:

default

Phase:

public

Convert:

svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@1683

Message:

• src/lemon/utility.h: dummy<> template added
• LpSolverBase::INF is now really defined
• AddColSet?() to add several column at once
  • using enable_if
  • with some doxygen hack
• More doc improvements
• Better Makefile

Location:

src/work/athos/lp

Files:

• Makefile (modified) (1 diff)
• lp_base.cc (modified) (1 diff)
• lp_base.h (modified) (5 diffs)
• lp_test.cc (modified) (1 diff)

src/work/athos/lp/Makefile

@@ -2 +2 @@
 
 all: lp_test
+
+clean:
+        rm lp_test *.o
 
 lp_base.o: lp_base.cc lp_base.h lin_expr.h

src/work/athos/lp/lp_base.cc

@@ -20 +20 @@
 #include "lp_base.h"
 namespace lemon {
-
+  
+  const LpSolverBase::Value
+  LpSolverBase::INF = std::numeric_limits<Value>::infinity();
 
 

src/work/athos/lp/lp_base.h

@@ -19 +19 @@
 
 #include<vector>
-
+#include<limits>
+
+#include<lemon/utility.h>
 #include<lemon/error.h>
+#include<lemon/invalid.h>
 
 #include"lin_expr.h"
@@ -66 +69 @@
           first_free=next;
         }
+        return cross[n];
       }
       else throw LogicError(); //floatingId-s must form a continuous range;
@@ -97 +101 @@
   public:
 
-    /// \e
+    ///The floating point type used by the solver
     typedef double Value;
-    /// \e 
+    ///The infinity constant
     static const Value INF;
     
-    ///\e
-    class Col { protected: int id; friend class LpSolverBase; };
-    ///\e
-    class Row { protected: int id; friend class LpSolverBase; };
+    ///Refer to a column of the LP.
+
+    ///This type is used to refer to a column of the LP.
+    ///
+    ///Its value remains valid and correct even after the addition or erase of
+    ///new column (unless the referred column itself was also deleted,
+    ///of course).
+    ///
+    ///\todo Document what can one do with a Col (INVALID, comparing,
+    ///it is similar to Node/Edge)
+    class Col {
+    protected:
+      int id;
+      friend class LpSolverBase;
+    public:
+      typedef True LpSolverCol;
+      Col() {}
+      Col(const Invalid&) : id(-1) {}
+      bool operator<(Col c) const  {return id<c.id;}
+      bool operator==(Col c) const  {return id==c.id;}
+      bool operator!=(Col c) const  {return id==c.id;}
+    };
+
+    ///Refer to a row of the LP.
+
+    ///This type is used to refer to a row of the LP.
+    ///
+    ///Its value remains valid and correct even after the addition or erase of
+    ///new rows (unless the referred row itself was also deleted, of course).
+    ///
+    ///\todo Document what can one do with a Row (INVALID, comparing,
+    ///it is similar to Node/Edge)
+    class Row {
+    protected:
+      int id;
+      friend class LpSolverBase;
+    public:
+      typedef True LpSolverRow;
+      Row() {}
+      Row(const Invalid&) : id(-1) {}
+      typedef True LpSolverRow;
+      bool operator<(Row c) const  {return id<c.id;}
+      bool operator==(Row c) const  {return id==c.id;}
+      bool operator!=(Row c) const  {return id==c.id;} 
+   };
 
     typedef SparseLinExpr<Col, Value> Expr;
@@ -176 +221 @@
     ///Add a new empty column (i.e a new variable) to the LP
     Col addCol() { Col c; c.id=cols.insert(_addCol()); return c;}
+    ///\brief Fill the elements of a container with newly created columns
+    ///(i.e a new variables)
+    ///
+    ///This magic function takes container as its argument
+    ///and fills its elements
+    ///with new columns (i.e. variables)
+    ///\param t can be either any standard STL iterable container with
+    ///\ref Col \c values_type or \c mapped_type
+    ///like <tt>std::vector<LpSolverBase::Col></tt>,
+    /// <tt>std::list<LpSolverBase::Col></tt> or
+    /// <tt>std::map<AnyType,LpSolverBase::Col></tt> or
+    ///it can be an iterable lemon map like 
+    /// <tt>ListGraph::NodeMap<LpSolverBase::Col></tt>.
+    ///\return The number of the created column.
+    ///\bug Iterable nodemap hasn't been implemented yet.
+#ifdef DOXYGEN
+    template<class T>
+    int addColSet(T &t) { return 0;} 
+#else
+    template<class T>
+    typename enable_if<typename T::value_type::LpSolverCol,int>::type
+    addColSet(T &t,dummy<0> = 0) {
+      int s=0;
+      for(typename T::iterator i=t.begin();i!=t.end();++i) {*i=addCol();s++;}
+      return s;
+    }
+    template<class T>
+    typename enable_if<typename T::value_type::second_type::LpSolverCol,
+                       int>::type
+    addColSet(T &t,dummy<1> = 1) { 
+      int s=0;
+      for(typename T::iterator i=t.begin();i!=t.end();++i) {
+        i->second=addCol();
+        s++;
+      }
+      return s;
+    }
+#endif
     ///Add a new empty row (i.e a new constaint) to the LP
     Row addRow() { Row r; r.id=rows.insert(_addRow()); return r;}
@@ -192 +275 @@
       indices.push_back(0);
       values.push_back(0);
-      for(Expr::iterator i=e.begin(); i!=e.end(); ++i) {
-        indices.push_back(cols.floatingId((*i).first.id));
-        values.push_back((*i).second);
-      }
+      for(Expr::iterator i=e.begin(); i!=e.end(); ++i)
+        if((*i).second!=0) { ///\bug EPSILON would be necessary here!!!
+          indices.push_back(cols.floatingId((*i).first.id));
+          values.push_back((*i).second);
+        }
       _setRowCoeffs(rows.floatingId(r.id),indices.size()-1,
                     &indices[0],&values[0]);
-      _setRowLowerBound(rows.floatingId(r.id),l);
-      _setRowUpperBound(rows.floatingId(r.id),l);
+      _setRowLowerBound(rows.floatingId(r.id),l-e.constComp());
+      _setRowUpperBound(rows.floatingId(r.id),u-e.constComp());
       return r;
     }

src/work/athos/lp/lp_test.cc

@@ -5 +5 @@
 int main()
 {
-  LpSolverSkeleton lp;
+  typedef LpSolverSkeleton LP;
+  LP lp;
+
+  std::vector<LP::Col> x;
+  for(int i=0;i<10;i++) x.push_back(lp.addCol());
+
+  std::vector<LP::Col> y(10);
+  lp.addColSet(y);
+
+  std::map<int,LP::Col> z;
+  
+  z.insert(std::make_pair(12,INVALID));
+  z.insert(std::make_pair(2,INVALID));
+  z.insert(std::make_pair(7,INVALID));
+  z.insert(std::make_pair(5,INVALID));
+  
+  lp.addColSet(z);
+
+
+  LP::Expr e;
+  e[x[3]]=2;
+  e[x[3]]=4;
+  e[x[3]]=1;
+  e.constComp()=12;
+  lp.addRow(LP::INF,e,23);
+
 }