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);