lemon/dimacs.h
author Peter Kovacs <kpeter@inf.elte.hu>
Fri, 08 Sep 2017 17:02:03 +0200
changeset 1005 f37f0845cf32
parent 561 6e0525ec5355
child 1006 332627dd249e
permissions -rw-r--r--
Bug fix in DIMACS reader (#607)
     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-2009
     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 <limits>
    26 #include <lemon/maps.h>
    27 #include <lemon/error.h>
    28 /// \ingroup dimacs_group
    29 /// \file
    30 /// \brief DIMACS file format reader.
    31 
    32 namespace lemon {
    33 
    34   /// \addtogroup dimacs_group
    35   /// @{
    36 
    37   /// DIMACS file type descriptor.
    38   struct DimacsDescriptor
    39   {
    40     ///File type enum
    41     enum Type
    42       {
    43         NONE, MIN, MAX, SP, MAT
    44       };
    45     ///The file type
    46     Type type;
    47     ///The number of nodes in the graph
    48     int nodeNum;
    49     ///The number of edges in the graph
    50     int edgeNum;
    51     int lineShift;
    52     /// Constructor. Sets the type to NONE.
    53     DimacsDescriptor() : type(NONE) {}
    54   };
    55 
    56   ///Discover the type of a DIMACS file
    57 
    58   ///It starts seeking the beginning of the file for the problem type
    59   ///and size info. The found data is returned in a special struct
    60   ///that can be evaluated and passed to the appropriate reader
    61   ///function.
    62   DimacsDescriptor dimacsType(std::istream& is)
    63   {
    64     DimacsDescriptor r;
    65     std::string problem,str;
    66     char c;
    67     r.lineShift=0;
    68     while (is >> c)
    69       switch(c)
    70         {
    71         case 'p':
    72           if(is >> problem >> r.nodeNum >> r.edgeNum)
    73             {
    74               getline(is, str);
    75               r.lineShift++;
    76               if(problem=="min") r.type=DimacsDescriptor::MIN;
    77               else if(problem=="max") r.type=DimacsDescriptor::MAX;
    78               else if(problem=="sp") r.type=DimacsDescriptor::SP;
    79               else if(problem=="mat") r.type=DimacsDescriptor::MAT;
    80               else throw FormatError("Unknown problem type");
    81               return r;
    82             }
    83           else
    84             {
    85               throw FormatError("Missing or wrong problem type declaration.");
    86             }
    87           break;
    88         case 'c':
    89           getline(is, str);
    90           r.lineShift++;
    91           break;
    92         default:
    93           throw FormatError("Unknown DIMACS declaration.");
    94         }
    95     throw FormatError("Missing problem type declaration.");
    96   }
    97 
    98 
    99 
   100   /// DIMACS minimum cost flow reader function.
   101   ///
   102   /// This function reads a minimum cost flow instance from DIMACS format,
   103   /// i.e. from a DIMACS file having a line starting with
   104   /// \code
   105   ///   p min
   106   /// \endcode
   107   /// At the beginning, \c g is cleared by \c g.clear(). The supply
   108   /// amount of the nodes are written to the \c supply node map
   109   /// (they are signed values). The lower bounds, capacities and costs
   110   /// of the arcs are written to the \c lower, \c capacity and \c cost
   111   /// arc maps.
   112   ///
   113   /// If the capacity of an arc is less than the lower bound, it will
   114   /// be set to "infinite" instead. The actual value of "infinite" is
   115   /// contolled by the \c infty parameter. If it is 0 (the default value),
   116   /// \c std::numeric_limits<Capacity>::infinity() will be used if available,
   117   /// \c std::numeric_limits<Capacity>::max() otherwise. If \c infty is set to
   118   /// a non-zero value, that value will be used as "infinite".
   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                      typename CapacityMap::Value infty = 0,
   132                      DimacsDescriptor desc=DimacsDescriptor())
   133   {
   134     g.clear();
   135     std::vector<typename Digraph::Node> nodes;
   136     typename Digraph::Arc e;
   137     std::string problem, str;
   138     char c;
   139     int i, j;
   140     if(desc.type==DimacsDescriptor::NONE) desc=dimacsType(is);
   141     if(desc.type!=DimacsDescriptor::MIN)
   142       throw FormatError("Problem type mismatch");
   143 
   144     nodes.resize(desc.nodeNum + 1);
   145     for (int k = 1; k <= desc.nodeNum; ++k) {
   146       nodes[k] = g.addNode();
   147       supply.set(nodes[k], 0);
   148     }
   149 
   150     typename SupplyMap::Value sup;
   151     typename CapacityMap::Value low;
   152     typename CapacityMap::Value cap;
   153     typename CostMap::Value co;
   154     typedef typename CapacityMap::Value Capacity;
   155     if(infty==0)
   156       infty = std::numeric_limits<Capacity>::has_infinity ?
   157         std::numeric_limits<Capacity>::infinity() :
   158         std::numeric_limits<Capacity>::max();
   159 
   160     while (is >> c) {
   161       switch (c) {
   162       case 'c': // comment line
   163         getline(is, str);
   164         break;
   165       case 'n': // node definition line
   166         is >> i >> sup;
   167         getline(is, str);
   168         supply.set(nodes[i], sup);
   169         break;
   170       case 'a': // arc definition line
   171         is >> i >> j >> low >> cap >> co;
   172         getline(is, str);
   173         e = g.addArc(nodes[i], nodes[j]);
   174         lower.set(e, low);
   175         if (cap >= low)
   176           capacity.set(e, cap);
   177         else
   178           capacity.set(e, infty);
   179         cost.set(e, co);
   180         break;
   181       }
   182     }
   183   }
   184 
   185   template<typename Digraph, typename CapacityMap>
   186   void _readDimacs(std::istream& is,
   187                    Digraph &g,
   188                    CapacityMap& capacity,
   189                    typename Digraph::Node &s,
   190                    typename Digraph::Node &t,
   191                    typename CapacityMap::Value infty = 0,
   192                    DimacsDescriptor desc=DimacsDescriptor()) {
   193     g.clear();
   194     s=t=INVALID;
   195     std::vector<typename Digraph::Node> nodes;
   196     typename Digraph::Arc e;
   197     char c, d;
   198     int i, j;
   199     typename CapacityMap::Value _cap;
   200     std::string str;
   201     nodes.resize(desc.nodeNum + 1);
   202     for (int k = 1; k <= desc.nodeNum; ++k) {
   203       nodes[k] = g.addNode();
   204     }
   205     typedef typename CapacityMap::Value Capacity;
   206 
   207     if(infty==0)
   208       infty = std::numeric_limits<Capacity>::has_infinity ?
   209         std::numeric_limits<Capacity>::infinity() :
   210         std::numeric_limits<Capacity>::max();
   211  
   212     while (is >> c) {
   213       switch (c) {
   214       case 'c': // comment line
   215         getline(is, str);
   216         break;
   217       case 'n': // node definition line
   218         if (desc.type==DimacsDescriptor::SP) { // shortest path problem
   219           is >> i;
   220           getline(is, str);
   221           s = nodes[i];
   222         }
   223         if (desc.type==DimacsDescriptor::MAX) { // max flow problem
   224           is >> i >> d;
   225           getline(is, str);
   226           if (d == 's') s = nodes[i];
   227           if (d == 't') t = nodes[i];
   228         }
   229         break;
   230       case 'a': // arc definition line
   231         if (desc.type==DimacsDescriptor::SP) {
   232           is >> i >> j >> _cap;
   233           getline(is, str);
   234           e = g.addArc(nodes[i], nodes[j]);
   235           capacity.set(e, _cap);
   236         } 
   237         else if (desc.type==DimacsDescriptor::MAX) {
   238           is >> i >> j >> _cap;
   239           getline(is, str);
   240           e = g.addArc(nodes[i], nodes[j]);
   241           if (_cap >= 0)
   242             capacity.set(e, _cap);
   243           else
   244             capacity.set(e, infty);
   245         }
   246         else {
   247           is >> i >> j;
   248           getline(is, str);
   249           g.addArc(nodes[i], nodes[j]);
   250         }
   251         break;
   252       }
   253     }
   254   }
   255 
   256   /// DIMACS maximum flow reader function.
   257   ///
   258   /// This function reads a maximum flow instance from DIMACS format,
   259   /// i.e. from a DIMACS file having a line starting with
   260   /// \code
   261   ///   p max
   262   /// \endcode
   263   /// At the beginning, \c g is cleared by \c g.clear(). The arc
   264   /// capacities are written to the \c capacity arc map and \c s and
   265   /// \c t are set to the source and the target nodes.
   266   ///
   267   /// If the capacity of an arc is negative, it will
   268   /// be set to "infinite" instead. The actual value of "infinite" is
   269   /// contolled by the \c infty parameter. If it is 0 (the default value),
   270   /// \c std::numeric_limits<Capacity>::infinity() will be used if available,
   271   /// \c std::numeric_limits<Capacity>::max() otherwise. If \c infty is set to
   272   /// a non-zero value, that value will be used as "infinite".
   273   ///
   274   /// If the file type was previously evaluated by dimacsType(), then
   275   /// the descriptor struct should be given by the \c dest parameter.
   276   template<typename Digraph, typename CapacityMap>
   277   void readDimacsMax(std::istream& is,
   278                      Digraph &g,
   279                      CapacityMap& capacity,
   280                      typename Digraph::Node &s,
   281                      typename Digraph::Node &t,
   282                      typename CapacityMap::Value infty = 0,
   283                      DimacsDescriptor desc=DimacsDescriptor()) {
   284     if(desc.type==DimacsDescriptor::NONE) desc=dimacsType(is);
   285     if(desc.type!=DimacsDescriptor::MAX)
   286       throw FormatError("Problem type mismatch");
   287     _readDimacs(is,g,capacity,s,t,infty,desc);
   288   }
   289 
   290   /// DIMACS shortest path reader function.
   291   ///
   292   /// This function reads a shortest path instance from DIMACS format,
   293   /// i.e. from a DIMACS file having a line starting with
   294   /// \code
   295   ///   p sp
   296   /// \endcode
   297   /// At the beginning, \c g is cleared by \c g.clear(). The arc
   298   /// lengths are written to the \c length arc map and \c s is set to the
   299   /// source node.
   300   ///
   301   /// If the file type was previously evaluated by dimacsType(), then
   302   /// the descriptor struct should be given by the \c dest parameter.
   303   template<typename Digraph, typename LengthMap>
   304   void readDimacsSp(std::istream& is,
   305                     Digraph &g,
   306                     LengthMap& length,
   307                     typename Digraph::Node &s,
   308                     DimacsDescriptor desc=DimacsDescriptor()) {
   309     typename Digraph::Node t;
   310     if(desc.type==DimacsDescriptor::NONE) desc=dimacsType(is);
   311     if(desc.type!=DimacsDescriptor::SP)
   312       throw FormatError("Problem type mismatch");
   313     _readDimacs(is, g, length, s, t, 0, desc);
   314   }
   315 
   316   /// DIMACS capacitated digraph reader function.
   317   ///
   318   /// This function reads an arc capacitated digraph instance from
   319   /// DIMACS 'max' or 'sp' format.
   320   /// At the beginning, \c g is cleared by \c g.clear()
   321   /// and the arc capacities/lengths are written to the \c capacity
   322   /// arc map.
   323   ///
   324   /// In case of the 'max' format, if the capacity of an arc is negative,
   325   /// it will
   326   /// be set to "infinite" instead. The actual value of "infinite" is
   327   /// contolled by the \c infty parameter. If it is 0 (the default value),
   328   /// \c std::numeric_limits<Capacity>::infinity() will be used if available,
   329   /// \c std::numeric_limits<Capacity>::max() otherwise. If \c infty is set to
   330   /// a non-zero value, that value will be used as "infinite".
   331   ///
   332   /// If the file type was previously evaluated by dimacsType(), then
   333   /// the descriptor struct should be given by the \c dest parameter.
   334   template<typename Digraph, typename CapacityMap>
   335   void readDimacsCap(std::istream& is,
   336                      Digraph &g,
   337                      CapacityMap& capacity,
   338                      typename CapacityMap::Value infty = 0,
   339                      DimacsDescriptor desc=DimacsDescriptor()) {
   340     typename Digraph::Node u,v;
   341     if(desc.type==DimacsDescriptor::NONE) desc=dimacsType(is);
   342     if(desc.type!=DimacsDescriptor::MAX && desc.type!=DimacsDescriptor::SP)
   343       throw FormatError("Problem type mismatch");
   344     _readDimacs(is, g, capacity, u, v, infty, desc);
   345   }
   346 
   347   template<typename Graph>
   348   typename enable_if<lemon::UndirectedTagIndicator<Graph>,void>::type
   349   _addArcEdge(Graph &g, typename Graph::Node s, typename Graph::Node t,
   350               dummy<0> = 0)
   351   {
   352     g.addEdge(s,t);
   353   }
   354   template<typename Graph>
   355   typename disable_if<lemon::UndirectedTagIndicator<Graph>,void>::type
   356   _addArcEdge(Graph &g, typename Graph::Node s, typename Graph::Node t,
   357               dummy<1> = 1)
   358   {
   359     g.addArc(s,t);
   360   }
   361   
   362   /// DIMACS plain (di)graph reader function.
   363   ///
   364   /// This function reads a (di)graph without any designated nodes and
   365   /// maps from DIMACS format, i.e. from DIMACS files having a line
   366   /// starting with
   367   /// \code
   368   ///   p mat
   369   /// \endcode
   370   /// At the beginning, \c g is cleared by \c g.clear().
   371   ///
   372   /// If the file type was previously evaluated by dimacsType(), then
   373   /// the descriptor struct should be given by the \c dest parameter.
   374   template<typename Graph>
   375   void readDimacsMat(std::istream& is, Graph &g,
   376                      DimacsDescriptor desc=DimacsDescriptor())
   377   {
   378     if(desc.type==DimacsDescriptor::NONE) desc=dimacsType(is);
   379     if(desc.type!=DimacsDescriptor::MAT)
   380       throw FormatError("Problem type mismatch");
   381 
   382     g.clear();
   383     std::vector<typename Graph::Node> nodes;
   384     char c;
   385     int i, j;
   386     std::string str;
   387     nodes.resize(desc.nodeNum + 1);
   388     for (int k = 1; k <= desc.nodeNum; ++k) {
   389       nodes[k] = g.addNode();
   390     }
   391     
   392     while (is >> c) {
   393       switch (c) {
   394       case 'c': // comment line
   395         getline(is, str);
   396         break;
   397       case 'n': // node definition line
   398         break;
   399       case 'a': // arc definition line
   400         is >> i >> j;
   401         getline(is, str);
   402         _addArcEdge(g,nodes[i], nodes[j]);
   403         break;
   404       }
   405     }
   406   }
   407 
   408   /// DIMACS plain digraph writer function.
   409   ///
   410   /// This function writes a digraph without any designated nodes and
   411   /// maps into DIMACS format, i.e. into DIMACS file having a line
   412   /// starting with
   413   /// \code
   414   ///   p mat
   415   /// \endcode
   416   /// If \c comment is not empty, then it will be printed in the first line
   417   /// prefixed by 'c'.
   418   template<typename Digraph>
   419   void writeDimacsMat(std::ostream& os, const Digraph &g,
   420                       std::string comment="") {
   421     typedef typename Digraph::NodeIt NodeIt;
   422     typedef typename Digraph::ArcIt ArcIt;
   423 
   424     if(!comment.empty())
   425       os << "c " << comment << std::endl;
   426     os << "p mat " << g.nodeNum() << " " << g.arcNum() << std::endl;
   427 
   428     typename Digraph::template NodeMap<int> nodes(g);
   429     int i = 1;
   430     for(NodeIt v(g); v != INVALID; ++v) {
   431       nodes.set(v, i);
   432       ++i;
   433     }
   434     for(ArcIt e(g); e != INVALID; ++e) {
   435       os << "a " << nodes[g.source(e)] << " " << nodes[g.target(e)]
   436          << std::endl;
   437     }
   438   }
   439 
   440   /// @}
   441 
   442 } //namespace lemon
   443 
   444 #endif //LEMON_DIMACS_H