... |
... |
@@ -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;
|