gravatar
alpar (Alpar Juttner)
alpar@cs.elte.hu
Accept negative values as unbounded capacity in dimacs readers (#243) and some doc improvements.
0 3 0
default
3 files changed with 87 insertions and 26 deletions:
↑ Collapse diff ↑
Ignore white space 6 line context
... ...
@@ -24,5 +24,5 @@
24 24
#include <vector>
25
#include <limits>
25 26
#include <lemon/maps.h>
26 27
#include <lemon/error.h>
27

	
28 28
/// \ingroup dimacs_group
... ...
@@ -57,3 +57,3 @@
57 57

	
58
  ///It starts seeking the begining of the file for the problem type
58
  ///It starts seeking the beginning of the file for the problem type
59 59
  ///and size info. The found data is returned in a special struct
... ...
@@ -107,5 +107,13 @@
107 107
  /// At the beginning, \c g is cleared by \c g.clear(). The supply
108
  /// amount of the nodes are written to \c supply (signed). The
109
  /// lower bounds, capacities and costs of the arcs are written to
110
  /// \c lower, \c capacity and \c cost.
108
  /// amount of the nodes are written to the \c supply node map
109
  /// (they are signed values). The lower bounds, capacities and costs
110
  /// of the arcs are written to the \c lower, \c capacity and \c cost
111
  /// arc maps.
112
  ///
113
  /// If the capacity of an arc is less than the lower bound, it will
114
  /// be set to "infinite" instead. The actual value of "infinite" is
115
  /// contolled by the \c infty parameter. If it is 0 (the default value),
116
  /// \c std::numeric_limits<Capacity>::infinity() will be used if available,
117
  /// \c std::numeric_limits<Capacity>::max() otherwise. If \c infty is set to
118
  /// a non-zero value, that value will be used as "infinite".
111 119
  ///
... ...
@@ -122,2 +130,3 @@
122 130
                     SupplyMap& supply,
131
                     typename CapacityMap::Value infty = 0,
123 132
                     DimacsDescriptor desc=DimacsDescriptor())
... ...
@@ -144,2 +153,8 @@
144 153
    typename CostMap::Value co;
154
    typedef typename CapacityMap::Value Capacity;
155
    if(infty==0)
156
      infty = std::numeric_limits<Capacity>::has_infinity ?
157
        std::numeric_limits<Capacity>::infinity() :
158
        std::numeric_limits<Capacity>::max();
159

	
145 160
    while (is >> c) {
... ...
@@ -154,3 +169,3 @@
154 169
        break;
155
      case 'a': // arc (arc) definition line
170
      case 'a': // arc definition line
156 171
        is >> i >> j >> low >> cap >> co;
... ...
@@ -159,6 +174,6 @@
159 174
        lower.set(e, low);
160
        if (cap >= 0)
175
        if (cap >= low)
161 176
          capacity.set(e, cap);
162 177
        else
163
          capacity.set(e, -1);
178
          capacity.set(e, infty);
164 179
        cost.set(e, co);
... ...
@@ -175,2 +190,3 @@
175 190
                   typename Digraph::Node &t,
191
                   typename CapacityMap::Value infty = 0,
176 192
                   DimacsDescriptor desc=DimacsDescriptor()) {
... ...
@@ -188,3 +204,9 @@
188 204
    }
205
    typedef typename CapacityMap::Value Capacity;
189 206

	
207
    if(infty==0)
208
      infty = std::numeric_limits<Capacity>::has_infinity ?
209
        std::numeric_limits<Capacity>::infinity() :
210
        std::numeric_limits<Capacity>::max();
211
 
190 212
    while (is >> c) {
... ...
@@ -207,5 +229,4 @@
207 229
        break;
208
      case 'a': // arc (arc) definition line
209
        if (desc.type==DimacsDescriptor::SP ||
210
            desc.type==DimacsDescriptor::MAX) {
230
      case 'a': // arc definition line
231
        if (desc.type==DimacsDescriptor::SP) {
211 232
          is >> i >> j >> _cap;
... ...
@@ -214,3 +235,13 @@
214 235
          capacity.set(e, _cap);
215
        } else {
236
        } 
237
        else if (desc.type==DimacsDescriptor::MAX) {
238
          is >> i >> j >> _cap;
239
          getline(is, str);
240
          e = g.addArc(nodes[i], nodes[j]);
241
          if (_cap >= 0)
242
            capacity.set(e, _cap);
243
          else
244
            capacity.set(e, infty);
245
        }
246
        else {
216 247
          is >> i >> j;
... ...
@@ -232,4 +263,11 @@
232 263
  /// At the beginning, \c g is cleared by \c g.clear(). The arc
233
  /// capacities are written to \c capacity and \c s and \c t are
234
  /// set to the source and the target nodes.
264
  /// capacities are written to the \c capacity arc map and \c s and
265
  /// \c t are set to the source and the target nodes.
266
  ///
267
  /// If the capacity of an arc is negative, it will
268
  /// be set to "infinite" instead. The actual value of "infinite" is
269
  /// contolled by the \c infty parameter. If it is 0 (the default value),
270
  /// \c std::numeric_limits<Capacity>::infinity() will be used if available,
271
  /// \c std::numeric_limits<Capacity>::max() otherwise. If \c infty is set to
272
  /// a non-zero value, that value will be used as "infinite".
235 273
  ///
... ...
@@ -243,2 +281,3 @@
243 281
                     typename Digraph::Node &t,
282
                     typename CapacityMap::Value infty = 0,
244 283
                     DimacsDescriptor desc=DimacsDescriptor()) {
... ...
@@ -247,3 +286,3 @@
247 286
      throw FormatError("Problem type mismatch");
248
    _readDimacs(is,g,capacity,s,t,desc);
287
    _readDimacs(is,g,capacity,s,t,infty,desc);
249 288
  }
... ...
@@ -258,3 +297,3 @@
258 297
  /// At the beginning, \c g is cleared by \c g.clear(). The arc
259
  /// lengths are written to \c length and \c s is set to the
298
  /// lengths are written to the \c length arc map and \c s is set to the
260 299
  /// source node.
... ...
@@ -273,3 +312,3 @@
273 312
      throw FormatError("Problem type mismatch");
274
    _readDimacs(is, g, length, s, t,desc);
313
    _readDimacs(is, g, length, s, t, 0, desc);
275 314
  }
... ...
@@ -279,5 +318,14 @@
279 318
  /// This function reads an arc capacitated digraph instance from
280
  /// DIMACS 'mat' or 'sp' format.
319
  /// DIMACS 'max' or 'sp' format.
281 320
  /// At the beginning, \c g is cleared by \c g.clear()
282
  /// and the arc capacities/lengths are written to \c capacity.
321
  /// and the arc capacities/lengths are written to the \c capacity
322
  /// arc map.
323
  ///
324
  /// In case of the 'max' format, if the capacity of an arc is negative,
325
  /// it will
326
  /// be set to "infinite" instead. The actual value of "infinite" is
327
  /// contolled by the \c infty parameter. If it is 0 (the default value),
328
  /// \c std::numeric_limits<Capacity>::infinity() will be used if available,
329
  /// \c std::numeric_limits<Capacity>::max() otherwise. If \c infty is set to
330
  /// a non-zero value, that value will be used as "infinite".
283 331
  ///
... ...
@@ -289,2 +337,3 @@
289 337
                     CapacityMap& capacity,
338
                     typename CapacityMap::Value infty = 0,
290 339
                     DimacsDescriptor desc=DimacsDescriptor()) {
... ...
@@ -294,3 +343,3 @@
294 343
      throw FormatError("Problem type mismatch");
295
    _readDimacs(is, g, capacity, u, v, desc);
344
    _readDimacs(is, g, capacity, u, v, infty, desc);
296 345
  }
... ...
@@ -349,3 +398,3 @@
349 398
        break;
350
      case 'a': // arc (arc) definition line
399
      case 'a': // arc definition line
351 400
        is >> i >> j;
Show white space 6 line context
... ...
@@ -74,3 +74,3 @@
74 74
void solve_max(ArgParser &ap, std::istream &is, std::ostream &,
75
              DimacsDescriptor &desc)
75
               Value infty, DimacsDescriptor &desc)
76 76
{
... ...
@@ -82,3 +82,3 @@
82 82
  ti.restart();
83
  readDimacsMax(is, g, cap, s, t, desc);
83
  readDimacsMax(is, g, cap, s, t, infty, desc);
84 84
  if(report) std::cerr << "Read the file: " << ti << '\n';
... ...
@@ -117,2 +117,13 @@
117 117
{
118
  std::stringstream iss(ap["infcap"]);
119
  Value infty;
120
  iss >> infty;
121
  if(iss.fail())
122
    {
123
      std::cerr << "Cannot interpret '"
124
                << static_cast<std::string>(ap["infcap"]) << "' as infinite"
125
                << std::endl;
126
      exit(1);
127
    }
128
  
118 129
  switch(desc.type)
... ...
@@ -124,3 +135,3 @@
124 135
    case DimacsDescriptor::MAX:
125
      solve_max<Value>(ap,is,os,desc);
136
      solve_max<Value>(ap,is,os,infty,desc);
126 137
      break;
... ...
@@ -161,2 +172,3 @@
161 172
    .onlyOneGroup("datatype")
173
    .stringOption("infcap","Value used for 'very high' capacities","0")
162 174
    .run();
Ignore white space 6 line context
... ...
@@ -98,3 +98,3 @@
98 98
        DoubleNodeMap supply(digraph);
99
        readDimacsMin(is, digraph, lower, capacity, cost, supply, desc);
99
        readDimacsMin(is, digraph, lower, capacity, cost, supply, 0, desc);
100 100
        DigraphWriter<Digraph>(digraph, os).
... ...
@@ -113,3 +113,3 @@
113 113
        DoubleArcMap capacity(digraph);
114
        readDimacsMax(is, digraph, capacity, s, t, desc);
114
        readDimacsMax(is, digraph, capacity, s, t, 0, desc);
115 115
        DigraphWriter<Digraph>(digraph, os).
0 comments (0 inline)