Changeset 608:6e0525ec5355 in lemon
 Timestamp:
 03/30/09 17:46:37 (14 years ago)
 Branch:
 default
 Children:
 609:538b3dd9a2c0, 1372:f37f0845cf32
 Phase:
 public
 Files:

 3 edited
Legend:
 Unmodified
 Added
 Removed

lemon/dimacs.h
r572 r608 23 23 #include <string> 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 29 29 /// \file … … 56 56 ///Discover the type of a DIMACS file 57 57 58 ///It starts seeking the begin ing of the file for the problem type58 ///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 60 60 ///that can be evaluated and passed to the appropriate reader … … 106 106 /// \endcode 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 nonzero value, that value will be used as "infinite". 111 119 /// 112 120 /// If the file type was previously evaluated by dimacsType(), then … … 121 129 CostMap& cost, 122 130 SupplyMap& supply, 131 typename CapacityMap::Value infty = 0, 123 132 DimacsDescriptor desc=DimacsDescriptor()) 124 133 { … … 143 152 typename CapacityMap::Value cap; 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) { 146 161 switch (c) { … … 153 168 supply.set(nodes[i], sup); 154 169 break; 155 case 'a': // arc (arc)definition line170 case 'a': // arc definition line 156 171 is >> i >> j >> low >> cap >> co; 157 172 getline(is, str); 158 173 e = g.addArc(nodes[i], nodes[j]); 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); 165 180 break; … … 174 189 typename Digraph::Node &s, 175 190 typename Digraph::Node &t, 191 typename CapacityMap::Value infty = 0, 176 192 DimacsDescriptor desc=DimacsDescriptor()) { 177 193 g.clear(); … … 187 203 nodes[k] = g.addNode(); 188 204 } 189 205 typedef typename CapacityMap::Value Capacity; 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) { 191 213 switch (c) { … … 206 228 } 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; 212 233 getline(is, str); 213 234 e = g.addArc(nodes[i], nodes[j]); 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; 217 248 getline(is, str); … … 231 262 /// \endcode 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 nonzero value, that value will be used as "infinite". 235 273 /// 236 274 /// If the file type was previously evaluated by dimacsType(), then … … 242 280 typename Digraph::Node &s, 243 281 typename Digraph::Node &t, 282 typename CapacityMap::Value infty = 0, 244 283 DimacsDescriptor desc=DimacsDescriptor()) { 245 284 if(desc.type==DimacsDescriptor::NONE) desc=dimacsType(is); 246 285 if(desc.type!=DimacsDescriptor::MAX) 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 } 250 289 … … 257 296 /// \endcode 258 297 /// At the beginning, \c g is cleared by \c g.clear(). The arc 259 /// lengths are written to \c lengthand \c s is set to the298 /// lengths are written to the \c length arc map and \c s is set to the 260 299 /// source node. 261 300 /// … … 272 311 if(desc.type!=DimacsDescriptor::SP) 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 } 276 315 … … 278 317 /// 279 318 /// This function reads an arc capacitated digraph instance from 280 /// DIMACS 'ma t' 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 nonzero value, that value will be used as "infinite". 283 331 /// 284 332 /// If the file type was previously evaluated by dimacsType(), then … … 288 336 Digraph &g, 289 337 CapacityMap& capacity, 338 typename CapacityMap::Value infty = 0, 290 339 DimacsDescriptor desc=DimacsDescriptor()) { 291 340 typename Digraph::Node u,v; … … 293 342 if(desc.type!=DimacsDescriptor::MAX  desc.type!=DimacsDescriptor::SP) 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 } 297 346 … … 348 397 case 'n': // node definition line 349 398 break; 350 case 'a': // arc (arc)definition line399 case 'a': // arc definition line 351 400 is >> i >> j; 352 401 getline(is, str); 
tools/dimacssolver.cc
r579 r608 73 73 template<class Value> 74 74 void solve_max(ArgParser &ap, std::istream &is, std::ostream &, 75 DimacsDescriptor &desc)75 Value infty, DimacsDescriptor &desc) 76 76 { 77 77 bool report = !ap.given("q"); … … 81 81 Timer ti; 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'; 85 85 ti.restart(); … … 116 116 DimacsDescriptor &desc) 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) 119 130 { … … 123 134 break; 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; 127 138 case DimacsDescriptor::SP: … … 160 171 .optionGroup("datatype","ldouble") 161 172 .onlyOneGroup("datatype") 173 .stringOption("infcap","Value used for 'very high' capacities","0") 162 174 .run(); 163 175 
tools/dimacstolgf.cc
r463 r608 97 97 DoubleArcMap lower(digraph), capacity(digraph), cost(digraph); 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). 101 101 nodeMap("supply", supply). … … 112 112 Node s, t; 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). 116 116 arcMap("capacity", capacity).
Note: See TracChangeset
for help on using the changeset viewer.