COIN-OR::LEMON - Graph Library

Changeset 2368:6b2e8b734ae7 in lemon-0.x


Ignore:
Timestamp:
02/19/07 13:11:41 (12 years ago)
Author:
Balazs Dezso
Branch:
default
Phase:
public
Convert:
svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@3183
Message:

Bug fixes
Documentation

Files:
6 edited

Legend:

Unmodified
Added
Removed
  • doc/groups.dox

    r2350 r2368  
    214214*/
    215215
     216/**
     217\ingroup gen_opt_group
     218@defgroup gen_opt_tools Various Tools for Optimization
     219\brief This group adds some helper tools to general optimization
     220framework implemented in LEMON.
     221
     222This group adds some helper tools to general optimization framework
     223implemented in LEMON.
     224
     225*/
     226
    216227/**
    217228@defgroup misc Miscellaneous Tools
  • lemon/lemon_reader.h

    r2334 r2368  
    741741  /// \brief SectionReader for reading a graph's nodeset.
    742742  ///
    743   /// The lemon format can store multiple graph nodesets with several maps.
    744   /// The nodeset section's header line is \c \@nodeset \c nodeset_name, but the
    745   /// \c nodeset_name may be empty.
     743  /// The lemon format can store multiple graph nodesets with several
     744  /// maps.  The nodeset section's header line is \c \@nodeset \c
     745  /// nodeset_name, but the \c nodeset_name may be empty.
    746746  ///
    747747  /// The first line of the section contains the names of the maps separated
  • lemon/lp_base.h

    r2366 r2368  
    10611061      _setColName(_lpId(c), name);
    10621062    }
     1063
     1064    /// Get the column by its name
     1065   
     1066    ///\param name The name of the column
     1067    ///\return the proper column or \c INVALID
     1068    Col colByName(const std::string& name) const {
     1069      int k = _colByName(name);
     1070      return k != -1 ? Col(cols.fixId(k)) : Col(INVALID);
     1071    }
    10631072   
    10641073    /// Set an element of the coefficient matrix of the LP
  • lemon/lp_glpk.cc

    r2366 r2368  
    2929    cols = _lp_bits::LpId(1);
    3030    lp = lpx_create_prob();
     31    lpx_create_index(lp);
    3132    ///\todo control function for this:
    3233    lpx_set_int_parm(lp, LPX_K_DUAL, 1);
  • lemon/lp_soplex.cc

    r2366 r2368  
    7777  void LpSoplex::_eraseCol(int i) {
    7878    soplex->removeCol(i);
     79    invColNames.erase(colNames[i]);
    7980    colNames[i] = colNames.back();
     81    invColNames[colNames.back()] = i;
    8082    colNames.pop_back();
    8183    primal_value[i] = primal_value.back();
  • lemon/lp_utils.h

    r2364 r2368  
    2525#include <lemon/lemon_writer.h>
    2626
     27#include <map>
     28#include <set>
     29
     30
    2731namespace lemon {
    2832
     33  /// \ingroup gen_opt_tools
     34  ///
     35  /// \brief The map for the result of the lp variables.
     36  ///
     37  /// The map for the result of the lp variables.
     38  class LpResultMap {
     39  public:
     40    typedef LpSolverBase::Col Key;
     41    typedef LpSolverBase::Value Value;
     42
     43    /// \brief Constructor
     44    ///
     45    /// Constructor
     46    LpResultMap(const LpSolverBase& _lp) : lp(_lp) {}
     47    LpSolverBase::Value operator[](const LpSolverBase::Col col) const {
     48      return lp.primal(col);
     49    }
     50  private:
     51    const LpSolverBase& lp;
     52  };
     53
     54  /// \ingroup gen_opt_tools
     55  ///
     56  /// \brief The map for the name of the lp variables.
     57  ///
     58  /// The map for the name of the lp variables.
     59  class LpColNameMap {
     60  public:
     61    typedef LpSolverBase::Col Key;
     62    typedef std::string Value;
     63
     64    /// \brief Constructor
     65    ///
     66    /// Constructor
     67    LpColNameMap(const LpSolverBase& _lp) : lp(_lp) {}
     68    std::string operator[](const LpSolverBase::Col col) const {
     69      return lp.colName(col);
     70    }
     71  private:
     72    const LpSolverBase& lp;
     73  };
     74
     75  /// \ingroup gen_opt_tools
     76  ///
     77  /// \brief Writeable map for the name of the lp variables.
     78  ///
     79  /// Writeable map for the name of the lp variables.
     80  class LpColNameWriteMap {
     81  public:
     82    typedef LpSolverBase::Col Key;
     83    typedef std::string Value;
     84
     85    /// \brief Constructor
     86    ///
     87    /// Constructor
     88    LpColNameWriteMap(LpSolverBase& _lp) : lp(_lp) {}
     89    std::string operator[](const LpSolverBase::Col col) const {
     90      return lp.colName(col);
     91    }
     92    void set(const LpSolverBase::Col col, const std::string& name) {
     93      lp.colName(col, name);
     94    }
     95  private:
     96    LpSolverBase& lp;
     97  };
     98
     99  /// \ingroup gen_opt_tools
     100  ///
     101  /// \brief Returns an \ref LpColNameMap class
     102  ///
     103  /// This function just returns an \ref LpColNameMap class.
     104  /// \relates LpColNameMap
     105  LpColNameMap lpColNameMap(const LpSolverBase& lp) {
     106    return LpColNameMap(lp);
     107  }
     108
     109  LpColNameWriteMap lpColNameMap(LpSolverBase& lp) {
     110    return LpColNameWriteMap(lp);
     111  }
     112
     113  /// \ingroup gen_opt_tools
     114  ///
     115  /// \brief Lp variable item reader for Lemon IO
     116  ///
     117  /// This class is an Lp variable item reader for Lemon IO. It makes
     118  /// possible to store lp variables in lemon file. The usage of this
     119  /// class is very simple:
     120  ///
     121  ///\code
     122  /// Graph graph;
     123  /// Lp lp;
     124  /// Graph::EdgeMap<Lp::Col> var(graph);
     125  ///
     126  /// GraphReader<Graph> reader(cin, graph);
     127  /// reader.readEdgeMap("lpvar", var, LpColReader(lp));
     128  /// reader.run();
     129  ///\endcode
     130  ///
     131  /// If there is already a variable with the same name in the lp then
     132  /// it will be used for the return value. If there is no such variable
     133  /// then it will be constructed. The file could contain \c '-' as value
     134  /// which means that no lp variable associated to the current item and
     135  /// in this case INVALID will be returned.
     136  class LpColReader {
     137  public:
     138
     139    /// \brief The value type of reader.
     140    ///
     141    /// The value type of reader.
     142    typedef LpSolverBase::Col Value;
     143
     144    /// \brief Constructor for the reader.
     145    ///
     146    /// Constructor for the reader.
     147    LpColReader(LpSolverBase& _lp) : lp(_lp) {}
     148
     149    /// \brief Reads an lp variable from the given stream.
     150    ///
     151    /// Reads an lp variable string from the given stream.
     152    void read(std::istream& is, LpSolverBase::Col& col) const {
     153      char x;
     154      is >> std::ws;
     155      if (!is.get(x))
     156        throw DataFormatError("Wrong Lp Column format!");
     157      if (varFirstChar(x)) {
     158        std::string var;
     159        var += x;
     160       
     161        while (is.get(x) && varChar(x)) {
     162          var += x;
     163        }
     164        if (!is) {
     165          is.clear();
     166        } else {
     167          is.putback(x);
     168        }
     169        col = lp.colByName(var);
     170        if (col == INVALID) {
     171          col = lp.addCol();
     172          lp.colName(col, var);
     173        }
     174      } else if (x == '-') {
     175        col = INVALID;
     176        is >> std::ws;
     177      } else {
     178        std::cerr << x << std::endl;
     179        throw DataFormatError("Wrong Lp Column format");
     180      }
     181    }
     182
     183  private:
     184
     185    static bool varFirstChar(char c) {
     186      return (c >= 'a' && c <= 'z') || (c >= 'A' && c <= 'Z');
     187    }
     188
     189    static bool varChar(char c) {
     190      return (c >= '0' && c <= '9') ||
     191        (c >= 'a' && c <= 'z') ||
     192        (c >= 'A' && c <= 'Z') ||
     193        c == '[' || c == ']';
     194    }
     195   
     196    LpSolverBase& lp;
     197
     198  };
     199
     200  /// \ingroup gen_opt_tools
     201  ///
     202  /// \brief Lp variable item writer for Lemon IO
     203  ///
     204  /// This class is an Lp variable item writer for Lemon IO. It makes
     205  /// possible to store lp variables in lemon file. The usage of this
     206  /// class is very simple:
     207  ///
     208  ///\code
     209  /// Graph graph;
     210  /// Lp lp;
     211  /// Graph::EdgeMap<Lp::Col> var(graph);
     212  ///
     213  /// GraphWriter<Graph> writer(cin, graph);
     214  /// writer.writeEdgeMap("lpvar", var, LpColWriter(lp));
     215  /// writer.run();
     216  ///\endcode
     217  ///
     218  /// If there is no name associated to the current item then the name
     219  /// will automatically constructed. If the value is INVALID then it
     220  /// will write an \c '-' value to the file.
     221  class LpColWriter {
     222  public:
     223
     224    /// \brief The value type of writer.
     225    ///
     226    /// The value type of writer.
     227    typedef LpSolverBase::Col Value;
     228
     229    /// \brief Constructor for the writer.
     230    ///
     231    /// Constructor for the writer.
     232    LpColWriter(const LpSolverBase& _lp) : lp(_lp), num(0) {}
     233
     234    /// \brief Writes an lp variable to the given stream.
     235    ///
     236    /// Writes an lp variable to the given stream.
     237    void write(std::ostream& os, const LpSolverBase::Col& col) const {
     238      if (col != INVALID) {
     239        std::string name = lp.colName(col);
     240        if (name.empty()) {
     241          std::ostringstream ls;
     242          ls << "x" << num;
     243          ++num;
     244          while (lp.colByName(ls.str()) != INVALID) {
     245            ls.str(std::string());
     246            ls << "x" << num;
     247            ++num;
     248          }
     249          const_cast<LpSolverBase&>(lp).colName(col, ls.str());
     250          os << ls.str();
     251        } else {
     252          os << name;
     253        }
     254      } else {
     255        os << "-";
     256      }
     257    }
     258
     259  private:
     260
     261    const LpSolverBase& lp;
     262    mutable int num;
     263
     264  };
     265
     266  /// \ingroup gen_opt_tools
     267  ///
     268  /// \brief Lp section reader for lemon IO
     269  ///
     270  /// This section reader provides an easy way to read an Lp problem
     271  /// from a file. The lemon lp section format contains three parts.
     272  ///
     273  ///\code
     274  /// @lp
     275  /// constraints
     276  ///   7 == x1 - 1 * x2
     277  ///   2 * x1 + x3 / 2 <= 7
     278  ///   x2 + -3 * x3 >= 8
     279  ///   3 <= x2 - 2 * x1 <= 8
     280  /// bounds
     281  ///   x1 >= 3
     282  ///   2 <= x2 <= 5
     283  ///   0 <= x3 <= 8
     284  /// objective
     285  ///   min x1 + 2 * x2 - x3
     286  ///\endcode
     287  ///
     288  /// The first part gives the constraints to the lp. The constraints
     289  /// could be equality, lower bound, upper bound or range for an
     290  /// expression or equality, less or more for two expressions.
     291  ///
     292  /// The second part gives the bounds for the variables. The bounds
     293  /// could be the same as for the single expression so equality,
     294  /// lower bound, upper bound or range.
     295  ///
     296  /// The third part is the objective function, it should start with
     297  /// \c min or \c max and then a valid linear expression.
     298  ///
     299  /// The reader constructs automatically the variable for a name if
     300  /// there is not already a variable with the same name.
     301  ///
     302  /// The basic way to read an LP problem is made by the next code:
     303  ///\code
     304  /// Lp lp;
     305  ///
     306  /// LemonReader reader(filename_or_istream);
     307  /// LpReader lpreader(reader, lp);
     308  ///
     309  /// reader.run();
     310  ///\endcode
     311  ///
     312  /// Of course instead of \c LemonReader you can give a \c
     313  /// GraphReader to the LpReader constructor. Also useful that you
     314  /// can mix lp problems and graphs in the same file.
    29315  class LpReader : public LemonReader::SectionReader {
    30316    typedef LemonReader::SectionReader Parent;
     
    34320    /// \brief Constructor.
    35321    ///
    36     /// Constructor for LpReader. It creates the LpReader and attach
     322    /// Constructor for LpReader. It creates the LpReader and attachs
    37323    /// it into the given LemonReader. The lp reader will add
    38324    /// variables, constraints and objective function to the
     
    45331    /// \brief Destructor.
    46332    ///
    47     /// Destructor for NodeSetReader.
     333    /// Destructor for LpReader.
    48334    virtual ~LpReader() {}
    49335
     
    69355  private:
    70356
    71     enum SubSection {
     357    enum Part {
    72358      CONSTRAINTS, BOUNDS, OBJECTIVE
    73359    };
     
    211497            lp.colUpperBound(c, v);
    212498          }
     499          is >> std::ws;
    213500          if (is.get(x)) {
    214501            throw DataFormatError("Wrong variable bounds format");
     
    344631        is.putback(x);
    345632      }
    346       ColMap::const_iterator it = cols.find(var);
    347       if (cols.find(var) != cols.end()) {
    348         c = it->second;
    349       } else {
     633      c = lp.colByName(var);
     634      if (c == INVALID) {
    350635        c = lp.addCol();
    351         cols.insert(std::make_pair(var, c));
    352636        lp.colName(c, var);
    353637      }
     
    391675      return (c >= '0' && c <= '9') || c == '.';
    392676    }
    393 
     677   
    394678    static bool varChar(char c) {
    395679      return (c >= '0' && c <= '9') ||
     
    406690    virtual void read(std::istream& is) {
    407691      std::string line;
    408       SubSection sub = CONSTRAINTS;
     692      Part part = CONSTRAINTS;
    409693      while (getline(is, line)) {
    410694        std::istringstream ls(line);
     
    412696        ls >> type;
    413697        if (type == "constraints") {
    414           sub = CONSTRAINTS;
     698          part = CONSTRAINTS;
     699          ls >> std::ws;
     700          char x;
     701          if (ls.get(x))
     702            throw DataFormatError("Wrong Lp format");
    415703        } else if (type == "bounds") {
    416           sub = BOUNDS;
     704          part = BOUNDS;
     705          ls >> std::ws;
     706          char x;
     707          if (ls.get(x))
     708            throw DataFormatError("Wrong Lp format");
    417709        } else if (type == "objective") {
    418           sub = OBJECTIVE;
     710          part = OBJECTIVE;
     711          ls >> std::ws;
     712          char x;
     713          if (ls.get(x))
     714            throw DataFormatError("Wrong Lp format");
    419715        } else {
    420716          ls.str(line);
    421           switch (sub) {
     717          switch (part) {
    422718          case CONSTRAINTS:
    423719            readConstraint(ls);
     
    430726            break;
    431727          }
    432         }       
     728        }
    433729      }
    434730    }
     
    442738  private:
    443739
    444     typedef std::map<std::string, LpSolverBase::Col> ColMap;
    445740     
    446741    LpSolverBase& lp;
    447742    std::string name;
    448     ColMap cols;
    449743  };
    450744
    451745
     746  /// \ingroup gen_opt_tools
     747  ///
     748  /// \brief Lp section writer for lemon IO
     749  ///
     750  /// This section reader provides an easy way to write an Lp problem
     751  /// to a file. The lemon lp section format contains three parts.
     752  ///
     753  ///\code
     754  /// @lp
     755  /// constraints
     756  ///   7 == x1 - 1 * x2
     757  ///   2 * x1 + x3 / 2 <= 7
     758  ///   x2 + -3 * x3 >= 8
     759  ///   3 <= x2 - 2 * x1 <= 8
     760  /// bounds
     761  ///   x1 >= 3
     762  ///   2 <= x2 <= 5
     763  ///   0 <= x3 <= 8
     764  /// objective
     765  ///   min x1 + 2 * x2 - x3
     766  ///\endcode
     767  ///
     768  /// The first part gives the constraints to the lp. The constraints
     769  /// could be equality, lower bound, upper bound or range for an
     770  /// expression or equality, less or more for two expressions.
     771  ///
     772  /// The second part gives the bounds for the variables. The bounds
     773  /// could be the same as for the single expression so equality,
     774  /// lower bound, upper bound or range.
     775  ///
     776  /// The third part is the objective function, it should start with
     777  /// \c min or \c max and then a valid linear expression.
     778  ///
     779  /// If an LP variable does not have name in the writer, then it will
     780  /// automatically created in the writer. This make a slight change
     781  /// in the \c const variable.
     782  ///
     783  /// The basic way to write an LP problem is made by the next code:
     784  ///\code
     785  /// Lp lp;
     786  ///
     787  /// LemonWriter writer(filename_or_ostream);
     788  /// LpWriter lpwriter(writer, lp);
     789  ///
     790  /// writer.run();
     791  ///\endcode
     792  ///
     793  /// Of course instead of \c LemonWriter you can give a \c
     794  /// GraphWriter to the LpWriter constructor. Also useful that you
     795  /// can mix lp problems and graphs in the same file.
    452796  class LpWriter : public LemonWriter::SectionWriter {
    453797    typedef LemonWriter::SectionWriter Parent;
     
    458802    ///
    459803    /// Constructor for LpWriter. It creates the LpWriter and attach
    460     /// it into the given LemonWriter. The lp writer will add
    461     /// variables, constraints and objective function to the
    462     /// given lp solver.
    463     LpWriter(LemonWriter& _writer, LpSolverBase& _lp,
     804    /// it into the given LemonWriter.
     805    LpWriter(LemonWriter& _writer, const LpSolverBase& _lp,
    464806             const std::string& _name = std::string())
    465807      : Parent(_writer), lp(_lp), name(_name) {}
     
    468810    /// \brief Destructor.
    469811    ///
    470     /// Destructor for NodeSetWriter.
     812    /// Destructor for LpWriter.
    471813    virtual ~LpWriter() {}
    472814
     
    490832
    491833    void createCols() {
    492       int num = 1;
    493 
    494       std::map<std::string, LpSolverBase::Col> inverse;
     834      int num = 0;
    495835
    496836      for (LpSolverBase::ColIt it(lp); it != INVALID; ++it) {
    497837        std::string name = lp.colName(it);
    498         if (!name.empty() && inverse.find(name) == inverse.end()) {
    499           cols.insert(std::make_pair(it, name));
    500           inverse.insert(std::make_pair(name, it));
    501         } else {
     838        if (name.empty()) {
    502839          std::ostringstream ls;
    503           ls << "var" << num;
     840          ls << "x" << num;
    504841          ++num;
    505           cols.insert(std::make_pair(it, ls.str()));
    506           inverse.insert(std::make_pair(ls.str(), it));
     842          while (lp.colByName(ls.str()) != INVALID) {
     843            ls.str(std::string());
     844            ls << "x" << num;
     845            ++num;
     846          }
     847          const_cast<LpSolverBase&>(lp).colName(it, ls.str());
    507848        }
    508849      }
     
    527868        }
    528869        first = false;
    529         os << cols[jt->first] << " ";
     870        os << lp.colName(jt->first) << " ";
    530871      }
    531872      if (e.constComp() < 0.0) {
     
    590931          }
    591932         
    592           os << cols[it] << " ";
     933          os << lp.colName(it) << " ";
    593934         
    594935          if (upper != LpSolverBase::INF) {
     
    596937          }
    597938        } else {
    598           os << cols[it] << " == " << upper << " ";
     939          os << lp.colName(it) << " == " << upper << " ";
    599940        }
    600941        os << std::endl;
     
    615956  private:
    616957
    617     typedef std::map<LpSolverBase::Col, std::string> ColMap;
    618      
    619     LpSolverBase& lp;
     958    const LpSolverBase& lp;
    620959    std::string name;
    621     ColMap cols;
    622960  };
    623961
Note: See TracChangeset for help on using the changeset viewer.