lemon/dimacs.h
author Peter Kovacs <kpeter@inf.elte.hu>
Fri, 03 Apr 2009 13:46:16 +0200
changeset 607 9ad8d2122b50
parent 440 88ed40ad0d4f
child 561 6e0525ec5355
permissions -rw-r--r--
Separate types for flow and cost values in NetworkSimplex (#234)
     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 <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   /// \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 begining 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 \c supply (signed). The
   109   /// lower bounds, capacities and costs of the arcs are written to
   110   /// \c lower, \c capacity and \c cost.
   111   ///
   112   /// If the file type was previously evaluated by dimacsType(), then
   113   /// the descriptor struct should be given by the \c dest parameter.
   114   template <typename Digraph, typename LowerMap,
   115             typename CapacityMap, typename CostMap,
   116             typename SupplyMap>
   117   void readDimacsMin(std::istream& is,
   118                      Digraph &g,
   119                      LowerMap& lower,
   120                      CapacityMap& capacity,
   121                      CostMap& cost,
   122                      SupplyMap& supply,
   123                      DimacsDescriptor desc=DimacsDescriptor())
   124   {
   125     g.clear();
   126     std::vector<typename Digraph::Node> nodes;
   127     typename Digraph::Arc e;
   128     std::string problem, str;
   129     char c;
   130     int i, j;
   131     if(desc.type==DimacsDescriptor::NONE) desc=dimacsType(is);
   132     if(desc.type!=DimacsDescriptor::MIN)
   133       throw FormatError("Problem type mismatch");
   134 
   135     nodes.resize(desc.nodeNum + 1);
   136     for (int k = 1; k <= desc.nodeNum; ++k) {
   137       nodes[k] = g.addNode();
   138       supply.set(nodes[k], 0);
   139     }
   140 
   141     typename SupplyMap::Value sup;
   142     typename CapacityMap::Value low;
   143     typename CapacityMap::Value cap;
   144     typename CostMap::Value co;
   145     while (is >> c) {
   146       switch (c) {
   147       case 'c': // comment line
   148         getline(is, str);
   149         break;
   150       case 'n': // node definition line
   151         is >> i >> sup;
   152         getline(is, str);
   153         supply.set(nodes[i], sup);
   154         break;
   155       case 'a': // arc (arc) definition line
   156         is >> i >> j >> low >> cap >> co;
   157         getline(is, str);
   158         e = g.addArc(nodes[i], nodes[j]);
   159         lower.set(e, low);
   160         if (cap >= 0)
   161           capacity.set(e, cap);
   162         else
   163           capacity.set(e, -1);
   164         cost.set(e, co);
   165         break;
   166       }
   167     }
   168   }
   169 
   170   template<typename Digraph, typename CapacityMap>
   171   void _readDimacs(std::istream& is,
   172                    Digraph &g,
   173                    CapacityMap& capacity,
   174                    typename Digraph::Node &s,
   175                    typename Digraph::Node &t,
   176                    DimacsDescriptor desc=DimacsDescriptor()) {
   177     g.clear();
   178     s=t=INVALID;
   179     std::vector<typename Digraph::Node> nodes;
   180     typename Digraph::Arc e;
   181     char c, d;
   182     int i, j;
   183     typename CapacityMap::Value _cap;
   184     std::string str;
   185     nodes.resize(desc.nodeNum + 1);
   186     for (int k = 1; k <= desc.nodeNum; ++k) {
   187       nodes[k] = g.addNode();
   188     }
   189 
   190     while (is >> c) {
   191       switch (c) {
   192       case 'c': // comment line
   193         getline(is, str);
   194         break;
   195       case 'n': // node definition line
   196         if (desc.type==DimacsDescriptor::SP) { // shortest path problem
   197           is >> i;
   198           getline(is, str);
   199           s = nodes[i];
   200         }
   201         if (desc.type==DimacsDescriptor::MAX) { // max flow problem
   202           is >> i >> d;
   203           getline(is, str);
   204           if (d == 's') s = nodes[i];
   205           if (d == 't') t = nodes[i];
   206         }
   207         break;
   208       case 'a': // arc (arc) definition line
   209         if (desc.type==DimacsDescriptor::SP ||
   210             desc.type==DimacsDescriptor::MAX) {
   211           is >> i >> j >> _cap;
   212           getline(is, str);
   213           e = g.addArc(nodes[i], nodes[j]);
   214           capacity.set(e, _cap);
   215         } else {
   216           is >> i >> j;
   217           getline(is, str);
   218           g.addArc(nodes[i], nodes[j]);
   219         }
   220         break;
   221       }
   222     }
   223   }
   224 
   225   /// DIMACS maximum flow reader function.
   226   ///
   227   /// This function reads a maximum flow instance from DIMACS format,
   228   /// i.e. from a DIMACS file having a line starting with
   229   /// \code
   230   ///   p max
   231   /// \endcode
   232   /// At the beginning, \c g is cleared by \c g.clear(). The arc
   233   /// capacities are written to \c capacity and \c s and \c t are
   234   /// set to the source and the target nodes.
   235   ///
   236   /// If the file type was previously evaluated by dimacsType(), then
   237   /// the descriptor struct should be given by the \c dest parameter.
   238   template<typename Digraph, typename CapacityMap>
   239   void readDimacsMax(std::istream& is,
   240                      Digraph &g,
   241                      CapacityMap& capacity,
   242                      typename Digraph::Node &s,
   243                      typename Digraph::Node &t,
   244                      DimacsDescriptor desc=DimacsDescriptor()) {
   245     if(desc.type==DimacsDescriptor::NONE) desc=dimacsType(is);
   246     if(desc.type!=DimacsDescriptor::MAX)
   247       throw FormatError("Problem type mismatch");
   248     _readDimacs(is,g,capacity,s,t,desc);
   249   }
   250 
   251   /// DIMACS shortest path reader function.
   252   ///
   253   /// This function reads a shortest path instance from DIMACS format,
   254   /// i.e. from a DIMACS file having a line starting with
   255   /// \code
   256   ///   p sp
   257   /// \endcode
   258   /// At the beginning, \c g is cleared by \c g.clear(). The arc
   259   /// lengths are written to \c length and \c s is set to the
   260   /// source node.
   261   ///
   262   /// If the file type was previously evaluated by dimacsType(), then
   263   /// the descriptor struct should be given by the \c dest parameter.
   264   template<typename Digraph, typename LengthMap>
   265   void readDimacsSp(std::istream& is,
   266                     Digraph &g,
   267                     LengthMap& length,
   268                     typename Digraph::Node &s,
   269                     DimacsDescriptor desc=DimacsDescriptor()) {
   270     typename Digraph::Node t;
   271     if(desc.type==DimacsDescriptor::NONE) desc=dimacsType(is);
   272     if(desc.type!=DimacsDescriptor::SP)
   273       throw FormatError("Problem type mismatch");
   274     _readDimacs(is, g, length, s, t,desc);
   275   }
   276 
   277   /// DIMACS capacitated digraph reader function.
   278   ///
   279   /// This function reads an arc capacitated digraph instance from
   280   /// DIMACS 'mat' or 'sp' format.
   281   /// At the beginning, \c g is cleared by \c g.clear()
   282   /// and the arc capacities/lengths are written to \c capacity.
   283   ///
   284   /// If the file type was previously evaluated by dimacsType(), then
   285   /// the descriptor struct should be given by the \c dest parameter.
   286   template<typename Digraph, typename CapacityMap>
   287   void readDimacsCap(std::istream& is,
   288                      Digraph &g,
   289                      CapacityMap& capacity,
   290                      DimacsDescriptor desc=DimacsDescriptor()) {
   291     typename Digraph::Node u,v;
   292     if(desc.type==DimacsDescriptor::NONE) desc=dimacsType(is);
   293     if(desc.type!=DimacsDescriptor::MAX || desc.type!=DimacsDescriptor::SP)
   294       throw FormatError("Problem type mismatch");
   295     _readDimacs(is, g, capacity, u, v, desc);
   296   }
   297 
   298   template<typename Graph>
   299   typename enable_if<lemon::UndirectedTagIndicator<Graph>,void>::type
   300   _addArcEdge(Graph &g, typename Graph::Node s, typename Graph::Node t,
   301               dummy<0> = 0)
   302   {
   303     g.addEdge(s,t);
   304   }
   305   template<typename Graph>
   306   typename disable_if<lemon::UndirectedTagIndicator<Graph>,void>::type
   307   _addArcEdge(Graph &g, typename Graph::Node s, typename Graph::Node t,
   308               dummy<1> = 1)
   309   {
   310     g.addArc(s,t);
   311   }
   312   
   313   /// DIMACS plain (di)graph reader function.
   314   ///
   315   /// This function reads a (di)graph without any designated nodes and
   316   /// maps from DIMACS format, i.e. from DIMACS files having a line
   317   /// starting with
   318   /// \code
   319   ///   p mat
   320   /// \endcode
   321   /// At the beginning, \c g is cleared by \c g.clear().
   322   ///
   323   /// If the file type was previously evaluated by dimacsType(), then
   324   /// the descriptor struct should be given by the \c dest parameter.
   325   template<typename Graph>
   326   void readDimacsMat(std::istream& is, Graph &g,
   327                      DimacsDescriptor desc=DimacsDescriptor())
   328   {
   329     if(desc.type==DimacsDescriptor::NONE) desc=dimacsType(is);
   330     if(desc.type!=DimacsDescriptor::MAT)
   331       throw FormatError("Problem type mismatch");
   332 
   333     g.clear();
   334     std::vector<typename Graph::Node> nodes;
   335     char c;
   336     int i, j;
   337     std::string str;
   338     nodes.resize(desc.nodeNum + 1);
   339     for (int k = 1; k <= desc.nodeNum; ++k) {
   340       nodes[k] = g.addNode();
   341     }
   342     
   343     while (is >> c) {
   344       switch (c) {
   345       case 'c': // comment line
   346         getline(is, str);
   347         break;
   348       case 'n': // node definition line
   349         break;
   350       case 'a': // arc (arc) definition line
   351         is >> i >> j;
   352         getline(is, str);
   353         _addArcEdge(g,nodes[i], nodes[j]);
   354         break;
   355       }
   356     }
   357   }
   358 
   359   /// DIMACS plain digraph writer function.
   360   ///
   361   /// This function writes a digraph without any designated nodes and
   362   /// maps into DIMACS format, i.e. into DIMACS file having a line
   363   /// starting with
   364   /// \code
   365   ///   p mat
   366   /// \endcode
   367   /// If \c comment is not empty, then it will be printed in the first line
   368   /// prefixed by 'c'.
   369   template<typename Digraph>
   370   void writeDimacsMat(std::ostream& os, const Digraph &g,
   371                       std::string comment="") {
   372     typedef typename Digraph::NodeIt NodeIt;
   373     typedef typename Digraph::ArcIt ArcIt;
   374 
   375     if(!comment.empty())
   376       os << "c " << comment << std::endl;
   377     os << "p mat " << g.nodeNum() << " " << g.arcNum() << std::endl;
   378 
   379     typename Digraph::template NodeMap<int> nodes(g);
   380     int i = 1;
   381     for(NodeIt v(g); v != INVALID; ++v) {
   382       nodes.set(v, i);
   383       ++i;
   384     }
   385     for(ArcIt e(g); e != INVALID; ++e) {
   386       os << "a " << nodes[g.source(e)] << " " << nodes[g.target(e)]
   387          << std::endl;
   388     }
   389   }
   390 
   391   /// @}
   392 
   393 } //namespace lemon
   394 
   395 #endif //LEMON_DIMACS_H