COIN-OR::LEMON - Graph Library

Changeset 387:24a2c6ee6cb0 in lemon-1.2 for lemon


Ignore:
Timestamp:
11/28/08 07:38:20 (11 years ago)
Author:
Alpar Juttner <alpar@…>
Branch:
default
Phase:
public
Message:

Refactoring of DIMACS tools

File:
1 edited

Legend:

Unmodified
Added
Removed
  • lemon/dimacs.h

    r386 r387  
    2424#include <vector>
    2525#include <lemon/maps.h>
     26#include <lemon/error.h>
    2627
    2728/// \ingroup dimacs_group
     
    4142  /// @{
    4243
     44
     45  /// DIMACS file type descriptor.
     46  struct DimacsDescriptor
     47  {
     48    ///File type enum
     49    enum Type
     50      {
     51        NONE, MIN, MAX, SP, MAT
     52      };
     53    ///The file type
     54    Type type;
     55    ///The number of nodes on the graph
     56    int nodeNum;
     57    ///The number of edges on the graph
     58    int edgeNum;
     59    int lineShift;
     60    /// Constructor. Sets the type to NONE.
     61    DimacsDescriptor() : type(NONE) {}
     62  };
     63
     64  ///Discover the type of a DIMACS file
     65
     66  ///It starts seeking the begining of the file for the problem type
     67  ///and size info. The found date is returned in a special struct
     68  ///that can be evaluated and passed to the appropriate reader
     69  ///function.
     70  DimacsDescriptor dimacsType(std::istream& is)
     71  {
     72    DimacsDescriptor r;
     73    std::string problem,str;
     74    char c;
     75    r.lineShift=0;
     76    while (is >> c)
     77      switch(c)
     78        {
     79        case 'p':
     80          if(is >> problem >> r.nodeNum >> r.edgeNum)
     81            {
     82              getline(is, str);
     83              r.lineShift++;
     84              if(problem=="min") r.type=DimacsDescriptor::MIN;
     85              else if(problem=="max") r.type=DimacsDescriptor::MAX;
     86              else if(problem=="sp") r.type=DimacsDescriptor::SP;
     87              else if(problem=="mat") r.type=DimacsDescriptor::MAT;
     88              else throw FormatError("Unknown problem type");
     89              return r;
     90            }
     91          else
     92            {
     93              throw FormatError("Missing or wrong problem type declaration.");
     94            }
     95          break;
     96        case 'c':
     97          getline(is, str);
     98          r.lineShift++;
     99          break;
     100        default:
     101          throw FormatError("Unknown DIMACS declaration.");
     102        }
     103    throw FormatError("Missing problem type declaration.");
     104  }
     105
     106
     107
    43108  /// DIMACS min cost flow reader function.
    44109  ///
     
    48113  ///   p min
    49114  /// \endcode
    50   /// At the beginning \c g is cleared by \c g.clear(). The supply
     115  /// At the beginning, \c g is cleared by \c g.clear(). The supply
    51116  /// amount of the nodes are written to \c supply (signed). The
    52117  /// lower bounds, capacities and costs of the arcs are written to
    53118  /// \c lower, \c capacity and \c cost.
     119  ///
     120  /// If the file type was previously evaluated by dimacsType(), then
     121  /// the descriptor struct should be given by the \c dest parameter.
    54122  template <typename Digraph, typename LowerMap,
    55     typename CapacityMap, typename CostMap,
    56     typename SupplyMap>
    57   void readDimacsMin( std::istream& is,
    58                    Digraph &g,
    59                    LowerMap& lower,
    60                    CapacityMap& capacity,
    61                    CostMap& cost,
    62                    SupplyMap& supply )
     123            typename CapacityMap, typename CostMap,
     124            typename SupplyMap>
     125  void readDimacsMin(std::istream& is,
     126                     Digraph &g,
     127                     LowerMap& lower,
     128                     CapacityMap& capacity,
     129                     CostMap& cost,
     130                     SupplyMap& supply,
     131                     DimacsDescriptor desc=DimacsDescriptor())
    63132  {
    64133    g.clear();
     
    67136    std::string problem, str;
    68137    char c;
    69     int n, m;
    70138    int i, j;
     139    if(desc.type==DimacsDescriptor::NONE) desc=dimacsType(is);
     140    if(desc.type!=DimacsDescriptor::MIN)
     141      throw FormatError("Problem type mismatch");
     142
     143    nodes.resize(desc.nodeNum + 1);
     144    for (int k = 1; k <= desc.nodeNum; ++k) {
     145      nodes[k] = g.addNode();
     146      supply.set(nodes[k], 0);
     147    }
     148
    71149    typename SupplyMap::Value sup;
    72150    typename CapacityMap::Value low;
     
    77155      case 'c': // comment line
    78156        getline(is, str);
    79         break;
    80       case 'p': // problem definition line
    81         is >> problem >> n >> m;
    82         getline(is, str);
    83         if (problem != "min") return;
    84         nodes.resize(n + 1);
    85         for (int k = 1; k <= n; ++k) {
    86           nodes[k] = g.addNode();
    87           supply.set(nodes[k], 0);
    88         }
    89157        break;
    90158      case 'n': // node definition line
     
    108176  }
    109177
    110   /// DIMACS max flow reader function.
    111   ///
    112   /// This function reads a max flow instance from DIMACS format,
    113   /// i.e. from DIMACS files having a line starting with
    114   /// \code
    115   ///   p max
    116   /// \endcode
    117   /// At the beginning \c g is cleared by \c g.clear(). The arc
    118   /// capacities are written to \c capacity and \c s and \c t are
    119   /// set to the source and the target nodes.
    120178  template<typename Digraph, typename CapacityMap>
    121   void readDimacsMax(std::istream& is, Digraph &g, CapacityMap& capacity,
    122                   typename Digraph::Node &s, typename Digraph::Node &t) {
     179  void _readDimacs(std::istream& is,
     180                   Digraph &g,
     181                   CapacityMap& capacity,
     182                   typename Digraph::Node &s,
     183                   typename Digraph::Node &t,
     184                   DimacsDescriptor desc=DimacsDescriptor()) {
    123185    g.clear();
     186    s=t=INVALID;
    124187    std::vector<typename Digraph::Node> nodes;
    125188    typename Digraph::Arc e;
    126     std::string problem;
    127189    char c, d;
    128     int n, m;
    129190    int i, j;
    130191    typename CapacityMap::Value _cap;
    131192    std::string str;
     193    nodes.resize(desc.nodeNum + 1);
     194    for (int k = 1; k <= desc.nodeNum; ++k) {
     195      nodes[k] = g.addNode();
     196    }
     197
    132198    while (is >> c) {
    133199      switch (c) {
     
    135201        getline(is, str);
    136202        break;
    137       case 'p': // problem definition line
    138         is >> problem >> n >> m;
    139         getline(is, str);
    140         nodes.resize(n + 1);
    141         for (int k = 1; k <= n; ++k)
    142           nodes[k] = g.addNode();
    143         break;
    144203      case 'n': // node definition line
    145         if (problem == "sp") { // shortest path problem
     204        if (desc.type==DimacsDescriptor::SP) { // shortest path problem
    146205          is >> i;
    147206          getline(is, str);
    148207          s = nodes[i];
    149208        }
    150         if (problem == "max") { // max flow problem
     209        if (desc.type==DimacsDescriptor::MAX) { // max flow problem
    151210          is >> i >> d;
    152211          getline(is, str);
     
    156215        break;
    157216      case 'a': // arc (arc) definition line
    158         if (problem == "max" || problem == "sp") {
     217        if (desc.type==DimacsDescriptor::SP ||
     218            desc.type==DimacsDescriptor::MAX) {
    159219          is >> i >> j >> _cap;
    160220          getline(is, str);
     
    171231  }
    172232
     233  /// DIMACS max flow reader function.
     234  ///
     235  /// This function reads a max flow instance from DIMACS format,
     236  /// i.e. from DIMACS files having a line starting with
     237  /// \code
     238  ///   p max
     239  /// \endcode
     240  /// At the beginning, \c g is cleared by \c g.clear(). The arc
     241  /// capacities are written to \c capacity and \c s and \c t are
     242  /// set to the source and the target nodes.
     243  ///
     244  /// If the file type was previously evaluated by dimacsType(), then
     245  /// the descriptor struct should be given by the \c dest parameter.
     246  template<typename Digraph, typename CapacityMap>
     247  void readDimacsMax(std::istream& is,
     248                     Digraph &g,
     249                     CapacityMap& capacity,
     250                     typename Digraph::Node &s,
     251                     typename Digraph::Node &t,
     252                     DimacsDescriptor desc=DimacsDescriptor()) {
     253    if(desc.type==DimacsDescriptor::NONE) desc=dimacsType(is);
     254    if(desc.type!=DimacsDescriptor::MAX)
     255      throw FormatError("Problem type mismatch");
     256    _readDimacs(is,g,capacity,s,t,desc);
     257  }
     258
    173259  /// DIMACS shortest path reader function.
    174260  ///
     
    178264  ///   p sp
    179265  /// \endcode
    180   /// At the beginning \c g is cleared by \c g.clear(). The arc
    181   /// capacities are written to \c capacity and \c s is set to the
     266  /// At the beginning, \c g is cleared by \c g.clear(). The arc
     267  /// lengths are written to \c lenght and \c s is set to the
    182268  /// source node.
     269  ///
     270  /// If the file type was previously evaluated by dimacsType(), then
     271  /// the descriptor struct should be given by the \c dest parameter.
     272  template<typename Digraph, typename LengthMap>
     273  void readDimacsSp(std::istream& is,
     274                    Digraph &g,
     275                    LengthMap& length,
     276                    typename Digraph::Node &s,
     277                    DimacsDescriptor desc=DimacsDescriptor()) {
     278    typename Digraph::Node t;
     279    if(desc.type==DimacsDescriptor::NONE) desc=dimacsType(is);
     280    if(desc.type!=DimacsDescriptor::SP)
     281      throw FormatError("Problem type mismatch");
     282    _readDimacs(is, g, length, s, t,desc);
     283  }
     284
     285  /// DIMACS capacitated digraph reader function.
     286  ///
     287  /// This function reads an arc capacitated digraph instance from
     288  /// DIMACS 'mat' or 'sp' format.
     289  /// At the beginning, \c g is cleared by \c g.clear()
     290  /// and the arc capacities/lengths are written to \c capacity.
     291  ///
     292  /// If the file type was previously evaluated by dimacsType(), then
     293  /// the descriptor struct should be given by the \c dest parameter.
    183294  template<typename Digraph, typename CapacityMap>
    184   void readDimacsSp(std::istream& is, Digraph &g, CapacityMap& capacity,
    185                   typename Digraph::Node &s) {
    186     typename Digraph::Node t;
    187     readDimacsMax(is, g, capacity, s, t);
    188   }
    189 
    190   /// DIMACS capacitated digraph reader function.
    191   ///
    192   /// This function reads an arc capacitated digraph instance from
    193   /// DIMACS format. At the beginning \c g is cleared by \c g.clear()
    194   /// and the arc capacities are written to \c capacity.
    195   template<typename Digraph, typename CapacityMap>
    196   void readDimacsMax(std::istream& is, Digraph &g, CapacityMap& capacity) {
     295  void readDimacsCap(std::istream& is,
     296                     Digraph &g,
     297                     CapacityMap& capacity,
     298                     DimacsDescriptor desc=DimacsDescriptor()) {
    197299    typename Digraph::Node u,v;
    198     readDimacsMax(is, g, capacity, u, v);
     300    if(desc.type==DimacsDescriptor::NONE) desc=dimacsType(is);
     301    if(desc.type!=DimacsDescriptor::MAX || desc.type!=DimacsDescriptor::SP)
     302      throw FormatError("Problem type mismatch");
     303    _readDimacs(is, g, capacity, u, v, desc);
    199304  }
    200305
     
    207312  ///   p mat
    208313  /// \endcode
    209   /// At the beginning \c g is cleared by \c g.clear().
     314  /// At the beginning, \c g is cleared by \c g.clear().
     315  ///
     316  /// If the file type was previously evaluated by dimacsType(), then
     317  /// the descriptor struct should be given by the \c dest parameter.
    210318  template<typename Digraph>
    211   void readDimacsMat(std::istream& is, Digraph &g) {
     319  void readDimacsMat(std::istream& is, Digraph &g,
     320                     DimacsDescriptor desc=DimacsDescriptor()) {
    212321    typename Digraph::Node u,v;
    213322    NullMap<typename Digraph::Arc, int> n;
    214     readDimacsMax(is, g, n, u, v);
     323    if(desc.type==DimacsDescriptor::NONE) desc=dimacsType(is);
     324    if(desc.type!=DimacsDescriptor::MAT)
     325      throw FormatError("Problem type mismatch");
     326    _readDimacs(is, g, n, u, v, desc);
    215327  }
    216328
     
    223335  ///   p mat
    224336  /// \endcode
     337  /// If \c comment is not empty, then it will be printed in the first line
     338  /// prefixed by 'c'.
    225339  template<typename Digraph>
    226   void writeDimacsMat(std::ostream& os, const Digraph &g) {
     340  void writeDimacsMat(std::ostream& os, const Digraph &g,
     341                      std::string comment="") {
    227342    typedef typename Digraph::NodeIt NodeIt;
    228343    typedef typename Digraph::ArcIt ArcIt;
    229344
    230     os << "c matching problem" << std::endl;
     345    if(!comment.empty())
     346      os << "c " << comment << std::endl;
    231347    os << "p mat " << g.nodeNum() << " " << g.arcNum() << std::endl;
    232348
Note: See TracChangeset for help on using the changeset viewer.