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