1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/lemon/dimacs.h Thu Nov 05 15:50:01 2009 +0100
1.3 @@ -0,0 +1,448 @@
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-2009
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 <limits>
1.29 +#include <lemon/maps.h>
1.30 +#include <lemon/error.h>
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 + ///\brief DIMACS file type enum
1.44 + ///
1.45 + ///DIMACS file type enum.
1.46 + enum Type {
1.47 + NONE, ///< Undefined type.
1.48 + MIN, ///< DIMACS file type for minimum cost flow problems.
1.49 + MAX, ///< DIMACS file type for maximum flow problems.
1.50 + SP, ///< DIMACS file type for shostest path problems.
1.51 + MAT ///< DIMACS file type for plain graphs and matching problems.
1.52 + };
1.53 + ///The file type
1.54 + Type type;
1.55 + ///The number of nodes in the graph
1.56 + int nodeNum;
1.57 + ///The number of edges in the graph
1.58 + int edgeNum;
1.59 + int lineShift;
1.60 + ///Constructor. It sets the type to \c NONE.
1.61 + DimacsDescriptor() : type(NONE) {}
1.62 + };
1.63 +
1.64 + ///Discover the type of a DIMACS file
1.65 +
1.66 + ///This function starts seeking the beginning of the given file for the
1.67 + ///problem type and size info.
1.68 + ///The found data is returned in a special struct that can be evaluated
1.69 + ///and passed to the appropriate reader function.
1.70 + DimacsDescriptor dimacsType(std::istream& is)
1.71 + {
1.72 + DimacsDescriptor r;
1.73 + std::string problem,str;
1.74 + char c;
1.75 + r.lineShift=0;
1.76 + while (is >> c)
1.77 + switch(c)
1.78 + {
1.79 + case 'p':
1.80 + if(is >> problem >> r.nodeNum >> r.edgeNum)
1.81 + {
1.82 + getline(is, str);
1.83 + r.lineShift++;
1.84 + if(problem=="min") r.type=DimacsDescriptor::MIN;
1.85 + else if(problem=="max") r.type=DimacsDescriptor::MAX;
1.86 + else if(problem=="sp") r.type=DimacsDescriptor::SP;
1.87 + else if(problem=="mat") r.type=DimacsDescriptor::MAT;
1.88 + else throw FormatError("Unknown problem type");
1.89 + return r;
1.90 + }
1.91 + else
1.92 + {
1.93 + throw FormatError("Missing or wrong problem type declaration.");
1.94 + }
1.95 + break;
1.96 + case 'c':
1.97 + getline(is, str);
1.98 + r.lineShift++;
1.99 + break;
1.100 + default:
1.101 + throw FormatError("Unknown DIMACS declaration.");
1.102 + }
1.103 + throw FormatError("Missing problem type declaration.");
1.104 + }
1.105 +
1.106 +
1.107 + /// \brief DIMACS minimum cost flow reader function.
1.108 + ///
1.109 + /// This function reads a minimum cost flow instance from DIMACS format,
1.110 + /// i.e. from a DIMACS file having a line starting with
1.111 + /// \code
1.112 + /// p min
1.113 + /// \endcode
1.114 + /// At the beginning, \c g is cleared by \c g.clear(). The supply
1.115 + /// amount of the nodes are written to the \c supply node map
1.116 + /// (they are signed values). The lower bounds, capacities and costs
1.117 + /// of the arcs are written to the \c lower, \c capacity and \c cost
1.118 + /// arc maps.
1.119 + ///
1.120 + /// If the capacity of an arc is less than the lower bound, it will
1.121 + /// be set to "infinite" instead. The actual value of "infinite" is
1.122 + /// contolled by the \c infty parameter. If it is 0 (the default value),
1.123 + /// \c std::numeric_limits<Capacity>::infinity() will be used if available,
1.124 + /// \c std::numeric_limits<Capacity>::max() otherwise. If \c infty is set to
1.125 + /// a non-zero value, that value will be used as "infinite".
1.126 + ///
1.127 + /// If the file type was previously evaluated by dimacsType(), then
1.128 + /// the descriptor struct should be given by the \c dest parameter.
1.129 + template <typename Digraph, typename LowerMap,
1.130 + typename CapacityMap, typename CostMap,
1.131 + typename SupplyMap>
1.132 + void readDimacsMin(std::istream& is,
1.133 + Digraph &g,
1.134 + LowerMap& lower,
1.135 + CapacityMap& capacity,
1.136 + CostMap& cost,
1.137 + SupplyMap& supply,
1.138 + typename CapacityMap::Value infty = 0,
1.139 + DimacsDescriptor desc=DimacsDescriptor())
1.140 + {
1.141 + g.clear();
1.142 + std::vector<typename Digraph::Node> nodes;
1.143 + typename Digraph::Arc e;
1.144 + std::string problem, str;
1.145 + char c;
1.146 + int i, j;
1.147 + if(desc.type==DimacsDescriptor::NONE) desc=dimacsType(is);
1.148 + if(desc.type!=DimacsDescriptor::MIN)
1.149 + throw FormatError("Problem type mismatch");
1.150 +
1.151 + nodes.resize(desc.nodeNum + 1);
1.152 + for (int k = 1; k <= desc.nodeNum; ++k) {
1.153 + nodes[k] = g.addNode();
1.154 + supply.set(nodes[k], 0);
1.155 + }
1.156 +
1.157 + typename SupplyMap::Value sup;
1.158 + typename CapacityMap::Value low;
1.159 + typename CapacityMap::Value cap;
1.160 + typename CostMap::Value co;
1.161 + typedef typename CapacityMap::Value Capacity;
1.162 + if(infty==0)
1.163 + infty = std::numeric_limits<Capacity>::has_infinity ?
1.164 + std::numeric_limits<Capacity>::infinity() :
1.165 + std::numeric_limits<Capacity>::max();
1.166 +
1.167 + while (is >> c) {
1.168 + switch (c) {
1.169 + case 'c': // comment line
1.170 + getline(is, str);
1.171 + break;
1.172 + case 'n': // node definition line
1.173 + is >> i >> sup;
1.174 + getline(is, str);
1.175 + supply.set(nodes[i], sup);
1.176 + break;
1.177 + case 'a': // arc definition line
1.178 + is >> i >> j >> low >> cap >> co;
1.179 + getline(is, str);
1.180 + e = g.addArc(nodes[i], nodes[j]);
1.181 + lower.set(e, low);
1.182 + if (cap >= low)
1.183 + capacity.set(e, cap);
1.184 + else
1.185 + capacity.set(e, infty);
1.186 + cost.set(e, co);
1.187 + break;
1.188 + }
1.189 + }
1.190 + }
1.191 +
1.192 + template<typename Digraph, typename CapacityMap>
1.193 + void _readDimacs(std::istream& is,
1.194 + Digraph &g,
1.195 + CapacityMap& capacity,
1.196 + typename Digraph::Node &s,
1.197 + typename Digraph::Node &t,
1.198 + typename CapacityMap::Value infty = 0,
1.199 + DimacsDescriptor desc=DimacsDescriptor()) {
1.200 + g.clear();
1.201 + s=t=INVALID;
1.202 + std::vector<typename Digraph::Node> nodes;
1.203 + typename Digraph::Arc e;
1.204 + char c, d;
1.205 + int i, j;
1.206 + typename CapacityMap::Value _cap;
1.207 + std::string str;
1.208 + nodes.resize(desc.nodeNum + 1);
1.209 + for (int k = 1; k <= desc.nodeNum; ++k) {
1.210 + nodes[k] = g.addNode();
1.211 + }
1.212 + typedef typename CapacityMap::Value Capacity;
1.213 +
1.214 + if(infty==0)
1.215 + infty = std::numeric_limits<Capacity>::has_infinity ?
1.216 + std::numeric_limits<Capacity>::infinity() :
1.217 + std::numeric_limits<Capacity>::max();
1.218 +
1.219 + while (is >> c) {
1.220 + switch (c) {
1.221 + case 'c': // comment line
1.222 + getline(is, str);
1.223 + break;
1.224 + case 'n': // node definition line
1.225 + if (desc.type==DimacsDescriptor::SP) { // shortest path problem
1.226 + is >> i;
1.227 + getline(is, str);
1.228 + s = nodes[i];
1.229 + }
1.230 + if (desc.type==DimacsDescriptor::MAX) { // max flow problem
1.231 + is >> i >> d;
1.232 + getline(is, str);
1.233 + if (d == 's') s = nodes[i];
1.234 + if (d == 't') t = nodes[i];
1.235 + }
1.236 + break;
1.237 + case 'a': // arc definition line
1.238 + if (desc.type==DimacsDescriptor::SP) {
1.239 + is >> i >> j >> _cap;
1.240 + getline(is, str);
1.241 + e = g.addArc(nodes[i], nodes[j]);
1.242 + capacity.set(e, _cap);
1.243 + }
1.244 + else if (desc.type==DimacsDescriptor::MAX) {
1.245 + is >> i >> j >> _cap;
1.246 + getline(is, str);
1.247 + e = g.addArc(nodes[i], nodes[j]);
1.248 + if (_cap >= 0)
1.249 + capacity.set(e, _cap);
1.250 + else
1.251 + capacity.set(e, infty);
1.252 + }
1.253 + else {
1.254 + is >> i >> j;
1.255 + getline(is, str);
1.256 + g.addArc(nodes[i], nodes[j]);
1.257 + }
1.258 + break;
1.259 + }
1.260 + }
1.261 + }
1.262 +
1.263 + /// \brief DIMACS maximum flow reader function.
1.264 + ///
1.265 + /// This function reads a maximum flow instance from DIMACS format,
1.266 + /// i.e. from a DIMACS file having a line starting with
1.267 + /// \code
1.268 + /// p max
1.269 + /// \endcode
1.270 + /// At the beginning, \c g is cleared by \c g.clear(). The arc
1.271 + /// capacities are written to the \c capacity arc map and \c s and
1.272 + /// \c t are set to the source and the target nodes.
1.273 + ///
1.274 + /// If the capacity of an arc is negative, it will
1.275 + /// be set to "infinite" instead. The actual value of "infinite" is
1.276 + /// contolled by the \c infty parameter. If it is 0 (the default value),
1.277 + /// \c std::numeric_limits<Capacity>::infinity() will be used if available,
1.278 + /// \c std::numeric_limits<Capacity>::max() otherwise. If \c infty is set to
1.279 + /// a non-zero value, that value will be used as "infinite".
1.280 + ///
1.281 + /// If the file type was previously evaluated by dimacsType(), then
1.282 + /// the descriptor struct should be given by the \c dest parameter.
1.283 + template<typename Digraph, typename CapacityMap>
1.284 + void readDimacsMax(std::istream& is,
1.285 + Digraph &g,
1.286 + CapacityMap& capacity,
1.287 + typename Digraph::Node &s,
1.288 + typename Digraph::Node &t,
1.289 + typename CapacityMap::Value infty = 0,
1.290 + DimacsDescriptor desc=DimacsDescriptor()) {
1.291 + if(desc.type==DimacsDescriptor::NONE) desc=dimacsType(is);
1.292 + if(desc.type!=DimacsDescriptor::MAX)
1.293 + throw FormatError("Problem type mismatch");
1.294 + _readDimacs(is,g,capacity,s,t,infty,desc);
1.295 + }
1.296 +
1.297 + /// \brief DIMACS shortest path reader function.
1.298 + ///
1.299 + /// This function reads a shortest path instance from DIMACS format,
1.300 + /// i.e. from a DIMACS file having a line starting with
1.301 + /// \code
1.302 + /// p sp
1.303 + /// \endcode
1.304 + /// At the beginning, \c g is cleared by \c g.clear(). The arc
1.305 + /// lengths are written to the \c length arc map and \c s is set to the
1.306 + /// source node.
1.307 + ///
1.308 + /// If the file type was previously evaluated by dimacsType(), then
1.309 + /// the descriptor struct should be given by the \c dest parameter.
1.310 + template<typename Digraph, typename LengthMap>
1.311 + void readDimacsSp(std::istream& is,
1.312 + Digraph &g,
1.313 + LengthMap& length,
1.314 + typename Digraph::Node &s,
1.315 + DimacsDescriptor desc=DimacsDescriptor()) {
1.316 + typename Digraph::Node t;
1.317 + if(desc.type==DimacsDescriptor::NONE) desc=dimacsType(is);
1.318 + if(desc.type!=DimacsDescriptor::SP)
1.319 + throw FormatError("Problem type mismatch");
1.320 + _readDimacs(is, g, length, s, t, 0, desc);
1.321 + }
1.322 +
1.323 + /// \brief DIMACS capacitated digraph reader function.
1.324 + ///
1.325 + /// This function reads an arc capacitated digraph instance from
1.326 + /// DIMACS 'max' or 'sp' format.
1.327 + /// At the beginning, \c g is cleared by \c g.clear()
1.328 + /// and the arc capacities/lengths are written to the \c capacity
1.329 + /// arc map.
1.330 + ///
1.331 + /// In case of the 'max' format, if the capacity of an arc is negative,
1.332 + /// it will
1.333 + /// be set to "infinite" instead. The actual value of "infinite" is
1.334 + /// contolled by the \c infty parameter. If it is 0 (the default value),
1.335 + /// \c std::numeric_limits<Capacity>::infinity() will be used if available,
1.336 + /// \c std::numeric_limits<Capacity>::max() otherwise. If \c infty is set to
1.337 + /// a non-zero value, that value will be used as "infinite".
1.338 + ///
1.339 + /// If the file type was previously evaluated by dimacsType(), then
1.340 + /// the descriptor struct should be given by the \c dest parameter.
1.341 + template<typename Digraph, typename CapacityMap>
1.342 + void readDimacsCap(std::istream& is,
1.343 + Digraph &g,
1.344 + CapacityMap& capacity,
1.345 + typename CapacityMap::Value infty = 0,
1.346 + DimacsDescriptor desc=DimacsDescriptor()) {
1.347 + typename Digraph::Node u,v;
1.348 + if(desc.type==DimacsDescriptor::NONE) desc=dimacsType(is);
1.349 + if(desc.type!=DimacsDescriptor::MAX || desc.type!=DimacsDescriptor::SP)
1.350 + throw FormatError("Problem type mismatch");
1.351 + _readDimacs(is, g, capacity, u, v, infty, desc);
1.352 + }
1.353 +
1.354 + template<typename Graph>
1.355 + typename enable_if<lemon::UndirectedTagIndicator<Graph>,void>::type
1.356 + _addArcEdge(Graph &g, typename Graph::Node s, typename Graph::Node t,
1.357 + dummy<0> = 0)
1.358 + {
1.359 + g.addEdge(s,t);
1.360 + }
1.361 + template<typename Graph>
1.362 + typename disable_if<lemon::UndirectedTagIndicator<Graph>,void>::type
1.363 + _addArcEdge(Graph &g, typename Graph::Node s, typename Graph::Node t,
1.364 + dummy<1> = 1)
1.365 + {
1.366 + g.addArc(s,t);
1.367 + }
1.368 +
1.369 + /// \brief DIMACS plain (di)graph reader function.
1.370 + ///
1.371 + /// This function reads a plain (di)graph without any designated nodes
1.372 + /// and maps (e.g. a matching instance) from DIMACS format, i.e. from
1.373 + /// DIMACS files having a line starting with
1.374 + /// \code
1.375 + /// p mat
1.376 + /// \endcode
1.377 + /// At the beginning, \c g is cleared by \c g.clear().
1.378 + ///
1.379 + /// If the file type was previously evaluated by dimacsType(), then
1.380 + /// the descriptor struct should be given by the \c dest parameter.
1.381 + template<typename Graph>
1.382 + void readDimacsMat(std::istream& is, Graph &g,
1.383 + DimacsDescriptor desc=DimacsDescriptor())
1.384 + {
1.385 + if(desc.type==DimacsDescriptor::NONE) desc=dimacsType(is);
1.386 + if(desc.type!=DimacsDescriptor::MAT)
1.387 + throw FormatError("Problem type mismatch");
1.388 +
1.389 + g.clear();
1.390 + std::vector<typename Graph::Node> nodes;
1.391 + char c;
1.392 + int i, j;
1.393 + std::string str;
1.394 + nodes.resize(desc.nodeNum + 1);
1.395 + for (int k = 1; k <= desc.nodeNum; ++k) {
1.396 + nodes[k] = g.addNode();
1.397 + }
1.398 +
1.399 + while (is >> c) {
1.400 + switch (c) {
1.401 + case 'c': // comment line
1.402 + getline(is, str);
1.403 + break;
1.404 + case 'n': // node definition line
1.405 + break;
1.406 + case 'a': // arc definition line
1.407 + is >> i >> j;
1.408 + getline(is, str);
1.409 + _addArcEdge(g,nodes[i], nodes[j]);
1.410 + break;
1.411 + }
1.412 + }
1.413 + }
1.414 +
1.415 + /// DIMACS plain digraph writer function.
1.416 + ///
1.417 + /// This function writes a digraph without any designated nodes and
1.418 + /// maps into DIMACS format, i.e. into DIMACS file having a line
1.419 + /// starting with
1.420 + /// \code
1.421 + /// p mat
1.422 + /// \endcode
1.423 + /// If \c comment is not empty, then it will be printed in the first line
1.424 + /// prefixed by 'c'.
1.425 + template<typename Digraph>
1.426 + void writeDimacsMat(std::ostream& os, const Digraph &g,
1.427 + std::string comment="") {
1.428 + typedef typename Digraph::NodeIt NodeIt;
1.429 + typedef typename Digraph::ArcIt ArcIt;
1.430 +
1.431 + if(!comment.empty())
1.432 + os << "c " << comment << std::endl;
1.433 + os << "p mat " << g.nodeNum() << " " << g.arcNum() << std::endl;
1.434 +
1.435 + typename Digraph::template NodeMap<int> nodes(g);
1.436 + int i = 1;
1.437 + for(NodeIt v(g); v != INVALID; ++v) {
1.438 + nodes.set(v, i);
1.439 + ++i;
1.440 + }
1.441 + for(ArcIt e(g); e != INVALID; ++e) {
1.442 + os << "a " << nodes[g.source(e)] << " " << nodes[g.target(e)]
1.443 + << std::endl;
1.444 + }
1.445 + }
1.446 +
1.447 + /// @}
1.448 +
1.449 +} //namespace lemon
1.450 +
1.451 +#endif //LEMON_DIMACS_H