1.1 --- a/lemon/dimacs.h Thu Nov 27 22:05:35 2008 +0000
1.2 +++ b/lemon/dimacs.h Fri Nov 28 06:38:20 2008 +0000
1.3 @@ -23,6 +23,7 @@
1.4 #include <string>
1.5 #include <vector>
1.6 #include <lemon/maps.h>
1.7 +#include <lemon/error.h>
1.8
1.9 /// \ingroup dimacs_group
1.10 /// \file
1.11 @@ -40,6 +41,70 @@
1.12 /// \addtogroup dimacs_group
1.13 /// @{
1.14
1.15 +
1.16 + /// DIMACS file type descriptor.
1.17 + struct DimacsDescriptor
1.18 + {
1.19 + ///File type enum
1.20 + enum Type
1.21 + {
1.22 + NONE, MIN, MAX, SP, MAT
1.23 + };
1.24 + ///The file type
1.25 + Type type;
1.26 + ///The number of nodes on the graph
1.27 + int nodeNum;
1.28 + ///The number of edges on the graph
1.29 + int edgeNum;
1.30 + int lineShift;
1.31 + /// Constructor. Sets the type to NONE.
1.32 + DimacsDescriptor() : type(NONE) {}
1.33 + };
1.34 +
1.35 + ///Discover the type of a DIMACS file
1.36 +
1.37 + ///It starts seeking the begining of the file for the problem type
1.38 + ///and size info. The found date is returned in a special struct
1.39 + ///that can be evaluated and passed to the appropriate reader
1.40 + ///function.
1.41 + DimacsDescriptor dimacsType(std::istream& is)
1.42 + {
1.43 + DimacsDescriptor r;
1.44 + std::string problem,str;
1.45 + char c;
1.46 + r.lineShift=0;
1.47 + while (is >> c)
1.48 + switch(c)
1.49 + {
1.50 + case 'p':
1.51 + if(is >> problem >> r.nodeNum >> r.edgeNum)
1.52 + {
1.53 + getline(is, str);
1.54 + r.lineShift++;
1.55 + if(problem=="min") r.type=DimacsDescriptor::MIN;
1.56 + else if(problem=="max") r.type=DimacsDescriptor::MAX;
1.57 + else if(problem=="sp") r.type=DimacsDescriptor::SP;
1.58 + else if(problem=="mat") r.type=DimacsDescriptor::MAT;
1.59 + else throw FormatError("Unknown problem type");
1.60 + return r;
1.61 + }
1.62 + else
1.63 + {
1.64 + throw FormatError("Missing or wrong problem type declaration.");
1.65 + }
1.66 + break;
1.67 + case 'c':
1.68 + getline(is, str);
1.69 + r.lineShift++;
1.70 + break;
1.71 + default:
1.72 + throw FormatError("Unknown DIMACS declaration.");
1.73 + }
1.74 + throw FormatError("Missing problem type declaration.");
1.75 + }
1.76 +
1.77 +
1.78 +
1.79 /// DIMACS min cost flow reader function.
1.80 ///
1.81 /// This function reads a min cost flow instance from DIMACS format,
1.82 @@ -47,27 +112,40 @@
1.83 /// \code
1.84 /// p min
1.85 /// \endcode
1.86 - /// At the beginning \c g is cleared by \c g.clear(). The supply
1.87 + /// At the beginning, \c g is cleared by \c g.clear(). The supply
1.88 /// amount of the nodes are written to \c supply (signed). The
1.89 /// lower bounds, capacities and costs of the arcs are written to
1.90 /// \c lower, \c capacity and \c cost.
1.91 + ///
1.92 + /// If the file type was previously evaluated by dimacsType(), then
1.93 + /// the descriptor struct should be given by the \c dest parameter.
1.94 template <typename Digraph, typename LowerMap,
1.95 - typename CapacityMap, typename CostMap,
1.96 - typename SupplyMap>
1.97 - void readDimacsMin( std::istream& is,
1.98 - Digraph &g,
1.99 - LowerMap& lower,
1.100 - CapacityMap& capacity,
1.101 - CostMap& cost,
1.102 - SupplyMap& supply )
1.103 + typename CapacityMap, typename CostMap,
1.104 + typename SupplyMap>
1.105 + void readDimacsMin(std::istream& is,
1.106 + Digraph &g,
1.107 + LowerMap& lower,
1.108 + CapacityMap& capacity,
1.109 + CostMap& cost,
1.110 + SupplyMap& supply,
1.111 + DimacsDescriptor desc=DimacsDescriptor())
1.112 {
1.113 g.clear();
1.114 std::vector<typename Digraph::Node> nodes;
1.115 typename Digraph::Arc e;
1.116 std::string problem, str;
1.117 char c;
1.118 - int n, m;
1.119 int i, j;
1.120 + if(desc.type==DimacsDescriptor::NONE) desc=dimacsType(is);
1.121 + if(desc.type!=DimacsDescriptor::MIN)
1.122 + throw FormatError("Problem type mismatch");
1.123 +
1.124 + nodes.resize(desc.nodeNum + 1);
1.125 + for (int k = 1; k <= desc.nodeNum; ++k) {
1.126 + nodes[k] = g.addNode();
1.127 + supply.set(nodes[k], 0);
1.128 + }
1.129 +
1.130 typename SupplyMap::Value sup;
1.131 typename CapacityMap::Value low;
1.132 typename CapacityMap::Value cap;
1.133 @@ -77,16 +155,6 @@
1.134 case 'c': // comment line
1.135 getline(is, str);
1.136 break;
1.137 - case 'p': // problem definition line
1.138 - is >> problem >> n >> m;
1.139 - getline(is, str);
1.140 - if (problem != "min") return;
1.141 - nodes.resize(n + 1);
1.142 - for (int k = 1; k <= n; ++k) {
1.143 - nodes[k] = g.addNode();
1.144 - supply.set(nodes[k], 0);
1.145 - }
1.146 - break;
1.147 case 'n': // node definition line
1.148 is >> i >> sup;
1.149 getline(is, str);
1.150 @@ -107,47 +175,38 @@
1.151 }
1.152 }
1.153
1.154 - /// DIMACS max flow reader function.
1.155 - ///
1.156 - /// This function reads a max flow instance from DIMACS format,
1.157 - /// i.e. from DIMACS files having a line starting with
1.158 - /// \code
1.159 - /// p max
1.160 - /// \endcode
1.161 - /// At the beginning \c g is cleared by \c g.clear(). The arc
1.162 - /// capacities are written to \c capacity and \c s and \c t are
1.163 - /// set to the source and the target nodes.
1.164 template<typename Digraph, typename CapacityMap>
1.165 - void readDimacsMax(std::istream& is, Digraph &g, CapacityMap& capacity,
1.166 - typename Digraph::Node &s, typename Digraph::Node &t) {
1.167 + void _readDimacs(std::istream& is,
1.168 + Digraph &g,
1.169 + CapacityMap& capacity,
1.170 + typename Digraph::Node &s,
1.171 + typename Digraph::Node &t,
1.172 + DimacsDescriptor desc=DimacsDescriptor()) {
1.173 g.clear();
1.174 + s=t=INVALID;
1.175 std::vector<typename Digraph::Node> nodes;
1.176 typename Digraph::Arc e;
1.177 - std::string problem;
1.178 char c, d;
1.179 - int n, m;
1.180 int i, j;
1.181 typename CapacityMap::Value _cap;
1.182 std::string str;
1.183 + nodes.resize(desc.nodeNum + 1);
1.184 + for (int k = 1; k <= desc.nodeNum; ++k) {
1.185 + nodes[k] = g.addNode();
1.186 + }
1.187 +
1.188 while (is >> c) {
1.189 switch (c) {
1.190 case 'c': // comment line
1.191 getline(is, str);
1.192 break;
1.193 - case 'p': // problem definition line
1.194 - is >> problem >> n >> m;
1.195 - getline(is, str);
1.196 - nodes.resize(n + 1);
1.197 - for (int k = 1; k <= n; ++k)
1.198 - nodes[k] = g.addNode();
1.199 - break;
1.200 case 'n': // node definition line
1.201 - if (problem == "sp") { // shortest path problem
1.202 + if (desc.type==DimacsDescriptor::SP) { // shortest path problem
1.203 is >> i;
1.204 getline(is, str);
1.205 s = nodes[i];
1.206 }
1.207 - if (problem == "max") { // max flow problem
1.208 + if (desc.type==DimacsDescriptor::MAX) { // max flow problem
1.209 is >> i >> d;
1.210 getline(is, str);
1.211 if (d == 's') s = nodes[i];
1.212 @@ -155,7 +214,8 @@
1.213 }
1.214 break;
1.215 case 'a': // arc (arc) definition line
1.216 - if (problem == "max" || problem == "sp") {
1.217 + if (desc.type==DimacsDescriptor::SP ||
1.218 + desc.type==DimacsDescriptor::MAX) {
1.219 is >> i >> j >> _cap;
1.220 getline(is, str);
1.221 e = g.addArc(nodes[i], nodes[j]);
1.222 @@ -170,6 +230,32 @@
1.223 }
1.224 }
1.225
1.226 + /// DIMACS max flow reader function.
1.227 + ///
1.228 + /// This function reads a max flow instance from DIMACS format,
1.229 + /// i.e. from DIMACS files having a line starting with
1.230 + /// \code
1.231 + /// p max
1.232 + /// \endcode
1.233 + /// At the beginning, \c g is cleared by \c g.clear(). The arc
1.234 + /// capacities are written to \c capacity and \c s and \c t are
1.235 + /// set to the source and the target nodes.
1.236 + ///
1.237 + /// If the file type was previously evaluated by dimacsType(), then
1.238 + /// the descriptor struct should be given by the \c dest parameter.
1.239 + template<typename Digraph, typename CapacityMap>
1.240 + void readDimacsMax(std::istream& is,
1.241 + Digraph &g,
1.242 + CapacityMap& capacity,
1.243 + typename Digraph::Node &s,
1.244 + typename Digraph::Node &t,
1.245 + DimacsDescriptor desc=DimacsDescriptor()) {
1.246 + if(desc.type==DimacsDescriptor::NONE) desc=dimacsType(is);
1.247 + if(desc.type!=DimacsDescriptor::MAX)
1.248 + throw FormatError("Problem type mismatch");
1.249 + _readDimacs(is,g,capacity,s,t,desc);
1.250 + }
1.251 +
1.252 /// DIMACS shortest path reader function.
1.253 ///
1.254 /// This function reads a shortest path instance from DIMACS format,
1.255 @@ -177,25 +263,44 @@
1.256 /// \code
1.257 /// p sp
1.258 /// \endcode
1.259 - /// At the beginning \c g is cleared by \c g.clear(). The arc
1.260 - /// capacities are written to \c capacity and \c s is set to the
1.261 + /// At the beginning, \c g is cleared by \c g.clear(). The arc
1.262 + /// lengths are written to \c lenght and \c s is set to the
1.263 /// source node.
1.264 - template<typename Digraph, typename CapacityMap>
1.265 - void readDimacsSp(std::istream& is, Digraph &g, CapacityMap& capacity,
1.266 - typename Digraph::Node &s) {
1.267 + ///
1.268 + /// If the file type was previously evaluated by dimacsType(), then
1.269 + /// the descriptor struct should be given by the \c dest parameter.
1.270 + template<typename Digraph, typename LengthMap>
1.271 + void readDimacsSp(std::istream& is,
1.272 + Digraph &g,
1.273 + LengthMap& length,
1.274 + typename Digraph::Node &s,
1.275 + DimacsDescriptor desc=DimacsDescriptor()) {
1.276 typename Digraph::Node t;
1.277 - readDimacsMax(is, g, capacity, s, t);
1.278 + if(desc.type==DimacsDescriptor::NONE) desc=dimacsType(is);
1.279 + if(desc.type!=DimacsDescriptor::SP)
1.280 + throw FormatError("Problem type mismatch");
1.281 + _readDimacs(is, g, length, s, t,desc);
1.282 }
1.283
1.284 /// DIMACS capacitated digraph reader function.
1.285 ///
1.286 /// This function reads an arc capacitated digraph instance from
1.287 - /// DIMACS format. At the beginning \c g is cleared by \c g.clear()
1.288 - /// and the arc capacities are written to \c capacity.
1.289 + /// DIMACS 'mat' or 'sp' format.
1.290 + /// At the beginning, \c g is cleared by \c g.clear()
1.291 + /// and the arc capacities/lengths are written to \c capacity.
1.292 + ///
1.293 + /// If the file type was previously evaluated by dimacsType(), then
1.294 + /// the descriptor struct should be given by the \c dest parameter.
1.295 template<typename Digraph, typename CapacityMap>
1.296 - void readDimacsMax(std::istream& is, Digraph &g, CapacityMap& capacity) {
1.297 + void readDimacsCap(std::istream& is,
1.298 + Digraph &g,
1.299 + CapacityMap& capacity,
1.300 + DimacsDescriptor desc=DimacsDescriptor()) {
1.301 typename Digraph::Node u,v;
1.302 - readDimacsMax(is, g, capacity, u, v);
1.303 + if(desc.type==DimacsDescriptor::NONE) desc=dimacsType(is);
1.304 + if(desc.type!=DimacsDescriptor::MAX || desc.type!=DimacsDescriptor::SP)
1.305 + throw FormatError("Problem type mismatch");
1.306 + _readDimacs(is, g, capacity, u, v, desc);
1.307 }
1.308
1.309 /// DIMACS plain digraph reader function.
1.310 @@ -206,12 +311,19 @@
1.311 /// \code
1.312 /// p mat
1.313 /// \endcode
1.314 - /// At the beginning \c g is cleared by \c g.clear().
1.315 + /// At the beginning, \c g is cleared by \c g.clear().
1.316 + ///
1.317 + /// If the file type was previously evaluated by dimacsType(), then
1.318 + /// the descriptor struct should be given by the \c dest parameter.
1.319 template<typename Digraph>
1.320 - void readDimacsMat(std::istream& is, Digraph &g) {
1.321 + void readDimacsMat(std::istream& is, Digraph &g,
1.322 + DimacsDescriptor desc=DimacsDescriptor()) {
1.323 typename Digraph::Node u,v;
1.324 NullMap<typename Digraph::Arc, int> n;
1.325 - readDimacsMax(is, g, n, u, v);
1.326 + if(desc.type==DimacsDescriptor::NONE) desc=dimacsType(is);
1.327 + if(desc.type!=DimacsDescriptor::MAT)
1.328 + throw FormatError("Problem type mismatch");
1.329 + _readDimacs(is, g, n, u, v, desc);
1.330 }
1.331
1.332 /// DIMACS plain digraph writer function.
1.333 @@ -222,12 +334,16 @@
1.334 /// \code
1.335 /// p mat
1.336 /// \endcode
1.337 + /// If \c comment is not empty, then it will be printed in the first line
1.338 + /// prefixed by 'c'.
1.339 template<typename Digraph>
1.340 - void writeDimacsMat(std::ostream& os, const Digraph &g) {
1.341 + void writeDimacsMat(std::ostream& os, const Digraph &g,
1.342 + std::string comment="") {
1.343 typedef typename Digraph::NodeIt NodeIt;
1.344 typedef typename Digraph::ArcIt ArcIt;
1.345
1.346 - os << "c matching problem" << std::endl;
1.347 + if(!comment.empty())
1.348 + os << "c " << comment << std::endl;
1.349 os << "p mat " << g.nodeNum() << " " << g.arcNum() << std::endl;
1.350
1.351 typename Digraph::template NodeMap<int> nodes(g);
2.1 --- a/tools/dimacs-to-lgf.cc Thu Nov 27 22:05:35 2008 +0000
2.2 +++ b/tools/dimacs-to-lgf.cc Fri Nov 28 06:38:20 2008 +0000
2.3 @@ -39,6 +39,7 @@
2.4 #include <lemon/lgf_writer.h>
2.5
2.6 #include <lemon/arg_parser.h>
2.7 +#include <lemon/error.h>
2.8
2.9 using namespace std;
2.10 using namespace lemon;
2.11 @@ -56,113 +57,93 @@
2.12
2.13 std::string inputName;
2.14 std::string outputName;
2.15 - std::string typeName;
2.16 -
2.17 - bool mincostflow;
2.18 - bool maxflow;
2.19 - bool shortestpath;
2.20 - bool capacitated;
2.21 - bool plain;
2.22 -
2.23 - bool version;
2.24
2.25 ArgParser ap(argc, argv);
2.26 - ap.refOption("-input",
2.27 - "use FILE as input instead of standard input",
2.28 - inputName).synonym("i", "-input")
2.29 - .refOption("-output",
2.30 - "use FILE as output instead of standard output",
2.31 - outputName).synonym("o", "-output")
2.32 - .refOption("-mincostflow",
2.33 - "set the type of the digraph to \"mincostflow\" digraph",
2.34 - mincostflow)
2.35 - .optionGroup("type", "-mincostflow").synonym("mcf", "-mincostflow")
2.36 - .refOption("-maxflow",
2.37 - "set the type of the digraph to \"maxflow\" digraph",
2.38 - maxflow)
2.39 - .optionGroup("type", "-maxflow").synonym("mf", "-maxflow")
2.40 - .refOption("-shortestpath",
2.41 - "set the type of the digraph to \"shortestpath\" digraph",
2.42 - shortestpath)
2.43 - .optionGroup("type", "-shortestpath").synonym("sp", "-shortestpath")
2.44 - .refOption("-capacitated",
2.45 - "set the type of the digraph to \"capacitated\" digraph",
2.46 - capacitated)
2.47 - .optionGroup("type", "-capacitated").synonym("cap", "-capacitated")
2.48 - .refOption("-plain",
2.49 - "set the type of the digraph to \"plain\" digraph",
2.50 - plain)
2.51 - .optionGroup("type", "-plain").synonym("pl", "-plain")
2.52 - .onlyOneGroup("type")
2.53 - .mandatoryGroup("type")
2.54 - .refOption("-version", "show version information", version)
2.55 - .synonym("v", "-version")
2.56 + ap.other("[INFILE [OUTFILE]]",
2.57 + "If either the INFILE or OUTFILE file is missing the standard\n"
2.58 + " input/output will be used instead.")
2.59 .run();
2.60
2.61 ifstream input;
2.62 - if (!inputName.empty()) {
2.63 - input.open(inputName.c_str());
2.64 - if (!input) {
2.65 - cerr << "File open error" << endl;
2.66 - return -1;
2.67 + ofstream output;
2.68 +
2.69 + switch(ap.files().size())
2.70 + {
2.71 + case 2:
2.72 + output.open(ap.files()[1].c_str());
2.73 + if (!output) {
2.74 + throw IoError("Cannot open the file for writing", ap.files()[1]);
2.75 + }
2.76 + case 1:
2.77 + input.open(ap.files()[0].c_str());
2.78 + if (!input) {
2.79 + throw IoError("File cannot be found", ap.files()[0]);
2.80 + }
2.81 + case 0:
2.82 + break;
2.83 + default:
2.84 + cerr << ap.commandName() << ": too many arguments\n";
2.85 + return 1;
2.86 + }
2.87 + istream& is = (ap.files().size()<1 ? cin : input);
2.88 + ostream& os = (ap.files().size()<2 ? cout : output);
2.89 +
2.90 + DimacsDescriptor desc = dimacsType(is);
2.91 + switch(desc.type)
2.92 + {
2.93 + case DimacsDescriptor::MIN:
2.94 + {
2.95 + Digraph digraph;
2.96 + DoubleArcMap lower(digraph), capacity(digraph), cost(digraph);
2.97 + DoubleNodeMap supply(digraph);
2.98 + readDimacsMin(is, digraph, lower, capacity, cost, supply, desc);
2.99 + DigraphWriter<Digraph>(digraph, os).
2.100 + nodeMap("supply", supply).
2.101 + arcMap("lower", lower).
2.102 + arcMap("capacity", capacity).
2.103 + arcMap("cost", cost).
2.104 + attribute("problem","min").
2.105 + run();
2.106 + }
2.107 + break;
2.108 + case DimacsDescriptor::MAX:
2.109 + {
2.110 + Digraph digraph;
2.111 + Node s, t;
2.112 + DoubleArcMap capacity(digraph);
2.113 + readDimacsMax(is, digraph, capacity, s, t, desc);
2.114 + DigraphWriter<Digraph>(digraph, os).
2.115 + arcMap("capacity", capacity).
2.116 + node("source", s).
2.117 + node("target", t).
2.118 + attribute("problem","max").
2.119 + run();
2.120 + }
2.121 + break;
2.122 + case DimacsDescriptor::SP:
2.123 + {
2.124 + Digraph digraph;
2.125 + Node s;
2.126 + DoubleArcMap capacity(digraph);
2.127 + readDimacsSp(is, digraph, capacity, s, desc);
2.128 + DigraphWriter<Digraph>(digraph, os).
2.129 + arcMap("capacity", capacity).
2.130 + node("source", s).
2.131 + attribute("problem","sp").
2.132 + run();
2.133 + }
2.134 + break;
2.135 + case DimacsDescriptor::MAT:
2.136 + {
2.137 + Digraph digraph;
2.138 + readDimacsMat(is, digraph,desc);
2.139 + DigraphWriter<Digraph>(digraph, os).
2.140 + attribute("problem","mat").
2.141 + run();
2.142 + }
2.143 + break;
2.144 + default:
2.145 + break;
2.146 }
2.147 - }
2.148 - istream& is = (inputName.empty() ? cin : input);
2.149 -
2.150 - ofstream output;
2.151 - if (!outputName.empty()) {
2.152 - output.open(outputName.c_str());
2.153 - if (!output) {
2.154 - cerr << "File open error" << endl;
2.155 - return -1;
2.156 - }
2.157 - }
2.158 - ostream& os = (outputName.empty() ? cout : output);
2.159 -
2.160 - if (mincostflow) {
2.161 - Digraph digraph;
2.162 - DoubleArcMap lower(digraph), capacity(digraph), cost(digraph);
2.163 - DoubleNodeMap supply(digraph);
2.164 - readDimacsMin(is, digraph, lower, capacity, cost, supply);
2.165 - DigraphWriter<Digraph>(digraph, os).
2.166 - nodeMap("supply", supply).
2.167 - arcMap("lower", lower).
2.168 - arcMap("capacity", capacity).
2.169 - arcMap("cost", cost).
2.170 - run();
2.171 - } else if (maxflow) {
2.172 - Digraph digraph;
2.173 - Node s, t;
2.174 - DoubleArcMap capacity(digraph);
2.175 - readDimacsMax(is, digraph, capacity, s, t);
2.176 - DigraphWriter<Digraph>(digraph, os).
2.177 - arcMap("capacity", capacity).
2.178 - node("source", s).
2.179 - node("target", t).
2.180 - run();
2.181 - } else if (shortestpath) {
2.182 - Digraph digraph;
2.183 - Node s;
2.184 - DoubleArcMap capacity(digraph);
2.185 - readDimacsSp(is, digraph, capacity, s);
2.186 - DigraphWriter<Digraph>(digraph, os).
2.187 - arcMap("capacity", capacity).
2.188 - node("source", s).
2.189 - run();
2.190 - } else if (capacitated) {
2.191 - Digraph digraph;
2.192 - DoubleArcMap capacity(digraph);
2.193 - readDimacsMax(is, digraph, capacity);
2.194 - DigraphWriter<Digraph>(digraph, os).
2.195 - arcMap("capacity", capacity).
2.196 - run();
2.197 - } else if (plain) {
2.198 - Digraph digraph;
2.199 - readDimacsMat(is, digraph);
2.200 - DigraphWriter<Digraph>(digraph, os).run();
2.201 - } else {
2.202 - cerr << "Invalid type error" << endl;
2.203 - return -1;
2.204 - }
2.205 return 0;
2.206 }