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