Accept negative values as unbounded capacity in dimacs readers (#243)
authorAlpar Juttner <alpar@cs.elte.hu>
Mon, 30 Mar 2009 16:46:37 +0100
changeset 5616e0525ec5355
parent 560 49a39bae067c
child 562 538b3dd9a2c0
child 1156 f37f0845cf32
Accept negative values as unbounded capacity in dimacs readers (#243)
and some doc improvements.
lemon/dimacs.h
tools/dimacs-solver.cc
tools/dimacs-to-lgf.cc
     1.1 --- a/lemon/dimacs.h	Sun Mar 29 22:19:14 2009 +0100
     1.2 +++ b/lemon/dimacs.h	Mon Mar 30 16:46:37 2009 +0100
     1.3 @@ -22,9 +22,9 @@
     1.4  #include <iostream>
     1.5  #include <string>
     1.6  #include <vector>
     1.7 +#include <limits>
     1.8  #include <lemon/maps.h>
     1.9  #include <lemon/error.h>
    1.10 -
    1.11  /// \ingroup dimacs_group
    1.12  /// \file
    1.13  /// \brief DIMACS file format reader.
    1.14 @@ -55,7 +55,7 @@
    1.15  
    1.16    ///Discover the type of a DIMACS file
    1.17  
    1.18 -  ///It starts seeking the begining of the file for the problem type
    1.19 +  ///It starts seeking the beginning of the file for the problem type
    1.20    ///and size info. The found data is returned in a special struct
    1.21    ///that can be evaluated and passed to the appropriate reader
    1.22    ///function.
    1.23 @@ -105,9 +105,17 @@
    1.24    ///   p min
    1.25    /// \endcode
    1.26    /// At the beginning, \c g is cleared by \c g.clear(). The supply
    1.27 -  /// amount of the nodes are written to \c supply (signed). The
    1.28 -  /// lower bounds, capacities and costs of the arcs are written to
    1.29 -  /// \c lower, \c capacity and \c cost.
    1.30 +  /// amount of the nodes are written to the \c supply node map
    1.31 +  /// (they are signed values). The lower bounds, capacities and costs
    1.32 +  /// of the arcs are written to the \c lower, \c capacity and \c cost
    1.33 +  /// arc maps.
    1.34 +  ///
    1.35 +  /// If the capacity of an arc is less than the lower bound, it will
    1.36 +  /// be set to "infinite" instead. The actual value of "infinite" is
    1.37 +  /// contolled by the \c infty parameter. If it is 0 (the default value),
    1.38 +  /// \c std::numeric_limits<Capacity>::infinity() will be used if available,
    1.39 +  /// \c std::numeric_limits<Capacity>::max() otherwise. If \c infty is set to
    1.40 +  /// a non-zero value, that value will be used as "infinite".
    1.41    ///
    1.42    /// If the file type was previously evaluated by dimacsType(), then
    1.43    /// the descriptor struct should be given by the \c dest parameter.
    1.44 @@ -120,6 +128,7 @@
    1.45                       CapacityMap& capacity,
    1.46                       CostMap& cost,
    1.47                       SupplyMap& supply,
    1.48 +                     typename CapacityMap::Value infty = 0,
    1.49                       DimacsDescriptor desc=DimacsDescriptor())
    1.50    {
    1.51      g.clear();
    1.52 @@ -142,6 +151,12 @@
    1.53      typename CapacityMap::Value low;
    1.54      typename CapacityMap::Value cap;
    1.55      typename CostMap::Value co;
    1.56 +    typedef typename CapacityMap::Value Capacity;
    1.57 +    if(infty==0)
    1.58 +      infty = std::numeric_limits<Capacity>::has_infinity ?
    1.59 +        std::numeric_limits<Capacity>::infinity() :
    1.60 +        std::numeric_limits<Capacity>::max();
    1.61 +
    1.62      while (is >> c) {
    1.63        switch (c) {
    1.64        case 'c': // comment line
    1.65 @@ -152,15 +167,15 @@
    1.66          getline(is, str);
    1.67          supply.set(nodes[i], sup);
    1.68          break;
    1.69 -      case 'a': // arc (arc) definition line
    1.70 +      case 'a': // arc definition line
    1.71          is >> i >> j >> low >> cap >> co;
    1.72          getline(is, str);
    1.73          e = g.addArc(nodes[i], nodes[j]);
    1.74          lower.set(e, low);
    1.75 -        if (cap >= 0)
    1.76 +        if (cap >= low)
    1.77            capacity.set(e, cap);
    1.78          else
    1.79 -          capacity.set(e, -1);
    1.80 +          capacity.set(e, infty);
    1.81          cost.set(e, co);
    1.82          break;
    1.83        }
    1.84 @@ -173,6 +188,7 @@
    1.85                     CapacityMap& capacity,
    1.86                     typename Digraph::Node &s,
    1.87                     typename Digraph::Node &t,
    1.88 +                   typename CapacityMap::Value infty = 0,
    1.89                     DimacsDescriptor desc=DimacsDescriptor()) {
    1.90      g.clear();
    1.91      s=t=INVALID;
    1.92 @@ -186,7 +202,13 @@
    1.93      for (int k = 1; k <= desc.nodeNum; ++k) {
    1.94        nodes[k] = g.addNode();
    1.95      }
    1.96 +    typedef typename CapacityMap::Value Capacity;
    1.97  
    1.98 +    if(infty==0)
    1.99 +      infty = std::numeric_limits<Capacity>::has_infinity ?
   1.100 +        std::numeric_limits<Capacity>::infinity() :
   1.101 +        std::numeric_limits<Capacity>::max();
   1.102 + 
   1.103      while (is >> c) {
   1.104        switch (c) {
   1.105        case 'c': // comment line
   1.106 @@ -205,14 +227,23 @@
   1.107            if (d == 't') t = nodes[i];
   1.108          }
   1.109          break;
   1.110 -      case 'a': // arc (arc) definition line
   1.111 -        if (desc.type==DimacsDescriptor::SP ||
   1.112 -            desc.type==DimacsDescriptor::MAX) {
   1.113 +      case 'a': // arc definition line
   1.114 +        if (desc.type==DimacsDescriptor::SP) {
   1.115            is >> i >> j >> _cap;
   1.116            getline(is, str);
   1.117            e = g.addArc(nodes[i], nodes[j]);
   1.118            capacity.set(e, _cap);
   1.119 -        } else {
   1.120 +        } 
   1.121 +        else if (desc.type==DimacsDescriptor::MAX) {
   1.122 +          is >> i >> j >> _cap;
   1.123 +          getline(is, str);
   1.124 +          e = g.addArc(nodes[i], nodes[j]);
   1.125 +          if (_cap >= 0)
   1.126 +            capacity.set(e, _cap);
   1.127 +          else
   1.128 +            capacity.set(e, infty);
   1.129 +        }
   1.130 +        else {
   1.131            is >> i >> j;
   1.132            getline(is, str);
   1.133            g.addArc(nodes[i], nodes[j]);
   1.134 @@ -230,8 +261,15 @@
   1.135    ///   p max
   1.136    /// \endcode
   1.137    /// At the beginning, \c g is cleared by \c g.clear(). The arc
   1.138 -  /// capacities are written to \c capacity and \c s and \c t are
   1.139 -  /// set to the source and the target nodes.
   1.140 +  /// capacities are written to the \c capacity arc map and \c s and
   1.141 +  /// \c t are set to the source and the target nodes.
   1.142 +  ///
   1.143 +  /// If the capacity of an arc is negative, it will
   1.144 +  /// be set to "infinite" instead. The actual value of "infinite" is
   1.145 +  /// contolled by the \c infty parameter. If it is 0 (the default value),
   1.146 +  /// \c std::numeric_limits<Capacity>::infinity() will be used if available,
   1.147 +  /// \c std::numeric_limits<Capacity>::max() otherwise. If \c infty is set to
   1.148 +  /// a non-zero value, that value will be used as "infinite".
   1.149    ///
   1.150    /// If the file type was previously evaluated by dimacsType(), then
   1.151    /// the descriptor struct should be given by the \c dest parameter.
   1.152 @@ -241,11 +279,12 @@
   1.153                       CapacityMap& capacity,
   1.154                       typename Digraph::Node &s,
   1.155                       typename Digraph::Node &t,
   1.156 +                     typename CapacityMap::Value infty = 0,
   1.157                       DimacsDescriptor desc=DimacsDescriptor()) {
   1.158      if(desc.type==DimacsDescriptor::NONE) desc=dimacsType(is);
   1.159      if(desc.type!=DimacsDescriptor::MAX)
   1.160        throw FormatError("Problem type mismatch");
   1.161 -    _readDimacs(is,g,capacity,s,t,desc);
   1.162 +    _readDimacs(is,g,capacity,s,t,infty,desc);
   1.163    }
   1.164  
   1.165    /// DIMACS shortest path reader function.
   1.166 @@ -256,7 +295,7 @@
   1.167    ///   p sp
   1.168    /// \endcode
   1.169    /// At the beginning, \c g is cleared by \c g.clear(). The arc
   1.170 -  /// lengths are written to \c length and \c s is set to the
   1.171 +  /// lengths are written to the \c length arc map and \c s is set to the
   1.172    /// source node.
   1.173    ///
   1.174    /// If the file type was previously evaluated by dimacsType(), then
   1.175 @@ -271,15 +310,24 @@
   1.176      if(desc.type==DimacsDescriptor::NONE) desc=dimacsType(is);
   1.177      if(desc.type!=DimacsDescriptor::SP)
   1.178        throw FormatError("Problem type mismatch");
   1.179 -    _readDimacs(is, g, length, s, t,desc);
   1.180 +    _readDimacs(is, g, length, s, t, 0, desc);
   1.181    }
   1.182  
   1.183    /// DIMACS capacitated digraph reader function.
   1.184    ///
   1.185    /// This function reads an arc capacitated digraph instance from
   1.186 -  /// DIMACS 'mat' or 'sp' format.
   1.187 +  /// DIMACS 'max' or 'sp' format.
   1.188    /// At the beginning, \c g is cleared by \c g.clear()
   1.189 -  /// and the arc capacities/lengths are written to \c capacity.
   1.190 +  /// and the arc capacities/lengths are written to the \c capacity
   1.191 +  /// arc map.
   1.192 +  ///
   1.193 +  /// In case of the 'max' format, if the capacity of an arc is negative,
   1.194 +  /// it will
   1.195 +  /// be set to "infinite" instead. The actual value of "infinite" is
   1.196 +  /// contolled by the \c infty parameter. If it is 0 (the default value),
   1.197 +  /// \c std::numeric_limits<Capacity>::infinity() will be used if available,
   1.198 +  /// \c std::numeric_limits<Capacity>::max() otherwise. If \c infty is set to
   1.199 +  /// a non-zero value, that value will be used as "infinite".
   1.200    ///
   1.201    /// If the file type was previously evaluated by dimacsType(), then
   1.202    /// the descriptor struct should be given by the \c dest parameter.
   1.203 @@ -287,12 +335,13 @@
   1.204    void readDimacsCap(std::istream& is,
   1.205                       Digraph &g,
   1.206                       CapacityMap& capacity,
   1.207 +                     typename CapacityMap::Value infty = 0,
   1.208                       DimacsDescriptor desc=DimacsDescriptor()) {
   1.209      typename Digraph::Node u,v;
   1.210      if(desc.type==DimacsDescriptor::NONE) desc=dimacsType(is);
   1.211      if(desc.type!=DimacsDescriptor::MAX || desc.type!=DimacsDescriptor::SP)
   1.212        throw FormatError("Problem type mismatch");
   1.213 -    _readDimacs(is, g, capacity, u, v, desc);
   1.214 +    _readDimacs(is, g, capacity, u, v, infty, desc);
   1.215    }
   1.216  
   1.217    template<typename Graph>
   1.218 @@ -347,7 +396,7 @@
   1.219          break;
   1.220        case 'n': // node definition line
   1.221          break;
   1.222 -      case 'a': // arc (arc) definition line
   1.223 +      case 'a': // arc definition line
   1.224          is >> i >> j;
   1.225          getline(is, str);
   1.226          _addArcEdge(g,nodes[i], nodes[j]);
     2.1 --- a/tools/dimacs-solver.cc	Sun Mar 29 22:19:14 2009 +0100
     2.2 +++ b/tools/dimacs-solver.cc	Mon Mar 30 16:46:37 2009 +0100
     2.3 @@ -72,7 +72,7 @@
     2.4  
     2.5  template<class Value>
     2.6  void solve_max(ArgParser &ap, std::istream &is, std::ostream &,
     2.7 -              DimacsDescriptor &desc)
     2.8 +               Value infty, DimacsDescriptor &desc)
     2.9  {
    2.10    bool report = !ap.given("q");
    2.11    Digraph g;
    2.12 @@ -80,7 +80,7 @@
    2.13    Digraph::ArcMap<Value> cap(g);
    2.14    Timer ti;
    2.15    ti.restart();
    2.16 -  readDimacsMax(is, g, cap, s, t, desc);
    2.17 +  readDimacsMax(is, g, cap, s, t, infty, desc);
    2.18    if(report) std::cerr << "Read the file: " << ti << '\n';
    2.19    ti.restart();
    2.20    Preflow<Digraph, Digraph::ArcMap<Value> > pre(g,cap,s,t);
    2.21 @@ -115,6 +115,17 @@
    2.22  void solve(ArgParser &ap, std::istream &is, std::ostream &os,
    2.23             DimacsDescriptor &desc)
    2.24  {
    2.25 +  std::stringstream iss(ap["infcap"]);
    2.26 +  Value infty;
    2.27 +  iss >> infty;
    2.28 +  if(iss.fail())
    2.29 +    {
    2.30 +      std::cerr << "Cannot interpret '"
    2.31 +                << static_cast<std::string>(ap["infcap"]) << "' as infinite"
    2.32 +                << std::endl;
    2.33 +      exit(1);
    2.34 +    }
    2.35 +  
    2.36    switch(desc.type)
    2.37      {
    2.38      case DimacsDescriptor::MIN:
    2.39 @@ -122,7 +133,7 @@
    2.40          "\n\n Sorry, the min. cost flow solver is not yet available.\n";
    2.41        break;
    2.42      case DimacsDescriptor::MAX:
    2.43 -      solve_max<Value>(ap,is,os,desc);
    2.44 +      solve_max<Value>(ap,is,os,infty,desc);
    2.45        break;
    2.46      case DimacsDescriptor::SP:
    2.47        solve_sp<Value>(ap,is,os,desc);
    2.48 @@ -159,6 +170,7 @@
    2.49      .boolOption("ldouble","Use 'long double' for capacities, costs etc.")
    2.50      .optionGroup("datatype","ldouble")
    2.51      .onlyOneGroup("datatype")
    2.52 +    .stringOption("infcap","Value used for 'very high' capacities","0")
    2.53      .run();
    2.54  
    2.55    std::ifstream input;
     3.1 --- a/tools/dimacs-to-lgf.cc	Sun Mar 29 22:19:14 2009 +0100
     3.2 +++ b/tools/dimacs-to-lgf.cc	Mon Mar 30 16:46:37 2009 +0100
     3.3 @@ -96,7 +96,7 @@
     3.4          Digraph digraph;
     3.5          DoubleArcMap lower(digraph), capacity(digraph), cost(digraph);
     3.6          DoubleNodeMap supply(digraph);
     3.7 -        readDimacsMin(is, digraph, lower, capacity, cost, supply, desc);
     3.8 +        readDimacsMin(is, digraph, lower, capacity, cost, supply, 0, desc);
     3.9          DigraphWriter<Digraph>(digraph, os).
    3.10            nodeMap("supply", supply).
    3.11            arcMap("lower", lower).
    3.12 @@ -111,7 +111,7 @@
    3.13          Digraph digraph;
    3.14          Node s, t;
    3.15          DoubleArcMap capacity(digraph);
    3.16 -        readDimacsMax(is, digraph, capacity, s, t, desc);
    3.17 +        readDimacsMax(is, digraph, capacity, s, t, 0, desc);
    3.18          DigraphWriter<Digraph>(digraph, os).
    3.19            arcMap("capacity", capacity).
    3.20            node("source", s).