1.1 --- a/lemon/dimacs.h Thu Mar 22 06:36:50 2007 +0000
1.2 +++ b/lemon/dimacs.h Thu Mar 22 15:40:50 2007 +0000
1.3 @@ -27,11 +27,10 @@
1.4
1.5 /// \ingroup dimacs_group
1.6 /// \file
1.7 -/// \brief Dimacs file format reader.
1.8 +/// \brief DIMACS file format reader.
1.9
1.10 namespace lemon {
1.11
1.12 - ///
1.13 ///@defgroup dimacs_group DIMACS format
1.14 ///\brief Read and write files in DIMACS format
1.15 ///
1.16 @@ -41,114 +40,147 @@
1.17
1.18 /// \addtogroup dimacs_group
1.19 /// @{
1.20 +
1.21 + /// DIMACS min cost flow reader function.
1.22 + ///
1.23 + /// This function reads a min cost flow instance from DIMACS format,
1.24 + /// i.e. from DIMACS files having a line starting with
1.25 + /// \code
1.26 + /// p min
1.27 + /// \endcode
1.28 + /// At the beginning \c g is cleared by \c g.clear(). The supply
1.29 + /// amount of the nodes are written to \c supply (signed). The
1.30 + /// lower bounds, capacities and costs of the edges are written to
1.31 + /// \c lower, \c capacity and \c cost.
1.32 + ///
1.33 + /// \author Marton Makai and Peter Kovacs
1.34 + template <typename Graph, typename SupplyMap,
1.35 + typename CapacityMap, typename CostMap>
1.36 + void readDimacs( std::istream& is,
1.37 + Graph &g,
1.38 + SupplyMap& supply,
1.39 + CapacityMap& lower,
1.40 + CapacityMap& capacity,
1.41 + CostMap& cost )
1.42 + {
1.43 + g.clear();
1.44 + std::vector<typename Graph::Node> nodes;
1.45 + typename Graph::Edge e;
1.46 + std::string problem, str;
1.47 + char c;
1.48 + int n, m;
1.49 + int i, j;
1.50 + typename SupplyMap::Value sup;
1.51 + typename CapacityMap::Value low;
1.52 + typename CapacityMap::Value cap;
1.53 + typename CostMap::Value co;
1.54 + while (is >> c) {
1.55 + switch (c) {
1.56 + case 'c': // comment line
1.57 + getline(is, str);
1.58 + break;
1.59 + case 'p': // problem definition line
1.60 + is >> problem >> n >> m;
1.61 + getline(is, str);
1.62 + if (problem != "min") return;
1.63 + nodes.resize(n + 1);
1.64 + for (int k = 1; k <= n; ++k) {
1.65 + nodes[k] = g.addNode();
1.66 + supply[nodes[k]] = 0;
1.67 + }
1.68 + break;
1.69 + case 'n': // node definition line
1.70 + is >> i >> sup;
1.71 + getline(is, str);
1.72 + supply.set(nodes[i], sup);
1.73 + break;
1.74 + case 'a': // edge (arc) definition line
1.75 + is >> i >> j >> low >> cap >> co;
1.76 + getline(is, str);
1.77 + e = g.addEdge(nodes[i], nodes[j]);
1.78 + lower.set(e, low);
1.79 + if (cap >= 0)
1.80 + capacity.set(e, cap);
1.81 + else
1.82 + capacity.set(e, -1);
1.83 + cost.set(e, co);
1.84 + break;
1.85 + }
1.86 + }
1.87 + }
1.88
1.89 - /// Dimacs min cost flow reader function.
1.90 -
1.91 - /// This function reads a min cost flow instance from dimacs format,
1.92 - /// i.e. from dimacs files having a line starting with
1.93 - ///\code
1.94 - /// p "min"
1.95 - ///\endcode
1.96 - /// At the beginning \c g is cleared by \c g.clear(). The edge
1.97 - /// capacities are written to \c capacity, \c s and \c t are set to
1.98 - /// the source and the target nodes resp. and the cost of the edges
1.99 - /// are written to \c cost.
1.100 + /// DIMACS max flow reader function.
1.101 + ///
1.102 + /// This function reads a max flow instance from DIMACS format,
1.103 + /// i.e. from DIMACS files having a line starting with
1.104 + /// \code
1.105 + /// p max
1.106 + /// \endcode
1.107 + /// At the beginning \c g is cleared by \c g.clear(). The edge
1.108 + /// capacities are written to \c capacity and \c s and \c t are
1.109 + /// set to the source and the target nodes.
1.110 ///
1.111 /// \author Marton Makai
1.112 - template<typename Graph, typename CapacityMap, typename CostMap>
1.113 + template<typename Graph, typename CapacityMap>
1.114 void readDimacs(std::istream& is, Graph &g, CapacityMap& capacity,
1.115 - typename Graph::Node &s, typename Graph::Node &t,
1.116 - CostMap& cost) {
1.117 + typename Graph::Node &s, typename Graph::Node &t) {
1.118 g.clear();
1.119 + std::vector<typename Graph::Node> nodes;
1.120 + typename Graph::Edge e;
1.121 + std::string problem;
1.122 + char c, d;
1.123 + int n, m;
1.124 + int i, j;
1.125 typename CapacityMap::Value _cap;
1.126 - typename CostMap::Value _cost;
1.127 - char d;
1.128 - std::string problem;
1.129 - char c;
1.130 - int i, j;
1.131 std::string str;
1.132 - int n, m;
1.133 - typename Graph::Edge e;
1.134 - std::vector<typename Graph::Node> nodes;
1.135 - while (is>>c) {
1.136 + while (is >> c) {
1.137 switch (c) {
1.138 - case 'c': //comment
1.139 + case 'c': // comment line
1.140 getline(is, str);
1.141 break;
1.142 - case 'p': //problem definition
1.143 + case 'p': // problem definition line
1.144 is >> problem >> n >> m;
1.145 getline(is, str);
1.146 - nodes.resize(n+1);
1.147 - for (int k=1; k<=n; ++k) nodes[k]=g.addNode();
1.148 + nodes.resize(n + 1);
1.149 + for (int k = 1; k <= n; ++k)
1.150 + nodes[k] = g.addNode();
1.151 break;
1.152 - case 'n': //node definition
1.153 - if (problem=="sp") { //shortest path problem
1.154 + case 'n': // node definition line
1.155 + if (problem == "sp") { // shortest path problem
1.156 is >> i;
1.157 getline(is, str);
1.158 - s=nodes[i];
1.159 + s = nodes[i];
1.160 }
1.161 - if (problem=="max" || problem=="min") { //((max) or (min cost)) flow problem
1.162 + if (problem == "max") { // max flow problem
1.163 is >> i >> d;
1.164 getline(is, str);
1.165 - if (d=='s') s=nodes[i];
1.166 - if (d=='t') t=nodes[i];
1.167 + if (d == 's') s = nodes[i];
1.168 + if (d == 't') t = nodes[i];
1.169 }
1.170 break;
1.171 - case 'a':
1.172 - if ( problem == "max" || problem == "sp") {
1.173 + case 'a': // edge (arc) definition line
1.174 + if (problem == "max" || problem == "sp") {
1.175 is >> i >> j >> _cap;
1.176 getline(is, str);
1.177 - e=g.addEdge(nodes[i], nodes[j]);
1.178 - //capacity.update();
1.179 + e = g.addEdge(nodes[i], nodes[j]);
1.180 capacity.set(e, _cap);
1.181 } else {
1.182 - if ( problem == "min" ) {
1.183 - is >> i >> j >> _cap >> _cost;
1.184 - getline(is, str);
1.185 - e=g.addEdge(nodes[i], nodes[j]);
1.186 - //capacity.update();
1.187 - capacity.set(e, _cap);
1.188 - //cost.update();
1.189 - cost.set(e, _cost);
1.190 - } else {
1.191 - is >> i >> j;
1.192 - getline(is, str);
1.193 - g.addEdge(nodes[i], nodes[j]);
1.194 - }
1.195 + is >> i >> j;
1.196 + getline(is, str);
1.197 + g.addEdge(nodes[i], nodes[j]);
1.198 }
1.199 break;
1.200 }
1.201 }
1.202 }
1.203
1.204 -
1.205 - /// Dimacs max flow reader function.
1.206 -
1.207 - /// This function reads a max flow instance from dimacs format,
1.208 - /// i.e. from dimacs files having a line starting with
1.209 - ///\code
1.210 - /// p "max"
1.211 - ///\endcode
1.212 - ///At the beginning \c g is cleared by \c g.clear(). The
1.213 - /// edge capacities are written to \c capacity and \c s and \c t are
1.214 - /// set to the source and the target nodes.
1.215 + /// DIMACS shortest path reader function.
1.216 ///
1.217 - /// \author Marton Makai
1.218 - template<typename Graph, typename CapacityMap>
1.219 - void readDimacs(std::istream& is, Graph &g, CapacityMap& capacity,
1.220 - typename Graph::Node &s, typename Graph::Node &t) {
1.221 - NullMap<typename Graph::Edge, int> n;
1.222 - readDimacs(is, g, capacity, s, t, n);
1.223 - }
1.224 -
1.225 -
1.226 - /// Dimacs shortest path reader function.
1.227 -
1.228 - /// This function reads a shortest path instance from dimacs format,
1.229 - /// i.e. from dimacs files having a line starting with
1.230 - ///\code
1.231 - /// p "sp"
1.232 - ///\endcode
1.233 + /// This function reads a shortest path instance from DIMACS format,
1.234 + /// i.e. from DIMACS files having a line starting with
1.235 + /// \code
1.236 + /// p sp
1.237 + /// \endcode
1.238 /// At the beginning \c g is cleared by \c g.clear(). The edge
1.239 /// capacities are written to \c capacity and \c s is set to the
1.240 /// source node.
1.241 @@ -157,70 +189,67 @@
1.242 template<typename Graph, typename CapacityMap>
1.243 void readDimacs(std::istream& is, Graph &g, CapacityMap& capacity,
1.244 typename Graph::Node &s) {
1.245 - NullMap<typename Graph::Edge, int> n;
1.246 - readDimacs(is, g, capacity, s, s, n);
1.247 + readDimacs(is, g, capacity, s, s);
1.248 }
1.249
1.250 -
1.251 - /// Dimacs capacitated graph reader function.
1.252 -
1.253 + /// DIMACS capacitated graph reader function.
1.254 + ///
1.255 /// This function reads an edge capacitated graph instance from
1.256 - /// dimacs format. At the beginning \c g is cleared by \c g.clear()
1.257 + /// DIMACS format. At the beginning \c g is cleared by \c g.clear()
1.258 /// and the edge capacities are written to \c capacity.
1.259 ///
1.260 /// \author Marton Makai
1.261 template<typename Graph, typename CapacityMap>
1.262 void readDimacs(std::istream& is, Graph &g, CapacityMap& capacity) {
1.263 typename Graph::Node u;
1.264 - NullMap<typename Graph::Edge, int> n;
1.265 - readDimacs(is, g, capacity, u, u, n);
1.266 + readDimacs(is, g, capacity, u, u);
1.267 }
1.268
1.269 -
1.270 - /// Dimacs plain graph reader function.
1.271 -
1.272 + /// DIMACS plain graph reader function.
1.273 + ///
1.274 /// This function reads a graph without any designated nodes and
1.275 - /// maps from dimacs format, i.e. from dimacs files having a line
1.276 + /// maps from DIMACS format, i.e. from DIMACS files having a line
1.277 /// starting with
1.278 - ///\code
1.279 - /// p "mat"
1.280 - ///\endcode
1.281 - /// At the beginning \c g is cleared
1.282 - /// by \c g.clear().
1.283 + /// \code
1.284 + /// p mat
1.285 + /// \endcode
1.286 + /// At the beginning \c g is cleared by \c g.clear().
1.287 ///
1.288 /// \author Marton Makai
1.289 template<typename Graph>
1.290 void readDimacs(std::istream& is, Graph &g) {
1.291 typename Graph::Node u;
1.292 NullMap<typename Graph::Edge, int> n;
1.293 - readDimacs(is, g, n, u, u, n);
1.294 + readDimacs(is, g, n, u, u);
1.295 }
1.296
1.297 -
1.298 -
1.299 -
1.300 - /// write matching problem
1.301 + /// DIMACS plain graph writer function.
1.302 + ///
1.303 + /// This function writes a graph without any designated nodes and
1.304 + /// maps into DIMACS format, i.e. into DIMACS file having a line
1.305 + /// starting with
1.306 + /// \code
1.307 + /// p mat
1.308 + /// \endcode
1.309 + ///
1.310 + /// \author Marton Makai
1.311 template<typename Graph>
1.312 void writeDimacs(std::ostream& os, const Graph &g) {
1.313 typedef typename Graph::NodeIt NodeIt;
1.314 typedef typename Graph::EdgeIt EdgeIt;
1.315
1.316 + os << "c matching problem" << std::endl;
1.317 + os << "p mat " << g.nodeNum() << " " << g.edgeNum() << std::endl;
1.318 +
1.319 typename Graph::template NodeMap<int> nodes(g);
1.320 -
1.321 - os << "c matching problem" << std::endl;
1.322 -
1.323 - int i=1;
1.324 - for(NodeIt v(g); v!=INVALID; ++v) {
1.325 + int i = 1;
1.326 + for(NodeIt v(g); v != INVALID; ++v) {
1.327 nodes.set(v, i);
1.328 ++i;
1.329 }
1.330 -
1.331 - os << "p mat " << g.nodeNum() << " " << g.edgeNum() << std::endl;
1.332 -
1.333 - for(EdgeIt e(g); e!=INVALID; ++e) {
1.334 + for(EdgeIt e(g); e != INVALID; ++e) {
1.335 os << "a " << nodes[g.source(e)] << " " << nodes[g.target(e)] << std::endl;
1.336 }
1.337 -
1.338 }
1.339
1.340 /// @}