Changeset 402:24a2c6ee6cb0 in lemon for lemon/dimacs.h
 Timestamp:
 11/28/08 07:38:20 (14 years ago)
 Branch:
 default
 Phase:
 public
 File:

 1 edited
Legend:
 Unmodified
 Added
 Removed

lemon/dimacs.h
r401 r402 24 24 #include <vector> 25 25 #include <lemon/maps.h> 26 #include <lemon/error.h> 26 27 27 28 /// \ingroup dimacs_group … … 41 42 /// @{ 42 43 44 45 /// DIMACS file type descriptor. 46 struct DimacsDescriptor 47 { 48 ///File type enum 49 enum Type 50 { 51 NONE, MIN, MAX, SP, MAT 52 }; 53 ///The file type 54 Type type; 55 ///The number of nodes on the graph 56 int nodeNum; 57 ///The number of edges on the graph 58 int edgeNum; 59 int lineShift; 60 /// Constructor. Sets the type to NONE. 61 DimacsDescriptor() : type(NONE) {} 62 }; 63 64 ///Discover the type of a DIMACS file 65 66 ///It starts seeking the begining of the file for the problem type 67 ///and size info. The found date is returned in a special struct 68 ///that can be evaluated and passed to the appropriate reader 69 ///function. 70 DimacsDescriptor dimacsType(std::istream& is) 71 { 72 DimacsDescriptor r; 73 std::string problem,str; 74 char c; 75 r.lineShift=0; 76 while (is >> c) 77 switch(c) 78 { 79 case 'p': 80 if(is >> problem >> r.nodeNum >> r.edgeNum) 81 { 82 getline(is, str); 83 r.lineShift++; 84 if(problem=="min") r.type=DimacsDescriptor::MIN; 85 else if(problem=="max") r.type=DimacsDescriptor::MAX; 86 else if(problem=="sp") r.type=DimacsDescriptor::SP; 87 else if(problem=="mat") r.type=DimacsDescriptor::MAT; 88 else throw FormatError("Unknown problem type"); 89 return r; 90 } 91 else 92 { 93 throw FormatError("Missing or wrong problem type declaration."); 94 } 95 break; 96 case 'c': 97 getline(is, str); 98 r.lineShift++; 99 break; 100 default: 101 throw FormatError("Unknown DIMACS declaration."); 102 } 103 throw FormatError("Missing problem type declaration."); 104 } 105 106 107 43 108 /// DIMACS min cost flow reader function. 44 109 /// … … 48 113 /// p min 49 114 /// \endcode 50 /// At the beginning \c g is cleared by \c g.clear(). The supply115 /// At the beginning, \c g is cleared by \c g.clear(). The supply 51 116 /// amount of the nodes are written to \c supply (signed). The 52 117 /// lower bounds, capacities and costs of the arcs are written to 53 118 /// \c lower, \c capacity and \c cost. 119 /// 120 /// If the file type was previously evaluated by dimacsType(), then 121 /// the descriptor struct should be given by the \c dest parameter. 54 122 template <typename Digraph, typename LowerMap, 55 typename CapacityMap, typename CostMap, 56 typename SupplyMap> 57 void readDimacsMin( std::istream& is, 58 Digraph &g, 59 LowerMap& lower, 60 CapacityMap& capacity, 61 CostMap& cost, 62 SupplyMap& supply ) 123 typename CapacityMap, typename CostMap, 124 typename SupplyMap> 125 void readDimacsMin(std::istream& is, 126 Digraph &g, 127 LowerMap& lower, 128 CapacityMap& capacity, 129 CostMap& cost, 130 SupplyMap& supply, 131 DimacsDescriptor desc=DimacsDescriptor()) 63 132 { 64 133 g.clear(); … … 67 136 std::string problem, str; 68 137 char c; 69 int n, m;70 138 int i, j; 139 if(desc.type==DimacsDescriptor::NONE) desc=dimacsType(is); 140 if(desc.type!=DimacsDescriptor::MIN) 141 throw FormatError("Problem type mismatch"); 142 143 nodes.resize(desc.nodeNum + 1); 144 for (int k = 1; k <= desc.nodeNum; ++k) { 145 nodes[k] = g.addNode(); 146 supply.set(nodes[k], 0); 147 } 148 71 149 typename SupplyMap::Value sup; 72 150 typename CapacityMap::Value low; … … 77 155 case 'c': // comment line 78 156 getline(is, str); 79 break;80 case 'p': // problem definition line81 is >> problem >> n >> m;82 getline(is, str);83 if (problem != "min") return;84 nodes.resize(n + 1);85 for (int k = 1; k <= n; ++k) {86 nodes[k] = g.addNode();87 supply.set(nodes[k], 0);88 }89 157 break; 90 158 case 'n': // node definition line … … 108 176 } 109 177 110 /// DIMACS max flow reader function.111 ///112 /// This function reads a max flow instance from DIMACS format,113 /// i.e. from DIMACS files having a line starting with114 /// \code115 /// p max116 /// \endcode117 /// At the beginning \c g is cleared by \c g.clear(). The arc118 /// capacities are written to \c capacity and \c s and \c t are119 /// set to the source and the target nodes.120 178 template<typename Digraph, typename CapacityMap> 121 void readDimacsMax(std::istream& is, Digraph &g, CapacityMap& capacity, 122 typename Digraph::Node &s, typename Digraph::Node &t) { 179 void _readDimacs(std::istream& is, 180 Digraph &g, 181 CapacityMap& capacity, 182 typename Digraph::Node &s, 183 typename Digraph::Node &t, 184 DimacsDescriptor desc=DimacsDescriptor()) { 123 185 g.clear(); 186 s=t=INVALID; 124 187 std::vector<typename Digraph::Node> nodes; 125 188 typename Digraph::Arc e; 126 std::string problem;127 189 char c, d; 128 int n, m;129 190 int i, j; 130 191 typename CapacityMap::Value _cap; 131 192 std::string str; 193 nodes.resize(desc.nodeNum + 1); 194 for (int k = 1; k <= desc.nodeNum; ++k) { 195 nodes[k] = g.addNode(); 196 } 197 132 198 while (is >> c) { 133 199 switch (c) { … … 135 201 getline(is, str); 136 202 break; 137 case 'p': // problem definition line138 is >> problem >> n >> m;139 getline(is, str);140 nodes.resize(n + 1);141 for (int k = 1; k <= n; ++k)142 nodes[k] = g.addNode();143 break;144 203 case 'n': // node definition line 145 if ( problem == "sp") { // shortest path problem204 if (desc.type==DimacsDescriptor::SP) { // shortest path problem 146 205 is >> i; 147 206 getline(is, str); 148 207 s = nodes[i]; 149 208 } 150 if ( problem == "max") { // max flow problem209 if (desc.type==DimacsDescriptor::MAX) { // max flow problem 151 210 is >> i >> d; 152 211 getline(is, str); … … 156 215 break; 157 216 case 'a': // arc (arc) definition line 158 if (problem == "max"  problem == "sp") { 217 if (desc.type==DimacsDescriptor::SP  218 desc.type==DimacsDescriptor::MAX) { 159 219 is >> i >> j >> _cap; 160 220 getline(is, str); … … 171 231 } 172 232 233 /// DIMACS max flow reader function. 234 /// 235 /// This function reads a max flow instance from DIMACS format, 236 /// i.e. from DIMACS files having a line starting with 237 /// \code 238 /// p max 239 /// \endcode 240 /// At the beginning, \c g is cleared by \c g.clear(). The arc 241 /// capacities are written to \c capacity and \c s and \c t are 242 /// set to the source and the target nodes. 243 /// 244 /// If the file type was previously evaluated by dimacsType(), then 245 /// the descriptor struct should be given by the \c dest parameter. 246 template<typename Digraph, typename CapacityMap> 247 void readDimacsMax(std::istream& is, 248 Digraph &g, 249 CapacityMap& capacity, 250 typename Digraph::Node &s, 251 typename Digraph::Node &t, 252 DimacsDescriptor desc=DimacsDescriptor()) { 253 if(desc.type==DimacsDescriptor::NONE) desc=dimacsType(is); 254 if(desc.type!=DimacsDescriptor::MAX) 255 throw FormatError("Problem type mismatch"); 256 _readDimacs(is,g,capacity,s,t,desc); 257 } 258 173 259 /// DIMACS shortest path reader function. 174 260 /// … … 178 264 /// p sp 179 265 /// \endcode 180 /// At the beginning \c g is cleared by \c g.clear(). The arc181 /// capacities are written to \c capacityand \c s is set to the266 /// At the beginning, \c g is cleared by \c g.clear(). The arc 267 /// lengths are written to \c lenght and \c s is set to the 182 268 /// source node. 269 /// 270 /// If the file type was previously evaluated by dimacsType(), then 271 /// the descriptor struct should be given by the \c dest parameter. 272 template<typename Digraph, typename LengthMap> 273 void readDimacsSp(std::istream& is, 274 Digraph &g, 275 LengthMap& length, 276 typename Digraph::Node &s, 277 DimacsDescriptor desc=DimacsDescriptor()) { 278 typename Digraph::Node t; 279 if(desc.type==DimacsDescriptor::NONE) desc=dimacsType(is); 280 if(desc.type!=DimacsDescriptor::SP) 281 throw FormatError("Problem type mismatch"); 282 _readDimacs(is, g, length, s, t,desc); 283 } 284 285 /// DIMACS capacitated digraph reader function. 286 /// 287 /// This function reads an arc capacitated digraph instance from 288 /// DIMACS 'mat' or 'sp' format. 289 /// At the beginning, \c g is cleared by \c g.clear() 290 /// and the arc capacities/lengths are written to \c capacity. 291 /// 292 /// If the file type was previously evaluated by dimacsType(), then 293 /// the descriptor struct should be given by the \c dest parameter. 183 294 template<typename Digraph, typename CapacityMap> 184 void readDimacsSp(std::istream& is, Digraph &g, CapacityMap& capacity, 185 typename Digraph::Node &s) { 186 typename Digraph::Node t; 187 readDimacsMax(is, g, capacity, s, t); 188 } 189 190 /// DIMACS capacitated digraph reader function. 191 /// 192 /// This function reads an arc capacitated digraph instance from 193 /// DIMACS format. At the beginning \c g is cleared by \c g.clear() 194 /// and the arc capacities are written to \c capacity. 195 template<typename Digraph, typename CapacityMap> 196 void readDimacsMax(std::istream& is, Digraph &g, CapacityMap& capacity) { 295 void readDimacsCap(std::istream& is, 296 Digraph &g, 297 CapacityMap& capacity, 298 DimacsDescriptor desc=DimacsDescriptor()) { 197 299 typename Digraph::Node u,v; 198 readDimacsMax(is, g, capacity, u, v); 300 if(desc.type==DimacsDescriptor::NONE) desc=dimacsType(is); 301 if(desc.type!=DimacsDescriptor::MAX  desc.type!=DimacsDescriptor::SP) 302 throw FormatError("Problem type mismatch"); 303 _readDimacs(is, g, capacity, u, v, desc); 199 304 } 200 305 … … 207 312 /// p mat 208 313 /// \endcode 209 /// At the beginning \c g is cleared by \c g.clear(). 314 /// At the beginning, \c g is cleared by \c g.clear(). 315 /// 316 /// If the file type was previously evaluated by dimacsType(), then 317 /// the descriptor struct should be given by the \c dest parameter. 210 318 template<typename Digraph> 211 void readDimacsMat(std::istream& is, Digraph &g) { 319 void readDimacsMat(std::istream& is, Digraph &g, 320 DimacsDescriptor desc=DimacsDescriptor()) { 212 321 typename Digraph::Node u,v; 213 322 NullMap<typename Digraph::Arc, int> n; 214 readDimacsMax(is, g, n, u, v); 323 if(desc.type==DimacsDescriptor::NONE) desc=dimacsType(is); 324 if(desc.type!=DimacsDescriptor::MAT) 325 throw FormatError("Problem type mismatch"); 326 _readDimacs(is, g, n, u, v, desc); 215 327 } 216 328 … … 223 335 /// p mat 224 336 /// \endcode 337 /// If \c comment is not empty, then it will be printed in the first line 338 /// prefixed by 'c'. 225 339 template<typename Digraph> 226 void writeDimacsMat(std::ostream& os, const Digraph &g) { 340 void writeDimacsMat(std::ostream& os, const Digraph &g, 341 std::string comment="") { 227 342 typedef typename Digraph::NodeIt NodeIt; 228 343 typedef typename Digraph::ArcIt ArcIt; 229 344 230 os << "c matching problem" << std::endl; 345 if(!comment.empty()) 346 os << "c " << comment << std::endl; 231 347 os << "p mat " << g.nodeNum() << " " << g.arcNum() << std::endl; 232 348
Note: See TracChangeset
for help on using the changeset viewer.