Changeset 402:24a2c6ee6cb0 in lemon
 Timestamp:
 11/28/08 07:38:20 (11 years ago)
 Branch:
 default
 Phase:
 public
 Files:

 2 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 
tools/dimacstolgf.cc
r401 r402 40 40 41 41 #include <lemon/arg_parser.h> 42 #include <lemon/error.h> 42 43 43 44 using namespace std; … … 57 58 std::string inputName; 58 59 std::string outputName; 59 std::string typeName;60 61 bool mincostflow;62 bool maxflow;63 bool shortestpath;64 bool capacitated;65 bool plain;66 67 bool version;68 60 69 61 ArgParser ap(argc, argv); 70 ap.refOption("input", 71 "use FILE as input instead of standard input", 72 inputName).synonym("i", "input") 73 .refOption("output", 74 "use FILE as output instead of standard output", 75 outputName).synonym("o", "output") 76 .refOption("mincostflow", 77 "set the type of the digraph to \"mincostflow\" digraph", 78 mincostflow) 79 .optionGroup("type", "mincostflow").synonym("mcf", "mincostflow") 80 .refOption("maxflow", 81 "set the type of the digraph to \"maxflow\" digraph", 82 maxflow) 83 .optionGroup("type", "maxflow").synonym("mf", "maxflow") 84 .refOption("shortestpath", 85 "set the type of the digraph to \"shortestpath\" digraph", 86 shortestpath) 87 .optionGroup("type", "shortestpath").synonym("sp", "shortestpath") 88 .refOption("capacitated", 89 "set the type of the digraph to \"capacitated\" digraph", 90 capacitated) 91 .optionGroup("type", "capacitated").synonym("cap", "capacitated") 92 .refOption("plain", 93 "set the type of the digraph to \"plain\" digraph", 94 plain) 95 .optionGroup("type", "plain").synonym("pl", "plain") 96 .onlyOneGroup("type") 97 .mandatoryGroup("type") 98 .refOption("version", "show version information", version) 99 .synonym("v", "version") 62 ap.other("[INFILE [OUTFILE]]", 63 "If either the INFILE or OUTFILE file is missing the standard\n" 64 " input/output will be used instead.") 100 65 .run(); 101 66 102 67 ifstream input; 103 if (!inputName.empty()) { 104 input.open(inputName.c_str()); 105 if (!input) { 106 cerr << "File open error" << endl; 107 return 1; 68 ofstream output; 69 70 switch(ap.files().size()) 71 { 72 case 2: 73 output.open(ap.files()[1].c_str()); 74 if (!output) { 75 throw IoError("Cannot open the file for writing", ap.files()[1]); 76 } 77 case 1: 78 input.open(ap.files()[0].c_str()); 79 if (!input) { 80 throw IoError("File cannot be found", ap.files()[0]); 81 } 82 case 0: 83 break; 84 default: 85 cerr << ap.commandName() << ": too many arguments\n"; 86 return 1; 87 } 88 istream& is = (ap.files().size()<1 ? cin : input); 89 ostream& os = (ap.files().size()<2 ? cout : output); 90 91 DimacsDescriptor desc = dimacsType(is); 92 switch(desc.type) 93 { 94 case DimacsDescriptor::MIN: 95 { 96 Digraph digraph; 97 DoubleArcMap lower(digraph), capacity(digraph), cost(digraph); 98 DoubleNodeMap supply(digraph); 99 readDimacsMin(is, digraph, lower, capacity, cost, supply, desc); 100 DigraphWriter<Digraph>(digraph, os). 101 nodeMap("supply", supply). 102 arcMap("lower", lower). 103 arcMap("capacity", capacity). 104 arcMap("cost", cost). 105 attribute("problem","min"). 106 run(); 107 } 108 break; 109 case DimacsDescriptor::MAX: 110 { 111 Digraph digraph; 112 Node s, t; 113 DoubleArcMap capacity(digraph); 114 readDimacsMax(is, digraph, capacity, s, t, desc); 115 DigraphWriter<Digraph>(digraph, os). 116 arcMap("capacity", capacity). 117 node("source", s). 118 node("target", t). 119 attribute("problem","max"). 120 run(); 121 } 122 break; 123 case DimacsDescriptor::SP: 124 { 125 Digraph digraph; 126 Node s; 127 DoubleArcMap capacity(digraph); 128 readDimacsSp(is, digraph, capacity, s, desc); 129 DigraphWriter<Digraph>(digraph, os). 130 arcMap("capacity", capacity). 131 node("source", s). 132 attribute("problem","sp"). 133 run(); 134 } 135 break; 136 case DimacsDescriptor::MAT: 137 { 138 Digraph digraph; 139 readDimacsMat(is, digraph,desc); 140 DigraphWriter<Digraph>(digraph, os). 141 attribute("problem","mat"). 142 run(); 143 } 144 break; 145 default: 146 break; 108 147 } 109 }110 istream& is = (inputName.empty() ? cin : input);111 112 ofstream output;113 if (!outputName.empty()) {114 output.open(outputName.c_str());115 if (!output) {116 cerr << "File open error" << endl;117 return 1;118 }119 }120 ostream& os = (outputName.empty() ? cout : output);121 122 if (mincostflow) {123 Digraph digraph;124 DoubleArcMap lower(digraph), capacity(digraph), cost(digraph);125 DoubleNodeMap supply(digraph);126 readDimacsMin(is, digraph, lower, capacity, cost, supply);127 DigraphWriter<Digraph>(digraph, os).128 nodeMap("supply", supply).129 arcMap("lower", lower).130 arcMap("capacity", capacity).131 arcMap("cost", cost).132 run();133 } else if (maxflow) {134 Digraph digraph;135 Node s, t;136 DoubleArcMap capacity(digraph);137 readDimacsMax(is, digraph, capacity, s, t);138 DigraphWriter<Digraph>(digraph, os).139 arcMap("capacity", capacity).140 node("source", s).141 node("target", t).142 run();143 } else if (shortestpath) {144 Digraph digraph;145 Node s;146 DoubleArcMap capacity(digraph);147 readDimacsSp(is, digraph, capacity, s);148 DigraphWriter<Digraph>(digraph, os).149 arcMap("capacity", capacity).150 node("source", s).151 run();152 } else if (capacitated) {153 Digraph digraph;154 DoubleArcMap capacity(digraph);155 readDimacsMax(is, digraph, capacity);156 DigraphWriter<Digraph>(digraph, os).157 arcMap("capacity", capacity).158 run();159 } else if (plain) {160 Digraph digraph;161 readDimacsMat(is, digraph);162 DigraphWriter<Digraph>(digraph, os).run();163 } else {164 cerr << "Invalid type error" << endl;165 return 1;166 }167 148 return 0; 168 149 }
Note: See TracChangeset
for help on using the changeset viewer.