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