Changeset 2368:6b2e8b734ae7 in lemon-0.x for lemon

Timestamp:

02/19/07 13:11:41 (17 years ago)

Author:

Balazs Dezso

Branch:

default

Phase:

public

Convert:

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

Message:

Bug fixes
Documentation

Location:

lemon

Files:

• lemon_reader.h (modified) (1 diff)
• lp_base.h (modified) (1 diff)
• lp_glpk.cc (modified) (1 diff)
• lp_soplex.cc (modified) (1 diff)
• lp_utils.h (modified) (18 diffs)

lemon/lemon_reader.h

@@ -741 +741 @@
   /// \brief SectionReader for reading a graph's nodeset.
   ///
-  /// The lemon format can store multiple graph nodesets with several maps.
-  /// The nodeset section's header line is \c \@nodeset \c nodeset_name, but the
-  /// \c nodeset_name may be empty.
+  /// The lemon format can store multiple graph nodesets with several
+  /// maps.  The nodeset section's header line is \c \@nodeset \c
+  /// nodeset_name, but the \c nodeset_name may be empty.
   ///
   /// The first line of the section contains the names of the maps separated

lemon/lp_base.h

@@ -1061 +1061 @@
       _setColName(_lpId(c), name);
     }
+
+    /// Get the column by its name
+    
+    ///\param name The name of the column
+    ///\return the proper column or \c INVALID
+    Col colByName(const std::string& name) const {
+      int k = _colByName(name);
+      return k != -1 ? Col(cols.fixId(k)) : Col(INVALID);
+    }
     
     /// Set an element of the coefficient matrix of the LP

lemon/lp_glpk.cc

@@ -29 +29 @@
     cols = _lp_bits::LpId(1);
     lp = lpx_create_prob();
+    lpx_create_index(lp);
     ///\todo control function for this:
     lpx_set_int_parm(lp, LPX_K_DUAL, 1);

lemon/lp_soplex.cc

@@ -77 +77 @@
   void LpSoplex::_eraseCol(int i) {
     soplex->removeCol(i);
+    invColNames.erase(colNames[i]);
     colNames[i] = colNames.back();
+    invColNames[colNames.back()] = i;
     colNames.pop_back();
     primal_value[i] = primal_value.back();

lemon/lp_utils.h

@@ -25 +25 @@
 #include <lemon/lemon_writer.h>
 
+#include <map>
+#include <set>
+
+
 namespace lemon {
 
+  /// \ingroup gen_opt_tools
+  ///
+  /// \brief The map for the result of the lp variables.
+  ///
+  /// The map for the result of the lp variables.
+  class LpResultMap {
+  public:
+    typedef LpSolverBase::Col Key;
+    typedef LpSolverBase::Value Value;
+
+    /// \brief Constructor
+    ///
+    /// Constructor
+    LpResultMap(const LpSolverBase& _lp) : lp(_lp) {}
+    LpSolverBase::Value operator[](const LpSolverBase::Col col) const {
+      return lp.primal(col);
+    }
+  private:
+    const LpSolverBase& lp;
+  };
+
+  /// \ingroup gen_opt_tools
+  ///
+  /// \brief The map for the name of the lp variables.
+  ///
+  /// The map for the name of the lp variables.
+  class LpColNameMap {
+  public:
+    typedef LpSolverBase::Col Key;
+    typedef std::string Value;
+
+    /// \brief Constructor
+    ///
+    /// Constructor
+    LpColNameMap(const LpSolverBase& _lp) : lp(_lp) {}
+    std::string operator[](const LpSolverBase::Col col) const {
+      return lp.colName(col);
+    }
+  private:
+    const LpSolverBase& lp;
+  };
+
+  /// \ingroup gen_opt_tools
+  ///
+  /// \brief Writeable map for the name of the lp variables.
+  ///
+  /// Writeable map for the name of the lp variables.
+  class LpColNameWriteMap {
+  public:
+    typedef LpSolverBase::Col Key;
+    typedef std::string Value;
+
+    /// \brief Constructor
+    ///
+    /// Constructor
+    LpColNameWriteMap(LpSolverBase& _lp) : lp(_lp) {}
+    std::string operator[](const LpSolverBase::Col col) const {
+      return lp.colName(col);
+    }
+    void set(const LpSolverBase::Col col, const std::string& name) {
+      lp.colName(col, name);
+    }
+  private:
+    LpSolverBase& lp;
+  };
+
+  /// \ingroup gen_opt_tools
+  ///
+  /// \brief Returns an \ref LpColNameMap class
+  ///
+  /// This function just returns an \ref LpColNameMap class.
+  /// \relates LpColNameMap
+  LpColNameMap lpColNameMap(const LpSolverBase& lp) {
+    return LpColNameMap(lp);
+  }
+
+  LpColNameWriteMap lpColNameMap(LpSolverBase& lp) {
+    return LpColNameWriteMap(lp);
+  }
+
+  /// \ingroup gen_opt_tools
+  ///
+  /// \brief Lp variable item reader for Lemon IO
+  ///
+  /// This class is an Lp variable item reader for Lemon IO. It makes
+  /// possible to store lp variables in lemon file. The usage of this
+  /// class is very simple:
+  ///
+  ///\code
+  /// Graph graph;
+  /// Lp lp;
+  /// Graph::EdgeMap<Lp::Col> var(graph); 
+  ///
+  /// GraphReader<Graph> reader(cin, graph);
+  /// reader.readEdgeMap("lpvar", var, LpColReader(lp));
+  /// reader.run();
+  ///\endcode
+  ///
+  /// If there is already a variable with the same name in the lp then
+  /// it will be used for the return value. If there is no such variable
+  /// then it will be constructed. The file could contain \c '-' as value
+  /// which means that no lp variable associated to the current item and
+  /// in this case INVALID will be returned.
+  class LpColReader {
+  public:
+
+    /// \brief The value type of reader.
+    ///
+    /// The value type of reader.
+    typedef LpSolverBase::Col Value;
+
+    /// \brief Constructor for the reader.
+    ///
+    /// Constructor for the reader.
+    LpColReader(LpSolverBase& _lp) : lp(_lp) {}
+
+    /// \brief Reads an lp variable from the given stream.
+    ///
+    /// Reads an lp variable string from the given stream.
+    void read(std::istream& is, LpSolverBase::Col& col) const {
+      char x;
+      is >> std::ws;
+      if (!is.get(x))
+        throw DataFormatError("Wrong Lp Column format!");
+      if (varFirstChar(x)) {
+        std::string var;
+        var += x;
+        
+        while (is.get(x) && varChar(x)) {
+          var += x;
+        }
+        if (!is) {
+          is.clear();
+        } else {
+          is.putback(x);
+        }
+        col = lp.colByName(var);
+        if (col == INVALID) {
+          col = lp.addCol();
+          lp.colName(col, var);
+        }
+      } else if (x == '-') {
+        col = INVALID;
+        is >> std::ws;
+      } else {
+        std::cerr << x << std::endl;
+        throw DataFormatError("Wrong Lp Column format");
+      }
+    }
+
+  private:
+
+    static bool varFirstChar(char c) {
+      return (c >= 'a' && c <= 'z') || (c >= 'A' && c <= 'Z');
+    }
+
+    static bool varChar(char c) {
+      return (c >= '0' && c <= '9') || 
+        (c >= 'a' && c <= 'z') || 
+        (c >= 'A' && c <= 'Z') ||
+        c == '[' || c == ']';
+    }
+    
+    LpSolverBase& lp;
+
+  };
+
+  /// \ingroup gen_opt_tools
+  ///
+  /// \brief Lp variable item writer for Lemon IO
+  ///
+  /// This class is an Lp variable item writer for Lemon IO. It makes
+  /// possible to store lp variables in lemon file. The usage of this
+  /// class is very simple:
+  ///
+  ///\code
+  /// Graph graph;
+  /// Lp lp;
+  /// Graph::EdgeMap<Lp::Col> var(graph); 
+  ///
+  /// GraphWriter<Graph> writer(cin, graph);
+  /// writer.writeEdgeMap("lpvar", var, LpColWriter(lp));
+  /// writer.run();
+  ///\endcode
+  ///
+  /// If there is no name associated to the current item then the name
+  /// will automatically constructed. If the value is INVALID then it
+  /// will write an \c '-' value to the file.
+  class LpColWriter {
+  public:
+
+    /// \brief The value type of writer.
+    ///
+    /// The value type of writer.
+    typedef LpSolverBase::Col Value;
+
+    /// \brief Constructor for the writer.
+    ///
+    /// Constructor for the writer.
+    LpColWriter(const LpSolverBase& _lp) : lp(_lp), num(0) {}
+
+    /// \brief Writes an lp variable to the given stream.
+    ///
+    /// Writes an lp variable to the given stream.
+    void write(std::ostream& os, const LpSolverBase::Col& col) const {
+      if (col != INVALID) {
+        std::string name = lp.colName(col);
+        if (name.empty()) {
+          std::ostringstream ls;
+          ls << "x" << num;
+          ++num;
+          while (lp.colByName(ls.str()) != INVALID) {
+            ls.str(std::string());
+            ls << "x" << num;
+            ++num;
+          }
+          const_cast<LpSolverBase&>(lp).colName(col, ls.str());
+          os << ls.str();
+        } else {
+          os << name;
+        }
+      } else {
+        os << "-";
+      }
+    }
+
+  private:
+
+    const LpSolverBase& lp;
+    mutable int num;
+
+  };
+
+  /// \ingroup gen_opt_tools
+  ///
+  /// \brief Lp section reader for lemon IO
+  ///
+  /// This section reader provides an easy way to read an Lp problem
+  /// from a file. The lemon lp section format contains three parts.
+  ///
+  ///\code
+  /// @lp
+  /// constraints
+  ///   7 == x1 - 1 * x2
+  ///   2 * x1 + x3 / 2 <= 7
+  ///   x2 + -3 * x3 >= 8
+  ///   3 <= x2 - 2 * x1 <= 8
+  /// bounds
+  ///   x1 >= 3
+  ///   2 <= x2 <= 5
+  ///   0 <= x3 <= 8
+  /// objective
+  ///   min x1 + 2 * x2 - x3
+  ///\endcode
+  ///
+  /// The first part gives the constraints to the lp. The constraints
+  /// could be equality, lower bound, upper bound or range for an
+  /// expression or equality, less or more for two expressions.
+  ///
+  /// The second part gives the bounds for the variables. The bounds
+  /// could be the same as for the single expression so equality,
+  /// lower bound, upper bound or range.
+  ///
+  /// The third part is the objective function, it should start with
+  /// \c min or \c max and then a valid linear expression.
+  ///
+  /// The reader constructs automatically the variable for a name if
+  /// there is not already a variable with the same name.
+  ///
+  /// The basic way to read an LP problem is made by the next code:
+  ///\code
+  /// Lp lp;
+  ///
+  /// LemonReader reader(filename_or_istream);
+  /// LpReader lpreader(reader, lp);
+  /// 
+  /// reader.run();
+  ///\endcode
+  ///
+  /// Of course instead of \c LemonReader you can give a \c
+  /// GraphReader to the LpReader constructor. Also useful that you
+  /// can mix lp problems and graphs in the same file.
   class LpReader : public LemonReader::SectionReader {
     typedef LemonReader::SectionReader Parent;
@@ -34 +320 @@
     /// \brief Constructor.
     ///
-    /// Constructor for LpReader. It creates the LpReader and attach
+    /// Constructor for LpReader. It creates the LpReader and attachs
     /// it into the given LemonReader. The lp reader will add
     /// variables, constraints and objective function to the
@@ -45 +331 @@
     /// \brief Destructor.
     ///
-    /// Destructor for NodeSetReader.
+    /// Destructor for LpReader.
     virtual ~LpReader() {}
 
@@ -69 +355 @@
   private:
 
-    enum SubSection {
+    enum Part {
       CONSTRAINTS, BOUNDS, OBJECTIVE
     };
@@ -211 +497 @@
             lp.colUpperBound(c, v);
           }
+          is >> std::ws;
           if (is.get(x)) {
             throw DataFormatError("Wrong variable bounds format");
@@ -344 +631 @@
         is.putback(x);
       }
-      ColMap::const_iterator it = cols.find(var);
-      if (cols.find(var) != cols.end()) {
-        c = it->second;
-      } else {
+      c = lp.colByName(var);
+      if (c == INVALID) {
         c = lp.addCol();
-        cols.insert(std::make_pair(var, c));
         lp.colName(c, var);
       }
@@ -391 +675 @@
       return (c >= '0' && c <= '9') || c == '.';
     }
-
+    
     static bool varChar(char c) {
       return (c >= '0' && c <= '9') || 
@@ -406 +690 @@
     virtual void read(std::istream& is) {
       std::string line;
-      SubSection sub = CONSTRAINTS;
+      Part part = CONSTRAINTS;
       while (getline(is, line)) {
         std::istringstream ls(line);
@@ -412 +696 @@
         ls >> type;
         if (type == "constraints") {
-          sub = CONSTRAINTS;
+          part = CONSTRAINTS;
+          ls >> std::ws;
+          char x;
+          if (ls.get(x))
+            throw DataFormatError("Wrong Lp format");
         } else if (type == "bounds") {
-          sub = BOUNDS;
+          part = BOUNDS;
+          ls >> std::ws;
+          char x;
+          if (ls.get(x))
+            throw DataFormatError("Wrong Lp format");
         } else if (type == "objective") {
-          sub = OBJECTIVE;
+          part = OBJECTIVE;
+          ls >> std::ws;
+          char x;
+          if (ls.get(x))
+            throw DataFormatError("Wrong Lp format");
         } else {
           ls.str(line);
-          switch (sub) {
+          switch (part) {
           case CONSTRAINTS:
             readConstraint(ls);
@@ -430 +726 @@
             break;
           }
-        }        
+        }
       }
     }
@@ -442 +738 @@
   private:
 
-    typedef std::map<std::string, LpSolverBase::Col> ColMap;
       
     LpSolverBase& lp;
     std::string name;
-    ColMap cols;
   };
 
 
+  /// \ingroup gen_opt_tools
+  ///
+  /// \brief Lp section writer for lemon IO
+  ///
+  /// This section reader provides an easy way to write an Lp problem
+  /// to a file. The lemon lp section format contains three parts.
+  ///
+  ///\code
+  /// @lp
+  /// constraints
+  ///   7 == x1 - 1 * x2
+  ///   2 * x1 + x3 / 2 <= 7
+  ///   x2 + -3 * x3 >= 8
+  ///   3 <= x2 - 2 * x1 <= 8
+  /// bounds
+  ///   x1 >= 3
+  ///   2 <= x2 <= 5
+  ///   0 <= x3 <= 8
+  /// objective
+  ///   min x1 + 2 * x2 - x3
+  ///\endcode
+  ///
+  /// The first part gives the constraints to the lp. The constraints
+  /// could be equality, lower bound, upper bound or range for an
+  /// expression or equality, less or more for two expressions.
+  ///
+  /// The second part gives the bounds for the variables. The bounds
+  /// could be the same as for the single expression so equality,
+  /// lower bound, upper bound or range.
+  ///
+  /// The third part is the objective function, it should start with
+  /// \c min or \c max and then a valid linear expression.
+  ///
+  /// If an LP variable does not have name in the writer, then it will
+  /// automatically created in the writer. This make a slight change
+  /// in the \c const variable.
+  ///
+  /// The basic way to write an LP problem is made by the next code:
+  ///\code
+  /// Lp lp;
+  ///
+  /// LemonWriter writer(filename_or_ostream);
+  /// LpWriter lpwriter(writer, lp);
+  /// 
+  /// writer.run();
+  ///\endcode
+  ///
+  /// Of course instead of \c LemonWriter you can give a \c
+  /// GraphWriter to the LpWriter constructor. Also useful that you
+  /// can mix lp problems and graphs in the same file.
   class LpWriter : public LemonWriter::SectionWriter {
     typedef LemonWriter::SectionWriter Parent;
@@ -458 +802 @@
     ///
     /// Constructor for LpWriter. It creates the LpWriter and attach
-    /// it into the given LemonWriter. The lp writer will add
-    /// variables, constraints and objective function to the
-    /// given lp solver.
-    LpWriter(LemonWriter& _writer, LpSolverBase& _lp, 
+    /// it into the given LemonWriter.
+    LpWriter(LemonWriter& _writer, const LpSolverBase& _lp, 
              const std::string& _name = std::string())
       : Parent(_writer), lp(_lp), name(_name) {} 
@@ -468 +810 @@
     /// \brief Destructor.
     ///
-    /// Destructor for NodeSetWriter.
+    /// Destructor for LpWriter.
     virtual ~LpWriter() {}
 
@@ -490 +832 @@
 
     void createCols() {
-      int num = 1;
-
-      std::map<std::string, LpSolverBase::Col> inverse;
+      int num = 0;
 
       for (LpSolverBase::ColIt it(lp); it != INVALID; ++it) {
         std::string name = lp.colName(it);
-        if (!name.empty() && inverse.find(name) == inverse.end()) {
-          cols.insert(std::make_pair(it, name));
-          inverse.insert(std::make_pair(name, it));
-        } else {
+        if (name.empty()) {
           std::ostringstream ls;
-          ls << "var" << num;
+          ls << "x" << num;
           ++num;
-          cols.insert(std::make_pair(it, ls.str()));
-          inverse.insert(std::make_pair(ls.str(), it));
+          while (lp.colByName(ls.str()) != INVALID) {
+            ls.str(std::string());
+            ls << "x" << num;
+            ++num;
+          }
+          const_cast<LpSolverBase&>(lp).colName(it, ls.str());
         }
       }
@@ -527 +868 @@
         }
         first = false;
-        os << cols[jt->first] << " ";
+        os << lp.colName(jt->first) << " ";
       }
       if (e.constComp() < 0.0) {
@@ -590 +931 @@
           }
           
-          os << cols[it] << " ";
+          os << lp.colName(it) << " ";
           
           if (upper != LpSolverBase::INF) {
@@ -596 +937 @@
           }
         } else {
-          os << cols[it] << " == " << upper << " ";
+          os << lp.colName(it) << " == " << upper << " ";
         }
         os << std::endl;
@@ -615 +956 @@
   private:
 
-    typedef std::map<LpSolverBase::Col, std::string> ColMap;
-      
-    LpSolverBase& lp;
+    const LpSolverBase& lp;
     std::string name;
-    ColMap cols;
   };