lemon/lp_utils.h
author deba
Fri, 31 Aug 2007 08:40:49 +0000
changeset 2469 d6f12a9b5cbf
parent 2391 14a343be7a5a
child 2553 bfced05fa852
permissions -rw-r--r--
Invalid assignments ambiguity handling
deba@2316
     1
/* -*- C++ -*-
deba@2316
     2
 *
deba@2316
     3
 * This file is a part of LEMON, a generic C++ optimization library
deba@2316
     4
 *
alpar@2391
     5
 * Copyright (C) 2003-2007
deba@2316
     6
 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
deba@2316
     7
 * (Egervary Research Group on Combinatorial Optimization, EGRES).
deba@2316
     8
 *
deba@2316
     9
 * Permission to use, modify and distribute this software is granted
deba@2316
    10
 * provided that this copyright notice appears in all copies. For
deba@2316
    11
 * precise terms see the accompanying LICENSE file.
deba@2316
    12
 *
deba@2316
    13
 * This software is provided "AS IS" with no warranty of any kind,
deba@2316
    14
 * express or implied, and with no claim as to its suitability for any
deba@2316
    15
 * purpose.
deba@2316
    16
 *
deba@2316
    17
 */
deba@2316
    18
deba@2316
    19
#ifndef LEMON_LP_UTILS_H
deba@2316
    20
#define LEMON_LP_UTILS_H
deba@2316
    21
deba@2316
    22
#include <lemon/lp_base.h>
deba@2316
    23
deba@2316
    24
#include <lemon/lemon_reader.h>
deba@2363
    25
#include <lemon/lemon_writer.h>
deba@2316
    26
deba@2368
    27
#include <map>
deba@2368
    28
#include <set>
deba@2368
    29
deba@2368
    30
deba@2316
    31
namespace lemon {
deba@2316
    32
deba@2370
    33
  /// \ingroup lp_utils
deba@2368
    34
  ///
deba@2368
    35
  /// \brief The map for the result of the lp variables.
deba@2368
    36
  ///
deba@2368
    37
  /// The map for the result of the lp variables.
deba@2368
    38
  class LpResultMap {
deba@2368
    39
  public:
deba@2368
    40
    typedef LpSolverBase::Col Key;
deba@2368
    41
    typedef LpSolverBase::Value Value;
deba@2368
    42
deba@2368
    43
    /// \brief Constructor
deba@2368
    44
    ///
deba@2368
    45
    /// Constructor
deba@2368
    46
    LpResultMap(const LpSolverBase& _lp) : lp(_lp) {}
deba@2368
    47
    LpSolverBase::Value operator[](const LpSolverBase::Col col) const {
deba@2368
    48
      return lp.primal(col);
deba@2368
    49
    }
deba@2368
    50
  private:
deba@2368
    51
    const LpSolverBase& lp;
deba@2368
    52
  };
deba@2368
    53
deba@2370
    54
  /// \ingroup lp_utils
deba@2370
    55
  ///
deba@2370
    56
  /// \brief Returns an \ref LpResultMap class
deba@2370
    57
  ///
deba@2370
    58
  /// This function just returns an \ref LpResultMap class.
deba@2370
    59
  /// \relates LpResultMap
deba@2370
    60
  LpResultMap lpResultMap(const LpSolverBase& lp) {
deba@2370
    61
    return LpResultMap(lp);
deba@2370
    62
  }
deba@2370
    63
deba@2370
    64
  /// \ingroup lp_utils
deba@2368
    65
  ///
deba@2368
    66
  /// \brief The map for the name of the lp variables.
deba@2368
    67
  ///
deba@2368
    68
  /// The map for the name of the lp variables.
deba@2368
    69
  class LpColNameMap {
deba@2368
    70
  public:
deba@2368
    71
    typedef LpSolverBase::Col Key;
deba@2368
    72
    typedef std::string Value;
deba@2368
    73
deba@2368
    74
    /// \brief Constructor
deba@2368
    75
    ///
deba@2368
    76
    /// Constructor
deba@2368
    77
    LpColNameMap(const LpSolverBase& _lp) : lp(_lp) {}
deba@2368
    78
    std::string operator[](const LpSolverBase::Col col) const {
deba@2368
    79
      return lp.colName(col);
deba@2368
    80
    }
deba@2368
    81
  private:
deba@2368
    82
    const LpSolverBase& lp;
deba@2368
    83
  };
deba@2368
    84
deba@2370
    85
  /// \ingroup lp_utils
deba@2368
    86
  ///
deba@2368
    87
  /// \brief Writeable map for the name of the lp variables.
deba@2368
    88
  ///
deba@2368
    89
  /// Writeable map for the name of the lp variables.
deba@2368
    90
  class LpColNameWriteMap {
deba@2368
    91
  public:
deba@2368
    92
    typedef LpSolverBase::Col Key;
deba@2368
    93
    typedef std::string Value;
deba@2368
    94
deba@2368
    95
    /// \brief Constructor
deba@2368
    96
    ///
deba@2368
    97
    /// Constructor
deba@2368
    98
    LpColNameWriteMap(LpSolverBase& _lp) : lp(_lp) {}
deba@2368
    99
    std::string operator[](const LpSolverBase::Col col) const {
deba@2368
   100
      return lp.colName(col);
deba@2368
   101
    }
deba@2368
   102
    void set(const LpSolverBase::Col col, const std::string& name) {
deba@2368
   103
      lp.colName(col, name);
deba@2368
   104
    }
deba@2368
   105
  private:
deba@2368
   106
    LpSolverBase& lp;
deba@2368
   107
  };
deba@2368
   108
deba@2370
   109
  /// \ingroup lp_utils
deba@2368
   110
  ///
deba@2368
   111
  /// \brief Returns an \ref LpColNameMap class
deba@2368
   112
  ///
deba@2368
   113
  /// This function just returns an \ref LpColNameMap class.
deba@2368
   114
  /// \relates LpColNameMap
deba@2368
   115
  LpColNameMap lpColNameMap(const LpSolverBase& lp) {
deba@2368
   116
    return LpColNameMap(lp);
deba@2368
   117
  }
deba@2368
   118
deba@2368
   119
  LpColNameWriteMap lpColNameMap(LpSolverBase& lp) {
deba@2368
   120
    return LpColNameWriteMap(lp);
deba@2368
   121
  }
deba@2368
   122
deba@2370
   123
  /// \ingroup lp_utils
deba@2368
   124
  ///
deba@2368
   125
  /// \brief Lp variable item reader for Lemon IO
deba@2368
   126
  ///
deba@2368
   127
  /// This class is an Lp variable item reader for Lemon IO. It makes
deba@2368
   128
  /// possible to store lp variables in lemon file. The usage of this
deba@2368
   129
  /// class is very simple:
deba@2368
   130
  ///
deba@2368
   131
  ///\code
deba@2368
   132
  /// Graph graph;
deba@2368
   133
  /// Lp lp;
deba@2368
   134
  /// Graph::EdgeMap<Lp::Col> var(graph); 
deba@2368
   135
  ///
deba@2368
   136
  /// GraphReader<Graph> reader(cin, graph);
deba@2368
   137
  /// reader.readEdgeMap("lpvar", var, LpColReader(lp));
deba@2368
   138
  /// reader.run();
deba@2368
   139
  ///\endcode
deba@2368
   140
  ///
deba@2368
   141
  /// If there is already a variable with the same name in the lp then
deba@2368
   142
  /// it will be used for the return value. If there is no such variable
deba@2368
   143
  /// then it will be constructed. The file could contain \c '-' as value
deba@2368
   144
  /// which means that no lp variable associated to the current item and
deba@2368
   145
  /// in this case INVALID will be returned.
deba@2368
   146
  class LpColReader {
deba@2368
   147
  public:
deba@2368
   148
deba@2368
   149
    /// \brief The value type of reader.
deba@2368
   150
    ///
deba@2368
   151
    /// The value type of reader.
deba@2368
   152
    typedef LpSolverBase::Col Value;
deba@2368
   153
deba@2368
   154
    /// \brief Constructor for the reader.
deba@2368
   155
    ///
deba@2368
   156
    /// Constructor for the reader.
deba@2368
   157
    LpColReader(LpSolverBase& _lp) : lp(_lp) {}
deba@2368
   158
deba@2368
   159
    /// \brief Reads an lp variable from the given stream.
deba@2368
   160
    ///
deba@2368
   161
    /// Reads an lp variable string from the given stream.
deba@2368
   162
    void read(std::istream& is, LpSolverBase::Col& col) const {
deba@2368
   163
      char x;
deba@2368
   164
      is >> std::ws;
deba@2368
   165
      if (!is.get(x))
deba@2368
   166
        throw DataFormatError("Wrong Lp Column format!");
deba@2368
   167
      if (varFirstChar(x)) {
deba@2368
   168
        std::string var;
deba@2368
   169
        var += x;
deba@2368
   170
        
deba@2368
   171
        while (is.get(x) && varChar(x)) {
deba@2368
   172
          var += x;
deba@2368
   173
        }
deba@2368
   174
        if (!is) {
deba@2368
   175
          is.clear();
deba@2368
   176
        } else {
deba@2368
   177
          is.putback(x);
deba@2368
   178
        }
deba@2368
   179
        col = lp.colByName(var);
deba@2368
   180
        if (col == INVALID) {
deba@2368
   181
          col = lp.addCol();
deba@2368
   182
          lp.colName(col, var);
deba@2368
   183
        }
deba@2368
   184
      } else if (x == '-') {
deba@2368
   185
        col = INVALID;
deba@2368
   186
        is >> std::ws;
deba@2368
   187
      } else {
deba@2368
   188
        std::cerr << x << std::endl;
deba@2368
   189
        throw DataFormatError("Wrong Lp Column format");
deba@2368
   190
      }
deba@2368
   191
    }
deba@2368
   192
deba@2368
   193
  private:
deba@2368
   194
deba@2368
   195
    static bool varFirstChar(char c) {
deba@2368
   196
      return (c >= 'a' && c <= 'z') || (c >= 'A' && c <= 'Z');
deba@2368
   197
    }
deba@2368
   198
deba@2368
   199
    static bool varChar(char c) {
deba@2368
   200
      return (c >= '0' && c <= '9') || 
deba@2368
   201
        (c >= 'a' && c <= 'z') || 
deba@2368
   202
        (c >= 'A' && c <= 'Z') ||
deba@2368
   203
        c == '[' || c == ']';
deba@2368
   204
    }
deba@2368
   205
    
deba@2368
   206
    LpSolverBase& lp;
deba@2368
   207
deba@2368
   208
  };
deba@2368
   209
deba@2370
   210
  /// \ingroup lp_utils
deba@2368
   211
  ///
deba@2368
   212
  /// \brief Lp variable item writer for Lemon IO
deba@2368
   213
  ///
deba@2368
   214
  /// This class is an Lp variable item writer for Lemon IO. It makes
deba@2368
   215
  /// possible to store lp variables in lemon file. The usage of this
deba@2368
   216
  /// class is very simple:
deba@2368
   217
  ///
deba@2368
   218
  ///\code
deba@2368
   219
  /// Graph graph;
deba@2368
   220
  /// Lp lp;
deba@2368
   221
  /// Graph::EdgeMap<Lp::Col> var(graph); 
deba@2368
   222
  ///
deba@2368
   223
  /// GraphWriter<Graph> writer(cin, graph);
deba@2368
   224
  /// writer.writeEdgeMap("lpvar", var, LpColWriter(lp));
deba@2368
   225
  /// writer.run();
deba@2368
   226
  ///\endcode
deba@2368
   227
  ///
deba@2368
   228
  /// If there is no name associated to the current item then the name
deba@2368
   229
  /// will automatically constructed. If the value is INVALID then it
deba@2368
   230
  /// will write an \c '-' value to the file.
deba@2368
   231
  class LpColWriter {
deba@2368
   232
  public:
deba@2368
   233
deba@2368
   234
    /// \brief The value type of writer.
deba@2368
   235
    ///
deba@2368
   236
    /// The value type of writer.
deba@2368
   237
    typedef LpSolverBase::Col Value;
deba@2368
   238
deba@2368
   239
    /// \brief Constructor for the writer.
deba@2368
   240
    ///
deba@2368
   241
    /// Constructor for the writer.
deba@2368
   242
    LpColWriter(const LpSolverBase& _lp) : lp(_lp), num(0) {}
deba@2368
   243
deba@2368
   244
    /// \brief Writes an lp variable to the given stream.
deba@2368
   245
    ///
deba@2368
   246
    /// Writes an lp variable to the given stream.
deba@2368
   247
    void write(std::ostream& os, const LpSolverBase::Col& col) const {
deba@2368
   248
      if (col != INVALID) {
deba@2368
   249
        std::string name = lp.colName(col);
deba@2368
   250
        if (name.empty()) {
deba@2368
   251
          std::ostringstream ls;
deba@2368
   252
          ls << "x" << num;
deba@2368
   253
          ++num;
deba@2368
   254
          while (lp.colByName(ls.str()) != INVALID) {
deba@2368
   255
            ls.str(std::string());
deba@2368
   256
            ls << "x" << num;
deba@2368
   257
            ++num;
deba@2368
   258
          }
deba@2368
   259
          const_cast<LpSolverBase&>(lp).colName(col, ls.str());
deba@2368
   260
          os << ls.str();
deba@2368
   261
        } else {
deba@2368
   262
          os << name;
deba@2368
   263
        }
deba@2368
   264
      } else {
deba@2368
   265
        os << "-";
deba@2368
   266
      }
deba@2368
   267
    }
deba@2368
   268
deba@2368
   269
  private:
deba@2368
   270
deba@2368
   271
    const LpSolverBase& lp;
deba@2368
   272
    mutable int num;
deba@2368
   273
deba@2368
   274
  };
deba@2368
   275
deba@2370
   276
  /// \ingroup lp_utils
deba@2368
   277
  ///
deba@2368
   278
  /// \brief Lp section reader for lemon IO
deba@2368
   279
  ///
deba@2368
   280
  /// This section reader provides an easy way to read an Lp problem
deba@2368
   281
  /// from a file. The lemon lp section format contains three parts.
deba@2368
   282
  ///
deba@2368
   283
  ///\code
deba@2368
   284
  /// @lp
deba@2368
   285
  /// constraints
deba@2368
   286
  ///   7 == x1 - 1 * x2
deba@2368
   287
  ///   2 * x1 + x3 / 2 <= 7
deba@2368
   288
  ///   x2 + -3 * x3 >= 8
deba@2368
   289
  ///   3 <= x2 - 2 * x1 <= 8
deba@2368
   290
  /// bounds
deba@2368
   291
  ///   x1 >= 3
deba@2368
   292
  ///   2 <= x2 <= 5
deba@2368
   293
  ///   0 <= x3 <= 8
deba@2368
   294
  /// objective
deba@2368
   295
  ///   min x1 + 2 * x2 - x3
deba@2368
   296
  ///\endcode
deba@2368
   297
  ///
deba@2368
   298
  /// The first part gives the constraints to the lp. The constraints
deba@2368
   299
  /// could be equality, lower bound, upper bound or range for an
deba@2368
   300
  /// expression or equality, less or more for two expressions.
deba@2368
   301
  ///
deba@2368
   302
  /// The second part gives the bounds for the variables. The bounds
deba@2368
   303
  /// could be the same as for the single expression so equality,
deba@2368
   304
  /// lower bound, upper bound or range.
deba@2368
   305
  ///
deba@2368
   306
  /// The third part is the objective function, it should start with
deba@2368
   307
  /// \c min or \c max and then a valid linear expression.
deba@2368
   308
  ///
deba@2368
   309
  /// The reader constructs automatically the variable for a name if
deba@2368
   310
  /// there is not already a variable with the same name.
deba@2368
   311
  ///
deba@2368
   312
  /// The basic way to read an LP problem is made by the next code:
deba@2368
   313
  ///\code
deba@2368
   314
  /// Lp lp;
deba@2368
   315
  ///
deba@2368
   316
  /// LemonReader reader(filename_or_istream);
deba@2368
   317
  /// LpReader lpreader(reader, lp);
deba@2368
   318
  /// 
deba@2368
   319
  /// reader.run();
deba@2368
   320
  ///\endcode
deba@2368
   321
  ///
deba@2368
   322
  /// Of course instead of \c LemonReader you can give a \c
deba@2368
   323
  /// GraphReader to the LpReader constructor. Also useful that you
deba@2368
   324
  /// can mix lp problems and graphs in the same file.
deba@2316
   325
  class LpReader : public LemonReader::SectionReader {
deba@2316
   326
    typedef LemonReader::SectionReader Parent;
deba@2316
   327
  public:
deba@2316
   328
deba@2316
   329
deba@2316
   330
    /// \brief Constructor.
deba@2316
   331
    ///
deba@2368
   332
    /// Constructor for LpReader. It creates the LpReader and attachs
deba@2316
   333
    /// it into the given LemonReader. The lp reader will add
deba@2316
   334
    /// variables, constraints and objective function to the
deba@2316
   335
    /// given lp solver.
deba@2316
   336
    LpReader(LemonReader& _reader, LpSolverBase& _lp, 
deba@2316
   337
             const std::string& _name = std::string())
deba@2316
   338
      : Parent(_reader), lp(_lp), name(_name) {} 
deba@2316
   339
deba@2316
   340
deba@2316
   341
    /// \brief Destructor.
deba@2316
   342
    ///
deba@2368
   343
    /// Destructor for LpReader.
deba@2316
   344
    virtual ~LpReader() {}
deba@2316
   345
deba@2316
   346
  private:
deba@2316
   347
    LpReader(const LpReader&);
deba@2316
   348
    void operator=(const LpReader&);
deba@2316
   349
  
deba@2316
   350
  protected:
deba@2316
   351
deba@2316
   352
    /// \brief Gives back true when the SectionReader can process 
deba@2316
   353
    /// the section with the given header line.
deba@2316
   354
    ///
deba@2316
   355
    /// It gives back true when the header line starts with \c \@lp,
deba@2316
   356
    /// and the header line's name and the nodeset's name are the same.
deba@2316
   357
    virtual bool header(const std::string& line) {
deba@2316
   358
      std::istringstream ls(line);
deba@2316
   359
      std::string command;
deba@2316
   360
      std::string id;
deba@2316
   361
      ls >> command >> id;
deba@2316
   362
      return command == "@lp" && name == id;
deba@2316
   363
    }
deba@2316
   364
deba@2316
   365
  private:
deba@2316
   366
deba@2368
   367
    enum Part {
deba@2364
   368
      CONSTRAINTS, BOUNDS, OBJECTIVE
deba@2364
   369
    };
deba@2364
   370
deba@2316
   371
    enum Relation {
deba@2316
   372
      LE, EQ, GE
deba@2316
   373
    };
deba@2316
   374
deba@2364
   375
    std::istream& readConstraint(std::istream& is) {
deba@2364
   376
      LpSolverBase::Constr c;
deba@2316
   377
      char x;
deba@2316
   378
      LpSolverBase::Expr e1, e2;
deba@2316
   379
      Relation op1;
deba@2316
   380
      is >> std::ws;
deba@2316
   381
      readExpression(is, e1);
deba@2316
   382
      is >> std::ws;
deba@2316
   383
      readRelation(is, op1);
deba@2316
   384
      is >> std::ws;
deba@2316
   385
      readExpression(is, e2);
deba@2364
   386
      is >> std::ws;
deba@2316
   387
      if (!is.get(x)) {
deba@2316
   388
        if (op1 == LE) {
deba@2364
   389
          if (e1.size() == 0) {
deba@2364
   390
            c = e2 >= e1;
deba@2364
   391
          } else {
deba@2364
   392
            c = e1 <= e2;
deba@2364
   393
          }
deba@2316
   394
          c = e1 <= e2;
deba@2316
   395
        } else if (op1 == GE) {
deba@2364
   396
          if (e1.size() == 0) {
deba@2364
   397
            c = e2 <= e1;
deba@2364
   398
          } else {
deba@2364
   399
            c = e1 >= e2;
deba@2364
   400
          }
deba@2316
   401
        } else {
deba@2364
   402
          if (e1.size() == 0) {
deba@2364
   403
            c = e2 == e1;
deba@2364
   404
          } else {
deba@2364
   405
            c = e1 == e2;
deba@2364
   406
          }
deba@2316
   407
        }
deba@2316
   408
      } else {
deba@2316
   409
        is.putback(x);
deba@2316
   410
        LpSolverBase::Expr e3;
deba@2316
   411
        Relation op2;
deba@2316
   412
        readRelation(is, op2);
deba@2316
   413
        is >> std::ws;
deba@2316
   414
        readExpression(is, e3);
deba@2316
   415
        if (!e1.empty() || !e3.empty()) {
deba@2316
   416
          throw DataFormatError("Wrong range format");
deba@2316
   417
        }
deba@2316
   418
        if (op2 != op1 || op1 == EQ) {
deba@2316
   419
          throw DataFormatError("Wrong range format");
deba@2316
   420
        }
deba@2316
   421
        if (op1 == LE) {
deba@2316
   422
          c = e1.constComp() <= e2 <= e3.constComp();
deba@2316
   423
        } else {
deba@2316
   424
          c = e1.constComp() >= e2 >= e3.constComp();
deba@2316
   425
        }
deba@2364
   426
        is >> std::ws;
deba@2364
   427
        if (is.get(x)) {
deba@2364
   428
          throw DataFormatError("Wrong variable bounds format");
deba@2364
   429
        }
deba@2316
   430
      }
deba@2364
   431
      lp.addRow(c);
deba@2364
   432
      return is;
deba@2364
   433
    }
deba@2364
   434
deba@2364
   435
    std::istream& readObjective(std::istream& is) {
deba@2364
   436
      is >> std::ws;
deba@2364
   437
      std::string sense;
deba@2364
   438
      is >> sense;
deba@2364
   439
      if (sense != "min" && sense != "max") {
deba@2364
   440
        throw DataFormatError("Wrong objective function format");
deba@2364
   441
      }
deba@2364
   442
      LpSolverBase::Expr expr;
deba@2364
   443
      is >> std::ws;
deba@2364
   444
      readExpression(is, expr);
deba@2369
   445
      lp.obj(expr);
deba@2364
   446
      if (sense == "min") {
deba@2364
   447
        lp.min();
deba@2364
   448
      } else {
deba@2364
   449
        lp.max();
deba@2364
   450
      }
deba@2364
   451
      return is;
deba@2364
   452
    }
deba@2364
   453
deba@2364
   454
    std::istream& readBounds(std::istream& is) {
deba@2364
   455
      LpSolverBase::Col c;
deba@2364
   456
      char x;
deba@2364
   457
      is >> std::ws;
deba@2364
   458
      if (!is.get(x)) {
deba@2364
   459
        throw DataFormatError("Wrong variable bounds format");
deba@2364
   460
      }
deba@2364
   461
      if (varFirstChar(x)) {
deba@2364
   462
        is.putback(x);
deba@2364
   463
        readCol(is, c);
deba@2364
   464
        is >> std::ws;
deba@2364
   465
        Relation op1;
deba@2364
   466
        readRelation(is, op1);
deba@2364
   467
        double v;
deba@2364
   468
        readNum(is, v);
deba@2364
   469
        if (op1 == EQ) {
deba@2364
   470
          lp.colLowerBound(c, v);
deba@2364
   471
          lp.colUpperBound(c, v);
deba@2364
   472
        } else if (op1 == LE) {
deba@2364
   473
          lp.colUpperBound(c, v);
deba@2364
   474
        } else {
deba@2364
   475
          lp.colLowerBound(c, v);
deba@2364
   476
        }
deba@2364
   477
        is >> std::ws;
deba@2364
   478
        if (is.get(x)) {
deba@2364
   479
          throw DataFormatError("Wrong variable bounds format");
deba@2364
   480
        }
deba@2364
   481
      } else {
deba@2364
   482
        is.putback(x);
deba@2364
   483
        double v;
deba@2364
   484
        readNum(is, v);
deba@2364
   485
        is >> std::ws;
deba@2364
   486
        Relation op1;
deba@2364
   487
        readRelation(is, op1);
deba@2364
   488
        is >> std::ws;
deba@2364
   489
        readCol(is, c);
deba@2364
   490
        is >> std::ws;
deba@2364
   491
        if (is.get(x)) {
deba@2364
   492
          is.putback(x);
deba@2364
   493
          is >> std::ws;
deba@2364
   494
          Relation op2;
deba@2364
   495
          readRelation(is, op2);
deba@2364
   496
          double w;
deba@2364
   497
          is >> std::ws;
deba@2364
   498
          readNum(is, w);
deba@2364
   499
          if (op2 != op1 || op1 == EQ) {
deba@2364
   500
            throw DataFormatError("Wrong range format");
deba@2364
   501
          }
deba@2364
   502
          if (op1 == LE) {
deba@2364
   503
            lp.colLowerBound(c, v);
deba@2364
   504
            lp.colUpperBound(c, w);
deba@2364
   505
          } else {
deba@2364
   506
            lp.colLowerBound(c, w);
deba@2364
   507
            lp.colUpperBound(c, v);
deba@2364
   508
          }
deba@2368
   509
          is >> std::ws;
deba@2364
   510
          if (is.get(x)) {
deba@2364
   511
            throw DataFormatError("Wrong variable bounds format");
deba@2364
   512
          }
deba@2364
   513
        } else {
deba@2364
   514
          if (op1 == EQ) {
deba@2364
   515
            lp.colLowerBound(c, v);
deba@2364
   516
            lp.colUpperBound(c, v);
deba@2364
   517
          } else if (op1 == LE) {
deba@2364
   518
            lp.colLowerBound(c, v);
deba@2364
   519
          } else {
deba@2364
   520
            lp.colUpperBound(c, v);
deba@2364
   521
          }
deba@2364
   522
        }
deba@2364
   523
      }
deba@2364
   524
      return is;
deba@2316
   525
    }
deba@2316
   526
deba@2316
   527
    std::istream& readExpression(std::istream& is, LpSolverBase::Expr& e) {
deba@2316
   528
      LpSolverBase::Col c;
deba@2316
   529
      double d;
deba@2316
   530
      char x;
deba@2316
   531
      readElement(is, c, d);
deba@2316
   532
      if (c != INVALID) {
deba@2316
   533
        e += d * c;
deba@2316
   534
      } else {
deba@2316
   535
        e += d;
deba@2316
   536
      }
deba@2316
   537
      is >> std::ws;
deba@2316
   538
      while (is.get(x) && (x == '+' || x == '-')) {
deba@2316
   539
        is >> std::ws;
deba@2316
   540
        readElement(is, c, d);
deba@2316
   541
        if (c != INVALID) {
deba@2316
   542
          e += (x == '+' ? d : -d) * c;
deba@2316
   543
        } else {
deba@2316
   544
          e += (x == '+' ? d : -d);
deba@2316
   545
        }
deba@2316
   546
        is >> std::ws;
deba@2316
   547
      }
deba@2316
   548
      if (!is) {
deba@2316
   549
        is.clear();
deba@2316
   550
      } else {
deba@2316
   551
        is.putback(x);
deba@2316
   552
      }
deba@2316
   553
      return is;
deba@2316
   554
    }
deba@2316
   555
deba@2316
   556
    std::istream& readElement(std::istream& is, 
deba@2316
   557
                              LpSolverBase::Col& c, double& d) { 
deba@2316
   558
      d = 1.0;
deba@2316
   559
      c = INVALID;
deba@2316
   560
      char x, y;
deba@2316
   561
      if (!is.get(x)) throw DataFormatError("Cannot find lp element");
deba@2316
   562
      if (x == '+' || x == '-') {
deba@2316
   563
        is >> std::ws;
deba@2316
   564
        d *= x == '-' ? -1 : 1;
deba@2316
   565
        while (is.get(x) && (x == '+' || x == '-')) {
deba@2316
   566
          d *= x == '-' ? -1 : 1;
deba@2316
   567
          is >> std::ws;
deba@2316
   568
        }
deba@2316
   569
        if (!is) throw DataFormatError("Cannot find lp element");
deba@2316
   570
      }
deba@2316
   571
      if (numFirstChar(x)) {
deba@2316
   572
        is.putback(x);
deba@2316
   573
        double e;
deba@2316
   574
        readNum(is, e);
deba@2316
   575
        d *= e;
deba@2316
   576
      } else if (varFirstChar(x)) {
deba@2316
   577
        is.putback(x);
deba@2316
   578
        LpSolverBase::Col f;
deba@2316
   579
        readCol(is, f);
deba@2316
   580
        c = f;
deba@2316
   581
      } else {
deba@2316
   582
        throw DataFormatError("Invalid expression format");          
deba@2316
   583
      }
deba@2316
   584
      is >> std::ws;
deba@2316
   585
      while (is.get(y) && (y == '*' || y == '/')) {
deba@2316
   586
        is >> std::ws;
deba@2316
   587
        if (!is.get(x)) throw DataFormatError("Cannot find lp element");
deba@2316
   588
        if (x == '+' || x == '-') {
deba@2316
   589
          is >> std::ws;
deba@2316
   590
          d *= x == '-' ? -1 : 1;
deba@2316
   591
          while (is.get(x) && (x == '+' || x == '-')) {
deba@2316
   592
            d *= x == '-' ? -1 : 1;
deba@2316
   593
            is >> std::ws;
deba@2316
   594
          }
deba@2316
   595
          if (!is) throw DataFormatError("Cannot find lp element");
deba@2316
   596
        }
deba@2316
   597
        if (numFirstChar(x)) {
deba@2316
   598
          is.putback(x);
deba@2316
   599
          double e;
deba@2316
   600
          readNum(is, e);
deba@2316
   601
          if (y == '*') {
deba@2316
   602
            d *= e;
deba@2316
   603
          } else {
deba@2316
   604
            d /= e;
deba@2316
   605
          }
deba@2316
   606
        } else if (varFirstChar(x)) {
deba@2316
   607
          is.putback(x);
deba@2316
   608
          LpSolverBase::Col f;
deba@2316
   609
          readCol(is, f);
deba@2316
   610
          if (y == '*') {
deba@2316
   611
            if (c == INVALID) {
deba@2316
   612
              c = f;
deba@2316
   613
            } else {
deba@2316
   614
              throw DataFormatError("Quadratic element in expression");
deba@2316
   615
            }
deba@2316
   616
          } else {
deba@2316
   617
            throw DataFormatError("Division by variable");
deba@2316
   618
          }
deba@2316
   619
        } else {
deba@2316
   620
          throw DataFormatError("Invalid expression format");          
deba@2316
   621
        }
deba@2316
   622
        is >> std::ws;
deba@2316
   623
      }
deba@2316
   624
      if (!is) {
deba@2316
   625
        is.clear();
deba@2316
   626
      } else {
deba@2316
   627
        is.putback(y);
deba@2316
   628
      }
deba@2316
   629
      return is;
deba@2316
   630
    }
deba@2316
   631
deba@2316
   632
    std::istream& readCol(std::istream& is, LpSolverBase::Col& c) {
deba@2316
   633
      char x;
deba@2316
   634
      std::string var;
deba@2316
   635
      while (is.get(x) && varChar(x)) {
deba@2316
   636
        var += x;
deba@2316
   637
      }
deba@2316
   638
      if (!is) {
deba@2316
   639
        is.clear();
deba@2316
   640
      } else {
deba@2316
   641
        is.putback(x);
deba@2316
   642
      }
deba@2368
   643
      c = lp.colByName(var);
deba@2368
   644
      if (c == INVALID) {
deba@2316
   645
        c = lp.addCol();
deba@2316
   646
        lp.colName(c, var);
deba@2316
   647
      }
deba@2316
   648
      return is;
deba@2316
   649
    }
deba@2316
   650
deba@2316
   651
    std::istream& readNum(std::istream& is, double& d) {
deba@2316
   652
      is >> d;
deba@2316
   653
      if (!is) throw DataFormatError("Wrong number format");
deba@2316
   654
      return is;
deba@2316
   655
    }
deba@2316
   656
deba@2316
   657
    std::istream& readRelation(std::istream& is, Relation& op) {
deba@2316
   658
      char x, y;
deba@2316
   659
      if (!is.get(x) || !(x == '<' || x == '=' || x == '>')) {
deba@2316
   660
        throw DataFormatError("Wrong relation operator");
deba@2316
   661
      }
deba@2316
   662
      if (!is.get(y) || y != '=') {
deba@2316
   663
        throw DataFormatError("Wrong relation operator");
deba@2316
   664
      }
deba@2316
   665
      switch (x) {
deba@2316
   666
      case '<': op = LE; 
deba@2316
   667
        break;
deba@2316
   668
      case '=': op = EQ; 
deba@2316
   669
        break;
deba@2316
   670
      case '>': op = GE; 
deba@2316
   671
        break;
deba@2316
   672
      }
deba@2316
   673
      return is;
deba@2316
   674
    }
deba@2316
   675
deba@2316
   676
    static bool relationFirstChar(char c) {
deba@2316
   677
      return c == '<' || c == '=' || c == '>';
deba@2316
   678
    }
deba@2316
   679
deba@2316
   680
    static bool varFirstChar(char c) {
deba@2316
   681
      return (c >= 'a' && c <= 'z') || (c >= 'A' && c <= 'Z');
deba@2316
   682
    }
deba@2316
   683
deba@2316
   684
    static bool numFirstChar(char c) {
deba@2316
   685
      return (c >= '0' && c <= '9') || c == '.';
deba@2316
   686
    }
deba@2368
   687
    
deba@2316
   688
    static bool varChar(char c) {
deba@2316
   689
      return (c >= '0' && c <= '9') || 
deba@2364
   690
        (c >= 'a' && c <= 'z') || 
deba@2364
   691
        (c >= 'A' && c <= 'Z') ||
deba@2364
   692
        c == '[' || c == ']';
deba@2316
   693
    }
deba@2316
   694
    
deba@2316
   695
  protected:
deba@2316
   696
deba@2316
   697
    /// \brief Reader function of the section.
deba@2316
   698
    ///
deba@2316
   699
    /// It reads the content of the section.
deba@2316
   700
    virtual void read(std::istream& is) {
deba@2316
   701
      std::string line;
deba@2368
   702
      Part part = CONSTRAINTS;
deba@2316
   703
      while (getline(is, line)) {
deba@2316
   704
        std::istringstream ls(line);
deba@2364
   705
        std::string type;
deba@2364
   706
        ls >> type;
deba@2364
   707
        if (type == "constraints") {
deba@2368
   708
          part = CONSTRAINTS;
deba@2368
   709
          ls >> std::ws;
deba@2368
   710
          char x;
deba@2368
   711
          if (ls.get(x))
deba@2368
   712
            throw DataFormatError("Wrong Lp format");
deba@2364
   713
        } else if (type == "bounds") {
deba@2368
   714
          part = BOUNDS;
deba@2368
   715
          ls >> std::ws;
deba@2368
   716
          char x;
deba@2368
   717
          if (ls.get(x))
deba@2368
   718
            throw DataFormatError("Wrong Lp format");
deba@2364
   719
        } else if (type == "objective") {
deba@2368
   720
          part = OBJECTIVE;
deba@2368
   721
          ls >> std::ws;
deba@2368
   722
          char x;
deba@2368
   723
          if (ls.get(x))
deba@2368
   724
            throw DataFormatError("Wrong Lp format");
deba@2316
   725
        } else {
deba@2316
   726
          ls.str(line);
deba@2368
   727
          switch (part) {
deba@2364
   728
          case CONSTRAINTS:
deba@2364
   729
            readConstraint(ls);
deba@2364
   730
            break;
deba@2364
   731
          case BOUNDS:
deba@2364
   732
            readBounds(ls);
deba@2364
   733
            break;
deba@2364
   734
          case OBJECTIVE:
deba@2364
   735
            readObjective(ls);
deba@2364
   736
            break;
deba@2364
   737
          }
deba@2368
   738
        }
deba@2316
   739
      }
deba@2316
   740
    }
deba@2316
   741
      
deba@2316
   742
    virtual void missing() {
deba@2316
   743
      ErrorMessage msg;
deba@2316
   744
      msg << "Lp section not found in file: @lp " << name;
deba@2316
   745
      throw IoParameterError(msg.message());
deba@2316
   746
    }
deba@2316
   747
deba@2316
   748
  private:
deba@2316
   749
deba@2316
   750
      
deba@2316
   751
    LpSolverBase& lp;
deba@2316
   752
    std::string name;
deba@2316
   753
  };
deba@2316
   754
deba@2363
   755
deba@2370
   756
  /// \ingroup lp_utils
deba@2368
   757
  ///
deba@2368
   758
  /// \brief Lp section writer for lemon IO
deba@2368
   759
  ///
deba@2368
   760
  /// This section reader provides an easy way to write an Lp problem
deba@2368
   761
  /// to a file. The lemon lp section format contains three parts.
deba@2368
   762
  ///
deba@2368
   763
  ///\code
deba@2368
   764
  /// @lp
deba@2368
   765
  /// constraints
deba@2368
   766
  ///   7 == x1 - 1 * x2
deba@2368
   767
  ///   2 * x1 + x3 / 2 <= 7
deba@2368
   768
  ///   x2 + -3 * x3 >= 8
deba@2368
   769
  ///   3 <= x2 - 2 * x1 <= 8
deba@2368
   770
  /// bounds
deba@2368
   771
  ///   x1 >= 3
deba@2368
   772
  ///   2 <= x2 <= 5
deba@2368
   773
  ///   0 <= x3 <= 8
deba@2368
   774
  /// objective
deba@2368
   775
  ///   min x1 + 2 * x2 - x3
deba@2368
   776
  ///\endcode
deba@2368
   777
  ///
deba@2368
   778
  /// The first part gives the constraints to the lp. The constraints
deba@2368
   779
  /// could be equality, lower bound, upper bound or range for an
deba@2368
   780
  /// expression or equality, less or more for two expressions.
deba@2368
   781
  ///
deba@2368
   782
  /// The second part gives the bounds for the variables. The bounds
deba@2368
   783
  /// could be the same as for the single expression so equality,
deba@2368
   784
  /// lower bound, upper bound or range.
deba@2368
   785
  ///
deba@2368
   786
  /// The third part is the objective function, it should start with
deba@2368
   787
  /// \c min or \c max and then a valid linear expression.
deba@2368
   788
  ///
deba@2368
   789
  /// If an LP variable does not have name in the writer, then it will
deba@2368
   790
  /// automatically created in the writer. This make a slight change
deba@2368
   791
  /// in the \c const variable.
deba@2368
   792
  ///
deba@2368
   793
  /// The basic way to write an LP problem is made by the next code:
deba@2368
   794
  ///\code
deba@2368
   795
  /// Lp lp;
deba@2368
   796
  ///
deba@2368
   797
  /// LemonWriter writer(filename_or_ostream);
deba@2368
   798
  /// LpWriter lpwriter(writer, lp);
deba@2368
   799
  /// 
deba@2368
   800
  /// writer.run();
deba@2368
   801
  ///\endcode
deba@2368
   802
  ///
deba@2368
   803
  /// Of course instead of \c LemonWriter you can give a \c
deba@2368
   804
  /// GraphWriter to the LpWriter constructor. Also useful that you
deba@2368
   805
  /// can mix lp problems and graphs in the same file.
deba@2364
   806
  class LpWriter : public LemonWriter::SectionWriter {
deba@2364
   807
    typedef LemonWriter::SectionWriter Parent;
deba@2364
   808
  public:
deba@2363
   809
deba@2363
   810
deba@2364
   811
    /// \brief Constructor.
deba@2364
   812
    ///
deba@2364
   813
    /// Constructor for LpWriter. It creates the LpWriter and attach
deba@2368
   814
    /// it into the given LemonWriter.
deba@2368
   815
    LpWriter(LemonWriter& _writer, const LpSolverBase& _lp, 
deba@2364
   816
             const std::string& _name = std::string())
deba@2364
   817
      : Parent(_writer), lp(_lp), name(_name) {} 
deba@2363
   818
deba@2363
   819
deba@2364
   820
    /// \brief Destructor.
deba@2364
   821
    ///
deba@2368
   822
    /// Destructor for LpWriter.
deba@2364
   823
    virtual ~LpWriter() {}
deba@2363
   824
deba@2364
   825
  private:
deba@2364
   826
    LpWriter(const LpWriter&);
deba@2364
   827
    void operator=(const LpWriter&);
deba@2363
   828
  
deba@2364
   829
  protected:
deba@2363
   830
deba@2364
   831
    /// \brief Gives back true when the SectionWriter can process 
deba@2364
   832
    /// the section with the given header line.
deba@2364
   833
    ///
deba@2364
   834
    /// It gives back the header line of the \c \@lp section.
deba@2364
   835
    virtual std::string header() {
deba@2364
   836
      std::ostringstream ls;
deba@2364
   837
      ls << "@lp " << name;
deba@2364
   838
      return ls.str();
deba@2364
   839
    }
deba@2363
   840
deba@2364
   841
  private:
deba@2363
   842
deba@2364
   843
    void createCols() {
deba@2368
   844
      int num = 0;
deba@2364
   845
deba@2364
   846
      for (LpSolverBase::ColIt it(lp); it != INVALID; ++it) {
deba@2364
   847
        std::string name = lp.colName(it);
deba@2368
   848
        if (name.empty()) {
deba@2364
   849
          std::ostringstream ls;
deba@2368
   850
          ls << "x" << num;
deba@2364
   851
          ++num;
deba@2368
   852
          while (lp.colByName(ls.str()) != INVALID) {
deba@2368
   853
            ls.str(std::string());
deba@2368
   854
            ls << "x" << num;
deba@2368
   855
            ++num;
deba@2368
   856
          }
deba@2368
   857
          const_cast<LpSolverBase&>(lp).colName(it, ls.str());
deba@2364
   858
        }
deba@2364
   859
      }
deba@2364
   860
    }
deba@2364
   861
    
deba@2364
   862
    void writeExpression(std::ostream& os, const LpSolverBase::Expr& e) {
deba@2364
   863
      bool first = true;
deba@2364
   864
      for (LpSolverBase::Expr::const_iterator jt = e.begin(); 
deba@2364
   865
           jt != e.end(); ++jt) {
deba@2364
   866
        if (jt->second < 0.0) {
deba@2364
   867
          os << "- ";
deba@2364
   868
          if (jt->second != -1.0) {
deba@2364
   869
            os << -jt->second << " * ";
deba@2364
   870
          }
deba@2364
   871
        } else if (jt->second > 0.0) {
deba@2364
   872
          if (!first) {
deba@2364
   873
            os << "+ ";
deba@2364
   874
          }
deba@2364
   875
          if (jt->second != 1.0) {
deba@2364
   876
            os << jt->second << " * ";
deba@2364
   877
          }          
deba@2364
   878
        }
deba@2364
   879
        first = false;
deba@2368
   880
        os << lp.colName(jt->first) << " ";
deba@2364
   881
      }
deba@2364
   882
      if (e.constComp() < 0.0) {
deba@2364
   883
        os << "- " << -e.constComp() << " ";
deba@2364
   884
      } else if (e.constComp() > 0.0) {
deba@2364
   885
        if (!first) {
deba@2364
   886
          os << "+ ";
deba@2364
   887
        }
deba@2364
   888
        os << e.constComp() << " ";
deba@2421
   889
      }
deba@2421
   890
      if (e.begin() == e.end() && e.constComp() == 0.0) {
deba@2421
   891
        os << "0 ";
deba@2421
   892
      }
deba@2364
   893
    }
deba@2364
   894
deba@2364
   895
  protected:
deba@2364
   896
deba@2364
   897
    /// \brief Writer function of the section.
deba@2364
   898
    ///
deba@2364
   899
    /// It writes the content of the section.
deba@2364
   900
    virtual void write(std::ostream& os) {
deba@2364
   901
      createCols();
deba@2364
   902
deba@2364
   903
      os << "constraints" << std::endl;
deba@2363
   904
      
deba@2364
   905
      for (LpSolverBase::RowIt it(lp); it != INVALID; ++it) {
deba@2364
   906
        double lower, upper;
deba@2364
   907
        lp.getRowBounds(it, lower, upper);
deba@2364
   908
        if (lower == -LpSolverBase::INF && upper == LpSolverBase::INF) 
deba@2364
   909
          continue;
deba@2364
   910
        os << "   ";
deba@2364
   911
        
deba@2364
   912
        if (lower != upper) {
deba@2364
   913
          if (lower != -LpSolverBase::INF) {
deba@2364
   914
            os << lower << " <= ";
deba@2364
   915
          }
deba@2364
   916
          
deba@2364
   917
          writeExpression(os, lp.row(it));
deba@2364
   918
          
deba@2364
   919
          if (upper != LpSolverBase::INF) {
deba@2364
   920
            os << "<= " << upper << " ";
deba@2364
   921
          }
deba@2364
   922
        } else {
deba@2363
   923
deba@2364
   924
          writeExpression(os, lp.row(it));
deba@2364
   925
          os << "== " << upper << " ";
deba@2364
   926
          
deba@2364
   927
        }
deba@2363
   928
deba@2364
   929
        os << std::endl;
deba@2364
   930
      }
deba@2363
   931
deba@2364
   932
      os << "bounds" << std::endl;
deba@2364
   933
      
deba@2364
   934
      for (LpSolverBase::ColIt it(lp); it != INVALID; ++it) {
deba@2364
   935
        double lower = lp.colLowerBound(it);
deba@2364
   936
        double upper = lp.colUpperBound(it);
deba@2364
   937
        if (lower == -LpSolverBase::INF && upper == LpSolverBase::INF) 
deba@2364
   938
          continue;
deba@2364
   939
        os << "   ";
deba@2363
   940
deba@2364
   941
        if (lower != upper) {
deba@2364
   942
          if (lower != -LpSolverBase::INF) {
deba@2364
   943
            os << lower << " <= ";
deba@2364
   944
          }
deba@2364
   945
          
deba@2368
   946
          os << lp.colName(it) << " ";
deba@2364
   947
          
deba@2364
   948
          if (upper != LpSolverBase::INF) {
deba@2364
   949
            os << "<= " << upper << " ";
deba@2364
   950
          }
deba@2364
   951
        } else {
deba@2368
   952
          os << lp.colName(it) << " == " << upper << " ";
deba@2364
   953
        }
deba@2364
   954
        os << std::endl;
deba@2364
   955
      }
deba@2363
   956
deba@2364
   957
      os << "objective" << std::endl;
deba@2364
   958
      os << "   ";
deba@2369
   959
      if (lp.isMin()) {
deba@2364
   960
        os << "min ";
deba@2364
   961
      } else {
deba@2364
   962
        os << "max ";
deba@2364
   963
      }
deba@2364
   964
      writeExpression(os, lp.obj());
deba@2364
   965
      os << std::endl;
deba@2364
   966
    }
deba@2364
   967
      
deba@2363
   968
deba@2364
   969
  private:
deba@2363
   970
deba@2368
   971
    const LpSolverBase& lp;
deba@2364
   972
    std::string name;
deba@2364
   973
  };
deba@2363
   974
deba@2316
   975
}
deba@2316
   976
deba@2316
   977
#endif