COIN-OR::LEMON - Graph Library

Changeset 2368:6b2e8b734ae7 in lemon-0.x


Ignore:
Timestamp:
02/19/07 13:11:41 (11 years ago)
Author:
deba
Branch:
default
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.