1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/lemon/dimacs.h Sun Nov 30 09:39:34 2008 +0000
1.3 @@ -0,0 +1,357 @@
1.4 +/* -*- mode: C++; indent-tabs-mode: nil; -*-
1.5 + *
1.6 + * This file is a part of LEMON, a generic C++ optimization library.
1.7 + *
1.8 + * Copyright (C) 2003-2008
1.9 + * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
1.10 + * (Egervary Research Group on Combinatorial Optimization, EGRES).
1.11 + *
1.12 + * Permission to use, modify and distribute this software is granted
1.13 + * provided that this copyright notice appears in all copies. For
1.14 + * precise terms see the accompanying LICENSE file.
1.15 + *
1.16 + * This software is provided "AS IS" with no warranty of any kind,
1.17 + * express or implied, and with no claim as to its suitability for any
1.18 + * purpose.
1.19 + *
1.20 + */
1.21 +
1.22 +#ifndef LEMON_DIMACS_H
1.23 +#define LEMON_DIMACS_H
1.24 +
1.25 +#include <iostream>
1.26 +#include <string>
1.27 +#include <vector>
1.28 +#include <lemon/maps.h>
1.29 +#include <lemon/error.h>
1.30 +
1.31 +/// \ingroup dimacs_group
1.32 +/// \file
1.33 +/// \brief DIMACS file format reader.
1.34 +
1.35 +namespace lemon {
1.36 +
1.37 + /// \addtogroup dimacs_group
1.38 + /// @{
1.39 +
1.40 + /// DIMACS file type descriptor.
1.41 + struct DimacsDescriptor
1.42 + {
1.43 + ///File type enum
1.44 + enum Type
1.45 + {
1.46 + NONE, MIN, MAX, SP, MAT
1.47 + };
1.48 + ///The file type
1.49 + Type type;
1.50 + ///The number of nodes in the graph
1.51 + int nodeNum;
1.52 + ///The number of edges in the graph
1.53 + int edgeNum;
1.54 + int lineShift;
1.55 + /// Constructor. Sets the type to NONE.
1.56 + DimacsDescriptor() : type(NONE) {}
1.57 + };
1.58 +
1.59 + ///Discover the type of a DIMACS file
1.60 +
1.61 + ///It starts seeking the begining of the file for the problem type
1.62 + ///and size info. The found data is returned in a special struct
1.63 + ///that can be evaluated and passed to the appropriate reader
1.64 + ///function.
1.65 + DimacsDescriptor dimacsType(std::istream& is)
1.66 + {
1.67 + DimacsDescriptor r;
1.68 + std::string problem,str;
1.69 + char c;
1.70 + r.lineShift=0;
1.71 + while (is >> c)
1.72 + switch(c)
1.73 + {
1.74 + case 'p':
1.75 + if(is >> problem >> r.nodeNum >> r.edgeNum)
1.76 + {
1.77 + getline(is, str);
1.78 + r.lineShift++;
1.79 + if(problem=="min") r.type=DimacsDescriptor::MIN;
1.80 + else if(problem=="max") r.type=DimacsDescriptor::MAX;
1.81 + else if(problem=="sp") r.type=DimacsDescriptor::SP;
1.82 + else if(problem=="mat") r.type=DimacsDescriptor::MAT;
1.83 + else throw FormatError("Unknown problem type");
1.84 + return r;
1.85 + }
1.86 + else
1.87 + {
1.88 + throw FormatError("Missing or wrong problem type declaration.");
1.89 + }
1.90 + break;
1.91 + case 'c':
1.92 + getline(is, str);
1.93 + r.lineShift++;
1.94 + break;
1.95 + default:
1.96 + throw FormatError("Unknown DIMACS declaration.");
1.97 + }
1.98 + throw FormatError("Missing problem type declaration.");
1.99 + }
1.100 +
1.101 +
1.102 +
1.103 + /// DIMACS minimum cost flow reader function.
1.104 + ///
1.105 + /// This function reads a minimum cost flow instance from DIMACS format,
1.106 + /// i.e. from a DIMACS file having a line starting with
1.107 + /// \code
1.108 + /// p min
1.109 + /// \endcode
1.110 + /// At the beginning, \c g is cleared by \c g.clear(). The supply
1.111 + /// amount of the nodes are written to \c supply (signed). The
1.112 + /// lower bounds, capacities and costs of the arcs are written to
1.113 + /// \c lower, \c capacity and \c cost.
1.114 + ///
1.115 + /// If the file type was previously evaluated by dimacsType(), then
1.116 + /// the descriptor struct should be given by the \c dest parameter.
1.117 + template <typename Digraph, typename LowerMap,
1.118 + typename CapacityMap, typename CostMap,
1.119 + typename SupplyMap>
1.120 + void readDimacsMin(std::istream& is,
1.121 + Digraph &g,
1.122 + LowerMap& lower,
1.123 + CapacityMap& capacity,
1.124 + CostMap& cost,
1.125 + SupplyMap& supply,
1.126 + DimacsDescriptor desc=DimacsDescriptor())
1.127 + {
1.128 + g.clear();
1.129 + std::vector<typename Digraph::Node> nodes;
1.130 + typename Digraph::Arc e;
1.131 + std::string problem, str;
1.132 + char c;
1.133 + int i, j;
1.134 + if(desc.type==DimacsDescriptor::NONE) desc=dimacsType(is);
1.135 + if(desc.type!=DimacsDescriptor::MIN)
1.136 + throw FormatError("Problem type mismatch");
1.137 +
1.138 + nodes.resize(desc.nodeNum + 1);
1.139 + for (int k = 1; k <= desc.nodeNum; ++k) {
1.140 + nodes[k] = g.addNode();
1.141 + supply.set(nodes[k], 0);
1.142 + }
1.143 +
1.144 + typename SupplyMap::Value sup;
1.145 + typename CapacityMap::Value low;
1.146 + typename CapacityMap::Value cap;
1.147 + typename CostMap::Value co;
1.148 + while (is >> c) {
1.149 + switch (c) {
1.150 + case 'c': // comment line
1.151 + getline(is, str);
1.152 + break;
1.153 + case 'n': // node definition line
1.154 + is >> i >> sup;
1.155 + getline(is, str);
1.156 + supply.set(nodes[i], sup);
1.157 + break;
1.158 + case 'a': // arc (arc) definition line
1.159 + is >> i >> j >> low >> cap >> co;
1.160 + getline(is, str);
1.161 + e = g.addArc(nodes[i], nodes[j]);
1.162 + lower.set(e, low);
1.163 + if (cap >= 0)
1.164 + capacity.set(e, cap);
1.165 + else
1.166 + capacity.set(e, -1);
1.167 + cost.set(e, co);
1.168 + break;
1.169 + }
1.170 + }
1.171 + }
1.172 +
1.173 + template<typename Digraph, typename CapacityMap>
1.174 + void _readDimacs(std::istream& is,
1.175 + Digraph &g,
1.176 + CapacityMap& capacity,
1.177 + typename Digraph::Node &s,
1.178 + typename Digraph::Node &t,
1.179 + DimacsDescriptor desc=DimacsDescriptor()) {
1.180 + g.clear();
1.181 + s=t=INVALID;
1.182 + std::vector<typename Digraph::Node> nodes;
1.183 + typename Digraph::Arc e;
1.184 + char c, d;
1.185 + int i, j;
1.186 + typename CapacityMap::Value _cap;
1.187 + std::string str;
1.188 + nodes.resize(desc.nodeNum + 1);
1.189 + for (int k = 1; k <= desc.nodeNum; ++k) {
1.190 + nodes[k] = g.addNode();
1.191 + }
1.192 +
1.193 + while (is >> c) {
1.194 + switch (c) {
1.195 + case 'c': // comment line
1.196 + getline(is, str);
1.197 + break;
1.198 + case 'n': // node definition line
1.199 + if (desc.type==DimacsDescriptor::SP) { // shortest path problem
1.200 + is >> i;
1.201 + getline(is, str);
1.202 + s = nodes[i];
1.203 + }
1.204 + if (desc.type==DimacsDescriptor::MAX) { // max flow problem
1.205 + is >> i >> d;
1.206 + getline(is, str);
1.207 + if (d == 's') s = nodes[i];
1.208 + if (d == 't') t = nodes[i];
1.209 + }
1.210 + break;
1.211 + case 'a': // arc (arc) definition line
1.212 + if (desc.type==DimacsDescriptor::SP ||
1.213 + desc.type==DimacsDescriptor::MAX) {
1.214 + is >> i >> j >> _cap;
1.215 + getline(is, str);
1.216 + e = g.addArc(nodes[i], nodes[j]);
1.217 + capacity.set(e, _cap);
1.218 + } else {
1.219 + is >> i >> j;
1.220 + getline(is, str);
1.221 + g.addArc(nodes[i], nodes[j]);
1.222 + }
1.223 + break;
1.224 + }
1.225 + }
1.226 + }
1.227 +
1.228 + /// DIMACS maximum flow reader function.
1.229 + ///
1.230 + /// This function reads a maximum flow instance from DIMACS format,
1.231 + /// i.e. from a DIMACS file having a line starting with
1.232 + /// \code
1.233 + /// p max
1.234 + /// \endcode
1.235 + /// At the beginning, \c g is cleared by \c g.clear(). The arc
1.236 + /// capacities are written to \c capacity and \c s and \c t are
1.237 + /// set to the source and the target nodes.
1.238 + ///
1.239 + /// If the file type was previously evaluated by dimacsType(), then
1.240 + /// the descriptor struct should be given by the \c dest parameter.
1.241 + template<typename Digraph, typename CapacityMap>
1.242 + void readDimacsMax(std::istream& is,
1.243 + Digraph &g,
1.244 + CapacityMap& capacity,
1.245 + typename Digraph::Node &s,
1.246 + typename Digraph::Node &t,
1.247 + DimacsDescriptor desc=DimacsDescriptor()) {
1.248 + if(desc.type==DimacsDescriptor::NONE) desc=dimacsType(is);
1.249 + if(desc.type!=DimacsDescriptor::MAX)
1.250 + throw FormatError("Problem type mismatch");
1.251 + _readDimacs(is,g,capacity,s,t,desc);
1.252 + }
1.253 +
1.254 + /// DIMACS shortest path reader function.
1.255 + ///
1.256 + /// This function reads a shortest path instance from DIMACS format,
1.257 + /// i.e. from a DIMACS file having a line starting with
1.258 + /// \code
1.259 + /// p sp
1.260 + /// \endcode
1.261 + /// At the beginning, \c g is cleared by \c g.clear(). The arc
1.262 + /// lengths are written to \c length and \c s is set to the
1.263 + /// source node.
1.264 + ///
1.265 + /// If the file type was previously evaluated by dimacsType(), then
1.266 + /// the descriptor struct should be given by the \c dest parameter.
1.267 + template<typename Digraph, typename LengthMap>
1.268 + void readDimacsSp(std::istream& is,
1.269 + Digraph &g,
1.270 + LengthMap& length,
1.271 + typename Digraph::Node &s,
1.272 + DimacsDescriptor desc=DimacsDescriptor()) {
1.273 + typename Digraph::Node t;
1.274 + if(desc.type==DimacsDescriptor::NONE) desc=dimacsType(is);
1.275 + if(desc.type!=DimacsDescriptor::SP)
1.276 + throw FormatError("Problem type mismatch");
1.277 + _readDimacs(is, g, length, s, t,desc);
1.278 + }
1.279 +
1.280 + /// DIMACS capacitated digraph reader function.
1.281 + ///
1.282 + /// This function reads an arc capacitated digraph instance from
1.283 + /// DIMACS 'mat' or 'sp' format.
1.284 + /// At the beginning, \c g is cleared by \c g.clear()
1.285 + /// and the arc capacities/lengths are written to \c capacity.
1.286 + ///
1.287 + /// If the file type was previously evaluated by dimacsType(), then
1.288 + /// the descriptor struct should be given by the \c dest parameter.
1.289 + template<typename Digraph, typename CapacityMap>
1.290 + void readDimacsCap(std::istream& is,
1.291 + Digraph &g,
1.292 + CapacityMap& capacity,
1.293 + DimacsDescriptor desc=DimacsDescriptor()) {
1.294 + typename Digraph::Node u,v;
1.295 + if(desc.type==DimacsDescriptor::NONE) desc=dimacsType(is);
1.296 + if(desc.type!=DimacsDescriptor::MAX || desc.type!=DimacsDescriptor::SP)
1.297 + throw FormatError("Problem type mismatch");
1.298 + _readDimacs(is, g, capacity, u, v, desc);
1.299 + }
1.300 +
1.301 + /// DIMACS plain digraph reader function.
1.302 + ///
1.303 + /// This function reads a digraph without any designated nodes and
1.304 + /// maps from DIMACS format, i.e. from DIMACS files having a line
1.305 + /// starting with
1.306 + /// \code
1.307 + /// p mat
1.308 + /// \endcode
1.309 + /// At the beginning, \c g is cleared by \c g.clear().
1.310 + ///
1.311 + /// If the file type was previously evaluated by dimacsType(), then
1.312 + /// the descriptor struct should be given by the \c dest parameter.
1.313 + template<typename Digraph>
1.314 + void readDimacsMat(std::istream& is, Digraph &g,
1.315 + DimacsDescriptor desc=DimacsDescriptor()) {
1.316 + typename Digraph::Node u,v;
1.317 + NullMap<typename Digraph::Arc, int> n;
1.318 + if(desc.type==DimacsDescriptor::NONE) desc=dimacsType(is);
1.319 + if(desc.type!=DimacsDescriptor::MAT)
1.320 + throw FormatError("Problem type mismatch");
1.321 + _readDimacs(is, g, n, u, v, desc);
1.322 + }
1.323 +
1.324 + /// DIMACS plain digraph writer function.
1.325 + ///
1.326 + /// This function writes a digraph without any designated nodes and
1.327 + /// maps into DIMACS format, i.e. into DIMACS file having a line
1.328 + /// starting with
1.329 + /// \code
1.330 + /// p mat
1.331 + /// \endcode
1.332 + /// If \c comment is not empty, then it will be printed in the first line
1.333 + /// prefixed by 'c'.
1.334 + template<typename Digraph>
1.335 + void writeDimacsMat(std::ostream& os, const Digraph &g,
1.336 + std::string comment="") {
1.337 + typedef typename Digraph::NodeIt NodeIt;
1.338 + typedef typename Digraph::ArcIt ArcIt;
1.339 +
1.340 + if(!comment.empty())
1.341 + os << "c " << comment << std::endl;
1.342 + os << "p mat " << g.nodeNum() << " " << g.arcNum() << std::endl;
1.343 +
1.344 + typename Digraph::template NodeMap<int> nodes(g);
1.345 + int i = 1;
1.346 + for(NodeIt v(g); v != INVALID; ++v) {
1.347 + nodes.set(v, i);
1.348 + ++i;
1.349 + }
1.350 + for(ArcIt e(g); e != INVALID; ++e) {
1.351 + os << "a " << nodes[g.source(e)] << " " << nodes[g.target(e)]
1.352 + << std::endl;
1.353 + }
1.354 + }
1.355 +
1.356 + /// @}
1.357 +
1.358 +} //namespace lemon
1.359 +
1.360 +#endif //LEMON_DIMACS_H