lemon/dimacs.h
changeset 608 6e0525ec5355
parent 572 635a8375227d
child 631 33c6b6e755cd
child 1372 f37f0845cf32
equal deleted inserted replaced
5:1ba012539556 6:f5735f366c22
    20 #define LEMON_DIMACS_H
    20 #define LEMON_DIMACS_H
    21 
    21 
    22 #include <iostream>
    22 #include <iostream>
    23 #include <string>
    23 #include <string>
    24 #include <vector>
    24 #include <vector>
       
    25 #include <limits>
    25 #include <lemon/maps.h>
    26 #include <lemon/maps.h>
    26 #include <lemon/error.h>
    27 #include <lemon/error.h>
    27 
       
    28 /// \ingroup dimacs_group
    28 /// \ingroup dimacs_group
    29 /// \file
    29 /// \file
    30 /// \brief DIMACS file format reader.
    30 /// \brief DIMACS file format reader.
    31 
    31 
    32 namespace lemon {
    32 namespace lemon {
    53     DimacsDescriptor() : type(NONE) {}
    53     DimacsDescriptor() : type(NONE) {}
    54   };
    54   };
    55 
    55 
    56   ///Discover the type of a DIMACS file
    56   ///Discover the type of a DIMACS file
    57 
    57 
    58   ///It starts seeking the begining of the file for the problem type
    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
    59   ///and size info. The found data is returned in a special struct
    60   ///that can be evaluated and passed to the appropriate reader
    60   ///that can be evaluated and passed to the appropriate reader
    61   ///function.
    61   ///function.
    62   DimacsDescriptor dimacsType(std::istream& is)
    62   DimacsDescriptor dimacsType(std::istream& is)
    63   {
    63   {
   103   /// i.e. from a DIMACS file having a line starting with
   103   /// i.e. from a DIMACS file having a line starting with
   104   /// \code
   104   /// \code
   105   ///   p min
   105   ///   p min
   106   /// \endcode
   106   /// \endcode
   107   /// At the beginning, \c g is cleared by \c g.clear(). The supply
   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
   108   /// amount of the nodes are written to the \c supply node map
   109   /// lower bounds, capacities and costs of the arcs are written to
   109   /// (they are signed values). The lower bounds, capacities and costs
   110   /// \c lower, \c capacity and \c cost.
   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".
   111   ///
   119   ///
   112   /// If the file type was previously evaluated by dimacsType(), then
   120   /// If the file type was previously evaluated by dimacsType(), then
   113   /// the descriptor struct should be given by the \c dest parameter.
   121   /// the descriptor struct should be given by the \c dest parameter.
   114   template <typename Digraph, typename LowerMap,
   122   template <typename Digraph, typename LowerMap,
   115             typename CapacityMap, typename CostMap,
   123             typename CapacityMap, typename CostMap,
   118                      Digraph &g,
   126                      Digraph &g,
   119                      LowerMap& lower,
   127                      LowerMap& lower,
   120                      CapacityMap& capacity,
   128                      CapacityMap& capacity,
   121                      CostMap& cost,
   129                      CostMap& cost,
   122                      SupplyMap& supply,
   130                      SupplyMap& supply,
       
   131                      typename CapacityMap::Value infty = 0,
   123                      DimacsDescriptor desc=DimacsDescriptor())
   132                      DimacsDescriptor desc=DimacsDescriptor())
   124   {
   133   {
   125     g.clear();
   134     g.clear();
   126     std::vector<typename Digraph::Node> nodes;
   135     std::vector<typename Digraph::Node> nodes;
   127     typename Digraph::Arc e;
   136     typename Digraph::Arc e;
   140 
   149 
   141     typename SupplyMap::Value sup;
   150     typename SupplyMap::Value sup;
   142     typename CapacityMap::Value low;
   151     typename CapacityMap::Value low;
   143     typename CapacityMap::Value cap;
   152     typename CapacityMap::Value cap;
   144     typename CostMap::Value co;
   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 
   145     while (is >> c) {
   160     while (is >> c) {
   146       switch (c) {
   161       switch (c) {
   147       case 'c': // comment line
   162       case 'c': // comment line
   148         getline(is, str);
   163         getline(is, str);
   149         break;
   164         break;
   150       case 'n': // node definition line
   165       case 'n': // node definition line
   151         is >> i >> sup;
   166         is >> i >> sup;
   152         getline(is, str);
   167         getline(is, str);
   153         supply.set(nodes[i], sup);
   168         supply.set(nodes[i], sup);
   154         break;
   169         break;
   155       case 'a': // arc (arc) definition line
   170       case 'a': // arc definition line
   156         is >> i >> j >> low >> cap >> co;
   171         is >> i >> j >> low >> cap >> co;
   157         getline(is, str);
   172         getline(is, str);
   158         e = g.addArc(nodes[i], nodes[j]);
   173         e = g.addArc(nodes[i], nodes[j]);
   159         lower.set(e, low);
   174         lower.set(e, low);
   160         if (cap >= 0)
   175         if (cap >= low)
   161           capacity.set(e, cap);
   176           capacity.set(e, cap);
   162         else
   177         else
   163           capacity.set(e, -1);
   178           capacity.set(e, infty);
   164         cost.set(e, co);
   179         cost.set(e, co);
   165         break;
   180         break;
   166       }
   181       }
   167     }
   182     }
   168   }
   183   }
   171   void _readDimacs(std::istream& is,
   186   void _readDimacs(std::istream& is,
   172                    Digraph &g,
   187                    Digraph &g,
   173                    CapacityMap& capacity,
   188                    CapacityMap& capacity,
   174                    typename Digraph::Node &s,
   189                    typename Digraph::Node &s,
   175                    typename Digraph::Node &t,
   190                    typename Digraph::Node &t,
       
   191                    typename CapacityMap::Value infty = 0,
   176                    DimacsDescriptor desc=DimacsDescriptor()) {
   192                    DimacsDescriptor desc=DimacsDescriptor()) {
   177     g.clear();
   193     g.clear();
   178     s=t=INVALID;
   194     s=t=INVALID;
   179     std::vector<typename Digraph::Node> nodes;
   195     std::vector<typename Digraph::Node> nodes;
   180     typename Digraph::Arc e;
   196     typename Digraph::Arc e;
   184     std::string str;
   200     std::string str;
   185     nodes.resize(desc.nodeNum + 1);
   201     nodes.resize(desc.nodeNum + 1);
   186     for (int k = 1; k <= desc.nodeNum; ++k) {
   202     for (int k = 1; k <= desc.nodeNum; ++k) {
   187       nodes[k] = g.addNode();
   203       nodes[k] = g.addNode();
   188     }
   204     }
   189 
   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  
   190     while (is >> c) {
   212     while (is >> c) {
   191       switch (c) {
   213       switch (c) {
   192       case 'c': // comment line
   214       case 'c': // comment line
   193         getline(is, str);
   215         getline(is, str);
   194         break;
   216         break;
   203           getline(is, str);
   225           getline(is, str);
   204           if (d == 's') s = nodes[i];
   226           if (d == 's') s = nodes[i];
   205           if (d == 't') t = nodes[i];
   227           if (d == 't') t = nodes[i];
   206         }
   228         }
   207         break;
   229         break;
   208       case 'a': // arc (arc) definition line
   230       case 'a': // arc definition line
   209         if (desc.type==DimacsDescriptor::SP ||
   231         if (desc.type==DimacsDescriptor::SP) {
   210             desc.type==DimacsDescriptor::MAX) {
       
   211           is >> i >> j >> _cap;
   232           is >> i >> j >> _cap;
   212           getline(is, str);
   233           getline(is, str);
   213           e = g.addArc(nodes[i], nodes[j]);
   234           e = g.addArc(nodes[i], nodes[j]);
   214           capacity.set(e, _cap);
   235           capacity.set(e, _cap);
   215         } else {
   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 {
   216           is >> i >> j;
   247           is >> i >> j;
   217           getline(is, str);
   248           getline(is, str);
   218           g.addArc(nodes[i], nodes[j]);
   249           g.addArc(nodes[i], nodes[j]);
   219         }
   250         }
   220         break;
   251         break;
   228   /// i.e. from a DIMACS file having a line starting with
   259   /// i.e. from a DIMACS file having a line starting with
   229   /// \code
   260   /// \code
   230   ///   p max
   261   ///   p max
   231   /// \endcode
   262   /// \endcode
   232   /// At the beginning, \c g is cleared by \c g.clear(). The arc
   263   /// 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
   264   /// capacities are written to the \c capacity arc map and \c s and
   234   /// set to the source and the target nodes.
   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".
   235   ///
   273   ///
   236   /// If the file type was previously evaluated by dimacsType(), then
   274   /// If the file type was previously evaluated by dimacsType(), then
   237   /// the descriptor struct should be given by the \c dest parameter.
   275   /// the descriptor struct should be given by the \c dest parameter.
   238   template<typename Digraph, typename CapacityMap>
   276   template<typename Digraph, typename CapacityMap>
   239   void readDimacsMax(std::istream& is,
   277   void readDimacsMax(std::istream& is,
   240                      Digraph &g,
   278                      Digraph &g,
   241                      CapacityMap& capacity,
   279                      CapacityMap& capacity,
   242                      typename Digraph::Node &s,
   280                      typename Digraph::Node &s,
   243                      typename Digraph::Node &t,
   281                      typename Digraph::Node &t,
       
   282                      typename CapacityMap::Value infty = 0,
   244                      DimacsDescriptor desc=DimacsDescriptor()) {
   283                      DimacsDescriptor desc=DimacsDescriptor()) {
   245     if(desc.type==DimacsDescriptor::NONE) desc=dimacsType(is);
   284     if(desc.type==DimacsDescriptor::NONE) desc=dimacsType(is);
   246     if(desc.type!=DimacsDescriptor::MAX)
   285     if(desc.type!=DimacsDescriptor::MAX)
   247       throw FormatError("Problem type mismatch");
   286       throw FormatError("Problem type mismatch");
   248     _readDimacs(is,g,capacity,s,t,desc);
   287     _readDimacs(is,g,capacity,s,t,infty,desc);
   249   }
   288   }
   250 
   289 
   251   /// DIMACS shortest path reader function.
   290   /// DIMACS shortest path reader function.
   252   ///
   291   ///
   253   /// This function reads a shortest path instance from DIMACS format,
   292   /// This function reads a shortest path instance from DIMACS format,
   254   /// i.e. from a DIMACS file having a line starting with
   293   /// i.e. from a DIMACS file having a line starting with
   255   /// \code
   294   /// \code
   256   ///   p sp
   295   ///   p sp
   257   /// \endcode
   296   /// \endcode
   258   /// At the beginning, \c g is cleared by \c g.clear(). The arc
   297   /// 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
   298   /// lengths are written to the \c length arc map and \c s is set to the
   260   /// source node.
   299   /// source node.
   261   ///
   300   ///
   262   /// If the file type was previously evaluated by dimacsType(), then
   301   /// If the file type was previously evaluated by dimacsType(), then
   263   /// the descriptor struct should be given by the \c dest parameter.
   302   /// the descriptor struct should be given by the \c dest parameter.
   264   template<typename Digraph, typename LengthMap>
   303   template<typename Digraph, typename LengthMap>
   269                     DimacsDescriptor desc=DimacsDescriptor()) {
   308                     DimacsDescriptor desc=DimacsDescriptor()) {
   270     typename Digraph::Node t;
   309     typename Digraph::Node t;
   271     if(desc.type==DimacsDescriptor::NONE) desc=dimacsType(is);
   310     if(desc.type==DimacsDescriptor::NONE) desc=dimacsType(is);
   272     if(desc.type!=DimacsDescriptor::SP)
   311     if(desc.type!=DimacsDescriptor::SP)
   273       throw FormatError("Problem type mismatch");
   312       throw FormatError("Problem type mismatch");
   274     _readDimacs(is, g, length, s, t,desc);
   313     _readDimacs(is, g, length, s, t, 0, desc);
   275   }
   314   }
   276 
   315 
   277   /// DIMACS capacitated digraph reader function.
   316   /// DIMACS capacitated digraph reader function.
   278   ///
   317   ///
   279   /// This function reads an arc capacitated digraph instance from
   318   /// This function reads an arc capacitated digraph instance from
   280   /// DIMACS 'mat' or 'sp' format.
   319   /// DIMACS 'max' or 'sp' format.
   281   /// At the beginning, \c g is cleared by \c g.clear()
   320   /// At the beginning, \c g is cleared by \c g.clear()
   282   /// and the arc capacities/lengths are written to \c capacity.
   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".
   283   ///
   331   ///
   284   /// If the file type was previously evaluated by dimacsType(), then
   332   /// If the file type was previously evaluated by dimacsType(), then
   285   /// the descriptor struct should be given by the \c dest parameter.
   333   /// the descriptor struct should be given by the \c dest parameter.
   286   template<typename Digraph, typename CapacityMap>
   334   template<typename Digraph, typename CapacityMap>
   287   void readDimacsCap(std::istream& is,
   335   void readDimacsCap(std::istream& is,
   288                      Digraph &g,
   336                      Digraph &g,
   289                      CapacityMap& capacity,
   337                      CapacityMap& capacity,
       
   338                      typename CapacityMap::Value infty = 0,
   290                      DimacsDescriptor desc=DimacsDescriptor()) {
   339                      DimacsDescriptor desc=DimacsDescriptor()) {
   291     typename Digraph::Node u,v;
   340     typename Digraph::Node u,v;
   292     if(desc.type==DimacsDescriptor::NONE) desc=dimacsType(is);
   341     if(desc.type==DimacsDescriptor::NONE) desc=dimacsType(is);
   293     if(desc.type!=DimacsDescriptor::MAX || desc.type!=DimacsDescriptor::SP)
   342     if(desc.type!=DimacsDescriptor::MAX || desc.type!=DimacsDescriptor::SP)
   294       throw FormatError("Problem type mismatch");
   343       throw FormatError("Problem type mismatch");
   295     _readDimacs(is, g, capacity, u, v, desc);
   344     _readDimacs(is, g, capacity, u, v, infty, desc);
   296   }
   345   }
   297 
   346 
   298   template<typename Graph>
   347   template<typename Graph>
   299   typename enable_if<lemon::UndirectedTagIndicator<Graph>,void>::type
   348   typename enable_if<lemon::UndirectedTagIndicator<Graph>,void>::type
   300   _addArcEdge(Graph &g, typename Graph::Node s, typename Graph::Node t,
   349   _addArcEdge(Graph &g, typename Graph::Node s, typename Graph::Node t,
   345       case 'c': // comment line
   394       case 'c': // comment line
   346         getline(is, str);
   395         getline(is, str);
   347         break;
   396         break;
   348       case 'n': // node definition line
   397       case 'n': // node definition line
   349         break;
   398         break;
   350       case 'a': // arc (arc) definition line
   399       case 'a': // arc definition line
   351         is >> i >> j;
   400         is >> i >> j;
   352         getline(is, str);
   401         getline(is, str);
   353         _addArcEdge(g,nodes[i], nodes[j]);
   402         _addArcEdge(g,nodes[i], nodes[j]);
   354         break;
   403         break;
   355       }
   404       }