diff --git a/lemon/dimacs.h b/lemon/dimacs.h --- a/lemon/dimacs.h +++ b/lemon/dimacs.h @@ -22,9 +22,9 @@ #include #include #include +#include #include #include - /// \ingroup dimacs_group /// \file /// \brief DIMACS file format reader. @@ -55,7 +55,7 @@ ///Discover the type of a DIMACS file - ///It starts seeking the begining of the file for the problem type + ///It starts seeking the beginning of the file for the problem type ///and size info. The found data is returned in a special struct ///that can be evaluated and passed to the appropriate reader ///function. @@ -105,9 +105,17 @@ /// p min /// \endcode /// At the beginning, \c g is cleared by \c g.clear(). The supply - /// amount of the nodes are written to \c supply (signed). The - /// lower bounds, capacities and costs of the arcs are written to - /// \c lower, \c capacity and \c cost. + /// amount of the nodes are written to the \c supply node map + /// (they are signed values). The lower bounds, capacities and costs + /// of the arcs are written to the \c lower, \c capacity and \c cost + /// arc maps. + /// + /// If the capacity of an arc is less than the lower bound, it will + /// be set to "infinite" instead. The actual value of "infinite" is + /// contolled by the \c infty parameter. If it is 0 (the default value), + /// \c std::numeric_limits::infinity() will be used if available, + /// \c std::numeric_limits::max() otherwise. If \c infty is set to + /// a non-zero value, that value will be used as "infinite". /// /// If the file type was previously evaluated by dimacsType(), then /// the descriptor struct should be given by the \c dest parameter. @@ -120,6 +128,7 @@ CapacityMap& capacity, CostMap& cost, SupplyMap& supply, + typename CapacityMap::Value infty = 0, DimacsDescriptor desc=DimacsDescriptor()) { g.clear(); @@ -142,6 +151,12 @@ typename CapacityMap::Value low; typename CapacityMap::Value cap; typename CostMap::Value co; + typedef typename CapacityMap::Value Capacity; + if(infty==0) + infty = std::numeric_limits::has_infinity ? + std::numeric_limits::infinity() : + std::numeric_limits::max(); + while (is >> c) { switch (c) { case 'c': // comment line @@ -152,15 +167,15 @@ getline(is, str); supply.set(nodes[i], sup); break; - case 'a': // arc (arc) definition line + case 'a': // arc definition line is >> i >> j >> low >> cap >> co; getline(is, str); e = g.addArc(nodes[i], nodes[j]); lower.set(e, low); - if (cap >= 0) + if (cap >= low) capacity.set(e, cap); else - capacity.set(e, -1); + capacity.set(e, infty); cost.set(e, co); break; } @@ -173,6 +188,7 @@ CapacityMap& capacity, typename Digraph::Node &s, typename Digraph::Node &t, + typename CapacityMap::Value infty = 0, DimacsDescriptor desc=DimacsDescriptor()) { g.clear(); s=t=INVALID; @@ -186,7 +202,13 @@ for (int k = 1; k <= desc.nodeNum; ++k) { nodes[k] = g.addNode(); } + typedef typename CapacityMap::Value Capacity; + if(infty==0) + infty = std::numeric_limits::has_infinity ? + std::numeric_limits::infinity() : + std::numeric_limits::max(); + while (is >> c) { switch (c) { case 'c': // comment line @@ -205,14 +227,23 @@ if (d == 't') t = nodes[i]; } break; - case 'a': // arc (arc) definition line - if (desc.type==DimacsDescriptor::SP || - desc.type==DimacsDescriptor::MAX) { + case 'a': // arc definition line + if (desc.type==DimacsDescriptor::SP) { is >> i >> j >> _cap; getline(is, str); e = g.addArc(nodes[i], nodes[j]); capacity.set(e, _cap); - } else { + } + else if (desc.type==DimacsDescriptor::MAX) { + is >> i >> j >> _cap; + getline(is, str); + e = g.addArc(nodes[i], nodes[j]); + if (_cap >= 0) + capacity.set(e, _cap); + else + capacity.set(e, infty); + } + else { is >> i >> j; getline(is, str); g.addArc(nodes[i], nodes[j]); @@ -230,8 +261,15 @@ /// p max /// \endcode /// At the beginning, \c g is cleared by \c g.clear(). The arc - /// capacities are written to \c capacity and \c s and \c t are - /// set to the source and the target nodes. + /// capacities are written to the \c capacity arc map and \c s and + /// \c t are set to the source and the target nodes. + /// + /// If the capacity of an arc is negative, it will + /// be set to "infinite" instead. The actual value of "infinite" is + /// contolled by the \c infty parameter. If it is 0 (the default value), + /// \c std::numeric_limits::infinity() will be used if available, + /// \c std::numeric_limits::max() otherwise. If \c infty is set to + /// a non-zero value, that value will be used as "infinite". /// /// If the file type was previously evaluated by dimacsType(), then /// the descriptor struct should be given by the \c dest parameter. @@ -241,11 +279,12 @@ CapacityMap& capacity, typename Digraph::Node &s, typename Digraph::Node &t, + typename CapacityMap::Value infty = 0, DimacsDescriptor desc=DimacsDescriptor()) { if(desc.type==DimacsDescriptor::NONE) desc=dimacsType(is); if(desc.type!=DimacsDescriptor::MAX) throw FormatError("Problem type mismatch"); - _readDimacs(is,g,capacity,s,t,desc); + _readDimacs(is,g,capacity,s,t,infty,desc); } /// DIMACS shortest path reader function. @@ -256,7 +295,7 @@ /// p sp /// \endcode /// At the beginning, \c g is cleared by \c g.clear(). The arc - /// lengths are written to \c length and \c s is set to the + /// lengths are written to the \c length arc map and \c s is set to the /// source node. /// /// If the file type was previously evaluated by dimacsType(), then @@ -271,15 +310,24 @@ if(desc.type==DimacsDescriptor::NONE) desc=dimacsType(is); if(desc.type!=DimacsDescriptor::SP) throw FormatError("Problem type mismatch"); - _readDimacs(is, g, length, s, t,desc); + _readDimacs(is, g, length, s, t, 0, desc); } /// DIMACS capacitated digraph reader function. /// /// This function reads an arc capacitated digraph instance from - /// DIMACS 'mat' or 'sp' format. + /// DIMACS 'max' or 'sp' format. /// At the beginning, \c g is cleared by \c g.clear() - /// and the arc capacities/lengths are written to \c capacity. + /// and the arc capacities/lengths are written to the \c capacity + /// arc map. + /// + /// In case of the 'max' format, if the capacity of an arc is negative, + /// it will + /// be set to "infinite" instead. The actual value of "infinite" is + /// contolled by the \c infty parameter. If it is 0 (the default value), + /// \c std::numeric_limits::infinity() will be used if available, + /// \c std::numeric_limits::max() otherwise. If \c infty is set to + /// a non-zero value, that value will be used as "infinite". /// /// If the file type was previously evaluated by dimacsType(), then /// the descriptor struct should be given by the \c dest parameter. @@ -287,12 +335,13 @@ void readDimacsCap(std::istream& is, Digraph &g, CapacityMap& capacity, + typename CapacityMap::Value infty = 0, DimacsDescriptor desc=DimacsDescriptor()) { typename Digraph::Node u,v; if(desc.type==DimacsDescriptor::NONE) desc=dimacsType(is); if(desc.type!=DimacsDescriptor::MAX || desc.type!=DimacsDescriptor::SP) throw FormatError("Problem type mismatch"); - _readDimacs(is, g, capacity, u, v, desc); + _readDimacs(is, g, capacity, u, v, infty, desc); } template @@ -347,7 +396,7 @@ break; case 'n': // node definition line break; - case 'a': // arc (arc) definition line + case 'a': // arc definition line is >> i >> j; getline(is, str); _addArcEdge(g,nodes[i], nodes[j]);