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]); diff --git a/tools/dimacs-solver.cc b/tools/dimacs-solver.cc --- a/tools/dimacs-solver.cc +++ b/tools/dimacs-solver.cc @@ -72,7 +72,7 @@ template void solve_max(ArgParser &ap, std::istream &is, std::ostream &, - DimacsDescriptor &desc) + Value infty, DimacsDescriptor &desc) { bool report = !ap.given("q"); Digraph g; @@ -80,7 +80,7 @@ Digraph::ArcMap cap(g); Timer ti; ti.restart(); - readDimacsMax(is, g, cap, s, t, desc); + readDimacsMax(is, g, cap, s, t, infty, desc); if(report) std::cerr << "Read the file: " << ti << '\n'; ti.restart(); Preflow > pre(g,cap,s,t); @@ -115,6 +115,17 @@ void solve(ArgParser &ap, std::istream &is, std::ostream &os, DimacsDescriptor &desc) { + std::stringstream iss(ap["infcap"]); + Value infty; + iss >> infty; + if(iss.fail()) + { + std::cerr << "Cannot interpret '" + << static_cast(ap["infcap"]) << "' as infinite" + << std::endl; + exit(1); + } + switch(desc.type) { case DimacsDescriptor::MIN: @@ -122,7 +133,7 @@ "\n\n Sorry, the min. cost flow solver is not yet available.\n"; break; case DimacsDescriptor::MAX: - solve_max(ap,is,os,desc); + solve_max(ap,is,os,infty,desc); break; case DimacsDescriptor::SP: solve_sp(ap,is,os,desc); @@ -159,6 +170,7 @@ .boolOption("ldouble","Use 'long double' for capacities, costs etc.") .optionGroup("datatype","ldouble") .onlyOneGroup("datatype") + .stringOption("infcap","Value used for 'very high' capacities","0") .run(); std::ifstream input; diff --git a/tools/dimacs-to-lgf.cc b/tools/dimacs-to-lgf.cc --- a/tools/dimacs-to-lgf.cc +++ b/tools/dimacs-to-lgf.cc @@ -96,7 +96,7 @@ Digraph digraph; DoubleArcMap lower(digraph), capacity(digraph), cost(digraph); DoubleNodeMap supply(digraph); - readDimacsMin(is, digraph, lower, capacity, cost, supply, desc); + readDimacsMin(is, digraph, lower, capacity, cost, supply, 0, desc); DigraphWriter(digraph, os). nodeMap("supply", supply). arcMap("lower", lower). @@ -111,7 +111,7 @@ Digraph digraph; Node s, t; DoubleArcMap capacity(digraph); - readDimacsMax(is, digraph, capacity, s, t, desc); + readDimacsMax(is, digraph, capacity, s, t, 0, desc); DigraphWriter(digraph, os). arcMap("capacity", capacity). node("source", s).