1.1 --- a/lemon/dimacs.h Mon Jan 12 23:11:39 2009 +0100
1.2 +++ b/lemon/dimacs.h Thu Nov 05 15:48:01 2009 +0100
1.3 @@ -22,9 +22,9 @@
1.4 #include <iostream>
1.5 #include <string>
1.6 #include <vector>
1.7 +#include <limits>
1.8 #include <lemon/maps.h>
1.9 #include <lemon/error.h>
1.10 -
1.11 /// \ingroup dimacs_group
1.12 /// \file
1.13 /// \brief DIMACS file format reader.
1.14 @@ -37,11 +37,16 @@
1.15 /// DIMACS file type descriptor.
1.16 struct DimacsDescriptor
1.17 {
1.18 - ///File type enum
1.19 - enum Type
1.20 - {
1.21 - NONE, MIN, MAX, SP, MAT
1.22 - };
1.23 + ///\brief DIMACS file type enum
1.24 + ///
1.25 + ///DIMACS file type enum.
1.26 + enum Type {
1.27 + NONE, ///< Undefined type.
1.28 + MIN, ///< DIMACS file type for minimum cost flow problems.
1.29 + MAX, ///< DIMACS file type for maximum flow problems.
1.30 + SP, ///< DIMACS file type for shostest path problems.
1.31 + MAT ///< DIMACS file type for plain graphs and matching problems.
1.32 + };
1.33 ///The file type
1.34 Type type;
1.35 ///The number of nodes in the graph
1.36 @@ -49,16 +54,16 @@
1.37 ///The number of edges in the graph
1.38 int edgeNum;
1.39 int lineShift;
1.40 - /// Constructor. Sets the type to NONE.
1.41 + ///Constructor. It sets the type to \c NONE.
1.42 DimacsDescriptor() : type(NONE) {}
1.43 };
1.44
1.45 ///Discover the type of a DIMACS file
1.46
1.47 - ///It starts seeking the begining of the file for the problem type
1.48 - ///and size info. The found data is returned in a special struct
1.49 - ///that can be evaluated and passed to the appropriate reader
1.50 - ///function.
1.51 + ///This function starts seeking the beginning of the given file for the
1.52 + ///problem type and size info.
1.53 + ///The found data is returned in a special struct that can be evaluated
1.54 + ///and passed to the appropriate reader function.
1.55 DimacsDescriptor dimacsType(std::istream& is)
1.56 {
1.57 DimacsDescriptor r;
1.58 @@ -96,8 +101,7 @@
1.59 }
1.60
1.61
1.62 -
1.63 - /// DIMACS minimum cost flow reader function.
1.64 + /// \brief DIMACS minimum cost flow reader function.
1.65 ///
1.66 /// This function reads a minimum cost flow instance from DIMACS format,
1.67 /// i.e. from a DIMACS file having a line starting with
1.68 @@ -105,9 +109,17 @@
1.69 /// p min
1.70 /// \endcode
1.71 /// At the beginning, \c g is cleared by \c g.clear(). The supply
1.72 - /// amount of the nodes are written to \c supply (signed). The
1.73 - /// lower bounds, capacities and costs of the arcs are written to
1.74 - /// \c lower, \c capacity and \c cost.
1.75 + /// amount of the nodes are written to the \c supply node map
1.76 + /// (they are signed values). The lower bounds, capacities and costs
1.77 + /// of the arcs are written to the \c lower, \c capacity and \c cost
1.78 + /// arc maps.
1.79 + ///
1.80 + /// If the capacity of an arc is less than the lower bound, it will
1.81 + /// be set to "infinite" instead. The actual value of "infinite" is
1.82 + /// contolled by the \c infty parameter. If it is 0 (the default value),
1.83 + /// \c std::numeric_limits<Capacity>::infinity() will be used if available,
1.84 + /// \c std::numeric_limits<Capacity>::max() otherwise. If \c infty is set to
1.85 + /// a non-zero value, that value will be used as "infinite".
1.86 ///
1.87 /// If the file type was previously evaluated by dimacsType(), then
1.88 /// the descriptor struct should be given by the \c dest parameter.
1.89 @@ -120,6 +132,7 @@
1.90 CapacityMap& capacity,
1.91 CostMap& cost,
1.92 SupplyMap& supply,
1.93 + typename CapacityMap::Value infty = 0,
1.94 DimacsDescriptor desc=DimacsDescriptor())
1.95 {
1.96 g.clear();
1.97 @@ -142,6 +155,12 @@
1.98 typename CapacityMap::Value low;
1.99 typename CapacityMap::Value cap;
1.100 typename CostMap::Value co;
1.101 + typedef typename CapacityMap::Value Capacity;
1.102 + if(infty==0)
1.103 + infty = std::numeric_limits<Capacity>::has_infinity ?
1.104 + std::numeric_limits<Capacity>::infinity() :
1.105 + std::numeric_limits<Capacity>::max();
1.106 +
1.107 while (is >> c) {
1.108 switch (c) {
1.109 case 'c': // comment line
1.110 @@ -152,15 +171,15 @@
1.111 getline(is, str);
1.112 supply.set(nodes[i], sup);
1.113 break;
1.114 - case 'a': // arc (arc) definition line
1.115 + case 'a': // arc definition line
1.116 is >> i >> j >> low >> cap >> co;
1.117 getline(is, str);
1.118 e = g.addArc(nodes[i], nodes[j]);
1.119 lower.set(e, low);
1.120 - if (cap >= 0)
1.121 + if (cap >= low)
1.122 capacity.set(e, cap);
1.123 else
1.124 - capacity.set(e, -1);
1.125 + capacity.set(e, infty);
1.126 cost.set(e, co);
1.127 break;
1.128 }
1.129 @@ -173,6 +192,7 @@
1.130 CapacityMap& capacity,
1.131 typename Digraph::Node &s,
1.132 typename Digraph::Node &t,
1.133 + typename CapacityMap::Value infty = 0,
1.134 DimacsDescriptor desc=DimacsDescriptor()) {
1.135 g.clear();
1.136 s=t=INVALID;
1.137 @@ -186,7 +206,13 @@
1.138 for (int k = 1; k <= desc.nodeNum; ++k) {
1.139 nodes[k] = g.addNode();
1.140 }
1.141 + typedef typename CapacityMap::Value Capacity;
1.142
1.143 + if(infty==0)
1.144 + infty = std::numeric_limits<Capacity>::has_infinity ?
1.145 + std::numeric_limits<Capacity>::infinity() :
1.146 + std::numeric_limits<Capacity>::max();
1.147 +
1.148 while (is >> c) {
1.149 switch (c) {
1.150 case 'c': // comment line
1.151 @@ -205,14 +231,23 @@
1.152 if (d == 't') t = nodes[i];
1.153 }
1.154 break;
1.155 - case 'a': // arc (arc) definition line
1.156 - if (desc.type==DimacsDescriptor::SP ||
1.157 - desc.type==DimacsDescriptor::MAX) {
1.158 + case 'a': // arc definition line
1.159 + if (desc.type==DimacsDescriptor::SP) {
1.160 is >> i >> j >> _cap;
1.161 getline(is, str);
1.162 e = g.addArc(nodes[i], nodes[j]);
1.163 capacity.set(e, _cap);
1.164 - } else {
1.165 + }
1.166 + else if (desc.type==DimacsDescriptor::MAX) {
1.167 + is >> i >> j >> _cap;
1.168 + getline(is, str);
1.169 + e = g.addArc(nodes[i], nodes[j]);
1.170 + if (_cap >= 0)
1.171 + capacity.set(e, _cap);
1.172 + else
1.173 + capacity.set(e, infty);
1.174 + }
1.175 + else {
1.176 is >> i >> j;
1.177 getline(is, str);
1.178 g.addArc(nodes[i], nodes[j]);
1.179 @@ -222,7 +257,7 @@
1.180 }
1.181 }
1.182
1.183 - /// DIMACS maximum flow reader function.
1.184 + /// \brief DIMACS maximum flow reader function.
1.185 ///
1.186 /// This function reads a maximum flow instance from DIMACS format,
1.187 /// i.e. from a DIMACS file having a line starting with
1.188 @@ -230,8 +265,15 @@
1.189 /// p max
1.190 /// \endcode
1.191 /// At the beginning, \c g is cleared by \c g.clear(). The arc
1.192 - /// capacities are written to \c capacity and \c s and \c t are
1.193 - /// set to the source and the target nodes.
1.194 + /// capacities are written to the \c capacity arc map and \c s and
1.195 + /// \c t are set to the source and the target nodes.
1.196 + ///
1.197 + /// If the capacity of an arc is negative, it will
1.198 + /// be set to "infinite" instead. The actual value of "infinite" is
1.199 + /// contolled by the \c infty parameter. If it is 0 (the default value),
1.200 + /// \c std::numeric_limits<Capacity>::infinity() will be used if available,
1.201 + /// \c std::numeric_limits<Capacity>::max() otherwise. If \c infty is set to
1.202 + /// a non-zero value, that value will be used as "infinite".
1.203 ///
1.204 /// If the file type was previously evaluated by dimacsType(), then
1.205 /// the descriptor struct should be given by the \c dest parameter.
1.206 @@ -241,14 +283,15 @@
1.207 CapacityMap& capacity,
1.208 typename Digraph::Node &s,
1.209 typename Digraph::Node &t,
1.210 + typename CapacityMap::Value infty = 0,
1.211 DimacsDescriptor desc=DimacsDescriptor()) {
1.212 if(desc.type==DimacsDescriptor::NONE) desc=dimacsType(is);
1.213 if(desc.type!=DimacsDescriptor::MAX)
1.214 throw FormatError("Problem type mismatch");
1.215 - _readDimacs(is,g,capacity,s,t,desc);
1.216 + _readDimacs(is,g,capacity,s,t,infty,desc);
1.217 }
1.218
1.219 - /// DIMACS shortest path reader function.
1.220 + /// \brief DIMACS shortest path reader function.
1.221 ///
1.222 /// This function reads a shortest path instance from DIMACS format,
1.223 /// i.e. from a DIMACS file having a line starting with
1.224 @@ -256,7 +299,7 @@
1.225 /// p sp
1.226 /// \endcode
1.227 /// At the beginning, \c g is cleared by \c g.clear(). The arc
1.228 - /// lengths are written to \c length and \c s is set to the
1.229 + /// lengths are written to the \c length arc map and \c s is set to the
1.230 /// source node.
1.231 ///
1.232 /// If the file type was previously evaluated by dimacsType(), then
1.233 @@ -271,15 +314,24 @@
1.234 if(desc.type==DimacsDescriptor::NONE) desc=dimacsType(is);
1.235 if(desc.type!=DimacsDescriptor::SP)
1.236 throw FormatError("Problem type mismatch");
1.237 - _readDimacs(is, g, length, s, t,desc);
1.238 + _readDimacs(is, g, length, s, t, 0, desc);
1.239 }
1.240
1.241 - /// DIMACS capacitated digraph reader function.
1.242 + /// \brief DIMACS capacitated digraph reader function.
1.243 ///
1.244 /// This function reads an arc capacitated digraph instance from
1.245 - /// DIMACS 'mat' or 'sp' format.
1.246 + /// DIMACS 'max' or 'sp' format.
1.247 /// At the beginning, \c g is cleared by \c g.clear()
1.248 - /// and the arc capacities/lengths are written to \c capacity.
1.249 + /// and the arc capacities/lengths are written to the \c capacity
1.250 + /// arc map.
1.251 + ///
1.252 + /// In case of the 'max' format, if the capacity of an arc is negative,
1.253 + /// it will
1.254 + /// be set to "infinite" instead. The actual value of "infinite" is
1.255 + /// contolled by the \c infty parameter. If it is 0 (the default value),
1.256 + /// \c std::numeric_limits<Capacity>::infinity() will be used if available,
1.257 + /// \c std::numeric_limits<Capacity>::max() otherwise. If \c infty is set to
1.258 + /// a non-zero value, that value will be used as "infinite".
1.259 ///
1.260 /// If the file type was previously evaluated by dimacsType(), then
1.261 /// the descriptor struct should be given by the \c dest parameter.
1.262 @@ -287,19 +339,35 @@
1.263 void readDimacsCap(std::istream& is,
1.264 Digraph &g,
1.265 CapacityMap& capacity,
1.266 + typename CapacityMap::Value infty = 0,
1.267 DimacsDescriptor desc=DimacsDescriptor()) {
1.268 typename Digraph::Node u,v;
1.269 if(desc.type==DimacsDescriptor::NONE) desc=dimacsType(is);
1.270 if(desc.type!=DimacsDescriptor::MAX || desc.type!=DimacsDescriptor::SP)
1.271 throw FormatError("Problem type mismatch");
1.272 - _readDimacs(is, g, capacity, u, v, desc);
1.273 + _readDimacs(is, g, capacity, u, v, infty, desc);
1.274 }
1.275
1.276 - /// DIMACS plain digraph reader function.
1.277 + template<typename Graph>
1.278 + typename enable_if<lemon::UndirectedTagIndicator<Graph>,void>::type
1.279 + _addArcEdge(Graph &g, typename Graph::Node s, typename Graph::Node t,
1.280 + dummy<0> = 0)
1.281 + {
1.282 + g.addEdge(s,t);
1.283 + }
1.284 + template<typename Graph>
1.285 + typename disable_if<lemon::UndirectedTagIndicator<Graph>,void>::type
1.286 + _addArcEdge(Graph &g, typename Graph::Node s, typename Graph::Node t,
1.287 + dummy<1> = 1)
1.288 + {
1.289 + g.addArc(s,t);
1.290 + }
1.291 +
1.292 + /// \brief DIMACS plain (di)graph reader function.
1.293 ///
1.294 - /// This function reads a digraph without any designated nodes and
1.295 - /// maps from DIMACS format, i.e. from DIMACS files having a line
1.296 - /// starting with
1.297 + /// This function reads a plain (di)graph without any designated nodes
1.298 + /// and maps (e.g. a matching instance) from DIMACS format, i.e. from
1.299 + /// DIMACS files having a line starting with
1.300 /// \code
1.301 /// p mat
1.302 /// \endcode
1.303 @@ -307,15 +375,38 @@
1.304 ///
1.305 /// If the file type was previously evaluated by dimacsType(), then
1.306 /// the descriptor struct should be given by the \c dest parameter.
1.307 - template<typename Digraph>
1.308 - void readDimacsMat(std::istream& is, Digraph &g,
1.309 - DimacsDescriptor desc=DimacsDescriptor()) {
1.310 - typename Digraph::Node u,v;
1.311 - NullMap<typename Digraph::Arc, int> n;
1.312 + template<typename Graph>
1.313 + void readDimacsMat(std::istream& is, Graph &g,
1.314 + DimacsDescriptor desc=DimacsDescriptor())
1.315 + {
1.316 if(desc.type==DimacsDescriptor::NONE) desc=dimacsType(is);
1.317 if(desc.type!=DimacsDescriptor::MAT)
1.318 throw FormatError("Problem type mismatch");
1.319 - _readDimacs(is, g, n, u, v, desc);
1.320 +
1.321 + g.clear();
1.322 + std::vector<typename Graph::Node> nodes;
1.323 + char c;
1.324 + int i, j;
1.325 + std::string str;
1.326 + nodes.resize(desc.nodeNum + 1);
1.327 + for (int k = 1; k <= desc.nodeNum; ++k) {
1.328 + nodes[k] = g.addNode();
1.329 + }
1.330 +
1.331 + while (is >> c) {
1.332 + switch (c) {
1.333 + case 'c': // comment line
1.334 + getline(is, str);
1.335 + break;
1.336 + case 'n': // node definition line
1.337 + break;
1.338 + case 'a': // arc definition line
1.339 + is >> i >> j;
1.340 + getline(is, str);
1.341 + _addArcEdge(g,nodes[i], nodes[j]);
1.342 + break;
1.343 + }
1.344 + }
1.345 }
1.346
1.347 /// DIMACS plain digraph writer function.