lemon/dimacs.h
author Alpar Juttner <alpar@cs.elte.hu>
Fri, 28 Nov 2008 06:38:20 +0000
changeset 402 24a2c6ee6cb0
parent 401 9d1faab5e0f1
child 403 0a3ec097a76c
permissions -rw-r--r--
Refactoring of DIMACS tools
     1 /* -*- mode: C++; indent-tabs-mode: nil; -*-
     2  *
     3  * This file is a part of LEMON, a generic C++ optimization library.
     4  *
     5  * Copyright (C) 2003-2008
     6  * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
     7  * (Egervary Research Group on Combinatorial Optimization, EGRES).
     8  *
     9  * Permission to use, modify and distribute this software is granted
    10  * provided that this copyright notice appears in all copies. For
    11  * precise terms see the accompanying LICENSE file.
    12  *
    13  * This software is provided "AS IS" with no warranty of any kind,
    14  * express or implied, and with no claim as to its suitability for any
    15  * purpose.
    16  *
    17  */
    18 
    19 #ifndef LEMON_DIMACS_H
    20 #define LEMON_DIMACS_H
    21 
    22 #include <iostream>
    23 #include <string>
    24 #include <vector>
    25 #include <lemon/maps.h>
    26 #include <lemon/error.h>
    27 
    28 /// \ingroup dimacs_group
    29 /// \file
    30 /// \brief DIMACS file format reader.
    31 
    32 namespace lemon {
    33 
    34   ///@defgroup dimacs_group DIMACS format
    35   ///\brief Read and write files in DIMACS format
    36   ///
    37   ///Tools to read a digraph from or write it to a file in DIMACS format
    38   ///data
    39   ///\ingroup io_group
    40 
    41   /// \addtogroup dimacs_group
    42   /// @{
    43 
    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 
   108   /// DIMACS min cost flow reader function.
   109   ///
   110   /// This function reads a min cost flow instance from DIMACS format,
   111   /// i.e. from DIMACS files having a line starting with
   112   /// \code
   113   ///   p min
   114   /// \endcode
   115   /// At the beginning, \c g is cleared by \c g.clear(). The supply
   116   /// amount of the nodes are written to \c supply (signed). The
   117   /// lower bounds, capacities and costs of the arcs are written to
   118   /// \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.
   122   template <typename Digraph, typename LowerMap,
   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())
   132   {
   133     g.clear();
   134     std::vector<typename Digraph::Node> nodes;
   135     typename Digraph::Arc e;
   136     std::string problem, str;
   137     char c;
   138     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 
   149     typename SupplyMap::Value sup;
   150     typename CapacityMap::Value low;
   151     typename CapacityMap::Value cap;
   152     typename CostMap::Value co;
   153     while (is >> c) {
   154       switch (c) {
   155       case 'c': // comment line
   156         getline(is, str);
   157         break;
   158       case 'n': // node definition line
   159         is >> i >> sup;
   160         getline(is, str);
   161         supply.set(nodes[i], sup);
   162         break;
   163       case 'a': // arc (arc) definition line
   164         is >> i >> j >> low >> cap >> co;
   165         getline(is, str);
   166         e = g.addArc(nodes[i], nodes[j]);
   167         lower.set(e, low);
   168         if (cap >= 0)
   169           capacity.set(e, cap);
   170         else
   171           capacity.set(e, -1);
   172         cost.set(e, co);
   173         break;
   174       }
   175     }
   176   }
   177 
   178   template<typename Digraph, typename CapacityMap>
   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()) {
   185     g.clear();
   186     s=t=INVALID;
   187     std::vector<typename Digraph::Node> nodes;
   188     typename Digraph::Arc e;
   189     char c, d;
   190     int i, j;
   191     typename CapacityMap::Value _cap;
   192     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 
   198     while (is >> c) {
   199       switch (c) {
   200       case 'c': // comment line
   201         getline(is, str);
   202         break;
   203       case 'n': // node definition line
   204         if (desc.type==DimacsDescriptor::SP) { // shortest path problem
   205           is >> i;
   206           getline(is, str);
   207           s = nodes[i];
   208         }
   209         if (desc.type==DimacsDescriptor::MAX) { // max flow problem
   210           is >> i >> d;
   211           getline(is, str);
   212           if (d == 's') s = nodes[i];
   213           if (d == 't') t = nodes[i];
   214         }
   215         break;
   216       case 'a': // arc (arc) definition line
   217         if (desc.type==DimacsDescriptor::SP ||
   218             desc.type==DimacsDescriptor::MAX) {
   219           is >> i >> j >> _cap;
   220           getline(is, str);
   221           e = g.addArc(nodes[i], nodes[j]);
   222           capacity.set(e, _cap);
   223         } else {
   224           is >> i >> j;
   225           getline(is, str);
   226           g.addArc(nodes[i], nodes[j]);
   227         }
   228         break;
   229       }
   230     }
   231   }
   232 
   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 
   259   /// DIMACS shortest path reader function.
   260   ///
   261   /// This function reads a shortest path instance from DIMACS format,
   262   /// i.e. from DIMACS files having a line starting with
   263   /// \code
   264   ///   p sp
   265   /// \endcode
   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
   268   /// 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.
   294   template<typename Digraph, typename CapacityMap>
   295   void readDimacsCap(std::istream& is,
   296                      Digraph &g,
   297                      CapacityMap& capacity,
   298                      DimacsDescriptor desc=DimacsDescriptor()) {
   299     typename Digraph::Node 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);
   304   }
   305 
   306   /// DIMACS plain digraph reader function.
   307   ///
   308   /// This function reads a digraph without any designated nodes and
   309   /// maps from DIMACS format, i.e. from DIMACS files having a line
   310   /// starting with
   311   /// \code
   312   ///   p mat
   313   /// \endcode
   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.
   318   template<typename Digraph>
   319   void readDimacsMat(std::istream& is, Digraph &g,
   320                      DimacsDescriptor desc=DimacsDescriptor()) {
   321     typename Digraph::Node u,v;
   322     NullMap<typename Digraph::Arc, int> n;
   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);
   327   }
   328 
   329   /// DIMACS plain digraph writer function.
   330   ///
   331   /// This function writes a digraph without any designated nodes and
   332   /// maps into DIMACS format, i.e. into DIMACS file having a line
   333   /// starting with
   334   /// \code
   335   ///   p mat
   336   /// \endcode
   337   /// If \c comment is not empty, then it will be printed in the first line
   338   /// prefixed by 'c'.
   339   template<typename Digraph>
   340   void writeDimacsMat(std::ostream& os, const Digraph &g,
   341                       std::string comment="") {
   342     typedef typename Digraph::NodeIt NodeIt;
   343     typedef typename Digraph::ArcIt ArcIt;
   344 
   345     if(!comment.empty()) 
   346       os << "c " << comment << std::endl;
   347     os << "p mat " << g.nodeNum() << " " << g.arcNum() << std::endl;
   348 
   349     typename Digraph::template NodeMap<int> nodes(g);
   350     int i = 1;
   351     for(NodeIt v(g); v != INVALID; ++v) {
   352       nodes.set(v, i);
   353       ++i;
   354     }
   355     for(ArcIt e(g); e != INVALID; ++e) {
   356       os << "a " << nodes[g.source(e)] << " " << nodes[g.target(e)]
   357          << std::endl;
   358     }
   359   }
   360 
   361   /// @}
   362 
   363 } //namespace lemon
   364 
   365 #endif //LEMON_DIMACS_H