lemon/dimacs.h
changeset 648 4ff8041e9c2e
parent 561 6e0525ec5355
child 877 141f9c0db4a3
equal deleted inserted replaced
6:f5735f366c22 7:ef2a4f1cc8b8
    35   /// @{
    35   /// @{
    36 
    36 
    37   /// DIMACS file type descriptor.
    37   /// DIMACS file type descriptor.
    38   struct DimacsDescriptor
    38   struct DimacsDescriptor
    39   {
    39   {
    40     ///File type enum
    40     ///\brief DIMACS file type enum
    41     enum Type
    41     ///
    42       {
    42     ///DIMACS file type enum.
    43         NONE, MIN, MAX, SP, MAT
    43     enum Type {
    44       };
    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     };
    45     ///The file type
    50     ///The file type
    46     Type type;
    51     Type type;
    47     ///The number of nodes in the graph
    52     ///The number of nodes in the graph
    48     int nodeNum;
    53     int nodeNum;
    49     ///The number of edges in the graph
    54     ///The number of edges in the graph
    50     int edgeNum;
    55     int edgeNum;
    51     int lineShift;
    56     int lineShift;
    52     /// Constructor. Sets the type to NONE.
    57     ///Constructor. It sets the type to \c NONE.
    53     DimacsDescriptor() : type(NONE) {}
    58     DimacsDescriptor() : type(NONE) {}
    54   };
    59   };
    55 
    60 
    56   ///Discover the type of a DIMACS file
    61   ///Discover the type of a DIMACS file
    57 
    62 
    58   ///It starts seeking the beginning of the file for the problem type
    63   ///This function starts seeking the beginning of the given file for the
    59   ///and size info. The found data is returned in a special struct
    64   ///problem type and size info. 
    60   ///that can be evaluated and passed to the appropriate reader
    65   ///The found data is returned in a special struct that can be evaluated
    61   ///function.
    66   ///and passed to the appropriate reader function.
    62   DimacsDescriptor dimacsType(std::istream& is)
    67   DimacsDescriptor dimacsType(std::istream& is)
    63   {
    68   {
    64     DimacsDescriptor r;
    69     DimacsDescriptor r;
    65     std::string problem,str;
    70     std::string problem,str;
    66     char c;
    71     char c;
    94         }
    99         }
    95     throw FormatError("Missing problem type declaration.");
   100     throw FormatError("Missing problem type declaration.");
    96   }
   101   }
    97 
   102 
    98 
   103 
    99 
   104   /// \brief DIMACS minimum cost flow reader function.
   100   /// DIMACS minimum cost flow reader function.
       
   101   ///
   105   ///
   102   /// This function reads a minimum cost flow instance from DIMACS format,
   106   /// This function reads a minimum cost flow instance from DIMACS format,
   103   /// i.e. from a DIMACS file having a line starting with
   107   /// i.e. from a DIMACS file having a line starting with
   104   /// \code
   108   /// \code
   105   ///   p min
   109   ///   p min
   251         break;
   255         break;
   252       }
   256       }
   253     }
   257     }
   254   }
   258   }
   255 
   259 
   256   /// DIMACS maximum flow reader function.
   260   /// \brief DIMACS maximum flow reader function.
   257   ///
   261   ///
   258   /// This function reads a maximum flow instance from DIMACS format,
   262   /// This function reads a maximum flow instance from DIMACS format,
   259   /// i.e. from a DIMACS file having a line starting with
   263   /// i.e. from a DIMACS file having a line starting with
   260   /// \code
   264   /// \code
   261   ///   p max
   265   ///   p max
   285     if(desc.type!=DimacsDescriptor::MAX)
   289     if(desc.type!=DimacsDescriptor::MAX)
   286       throw FormatError("Problem type mismatch");
   290       throw FormatError("Problem type mismatch");
   287     _readDimacs(is,g,capacity,s,t,infty,desc);
   291     _readDimacs(is,g,capacity,s,t,infty,desc);
   288   }
   292   }
   289 
   293 
   290   /// DIMACS shortest path reader function.
   294   /// \brief DIMACS shortest path reader function.
   291   ///
   295   ///
   292   /// This function reads a shortest path instance from DIMACS format,
   296   /// This function reads a shortest path instance from DIMACS format,
   293   /// i.e. from a DIMACS file having a line starting with
   297   /// i.e. from a DIMACS file having a line starting with
   294   /// \code
   298   /// \code
   295   ///   p sp
   299   ///   p sp
   311     if(desc.type!=DimacsDescriptor::SP)
   315     if(desc.type!=DimacsDescriptor::SP)
   312       throw FormatError("Problem type mismatch");
   316       throw FormatError("Problem type mismatch");
   313     _readDimacs(is, g, length, s, t, 0, desc);
   317     _readDimacs(is, g, length, s, t, 0, desc);
   314   }
   318   }
   315 
   319 
   316   /// DIMACS capacitated digraph reader function.
   320   /// \brief DIMACS capacitated digraph reader function.
   317   ///
   321   ///
   318   /// This function reads an arc capacitated digraph instance from
   322   /// This function reads an arc capacitated digraph instance from
   319   /// DIMACS 'max' or 'sp' format.
   323   /// DIMACS 'max' or 'sp' format.
   320   /// At the beginning, \c g is cleared by \c g.clear()
   324   /// At the beginning, \c g is cleared by \c g.clear()
   321   /// and the arc capacities/lengths are written to the \c capacity
   325   /// and the arc capacities/lengths are written to the \c capacity
   357               dummy<1> = 1)
   361               dummy<1> = 1)
   358   {
   362   {
   359     g.addArc(s,t);
   363     g.addArc(s,t);
   360   }
   364   }
   361   
   365   
   362   /// DIMACS plain (di)graph reader function.
   366   /// \brief DIMACS plain (di)graph reader function.
   363   ///
   367   ///
   364   /// This function reads a (di)graph without any designated nodes and
   368   /// This function reads a plain (di)graph without any designated nodes
   365   /// maps from DIMACS format, i.e. from DIMACS files having a line
   369   /// and maps (e.g. a matching instance) from DIMACS format, i.e. from 
   366   /// starting with
   370   /// DIMACS files having a line starting with
   367   /// \code
   371   /// \code
   368   ///   p mat
   372   ///   p mat
   369   /// \endcode
   373   /// \endcode
   370   /// At the beginning, \c g is cleared by \c g.clear().
   374   /// At the beginning, \c g is cleared by \c g.clear().
   371   ///
   375   ///