deba@2316: /* -*- C++ -*-
deba@2316:  *
deba@2316:  * This file is a part of LEMON, a generic C++ optimization library
deba@2316:  *
alpar@2553:  * Copyright (C) 2003-2008
deba@2316:  * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
deba@2316:  * (Egervary Research Group on Combinatorial Optimization, EGRES).
deba@2316:  *
deba@2316:  * Permission to use, modify and distribute this software is granted
deba@2316:  * provided that this copyright notice appears in all copies. For
deba@2316:  * precise terms see the accompanying LICENSE file.
deba@2316:  *
deba@2316:  * This software is provided "AS IS" with no warranty of any kind,
deba@2316:  * express or implied, and with no claim as to its suitability for any
deba@2316:  * purpose.
deba@2316:  *
deba@2316:  */
deba@2316: 
deba@2316: #ifndef LEMON_LP_UTILS_H
deba@2316: #define LEMON_LP_UTILS_H
deba@2316: 
deba@2316: #include <lemon/lp_base.h>
deba@2316: 
deba@2316: #include <lemon/lemon_reader.h>
deba@2363: #include <lemon/lemon_writer.h>
deba@2316: 
deba@2368: #include <map>
deba@2368: #include <set>
deba@2368: 
deba@2368: 
deba@2316: namespace lemon {
deba@2316: 
deba@2370:   /// \ingroup lp_utils
deba@2368:   ///
deba@2368:   /// \brief The map for the result of the lp variables.
deba@2368:   ///
deba@2368:   /// The map for the result of the lp variables.
deba@2368:   class LpResultMap {
deba@2368:   public:
deba@2368:     typedef LpSolverBase::Col Key;
deba@2368:     typedef LpSolverBase::Value Value;
deba@2368: 
deba@2368:     /// \brief Constructor
deba@2368:     ///
deba@2368:     /// Constructor
deba@2368:     LpResultMap(const LpSolverBase& _lp) : lp(_lp) {}
deba@2368:     LpSolverBase::Value operator[](const LpSolverBase::Col col) const {
deba@2368:       return lp.primal(col);
deba@2368:     }
deba@2368:   private:
deba@2368:     const LpSolverBase& lp;
deba@2368:   };
deba@2368: 
deba@2370:   /// \ingroup lp_utils
deba@2370:   ///
deba@2370:   /// \brief Returns an \ref LpResultMap class
deba@2370:   ///
deba@2370:   /// This function just returns an \ref LpResultMap class.
deba@2370:   /// \relates LpResultMap
deba@2370:   LpResultMap lpResultMap(const LpSolverBase& lp) {
deba@2370:     return LpResultMap(lp);
deba@2370:   }
deba@2370: 
deba@2370:   /// \ingroup lp_utils
deba@2368:   ///
deba@2368:   /// \brief The map for the name of the lp variables.
deba@2368:   ///
deba@2368:   /// The map for the name of the lp variables.
deba@2368:   class LpColNameMap {
deba@2368:   public:
deba@2368:     typedef LpSolverBase::Col Key;
deba@2368:     typedef std::string Value;
deba@2368: 
deba@2368:     /// \brief Constructor
deba@2368:     ///
deba@2368:     /// Constructor
deba@2368:     LpColNameMap(const LpSolverBase& _lp) : lp(_lp) {}
deba@2368:     std::string operator[](const LpSolverBase::Col col) const {
deba@2368:       return lp.colName(col);
deba@2368:     }
deba@2368:   private:
deba@2368:     const LpSolverBase& lp;
deba@2368:   };
deba@2368: 
deba@2370:   /// \ingroup lp_utils
deba@2368:   ///
deba@2368:   /// \brief Writeable map for the name of the lp variables.
deba@2368:   ///
deba@2368:   /// Writeable map for the name of the lp variables.
deba@2368:   class LpColNameWriteMap {
deba@2368:   public:
deba@2368:     typedef LpSolverBase::Col Key;
deba@2368:     typedef std::string Value;
deba@2368: 
deba@2368:     /// \brief Constructor
deba@2368:     ///
deba@2368:     /// Constructor
deba@2368:     LpColNameWriteMap(LpSolverBase& _lp) : lp(_lp) {}
deba@2368:     std::string operator[](const LpSolverBase::Col col) const {
deba@2368:       return lp.colName(col);
deba@2368:     }
deba@2368:     void set(const LpSolverBase::Col col, const std::string& name) {
deba@2368:       lp.colName(col, name);
deba@2368:     }
deba@2368:   private:
deba@2368:     LpSolverBase& lp;
deba@2368:   };
deba@2368: 
deba@2370:   /// \ingroup lp_utils
deba@2368:   ///
deba@2368:   /// \brief Returns an \ref LpColNameMap class
deba@2368:   ///
deba@2368:   /// This function just returns an \ref LpColNameMap class.
deba@2368:   /// \relates LpColNameMap
deba@2368:   LpColNameMap lpColNameMap(const LpSolverBase& lp) {
deba@2368:     return LpColNameMap(lp);
deba@2368:   }
deba@2368: 
deba@2368:   LpColNameWriteMap lpColNameMap(LpSolverBase& lp) {
deba@2368:     return LpColNameWriteMap(lp);
deba@2368:   }
deba@2368: 
deba@2370:   /// \ingroup lp_utils
deba@2368:   ///
deba@2368:   /// \brief Lp variable item reader for Lemon IO
deba@2368:   ///
deba@2368:   /// This class is an Lp variable item reader for Lemon IO. It makes
deba@2368:   /// possible to store lp variables in lemon file. The usage of this
deba@2368:   /// class is very simple:
deba@2368:   ///
deba@2368:   ///\code
deba@2368:   /// Graph graph;
deba@2368:   /// Lp lp;
deba@2368:   /// Graph::EdgeMap<Lp::Col> var(graph); 
deba@2368:   ///
deba@2368:   /// GraphReader<Graph> reader(cin, graph);
deba@2368:   /// reader.readEdgeMap("lpvar", var, LpColReader(lp));
deba@2368:   /// reader.run();
deba@2368:   ///\endcode
deba@2368:   ///
deba@2368:   /// If there is already a variable with the same name in the lp then
deba@2368:   /// it will be used for the return value. If there is no such variable
deba@2368:   /// then it will be constructed. The file could contain \c '-' as value
deba@2368:   /// which means that no lp variable associated to the current item and
deba@2368:   /// in this case INVALID will be returned.
deba@2368:   class LpColReader {
deba@2368:   public:
deba@2368: 
deba@2368:     /// \brief The value type of reader.
deba@2368:     ///
deba@2368:     /// The value type of reader.
deba@2368:     typedef LpSolverBase::Col Value;
deba@2368: 
deba@2368:     /// \brief Constructor for the reader.
deba@2368:     ///
deba@2368:     /// Constructor for the reader.
deba@2368:     LpColReader(LpSolverBase& _lp) : lp(_lp) {}
deba@2368: 
deba@2368:     /// \brief Reads an lp variable from the given stream.
deba@2368:     ///
deba@2368:     /// Reads an lp variable string from the given stream.
deba@2368:     void read(std::istream& is, LpSolverBase::Col& col) const {
deba@2368:       char x;
deba@2368:       is >> std::ws;
deba@2368:       if (!is.get(x))
deba@2368:         throw DataFormatError("Wrong Lp Column format!");
deba@2368:       if (varFirstChar(x)) {
deba@2368:         std::string var;
deba@2368:         var += x;
deba@2368:         
deba@2368:         while (is.get(x) && varChar(x)) {
deba@2368:           var += x;
deba@2368:         }
deba@2368:         if (!is) {
deba@2368:           is.clear();
deba@2368:         } else {
deba@2368:           is.putback(x);
deba@2368:         }
deba@2368:         col = lp.colByName(var);
deba@2368:         if (col == INVALID) {
deba@2368:           col = lp.addCol();
deba@2368:           lp.colName(col, var);
deba@2368:         }
deba@2368:       } else if (x == '-') {
deba@2368:         col = INVALID;
deba@2368:         is >> std::ws;
deba@2368:       } else {
deba@2368:         std::cerr << x << std::endl;
deba@2368:         throw DataFormatError("Wrong Lp Column format");
deba@2368:       }
deba@2368:     }
deba@2368: 
deba@2368:   private:
deba@2368: 
deba@2368:     static bool varFirstChar(char c) {
deba@2368:       return (c >= 'a' && c <= 'z') || (c >= 'A' && c <= 'Z');
deba@2368:     }
deba@2368: 
deba@2368:     static bool varChar(char c) {
deba@2368:       return (c >= '0' && c <= '9') || 
deba@2368:         (c >= 'a' && c <= 'z') || 
deba@2368:         (c >= 'A' && c <= 'Z') ||
deba@2368:         c == '[' || c == ']';
deba@2368:     }
deba@2368:     
deba@2368:     LpSolverBase& lp;
deba@2368: 
deba@2368:   };
deba@2368: 
deba@2370:   /// \ingroup lp_utils
deba@2368:   ///
deba@2368:   /// \brief Lp variable item writer for Lemon IO
deba@2368:   ///
deba@2368:   /// This class is an Lp variable item writer for Lemon IO. It makes
deba@2368:   /// possible to store lp variables in lemon file. The usage of this
deba@2368:   /// class is very simple:
deba@2368:   ///
deba@2368:   ///\code
deba@2368:   /// Graph graph;
deba@2368:   /// Lp lp;
deba@2368:   /// Graph::EdgeMap<Lp::Col> var(graph); 
deba@2368:   ///
deba@2368:   /// GraphWriter<Graph> writer(cin, graph);
deba@2368:   /// writer.writeEdgeMap("lpvar", var, LpColWriter(lp));
deba@2368:   /// writer.run();
deba@2368:   ///\endcode
deba@2368:   ///
deba@2368:   /// If there is no name associated to the current item then the name
deba@2368:   /// will automatically constructed. If the value is INVALID then it
deba@2368:   /// will write an \c '-' value to the file.
deba@2368:   class LpColWriter {
deba@2368:   public:
deba@2368: 
deba@2368:     /// \brief The value type of writer.
deba@2368:     ///
deba@2368:     /// The value type of writer.
deba@2368:     typedef LpSolverBase::Col Value;
deba@2368: 
deba@2368:     /// \brief Constructor for the writer.
deba@2368:     ///
deba@2368:     /// Constructor for the writer.
deba@2368:     LpColWriter(const LpSolverBase& _lp) : lp(_lp), num(0) {}
deba@2368: 
deba@2368:     /// \brief Writes an lp variable to the given stream.
deba@2368:     ///
deba@2368:     /// Writes an lp variable to the given stream.
deba@2368:     void write(std::ostream& os, const LpSolverBase::Col& col) const {
deba@2368:       if (col != INVALID) {
deba@2368:         std::string name = lp.colName(col);
deba@2368:         if (name.empty()) {
deba@2368:           std::ostringstream ls;
deba@2368:           ls << "x" << num;
deba@2368:           ++num;
deba@2368:           while (lp.colByName(ls.str()) != INVALID) {
deba@2368:             ls.str(std::string());
deba@2368:             ls << "x" << num;
deba@2368:             ++num;
deba@2368:           }
deba@2368:           const_cast<LpSolverBase&>(lp).colName(col, ls.str());
deba@2368:           os << ls.str();
deba@2368:         } else {
deba@2368:           os << name;
deba@2368:         }
deba@2368:       } else {
deba@2368:         os << "-";
deba@2368:       }
deba@2368:     }
deba@2368: 
deba@2368:   private:
deba@2368: 
deba@2368:     const LpSolverBase& lp;
deba@2368:     mutable int num;
deba@2368: 
deba@2368:   };
deba@2368: 
deba@2370:   /// \ingroup lp_utils
deba@2368:   ///
deba@2368:   /// \brief Lp section reader for lemon IO
deba@2368:   ///
deba@2368:   /// This section reader provides an easy way to read an Lp problem
deba@2368:   /// from a file. The lemon lp section format contains three parts.
deba@2368:   ///
deba@2368:   ///\code
deba@2368:   /// @lp
deba@2368:   /// constraints
deba@2368:   ///   7 == x1 - 1 * x2
deba@2368:   ///   2 * x1 + x3 / 2 <= 7
deba@2368:   ///   x2 + -3 * x3 >= 8
deba@2368:   ///   3 <= x2 - 2 * x1 <= 8
deba@2368:   /// bounds
deba@2368:   ///   x1 >= 3
deba@2368:   ///   2 <= x2 <= 5
deba@2368:   ///   0 <= x3 <= 8
deba@2368:   /// objective
deba@2368:   ///   min x1 + 2 * x2 - x3
deba@2368:   ///\endcode
deba@2368:   ///
deba@2368:   /// The first part gives the constraints to the lp. The constraints
deba@2368:   /// could be equality, lower bound, upper bound or range for an
deba@2368:   /// expression or equality, less or more for two expressions.
deba@2368:   ///
deba@2368:   /// The second part gives the bounds for the variables. The bounds
deba@2368:   /// could be the same as for the single expression so equality,
deba@2368:   /// lower bound, upper bound or range.
deba@2368:   ///
deba@2368:   /// The third part is the objective function, it should start with
deba@2368:   /// \c min or \c max and then a valid linear expression.
deba@2368:   ///
deba@2368:   /// The reader constructs automatically the variable for a name if
deba@2368:   /// there is not already a variable with the same name.
deba@2368:   ///
deba@2368:   /// The basic way to read an LP problem is made by the next code:
deba@2368:   ///\code
deba@2368:   /// Lp lp;
deba@2368:   ///
deba@2368:   /// LemonReader reader(filename_or_istream);
deba@2368:   /// LpReader lpreader(reader, lp);
deba@2368:   /// 
deba@2368:   /// reader.run();
deba@2368:   ///\endcode
deba@2368:   ///
deba@2368:   /// Of course instead of \c LemonReader you can give a \c
deba@2368:   /// GraphReader to the LpReader constructor. Also useful that you
deba@2368:   /// can mix lp problems and graphs in the same file.
deba@2316:   class LpReader : public LemonReader::SectionReader {
deba@2316:     typedef LemonReader::SectionReader Parent;
deba@2316:   public:
deba@2316: 
deba@2316: 
deba@2316:     /// \brief Constructor.
deba@2316:     ///
deba@2368:     /// Constructor for LpReader. It creates the LpReader and attachs
deba@2316:     /// it into the given LemonReader. The lp reader will add
deba@2316:     /// variables, constraints and objective function to the
deba@2316:     /// given lp solver.
deba@2316:     LpReader(LemonReader& _reader, LpSolverBase& _lp, 
deba@2316:              const std::string& _name = std::string())
deba@2316:       : Parent(_reader), lp(_lp), name(_name) {} 
deba@2316: 
deba@2316: 
deba@2316:     /// \brief Destructor.
deba@2316:     ///
deba@2368:     /// Destructor for LpReader.
deba@2316:     virtual ~LpReader() {}
deba@2316: 
deba@2316:   private:
deba@2316:     LpReader(const LpReader&);
deba@2316:     void operator=(const LpReader&);
deba@2316:   
deba@2316:   protected:
deba@2316: 
deba@2316:     /// \brief Gives back true when the SectionReader can process 
deba@2316:     /// the section with the given header line.
deba@2316:     ///
deba@2316:     /// It gives back true when the header line starts with \c \@lp,
deba@2316:     /// and the header line's name and the nodeset's name are the same.
deba@2316:     virtual bool header(const std::string& line) {
deba@2316:       std::istringstream ls(line);
deba@2316:       std::string command;
deba@2316:       std::string id;
deba@2316:       ls >> command >> id;
deba@2316:       return command == "@lp" && name == id;
deba@2316:     }
deba@2316: 
deba@2316:   private:
deba@2316: 
deba@2368:     enum Part {
deba@2364:       CONSTRAINTS, BOUNDS, OBJECTIVE
deba@2364:     };
deba@2364: 
deba@2316:     enum Relation {
deba@2316:       LE, EQ, GE
deba@2316:     };
deba@2316: 
deba@2364:     std::istream& readConstraint(std::istream& is) {
deba@2364:       LpSolverBase::Constr c;
deba@2316:       char x;
deba@2316:       LpSolverBase::Expr e1, e2;
deba@2316:       Relation op1;
deba@2316:       is >> std::ws;
deba@2316:       readExpression(is, e1);
deba@2316:       is >> std::ws;
deba@2316:       readRelation(is, op1);
deba@2316:       is >> std::ws;
deba@2316:       readExpression(is, e2);
deba@2364:       is >> std::ws;
deba@2316:       if (!is.get(x)) {
deba@2316:         if (op1 == LE) {
deba@2364:           if (e1.size() == 0) {
deba@2364:             c = e2 >= e1;
deba@2364:           } else {
deba@2364:             c = e1 <= e2;
deba@2364:           }
deba@2316:           c = e1 <= e2;
deba@2316:         } else if (op1 == GE) {
deba@2364:           if (e1.size() == 0) {
deba@2364:             c = e2 <= e1;
deba@2364:           } else {
deba@2364:             c = e1 >= e2;
deba@2364:           }
deba@2316:         } else {
deba@2364:           if (e1.size() == 0) {
deba@2364:             c = e2 == e1;
deba@2364:           } else {
deba@2364:             c = e1 == e2;
deba@2364:           }
deba@2316:         }
deba@2316:       } else {
deba@2316:         is.putback(x);
deba@2316:         LpSolverBase::Expr e3;
deba@2316:         Relation op2;
deba@2316:         readRelation(is, op2);
deba@2316:         is >> std::ws;
deba@2316:         readExpression(is, e3);
deba@2316:         if (!e1.empty() || !e3.empty()) {
deba@2316:           throw DataFormatError("Wrong range format");
deba@2316:         }
deba@2316:         if (op2 != op1 || op1 == EQ) {
deba@2316:           throw DataFormatError("Wrong range format");
deba@2316:         }
deba@2316:         if (op1 == LE) {
deba@2316:           c = e1.constComp() <= e2 <= e3.constComp();
deba@2316:         } else {
deba@2316:           c = e1.constComp() >= e2 >= e3.constComp();
deba@2316:         }
deba@2364:         is >> std::ws;
deba@2364:         if (is.get(x)) {
deba@2364:           throw DataFormatError("Wrong variable bounds format");
deba@2364:         }
deba@2316:       }
deba@2364:       lp.addRow(c);
deba@2364:       return is;
deba@2364:     }
deba@2364: 
deba@2364:     std::istream& readObjective(std::istream& is) {
deba@2364:       is >> std::ws;
deba@2364:       std::string sense;
deba@2364:       is >> sense;
deba@2364:       if (sense != "min" && sense != "max") {
deba@2364:         throw DataFormatError("Wrong objective function format");
deba@2364:       }
deba@2364:       LpSolverBase::Expr expr;
deba@2364:       is >> std::ws;
deba@2364:       readExpression(is, expr);
deba@2369:       lp.obj(expr);
deba@2364:       if (sense == "min") {
deba@2364:         lp.min();
deba@2364:       } else {
deba@2364:         lp.max();
deba@2364:       }
deba@2364:       return is;
deba@2364:     }
deba@2364: 
deba@2364:     std::istream& readBounds(std::istream& is) {
deba@2364:       LpSolverBase::Col c;
deba@2364:       char x;
deba@2364:       is >> std::ws;
deba@2364:       if (!is.get(x)) {
deba@2364:         throw DataFormatError("Wrong variable bounds format");
deba@2364:       }
deba@2364:       if (varFirstChar(x)) {
deba@2364:         is.putback(x);
deba@2364:         readCol(is, c);
deba@2364:         is >> std::ws;
deba@2364:         Relation op1;
deba@2364:         readRelation(is, op1);
deba@2364:         double v;
deba@2364:         readNum(is, v);
deba@2364:         if (op1 == EQ) {
deba@2364:           lp.colLowerBound(c, v);
deba@2364:           lp.colUpperBound(c, v);
deba@2364:         } else if (op1 == LE) {
deba@2364:           lp.colUpperBound(c, v);
deba@2364:         } else {
deba@2364:           lp.colLowerBound(c, v);
deba@2364:         }
deba@2364:         is >> std::ws;
deba@2364:         if (is.get(x)) {
deba@2364:           throw DataFormatError("Wrong variable bounds format");
deba@2364:         }
deba@2364:       } else {
deba@2364:         is.putback(x);
deba@2364:         double v;
deba@2364:         readNum(is, v);
deba@2364:         is >> std::ws;
deba@2364:         Relation op1;
deba@2364:         readRelation(is, op1);
deba@2364:         is >> std::ws;
deba@2364:         readCol(is, c);
deba@2364:         is >> std::ws;
deba@2364:         if (is.get(x)) {
deba@2364:           is.putback(x);
deba@2364:           is >> std::ws;
deba@2364:           Relation op2;
deba@2364:           readRelation(is, op2);
deba@2364:           double w;
deba@2364:           is >> std::ws;
deba@2364:           readNum(is, w);
deba@2364:           if (op2 != op1 || op1 == EQ) {
deba@2364:             throw DataFormatError("Wrong range format");
deba@2364:           }
deba@2364:           if (op1 == LE) {
deba@2364:             lp.colLowerBound(c, v);
deba@2364:             lp.colUpperBound(c, w);
deba@2364:           } else {
deba@2364:             lp.colLowerBound(c, w);
deba@2364:             lp.colUpperBound(c, v);
deba@2364:           }
deba@2368:           is >> std::ws;
deba@2364:           if (is.get(x)) {
deba@2364:             throw DataFormatError("Wrong variable bounds format");
deba@2364:           }
deba@2364:         } else {
deba@2364:           if (op1 == EQ) {
deba@2364:             lp.colLowerBound(c, v);
deba@2364:             lp.colUpperBound(c, v);
deba@2364:           } else if (op1 == LE) {
deba@2364:             lp.colLowerBound(c, v);
deba@2364:           } else {
deba@2364:             lp.colUpperBound(c, v);
deba@2364:           }
deba@2364:         }
deba@2364:       }
deba@2364:       return is;
deba@2316:     }
deba@2316: 
deba@2316:     std::istream& readExpression(std::istream& is, LpSolverBase::Expr& e) {
deba@2316:       LpSolverBase::Col c;
deba@2316:       double d;
deba@2316:       char x;
deba@2316:       readElement(is, c, d);
deba@2316:       if (c != INVALID) {
deba@2316:         e += d * c;
deba@2316:       } else {
deba@2316:         e += d;
deba@2316:       }
deba@2316:       is >> std::ws;
deba@2316:       while (is.get(x) && (x == '+' || x == '-')) {
deba@2316:         is >> std::ws;
deba@2316:         readElement(is, c, d);
deba@2316:         if (c != INVALID) {
deba@2316:           e += (x == '+' ? d : -d) * c;
deba@2316:         } else {
deba@2316:           e += (x == '+' ? d : -d);
deba@2316:         }
deba@2316:         is >> std::ws;
deba@2316:       }
deba@2316:       if (!is) {
deba@2316:         is.clear();
deba@2316:       } else {
deba@2316:         is.putback(x);
deba@2316:       }
deba@2316:       return is;
deba@2316:     }
deba@2316: 
deba@2316:     std::istream& readElement(std::istream& is, 
deba@2316:                               LpSolverBase::Col& c, double& d) { 
deba@2316:       d = 1.0;
deba@2316:       c = INVALID;
deba@2316:       char x, y;
deba@2316:       if (!is.get(x)) throw DataFormatError("Cannot find lp element");
deba@2316:       if (x == '+' || x == '-') {
deba@2316:         is >> std::ws;
deba@2316:         d *= x == '-' ? -1 : 1;
deba@2316:         while (is.get(x) && (x == '+' || x == '-')) {
deba@2316:           d *= x == '-' ? -1 : 1;
deba@2316:           is >> std::ws;
deba@2316:         }
deba@2316:         if (!is) throw DataFormatError("Cannot find lp element");
deba@2316:       }
deba@2316:       if (numFirstChar(x)) {
deba@2316:         is.putback(x);
deba@2316:         double e;
deba@2316:         readNum(is, e);
deba@2316:         d *= e;
deba@2316:       } else if (varFirstChar(x)) {
deba@2316:         is.putback(x);
deba@2316:         LpSolverBase::Col f;
deba@2316:         readCol(is, f);
deba@2316:         c = f;
deba@2316:       } else {
deba@2316:         throw DataFormatError("Invalid expression format");          
deba@2316:       }
deba@2316:       is >> std::ws;
deba@2316:       while (is.get(y) && (y == '*' || y == '/')) {
deba@2316:         is >> std::ws;
deba@2316:         if (!is.get(x)) throw DataFormatError("Cannot find lp element");
deba@2316:         if (x == '+' || x == '-') {
deba@2316:           is >> std::ws;
deba@2316:           d *= x == '-' ? -1 : 1;
deba@2316:           while (is.get(x) && (x == '+' || x == '-')) {
deba@2316:             d *= x == '-' ? -1 : 1;
deba@2316:             is >> std::ws;
deba@2316:           }
deba@2316:           if (!is) throw DataFormatError("Cannot find lp element");
deba@2316:         }
deba@2316:         if (numFirstChar(x)) {
deba@2316:           is.putback(x);
deba@2316:           double e;
deba@2316:           readNum(is, e);
deba@2316:           if (y == '*') {
deba@2316:             d *= e;
deba@2316:           } else {
deba@2316:             d /= e;
deba@2316:           }
deba@2316:         } else if (varFirstChar(x)) {
deba@2316:           is.putback(x);
deba@2316:           LpSolverBase::Col f;
deba@2316:           readCol(is, f);
deba@2316:           if (y == '*') {
deba@2316:             if (c == INVALID) {
deba@2316:               c = f;
deba@2316:             } else {
deba@2316:               throw DataFormatError("Quadratic element in expression");
deba@2316:             }
deba@2316:           } else {
deba@2316:             throw DataFormatError("Division by variable");
deba@2316:           }
deba@2316:         } else {
deba@2316:           throw DataFormatError("Invalid expression format");          
deba@2316:         }
deba@2316:         is >> std::ws;
deba@2316:       }
deba@2316:       if (!is) {
deba@2316:         is.clear();
deba@2316:       } else {
deba@2316:         is.putback(y);
deba@2316:       }
deba@2316:       return is;
deba@2316:     }
deba@2316: 
deba@2316:     std::istream& readCol(std::istream& is, LpSolverBase::Col& c) {
deba@2316:       char x;
deba@2316:       std::string var;
deba@2316:       while (is.get(x) && varChar(x)) {
deba@2316:         var += x;
deba@2316:       }
deba@2316:       if (!is) {
deba@2316:         is.clear();
deba@2316:       } else {
deba@2316:         is.putback(x);
deba@2316:       }
deba@2368:       c = lp.colByName(var);
deba@2368:       if (c == INVALID) {
deba@2316:         c = lp.addCol();
deba@2316:         lp.colName(c, var);
deba@2316:       }
deba@2316:       return is;
deba@2316:     }
deba@2316: 
deba@2316:     std::istream& readNum(std::istream& is, double& d) {
deba@2316:       is >> d;
deba@2316:       if (!is) throw DataFormatError("Wrong number format");
deba@2316:       return is;
deba@2316:     }
deba@2316: 
deba@2316:     std::istream& readRelation(std::istream& is, Relation& op) {
deba@2316:       char x, y;
deba@2316:       if (!is.get(x) || !(x == '<' || x == '=' || x == '>')) {
deba@2316:         throw DataFormatError("Wrong relation operator");
deba@2316:       }
deba@2316:       if (!is.get(y) || y != '=') {
deba@2316:         throw DataFormatError("Wrong relation operator");
deba@2316:       }
deba@2316:       switch (x) {
deba@2316:       case '<': op = LE; 
deba@2316:         break;
deba@2316:       case '=': op = EQ; 
deba@2316:         break;
deba@2316:       case '>': op = GE; 
deba@2316:         break;
deba@2316:       }
deba@2316:       return is;
deba@2316:     }
deba@2316: 
deba@2316:     static bool relationFirstChar(char c) {
deba@2316:       return c == '<' || c == '=' || c == '>';
deba@2316:     }
deba@2316: 
deba@2316:     static bool varFirstChar(char c) {
deba@2316:       return (c >= 'a' && c <= 'z') || (c >= 'A' && c <= 'Z');
deba@2316:     }
deba@2316: 
deba@2316:     static bool numFirstChar(char c) {
deba@2316:       return (c >= '0' && c <= '9') || c == '.';
deba@2316:     }
deba@2368:     
deba@2316:     static bool varChar(char c) {
deba@2316:       return (c >= '0' && c <= '9') || 
deba@2364:         (c >= 'a' && c <= 'z') || 
deba@2364:         (c >= 'A' && c <= 'Z') ||
deba@2364:         c == '[' || c == ']';
deba@2316:     }
deba@2316:     
deba@2316:   protected:
deba@2316: 
deba@2316:     /// \brief Reader function of the section.
deba@2316:     ///
deba@2316:     /// It reads the content of the section.
deba@2316:     virtual void read(std::istream& is) {
deba@2316:       std::string line;
deba@2368:       Part part = CONSTRAINTS;
deba@2316:       while (getline(is, line)) {
deba@2316:         std::istringstream ls(line);
deba@2364:         std::string type;
deba@2364:         ls >> type;
deba@2364:         if (type == "constraints") {
deba@2368:           part = CONSTRAINTS;
deba@2368:           ls >> std::ws;
deba@2368:           char x;
deba@2368:           if (ls.get(x))
deba@2368:             throw DataFormatError("Wrong Lp format");
deba@2364:         } else if (type == "bounds") {
deba@2368:           part = BOUNDS;
deba@2368:           ls >> std::ws;
deba@2368:           char x;
deba@2368:           if (ls.get(x))
deba@2368:             throw DataFormatError("Wrong Lp format");
deba@2364:         } else if (type == "objective") {
deba@2368:           part = OBJECTIVE;
deba@2368:           ls >> std::ws;
deba@2368:           char x;
deba@2368:           if (ls.get(x))
deba@2368:             throw DataFormatError("Wrong Lp format");
deba@2316:         } else {
deba@2316:           ls.str(line);
deba@2368:           switch (part) {
deba@2364:           case CONSTRAINTS:
deba@2364:             readConstraint(ls);
deba@2364:             break;
deba@2364:           case BOUNDS:
deba@2364:             readBounds(ls);
deba@2364:             break;
deba@2364:           case OBJECTIVE:
deba@2364:             readObjective(ls);
deba@2364:             break;
deba@2364:           }
deba@2368:         }
deba@2316:       }
deba@2316:     }
deba@2316:       
deba@2316:     virtual void missing() {
deba@2316:       ErrorMessage msg;
deba@2316:       msg << "Lp section not found in file: @lp " << name;
deba@2316:       throw IoParameterError(msg.message());
deba@2316:     }
deba@2316: 
deba@2316:   private:
deba@2316: 
deba@2316:       
deba@2316:     LpSolverBase& lp;
deba@2316:     std::string name;
deba@2316:   };
deba@2316: 
deba@2363: 
deba@2370:   /// \ingroup lp_utils
deba@2368:   ///
deba@2368:   /// \brief Lp section writer for lemon IO
deba@2368:   ///
deba@2368:   /// This section reader provides an easy way to write an Lp problem
deba@2368:   /// to a file. The lemon lp section format contains three parts.
deba@2368:   ///
deba@2368:   ///\code
deba@2368:   /// @lp
deba@2368:   /// constraints
deba@2368:   ///   7 == x1 - 1 * x2
deba@2368:   ///   2 * x1 + x3 / 2 <= 7
deba@2368:   ///   x2 + -3 * x3 >= 8
deba@2368:   ///   3 <= x2 - 2 * x1 <= 8
deba@2368:   /// bounds
deba@2368:   ///   x1 >= 3
deba@2368:   ///   2 <= x2 <= 5
deba@2368:   ///   0 <= x3 <= 8
deba@2368:   /// objective
deba@2368:   ///   min x1 + 2 * x2 - x3
deba@2368:   ///\endcode
deba@2368:   ///
deba@2368:   /// The first part gives the constraints to the lp. The constraints
deba@2368:   /// could be equality, lower bound, upper bound or range for an
deba@2368:   /// expression or equality, less or more for two expressions.
deba@2368:   ///
deba@2368:   /// The second part gives the bounds for the variables. The bounds
deba@2368:   /// could be the same as for the single expression so equality,
deba@2368:   /// lower bound, upper bound or range.
deba@2368:   ///
deba@2368:   /// The third part is the objective function, it should start with
deba@2368:   /// \c min or \c max and then a valid linear expression.
deba@2368:   ///
deba@2368:   /// If an LP variable does not have name in the writer, then it will
deba@2368:   /// automatically created in the writer. This make a slight change
deba@2368:   /// in the \c const variable.
deba@2368:   ///
deba@2368:   /// The basic way to write an LP problem is made by the next code:
deba@2368:   ///\code
deba@2368:   /// Lp lp;
deba@2368:   ///
deba@2368:   /// LemonWriter writer(filename_or_ostream);
deba@2368:   /// LpWriter lpwriter(writer, lp);
deba@2368:   /// 
deba@2368:   /// writer.run();
deba@2368:   ///\endcode
deba@2368:   ///
deba@2368:   /// Of course instead of \c LemonWriter you can give a \c
deba@2368:   /// GraphWriter to the LpWriter constructor. Also useful that you
deba@2368:   /// can mix lp problems and graphs in the same file.
deba@2364:   class LpWriter : public LemonWriter::SectionWriter {
deba@2364:     typedef LemonWriter::SectionWriter Parent;
deba@2364:   public:
deba@2363: 
deba@2363: 
deba@2364:     /// \brief Constructor.
deba@2364:     ///
deba@2364:     /// Constructor for LpWriter. It creates the LpWriter and attach
deba@2368:     /// it into the given LemonWriter.
deba@2368:     LpWriter(LemonWriter& _writer, const LpSolverBase& _lp, 
deba@2364:              const std::string& _name = std::string())
deba@2364:       : Parent(_writer), lp(_lp), name(_name) {} 
deba@2363: 
deba@2363: 
deba@2364:     /// \brief Destructor.
deba@2364:     ///
deba@2368:     /// Destructor for LpWriter.
deba@2364:     virtual ~LpWriter() {}
deba@2363: 
deba@2364:   private:
deba@2364:     LpWriter(const LpWriter&);
deba@2364:     void operator=(const LpWriter&);
deba@2363:   
deba@2364:   protected:
deba@2363: 
deba@2364:     /// \brief Gives back true when the SectionWriter can process 
deba@2364:     /// the section with the given header line.
deba@2364:     ///
deba@2364:     /// It gives back the header line of the \c \@lp section.
deba@2364:     virtual std::string header() {
deba@2364:       std::ostringstream ls;
deba@2364:       ls << "@lp " << name;
deba@2364:       return ls.str();
deba@2364:     }
deba@2363: 
deba@2364:   private:
deba@2363: 
deba@2364:     void createCols() {
deba@2368:       int num = 0;
deba@2364: 
deba@2364:       for (LpSolverBase::ColIt it(lp); it != INVALID; ++it) {
deba@2364:         std::string name = lp.colName(it);
deba@2368:         if (name.empty()) {
deba@2364:           std::ostringstream ls;
deba@2368:           ls << "x" << num;
deba@2364:           ++num;
deba@2368:           while (lp.colByName(ls.str()) != INVALID) {
deba@2368:             ls.str(std::string());
deba@2368:             ls << "x" << num;
deba@2368:             ++num;
deba@2368:           }
deba@2368:           const_cast<LpSolverBase&>(lp).colName(it, ls.str());
deba@2364:         }
deba@2364:       }
deba@2364:     }
deba@2364:     
deba@2364:     void writeExpression(std::ostream& os, const LpSolverBase::Expr& e) {
deba@2364:       bool first = true;
deba@2364:       for (LpSolverBase::Expr::const_iterator jt = e.begin(); 
deba@2364:            jt != e.end(); ++jt) {
deba@2364:         if (jt->second < 0.0) {
deba@2364:           os << "- ";
deba@2364:           if (jt->second != -1.0) {
deba@2364:             os << -jt->second << " * ";
deba@2364:           }
deba@2364:         } else if (jt->second > 0.0) {
deba@2364:           if (!first) {
deba@2364:             os << "+ ";
deba@2364:           }
deba@2364:           if (jt->second != 1.0) {
deba@2364:             os << jt->second << " * ";
deba@2364:           }          
deba@2364:         }
deba@2364:         first = false;
deba@2368:         os << lp.colName(jt->first) << " ";
deba@2364:       }
deba@2364:       if (e.constComp() < 0.0) {
deba@2364:         os << "- " << -e.constComp() << " ";
deba@2364:       } else if (e.constComp() > 0.0) {
deba@2364:         if (!first) {
deba@2364:           os << "+ ";
deba@2364:         }
deba@2364:         os << e.constComp() << " ";
deba@2421:       }
deba@2421:       if (e.begin() == e.end() && e.constComp() == 0.0) {
deba@2421:         os << "0 ";
deba@2421:       }
deba@2364:     }
deba@2364: 
deba@2364:   protected:
deba@2364: 
deba@2364:     /// \brief Writer function of the section.
deba@2364:     ///
deba@2364:     /// It writes the content of the section.
deba@2364:     virtual void write(std::ostream& os) {
deba@2364:       createCols();
deba@2364: 
deba@2364:       os << "constraints" << std::endl;
deba@2363:       
deba@2364:       for (LpSolverBase::RowIt it(lp); it != INVALID; ++it) {
deba@2364:         double lower, upper;
deba@2364:         lp.getRowBounds(it, lower, upper);
deba@2364:         if (lower == -LpSolverBase::INF && upper == LpSolverBase::INF) 
deba@2364:           continue;
deba@2364:         os << "   ";
deba@2364:         
deba@2364:         if (lower != upper) {
deba@2364:           if (lower != -LpSolverBase::INF) {
deba@2364:             os << lower << " <= ";
deba@2364:           }
deba@2364:           
deba@2364:           writeExpression(os, lp.row(it));
deba@2364:           
deba@2364:           if (upper != LpSolverBase::INF) {
deba@2364:             os << "<= " << upper << " ";
deba@2364:           }
deba@2364:         } else {
deba@2363: 
deba@2364:           writeExpression(os, lp.row(it));
deba@2364:           os << "== " << upper << " ";
deba@2364:           
deba@2364:         }
deba@2363: 
deba@2364:         os << std::endl;
deba@2364:       }
deba@2363: 
deba@2364:       os << "bounds" << std::endl;
deba@2364:       
deba@2364:       for (LpSolverBase::ColIt it(lp); it != INVALID; ++it) {
deba@2364:         double lower = lp.colLowerBound(it);
deba@2364:         double upper = lp.colUpperBound(it);
deba@2364:         if (lower == -LpSolverBase::INF && upper == LpSolverBase::INF) 
deba@2364:           continue;
deba@2364:         os << "   ";
deba@2363: 
deba@2364:         if (lower != upper) {
deba@2364:           if (lower != -LpSolverBase::INF) {
deba@2364:             os << lower << " <= ";
deba@2364:           }
deba@2364:           
deba@2368:           os << lp.colName(it) << " ";
deba@2364:           
deba@2364:           if (upper != LpSolverBase::INF) {
deba@2364:             os << "<= " << upper << " ";
deba@2364:           }
deba@2364:         } else {
deba@2368:           os << lp.colName(it) << " == " << upper << " ";
deba@2364:         }
deba@2364:         os << std::endl;
deba@2364:       }
deba@2363: 
deba@2364:       os << "objective" << std::endl;
deba@2364:       os << "   ";
deba@2369:       if (lp.isMin()) {
deba@2364:         os << "min ";
deba@2364:       } else {
deba@2364:         os << "max ";
deba@2364:       }
deba@2364:       writeExpression(os, lp.obj());
deba@2364:       os << std::endl;
deba@2364:     }
deba@2364:       
deba@2363: 
deba@2364:   private:
deba@2363: 
deba@2368:     const LpSolverBase& lp;
deba@2364:     std::string name;
deba@2364:   };
deba@2363: 
deba@2316: }
deba@2316: 
deba@2316: #endif