lemon/dimacs.h
changeset 1016 97975184f4aa
parent 584 33c6b6e755cd
child 1092 dceba191c00d
equal deleted inserted replaced
7:ef2a4f1cc8b8 8:f1e21016e886
     1 /* -*- mode: C++; indent-tabs-mode: nil; -*-
     1 /* -*- mode: C++; indent-tabs-mode: nil; -*-
     2  *
     2  *
     3  * This file is a part of LEMON, a generic C++ optimization library.
     3  * This file is a part of LEMON, a generic C++ optimization library.
     4  *
     4  *
     5  * Copyright (C) 2003-2009
     5  * Copyright (C) 2003-2010
     6  * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
     6  * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
     7  * (Egervary Research Group on Combinatorial Optimization, EGRES).
     7  * (Egervary Research Group on Combinatorial Optimization, EGRES).
     8  *
     8  *
     9  * Permission to use, modify and distribute this software is granted
     9  * Permission to use, modify and distribute this software is granted
    10  * provided that this copyright notice appears in all copies. For
    10  * provided that this copyright notice appears in all copies. For
    59   };
    59   };
    60 
    60 
    61   ///Discover the type of a DIMACS file
    61   ///Discover the type of a DIMACS file
    62 
    62 
    63   ///This function starts seeking the beginning of the given file for the
    63   ///This function starts seeking the beginning of the given file for the
    64   ///problem type and size info. 
    64   ///problem type and size info.
    65   ///The found data is returned in a special struct that can be evaluated
    65   ///The found data is returned in a special struct that can be evaluated
    66   ///and passed to the appropriate reader function.
    66   ///and passed to the appropriate reader function.
    67   DimacsDescriptor dimacsType(std::istream& is)
    67   DimacsDescriptor dimacsType(std::istream& is)
    68   {
    68   {
    69     DimacsDescriptor r;
    69     DimacsDescriptor r;
   210 
   210 
   211     if(infty==0)
   211     if(infty==0)
   212       infty = std::numeric_limits<Capacity>::has_infinity ?
   212       infty = std::numeric_limits<Capacity>::has_infinity ?
   213         std::numeric_limits<Capacity>::infinity() :
   213         std::numeric_limits<Capacity>::infinity() :
   214         std::numeric_limits<Capacity>::max();
   214         std::numeric_limits<Capacity>::max();
   215  
   215 
   216     while (is >> c) {
   216     while (is >> c) {
   217       switch (c) {
   217       switch (c) {
   218       case 'c': // comment line
   218       case 'c': // comment line
   219         getline(is, str);
   219         getline(is, str);
   220         break;
   220         break;
   235         if (desc.type==DimacsDescriptor::SP) {
   235         if (desc.type==DimacsDescriptor::SP) {
   236           is >> i >> j >> _cap;
   236           is >> i >> j >> _cap;
   237           getline(is, str);
   237           getline(is, str);
   238           e = g.addArc(nodes[i], nodes[j]);
   238           e = g.addArc(nodes[i], nodes[j]);
   239           capacity.set(e, _cap);
   239           capacity.set(e, _cap);
   240         } 
   240         }
   241         else if (desc.type==DimacsDescriptor::MAX) {
   241         else if (desc.type==DimacsDescriptor::MAX) {
   242           is >> i >> j >> _cap;
   242           is >> i >> j >> _cap;
   243           getline(is, str);
   243           getline(is, str);
   244           e = g.addArc(nodes[i], nodes[j]);
   244           e = g.addArc(nodes[i], nodes[j]);
   245           if (_cap >= 0)
   245           if (_cap >= 0)
   360   _addArcEdge(Graph &g, typename Graph::Node s, typename Graph::Node t,
   360   _addArcEdge(Graph &g, typename Graph::Node s, typename Graph::Node t,
   361               dummy<1> = 1)
   361               dummy<1> = 1)
   362   {
   362   {
   363     g.addArc(s,t);
   363     g.addArc(s,t);
   364   }
   364   }
   365   
   365 
   366   /// \brief DIMACS plain (di)graph reader function.
   366   /// \brief DIMACS plain (di)graph reader function.
   367   ///
   367   ///
   368   /// This function reads a plain (di)graph without any designated nodes
   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 
   369   /// and maps (e.g. a matching instance) from DIMACS format, i.e. from
   370   /// DIMACS files having a line starting with
   370   /// DIMACS files having a line starting with
   371   /// \code
   371   /// \code
   372   ///   p mat
   372   ///   p mat
   373   /// \endcode
   373   /// \endcode
   374   /// At the beginning, \c g is cleared by \c g.clear().
   374   /// At the beginning, \c g is cleared by \c g.clear().
   390     std::string str;
   390     std::string str;
   391     nodes.resize(desc.nodeNum + 1);
   391     nodes.resize(desc.nodeNum + 1);
   392     for (int k = 1; k <= desc.nodeNum; ++k) {
   392     for (int k = 1; k <= desc.nodeNum; ++k) {
   393       nodes[k] = g.addNode();
   393       nodes[k] = g.addNode();
   394     }
   394     }
   395     
   395 
   396     while (is >> c) {
   396     while (is >> c) {
   397       switch (c) {
   397       switch (c) {
   398       case 'c': // comment line
   398       case 'c': // comment line
   399         getline(is, str);
   399         getline(is, str);
   400         break;
   400         break;