# HG changeset patch
# User deba
# Date 1164821731 0
# Node ID c0fae4bbaa5cab33f157b439a8bc8b4c531cd46f
# Parent  bd09e00b64bbfa7916334f91c704445d4facfcb0
Lp section reader

diff -r bd09e00b64bb -r c0fae4bbaa5c lemon/Makefile.am
--- a/lemon/Makefile.am	Wed Nov 29 17:34:29 2006 +0000
+++ b/lemon/Makefile.am	Wed Nov 29 17:35:31 2006 +0000
@@ -76,6 +76,7 @@
 	lemon/lp_glpk.h \
 	lemon/lp_skeleton.h \
 	lemon/lp_soplex.h \
+	lemon/lp_utils.h \
 	lemon/map_iterator.h \
 	lemon/maps.h \
 	lemon/matrix_maps.h \
diff -r bd09e00b64bb -r c0fae4bbaa5c lemon/lp_utils.h
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/lemon/lp_utils.h	Wed Nov 29 17:35:31 2006 +0000
@@ -0,0 +1,364 @@
+/* -*- C++ -*-
+ *
+ * This file is a part of LEMON, a generic C++ optimization library
+ *
+ * Copyright (C) 2003-2006
+ * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
+ * (Egervary Research Group on Combinatorial Optimization, EGRES).
+ *
+ * Permission to use, modify and distribute this software is granted
+ * provided that this copyright notice appears in all copies. For
+ * precise terms see the accompanying LICENSE file.
+ *
+ * This software is provided "AS IS" with no warranty of any kind,
+ * express or implied, and with no claim as to its suitability for any
+ * purpose.
+ *
+ */
+
+#ifndef LEMON_LP_UTILS_H
+#define LEMON_LP_UTILS_H
+
+#include <lemon/lp_base.h>
+
+#include <lemon/lemon_reader.h>
+
+namespace lemon {
+
+  class LpReader : public LemonReader::SectionReader {
+    typedef LemonReader::SectionReader Parent;
+  public:
+
+
+    /// \brief Constructor.
+    ///
+    /// Constructor for LpReader. It creates the LpReader and attach
+    /// it into the given LemonReader. The lp reader will add
+    /// variables, constraints and objective function to the
+    /// given lp solver.
+    LpReader(LemonReader& _reader, LpSolverBase& _lp, 
+             const std::string& _name = std::string())
+      : Parent(_reader), lp(_lp), name(_name) {} 
+
+
+    /// \brief Destructor.
+    ///
+    /// Destructor for NodeSetReader.
+    virtual ~LpReader() {}
+
+  private:
+    LpReader(const LpReader&);
+    void operator=(const LpReader&);
+  
+  protected:
+
+    /// \brief Gives back true when the SectionReader can process 
+    /// the section with the given header line.
+    ///
+    /// It gives back true when the header line starts with \c \@lp,
+    /// and the header line's name and the nodeset's name are the same.
+    virtual bool header(const std::string& line) {
+      std::istringstream ls(line);
+      std::string command;
+      std::string id;
+      ls >> command >> id;
+      return command == "@lp" && name == id;
+    }
+
+  private:
+
+    enum Relation {
+      LE, EQ, GE
+    };
+
+    std::istream& readConstraint(std::istream& is, LpSolverBase::Constr& c) {
+      char x;
+      LpSolverBase::Expr e1, e2;
+      Relation op1;
+      is >> std::ws;
+      readExpression(is, e1);
+      is >> std::ws;
+      readRelation(is, op1);
+      is >> std::ws;
+      readExpression(is, e2);
+      if (!is.get(x)) {
+        if (op1 == LE) {
+          c = e1 <= e2;
+        } else if (op1 == GE) {
+          c = e1 >= e2;
+        } else {
+          c = e1 == e2;
+        }
+      } else {
+        is.putback(x);
+        LpSolverBase::Expr e3;
+        Relation op2;
+        readRelation(is, op2);
+        is >> std::ws;
+        readExpression(is, e3);
+        if (!e1.empty() || !e3.empty()) {
+          throw DataFormatError("Wrong range format");
+        }
+        if (op2 != op1 || op1 == EQ) {
+          throw DataFormatError("Wrong range format");
+        }
+        if (op1 == LE) {
+          c = e1.constComp() <= e2 <= e3.constComp();
+        } else {
+          c = e1.constComp() >= e2 >= e3.constComp();
+        }
+      }
+    }
+
+    std::istream& readExpression(std::istream& is, LpSolverBase::Expr& e) {
+      LpSolverBase::Col c;
+      double d;
+      char x;
+      readElement(is, c, d);
+      if (c != INVALID) {
+        e += d * c;
+      } else {
+        e += d;
+      }
+      is >> std::ws;
+      while (is.get(x) && (x == '+' || x == '-')) {
+        is >> std::ws;
+        readElement(is, c, d);
+        if (c != INVALID) {
+          e += (x == '+' ? d : -d) * c;
+        } else {
+          e += (x == '+' ? d : -d);
+        }
+        is >> std::ws;
+      }
+      if (!is) {
+        is.clear();
+      } else {
+        is.putback(x);
+      }
+      return is;
+    }
+
+    std::istream& readElement(std::istream& is, 
+                              LpSolverBase::Col& c, double& d) { 
+      d = 1.0;
+      c = INVALID;
+      char x, y;
+      if (!is.get(x)) throw DataFormatError("Cannot find lp element");
+      if (x == '+' || x == '-') {
+        is >> std::ws;
+        d *= x == '-' ? -1 : 1;
+        while (is.get(x) && (x == '+' || x == '-')) {
+          d *= x == '-' ? -1 : 1;
+          is >> std::ws;
+        }
+        if (!is) throw DataFormatError("Cannot find lp element");
+      }
+      if (numFirstChar(x)) {
+        is.putback(x);
+        double e;
+        readNum(is, e);
+        d *= e;
+      } else if (varFirstChar(x)) {
+        is.putback(x);
+        LpSolverBase::Col f;
+        readCol(is, f);
+        c = f;
+      } else {
+        throw DataFormatError("Invalid expression format");          
+      }
+      is >> std::ws;
+      while (is.get(y) && (y == '*' || y == '/')) {
+        is >> std::ws;
+        if (!is.get(x)) throw DataFormatError("Cannot find lp element");
+        if (x == '+' || x == '-') {
+          is >> std::ws;
+          d *= x == '-' ? -1 : 1;
+          while (is.get(x) && (x == '+' || x == '-')) {
+            d *= x == '-' ? -1 : 1;
+            is >> std::ws;
+          }
+          if (!is) throw DataFormatError("Cannot find lp element");
+        }
+        if (numFirstChar(x)) {
+          is.putback(x);
+          double e;
+          readNum(is, e);
+          if (y == '*') {
+            d *= e;
+          } else {
+            d /= e;
+          }
+        } else if (varFirstChar(x)) {
+          is.putback(x);
+          LpSolverBase::Col f;
+          readCol(is, f);
+          if (y == '*') {
+            if (c == INVALID) {
+              c = f;
+            } else {
+              throw DataFormatError("Quadratic element in expression");
+            }
+          } else {
+            throw DataFormatError("Division by variable");
+          }
+        } else {
+          throw DataFormatError("Invalid expression format");          
+        }
+        is >> std::ws;
+      }
+      if (!is) {
+        is.clear();
+      } else {
+        is.putback(y);
+      }
+      return is;
+    }
+
+    std::istream& readCol(std::istream& is, LpSolverBase::Col& c) {
+      char x;
+      std::string var;
+      while (is.get(x) && varChar(x)) {
+        var += x;
+      }
+      if (!is) {
+        is.clear();
+      } else {
+        is.putback(x);
+      }
+      ColMap::const_iterator it = cols.find(var);
+      if (cols.find(var) != cols.end()) {
+        c = it->second;
+      } else {
+        c = lp.addCol();
+        cols.insert(std::make_pair(var, c));
+        lp.colName(c, var);
+      }
+      return is;
+    }
+
+    std::istream& readNum(std::istream& is, double& d) {
+      is >> d;
+      if (!is) throw DataFormatError("Wrong number format");
+      return is;
+    }
+
+    std::istream& readRelation(std::istream& is, Relation& op) {
+      char x, y;
+      if (!is.get(x) || !(x == '<' || x == '=' || x == '>')) {
+        throw DataFormatError("Wrong relation operator");
+      }
+      if (!is.get(y) || y != '=') {
+        throw DataFormatError("Wrong relation operator");
+      }
+      switch (x) {
+      case '<': op = LE; 
+        break;
+      case '=': op = EQ; 
+        break;
+      case '>': op = GE; 
+        break;
+      }
+      return is;
+    }
+
+    static bool relationFirstChar(char c) {
+      return c == '<' || c == '=' || c == '>';
+    }
+
+    static bool varFirstChar(char c) {
+      return (c >= 'a' && c <= 'z') || (c >= 'A' && c <= 'Z');
+    }
+
+    static bool numFirstChar(char c) {
+      return (c >= '0' && c <= '9') || c == '.';
+    }
+
+    static bool varChar(char c) {
+      return (c >= '0' && c <= '9') || 
+        (c >= 'a' && c <= 'z') || (c >= 'A' && c <= 'Z');
+    }
+
+
+    void addConstraint(const LpSolverBase::Constr& constr) {
+      if (constr.expr().size() != 1) {
+        lp.addRow(constr);
+      } else {
+        Lp::Expr e = constr.expr();
+        LpSolverBase::Col col = e.begin()->first;
+        double coeff = e.begin()->second;
+        double lb = LpSolverBase::NaN;
+        double ub = LpSolverBase::NaN;
+        if (coeff > 0) {
+          if (constr.upperBounded()) {
+            lb = (constr.lowerBound() - e.constComp()) / coeff;
+          }
+          if (constr.lowerBounded()) {
+            ub = (constr.upperBound() - e.constComp()) / coeff;
+          }
+        } else if (coeff < 0) {
+          if (constr.upperBounded()) {
+            lb = (constr.upperBound() - e.constComp()) / coeff;
+          }
+          if (constr.lowerBounded()) {
+            ub = (constr.lowerBound() - e.constComp()) / coeff;
+          }
+        } else {
+          lb = -LpSolverBase::INF;
+          ub = LpSolverBase::INF;
+        }
+        lp.colLowerBound(col, lb);
+        lp.colUpperBound(col, ub);
+      }
+    }
+    
+  protected:
+
+    /// \brief Reader function of the section.
+    ///
+    /// It reads the content of the section.
+    virtual void read(std::istream& is) {
+      std::string line;
+      std::map<std::string, LpSolverBase::Col> vars;
+      while (getline(is, line)) {
+        std::istringstream ls(line);
+        std::string sense;
+        ls >> sense;
+        if (sense == "min" || sense == "max") {
+          LpSolverBase::Expr expr;
+          ls >> std::ws;
+          readExpression(ls, expr);
+          lp.setObj(expr);
+          if (sense == "min") {
+            lp.min();
+          } else {
+            lp.max();
+          }
+        } else {
+          ls.str(line);
+          LpSolverBase::Constr constr;
+          ls >> std::ws;
+          readConstraint(ls, constr);
+          addConstraint(constr);
+        }        
+      }
+    }
+      
+    virtual void missing() {
+      ErrorMessage msg;
+      msg << "Lp section not found in file: @lp " << name;
+      throw IoParameterError(msg.message());
+    }
+
+  private:
+
+    typedef std::map<std::string, LpSolverBase::Col> ColMap;
+      
+    LpSolverBase& lp;
+    std::string name;
+    ColMap cols;
+  };
+
+}
+
+#endif