COIN-OR::LEMON - Graph Library

About

Downloads

Documentation

Development

Issue Tracker

Browse Tickets

Custom Query

Roadmap

Browse Source

Local Info

Mailing Lists

Search

Changeset 387:24a2c6ee6cb0 in lemon-main


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

Refactoring of DIMACS tools

Files:
2 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

  • tools/dimacs-to-lgf.cc

    r386 r387  
    4040
    4141#include <lemon/arg_parser.h>
     42#include <lemon/error.h>
    4243
    4344using namespace std;
    … …  
    5758  std::string inputName;
    5859  std::string outputName;
    59   std::string typeName;
    60 
    61   bool mincostflow;
    62   bool maxflow;
    63   bool shortestpath;
    64   bool capacitated;
    65   bool plain;
    66 
    67   bool version;
    6860
    6961  ArgParser ap(argc, argv);
    70   ap.refOption("-input",
    71                "use FILE as input instead of standard input",
    72                inputName).synonym("i", "-input")
    73     .refOption("-output",
    74                "use FILE as output instead of standard output",
    75                outputName).synonym("o", "-output")
    76     .refOption("-mincostflow",
    77                "set the type of the digraph to \"mincostflow\" digraph",
    78                mincostflow)
    79     .optionGroup("type", "-mincostflow").synonym("mcf", "-mincostflow")
    80     .refOption("-maxflow",
    81                "set the type of the digraph to \"maxflow\" digraph",
    82                maxflow)
    83     .optionGroup("type", "-maxflow").synonym("mf", "-maxflow")
    84     .refOption("-shortestpath",
    85                "set the type of the digraph to \"shortestpath\" digraph",
    86                shortestpath)
    87     .optionGroup("type", "-shortestpath").synonym("sp", "-shortestpath")
    88     .refOption("-capacitated",
    89                "set the type of the digraph to \"capacitated\" digraph",
    90                capacitated)
    91     .optionGroup("type", "-capacitated").synonym("cap", "-capacitated")
    92     .refOption("-plain",
    93                "set the type of the digraph to \"plain\" digraph",
    94                plain)
    95     .optionGroup("type", "-plain").synonym("pl", "-plain")
    96     .onlyOneGroup("type")
    97     .mandatoryGroup("type")
    98     .refOption("-version", "show version information", version)
    99     .synonym("v", "-version")
     62  ap.other("[INFILE [OUTFILE]]",
     63           "If either the INFILE or OUTFILE file is missing the standard\n"
     64           "     input/output will be used instead.")
    10065    .run();
    10166
    10267  ifstream input;
    103   if (!inputName.empty()) {
    104     input.open(inputName.c_str());
    105     if (!input) {
    106       cerr << "File open error" << endl;
    107       return -1;
     68  ofstream output;
     69
     70  switch(ap.files().size())
     71    {
     72    case 2:
     73      output.open(ap.files()[1].c_str());
     74      if (!output) {
     75        throw IoError("Cannot open the file for writing", ap.files()[1]);
     76      }
     77    case 1:
     78      input.open(ap.files()[0].c_str());
     79      if (!input) {
     80        throw IoError("File cannot be found", ap.files()[0]);
     81      }
     82    case 0:
     83      break;
     84    default:
     85      cerr << ap.commandName() << ": too many arguments\n";
     86      return 1;
     87  }
     88  istream& is = (ap.files().size()<1 ? cin : input);
     89  ostream& os = (ap.files().size()<2 ? cout : output);
     90
     91  DimacsDescriptor desc = dimacsType(is);
     92  switch(desc.type)
     93    {
     94    case DimacsDescriptor::MIN:
     95      {
     96        Digraph digraph;
     97        DoubleArcMap lower(digraph), capacity(digraph), cost(digraph);
     98        DoubleNodeMap supply(digraph);
     99        readDimacsMin(is, digraph, lower, capacity, cost, supply, desc);
     100        DigraphWriter<Digraph>(digraph, os).
     101          nodeMap("supply", supply).
     102          arcMap("lower", lower).
     103          arcMap("capacity", capacity).
     104          arcMap("cost", cost).
     105          attribute("problem","min").
     106          run();
     107      }
     108      break;
     109    case DimacsDescriptor::MAX:
     110      {
     111        Digraph digraph;
     112        Node s, t;
     113        DoubleArcMap capacity(digraph);
     114        readDimacsMax(is, digraph, capacity, s, t, desc);
     115        DigraphWriter<Digraph>(digraph, os).
     116          arcMap("capacity", capacity).
     117          node("source", s).
     118          node("target", t).
     119          attribute("problem","max").
     120          run();
     121      }
     122      break;
     123    case DimacsDescriptor::SP:
     124      {
     125        Digraph digraph;
     126        Node s;
     127        DoubleArcMap capacity(digraph);
     128        readDimacsSp(is, digraph, capacity, s, desc);
     129        DigraphWriter<Digraph>(digraph, os).
     130          arcMap("capacity", capacity).
     131          node("source", s).
     132          attribute("problem","sp").
     133          run();
     134      }
     135      break;
     136    case DimacsDescriptor::MAT:
     137      {
     138        Digraph digraph;
     139        readDimacsMat(is, digraph,desc);
     140        DigraphWriter<Digraph>(digraph, os).
     141          attribute("problem","mat").
     142          run();
     143      }
     144      break;
     145    default:
     146      break;
    108147    }
    109   }
    110   istream& is = (inputName.empty() ? cin : input);
    111 
    112   ofstream output;
    113   if (!outputName.empty()) {
    114     output.open(outputName.c_str());
    115     if (!output) {
    116       cerr << "File open error" << endl;
    117       return -1;
    118     }
    119   }
    120   ostream& os = (outputName.empty() ? cout : output);
    121 
    122   if (mincostflow) {
    123     Digraph digraph;
    124     DoubleArcMap lower(digraph), capacity(digraph), cost(digraph);
    125     DoubleNodeMap supply(digraph);
    126     readDimacsMin(is, digraph, lower, capacity, cost, supply);
    127     DigraphWriter<Digraph>(digraph, os).
    128       nodeMap("supply", supply).
    129       arcMap("lower", lower).
    130       arcMap("capacity", capacity).
    131       arcMap("cost", cost).
    132       run();
    133   } else if (maxflow) {
    134     Digraph digraph;
    135     Node s, t;
    136     DoubleArcMap capacity(digraph);
    137     readDimacsMax(is, digraph, capacity, s, t);
    138     DigraphWriter<Digraph>(digraph, os).
    139       arcMap("capacity", capacity).
    140       node("source", s).
    141       node("target", t).
    142       run();
    143   } else if (shortestpath) {
    144     Digraph digraph;
    145     Node s;
    146     DoubleArcMap capacity(digraph);
    147     readDimacsSp(is, digraph, capacity, s);
    148     DigraphWriter<Digraph>(digraph, os).
    149       arcMap("capacity", capacity).
    150       node("source", s).
    151       run();
    152   } else if (capacitated) {
    153     Digraph digraph;
    154     DoubleArcMap capacity(digraph);
    155     readDimacsMax(is, digraph, capacity);
    156     DigraphWriter<Digraph>(digraph, os).
    157       arcMap("capacity", capacity).
    158       run();
    159   } else if (plain) {
    160     Digraph digraph;
    161     readDimacsMat(is, digraph);
    162     DigraphWriter<Digraph>(digraph, os).run();
    163   } else {
    164     cerr << "Invalid type error" << endl;
    165     return -1;
    166   }
    167148  return 0;
    168149}
Note: See TracChangeset for help on using the changeset viewer.