1.1 --- a/.hgignore Sun Nov 30 00:51:20 2008 +0100
1.2 +++ b/.hgignore Sun Nov 30 09:39:34 2008 +0000
1.3 @@ -36,6 +36,7 @@
1.4 ^build-aux/.*
1.5 ^objs.*/.*
1.6 ^test/[a-z_]*$
1.7 +^tools/[a-z-_]*$
1.8 ^demo/.*_demo$
1.9 ^build/.*
1.10 ^doc/gen-images/.*
2.1 --- a/doc/groups.dox Sun Nov 30 00:51:20 2008 +0100
2.2 +++ b/doc/groups.dox Sun Nov 30 09:39:34 2008 +0000
2.3 @@ -482,9 +482,18 @@
2.4 */
2.5
2.6 /**
2.7 +@defgroup dimacs_group DIMACS format
2.8 +@ingroup io_group
2.9 +\brief Read and write files in DIMACS format
2.10 +
2.11 +Tools to read a digraph from or write it to a file in DIMACS format data.
2.12 +*/
2.13 +
2.14 +/**
2.15 @defgroup nauty_group NAUTY Format
2.16 @ingroup io_group
2.17 \brief Read \e Nauty format
2.18 +
2.19 Tool to read graphs from \e Nauty format data.
2.20 */
2.21
3.1 --- a/lemon/Makefile.am Sun Nov 30 00:51:20 2008 +0100
3.2 +++ b/lemon/Makefile.am Sun Nov 30 09:39:34 2008 +0000
3.3 @@ -27,6 +27,7 @@
3.4 lemon/dfs.h \
3.5 lemon/dijkstra.h \
3.6 lemon/dim2.h \
3.7 + lemon/dimacs.h \
3.8 lemon/elevator.h \
3.9 lemon/error.h \
3.10 lemon/full_graph.h \
4.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
4.2 +++ b/lemon/dimacs.h Sun Nov 30 09:39:34 2008 +0000
4.3 @@ -0,0 +1,357 @@
4.4 +/* -*- mode: C++; indent-tabs-mode: nil; -*-
4.5 + *
4.6 + * This file is a part of LEMON, a generic C++ optimization library.
4.7 + *
4.8 + * Copyright (C) 2003-2008
4.9 + * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
4.10 + * (Egervary Research Group on Combinatorial Optimization, EGRES).
4.11 + *
4.12 + * Permission to use, modify and distribute this software is granted
4.13 + * provided that this copyright notice appears in all copies. For
4.14 + * precise terms see the accompanying LICENSE file.
4.15 + *
4.16 + * This software is provided "AS IS" with no warranty of any kind,
4.17 + * express or implied, and with no claim as to its suitability for any
4.18 + * purpose.
4.19 + *
4.20 + */
4.21 +
4.22 +#ifndef LEMON_DIMACS_H
4.23 +#define LEMON_DIMACS_H
4.24 +
4.25 +#include <iostream>
4.26 +#include <string>
4.27 +#include <vector>
4.28 +#include <lemon/maps.h>
4.29 +#include <lemon/error.h>
4.30 +
4.31 +/// \ingroup dimacs_group
4.32 +/// \file
4.33 +/// \brief DIMACS file format reader.
4.34 +
4.35 +namespace lemon {
4.36 +
4.37 + /// \addtogroup dimacs_group
4.38 + /// @{
4.39 +
4.40 + /// DIMACS file type descriptor.
4.41 + struct DimacsDescriptor
4.42 + {
4.43 + ///File type enum
4.44 + enum Type
4.45 + {
4.46 + NONE, MIN, MAX, SP, MAT
4.47 + };
4.48 + ///The file type
4.49 + Type type;
4.50 + ///The number of nodes in the graph
4.51 + int nodeNum;
4.52 + ///The number of edges in the graph
4.53 + int edgeNum;
4.54 + int lineShift;
4.55 + /// Constructor. Sets the type to NONE.
4.56 + DimacsDescriptor() : type(NONE) {}
4.57 + };
4.58 +
4.59 + ///Discover the type of a DIMACS file
4.60 +
4.61 + ///It starts seeking the begining of the file for the problem type
4.62 + ///and size info. The found data is returned in a special struct
4.63 + ///that can be evaluated and passed to the appropriate reader
4.64 + ///function.
4.65 + DimacsDescriptor dimacsType(std::istream& is)
4.66 + {
4.67 + DimacsDescriptor r;
4.68 + std::string problem,str;
4.69 + char c;
4.70 + r.lineShift=0;
4.71 + while (is >> c)
4.72 + switch(c)
4.73 + {
4.74 + case 'p':
4.75 + if(is >> problem >> r.nodeNum >> r.edgeNum)
4.76 + {
4.77 + getline(is, str);
4.78 + r.lineShift++;
4.79 + if(problem=="min") r.type=DimacsDescriptor::MIN;
4.80 + else if(problem=="max") r.type=DimacsDescriptor::MAX;
4.81 + else if(problem=="sp") r.type=DimacsDescriptor::SP;
4.82 + else if(problem=="mat") r.type=DimacsDescriptor::MAT;
4.83 + else throw FormatError("Unknown problem type");
4.84 + return r;
4.85 + }
4.86 + else
4.87 + {
4.88 + throw FormatError("Missing or wrong problem type declaration.");
4.89 + }
4.90 + break;
4.91 + case 'c':
4.92 + getline(is, str);
4.93 + r.lineShift++;
4.94 + break;
4.95 + default:
4.96 + throw FormatError("Unknown DIMACS declaration.");
4.97 + }
4.98 + throw FormatError("Missing problem type declaration.");
4.99 + }
4.100 +
4.101 +
4.102 +
4.103 + /// DIMACS minimum cost flow reader function.
4.104 + ///
4.105 + /// This function reads a minimum cost flow instance from DIMACS format,
4.106 + /// i.e. from a DIMACS file having a line starting with
4.107 + /// \code
4.108 + /// p min
4.109 + /// \endcode
4.110 + /// At the beginning, \c g is cleared by \c g.clear(). The supply
4.111 + /// amount of the nodes are written to \c supply (signed). The
4.112 + /// lower bounds, capacities and costs of the arcs are written to
4.113 + /// \c lower, \c capacity and \c cost.
4.114 + ///
4.115 + /// If the file type was previously evaluated by dimacsType(), then
4.116 + /// the descriptor struct should be given by the \c dest parameter.
4.117 + template <typename Digraph, typename LowerMap,
4.118 + typename CapacityMap, typename CostMap,
4.119 + typename SupplyMap>
4.120 + void readDimacsMin(std::istream& is,
4.121 + Digraph &g,
4.122 + LowerMap& lower,
4.123 + CapacityMap& capacity,
4.124 + CostMap& cost,
4.125 + SupplyMap& supply,
4.126 + DimacsDescriptor desc=DimacsDescriptor())
4.127 + {
4.128 + g.clear();
4.129 + std::vector<typename Digraph::Node> nodes;
4.130 + typename Digraph::Arc e;
4.131 + std::string problem, str;
4.132 + char c;
4.133 + int i, j;
4.134 + if(desc.type==DimacsDescriptor::NONE) desc=dimacsType(is);
4.135 + if(desc.type!=DimacsDescriptor::MIN)
4.136 + throw FormatError("Problem type mismatch");
4.137 +
4.138 + nodes.resize(desc.nodeNum + 1);
4.139 + for (int k = 1; k <= desc.nodeNum; ++k) {
4.140 + nodes[k] = g.addNode();
4.141 + supply.set(nodes[k], 0);
4.142 + }
4.143 +
4.144 + typename SupplyMap::Value sup;
4.145 + typename CapacityMap::Value low;
4.146 + typename CapacityMap::Value cap;
4.147 + typename CostMap::Value co;
4.148 + while (is >> c) {
4.149 + switch (c) {
4.150 + case 'c': // comment line
4.151 + getline(is, str);
4.152 + break;
4.153 + case 'n': // node definition line
4.154 + is >> i >> sup;
4.155 + getline(is, str);
4.156 + supply.set(nodes[i], sup);
4.157 + break;
4.158 + case 'a': // arc (arc) definition line
4.159 + is >> i >> j >> low >> cap >> co;
4.160 + getline(is, str);
4.161 + e = g.addArc(nodes[i], nodes[j]);
4.162 + lower.set(e, low);
4.163 + if (cap >= 0)
4.164 + capacity.set(e, cap);
4.165 + else
4.166 + capacity.set(e, -1);
4.167 + cost.set(e, co);
4.168 + break;
4.169 + }
4.170 + }
4.171 + }
4.172 +
4.173 + template<typename Digraph, typename CapacityMap>
4.174 + void _readDimacs(std::istream& is,
4.175 + Digraph &g,
4.176 + CapacityMap& capacity,
4.177 + typename Digraph::Node &s,
4.178 + typename Digraph::Node &t,
4.179 + DimacsDescriptor desc=DimacsDescriptor()) {
4.180 + g.clear();
4.181 + s=t=INVALID;
4.182 + std::vector<typename Digraph::Node> nodes;
4.183 + typename Digraph::Arc e;
4.184 + char c, d;
4.185 + int i, j;
4.186 + typename CapacityMap::Value _cap;
4.187 + std::string str;
4.188 + nodes.resize(desc.nodeNum + 1);
4.189 + for (int k = 1; k <= desc.nodeNum; ++k) {
4.190 + nodes[k] = g.addNode();
4.191 + }
4.192 +
4.193 + while (is >> c) {
4.194 + switch (c) {
4.195 + case 'c': // comment line
4.196 + getline(is, str);
4.197 + break;
4.198 + case 'n': // node definition line
4.199 + if (desc.type==DimacsDescriptor::SP) { // shortest path problem
4.200 + is >> i;
4.201 + getline(is, str);
4.202 + s = nodes[i];
4.203 + }
4.204 + if (desc.type==DimacsDescriptor::MAX) { // max flow problem
4.205 + is >> i >> d;
4.206 + getline(is, str);
4.207 + if (d == 's') s = nodes[i];
4.208 + if (d == 't') t = nodes[i];
4.209 + }
4.210 + break;
4.211 + case 'a': // arc (arc) definition line
4.212 + if (desc.type==DimacsDescriptor::SP ||
4.213 + desc.type==DimacsDescriptor::MAX) {
4.214 + is >> i >> j >> _cap;
4.215 + getline(is, str);
4.216 + e = g.addArc(nodes[i], nodes[j]);
4.217 + capacity.set(e, _cap);
4.218 + } else {
4.219 + is >> i >> j;
4.220 + getline(is, str);
4.221 + g.addArc(nodes[i], nodes[j]);
4.222 + }
4.223 + break;
4.224 + }
4.225 + }
4.226 + }
4.227 +
4.228 + /// DIMACS maximum flow reader function.
4.229 + ///
4.230 + /// This function reads a maximum flow instance from DIMACS format,
4.231 + /// i.e. from a DIMACS file having a line starting with
4.232 + /// \code
4.233 + /// p max
4.234 + /// \endcode
4.235 + /// At the beginning, \c g is cleared by \c g.clear(). The arc
4.236 + /// capacities are written to \c capacity and \c s and \c t are
4.237 + /// set to the source and the target nodes.
4.238 + ///
4.239 + /// If the file type was previously evaluated by dimacsType(), then
4.240 + /// the descriptor struct should be given by the \c dest parameter.
4.241 + template<typename Digraph, typename CapacityMap>
4.242 + void readDimacsMax(std::istream& is,
4.243 + Digraph &g,
4.244 + CapacityMap& capacity,
4.245 + typename Digraph::Node &s,
4.246 + typename Digraph::Node &t,
4.247 + DimacsDescriptor desc=DimacsDescriptor()) {
4.248 + if(desc.type==DimacsDescriptor::NONE) desc=dimacsType(is);
4.249 + if(desc.type!=DimacsDescriptor::MAX)
4.250 + throw FormatError("Problem type mismatch");
4.251 + _readDimacs(is,g,capacity,s,t,desc);
4.252 + }
4.253 +
4.254 + /// DIMACS shortest path reader function.
4.255 + ///
4.256 + /// This function reads a shortest path instance from DIMACS format,
4.257 + /// i.e. from a DIMACS file having a line starting with
4.258 + /// \code
4.259 + /// p sp
4.260 + /// \endcode
4.261 + /// At the beginning, \c g is cleared by \c g.clear(). The arc
4.262 + /// lengths are written to \c length and \c s is set to the
4.263 + /// source node.
4.264 + ///
4.265 + /// If the file type was previously evaluated by dimacsType(), then
4.266 + /// the descriptor struct should be given by the \c dest parameter.
4.267 + template<typename Digraph, typename LengthMap>
4.268 + void readDimacsSp(std::istream& is,
4.269 + Digraph &g,
4.270 + LengthMap& length,
4.271 + typename Digraph::Node &s,
4.272 + DimacsDescriptor desc=DimacsDescriptor()) {
4.273 + typename Digraph::Node t;
4.274 + if(desc.type==DimacsDescriptor::NONE) desc=dimacsType(is);
4.275 + if(desc.type!=DimacsDescriptor::SP)
4.276 + throw FormatError("Problem type mismatch");
4.277 + _readDimacs(is, g, length, s, t,desc);
4.278 + }
4.279 +
4.280 + /// DIMACS capacitated digraph reader function.
4.281 + ///
4.282 + /// This function reads an arc capacitated digraph instance from
4.283 + /// DIMACS 'mat' or 'sp' format.
4.284 + /// At the beginning, \c g is cleared by \c g.clear()
4.285 + /// and the arc capacities/lengths are written to \c capacity.
4.286 + ///
4.287 + /// If the file type was previously evaluated by dimacsType(), then
4.288 + /// the descriptor struct should be given by the \c dest parameter.
4.289 + template<typename Digraph, typename CapacityMap>
4.290 + void readDimacsCap(std::istream& is,
4.291 + Digraph &g,
4.292 + CapacityMap& capacity,
4.293 + DimacsDescriptor desc=DimacsDescriptor()) {
4.294 + typename Digraph::Node u,v;
4.295 + if(desc.type==DimacsDescriptor::NONE) desc=dimacsType(is);
4.296 + if(desc.type!=DimacsDescriptor::MAX || desc.type!=DimacsDescriptor::SP)
4.297 + throw FormatError("Problem type mismatch");
4.298 + _readDimacs(is, g, capacity, u, v, desc);
4.299 + }
4.300 +
4.301 + /// DIMACS plain digraph reader function.
4.302 + ///
4.303 + /// This function reads a digraph without any designated nodes and
4.304 + /// maps from DIMACS format, i.e. from DIMACS files having a line
4.305 + /// starting with
4.306 + /// \code
4.307 + /// p mat
4.308 + /// \endcode
4.309 + /// At the beginning, \c g is cleared by \c g.clear().
4.310 + ///
4.311 + /// If the file type was previously evaluated by dimacsType(), then
4.312 + /// the descriptor struct should be given by the \c dest parameter.
4.313 + template<typename Digraph>
4.314 + void readDimacsMat(std::istream& is, Digraph &g,
4.315 + DimacsDescriptor desc=DimacsDescriptor()) {
4.316 + typename Digraph::Node u,v;
4.317 + NullMap<typename Digraph::Arc, int> n;
4.318 + if(desc.type==DimacsDescriptor::NONE) desc=dimacsType(is);
4.319 + if(desc.type!=DimacsDescriptor::MAT)
4.320 + throw FormatError("Problem type mismatch");
4.321 + _readDimacs(is, g, n, u, v, desc);
4.322 + }
4.323 +
4.324 + /// DIMACS plain digraph writer function.
4.325 + ///
4.326 + /// This function writes a digraph without any designated nodes and
4.327 + /// maps into DIMACS format, i.e. into DIMACS file having a line
4.328 + /// starting with
4.329 + /// \code
4.330 + /// p mat
4.331 + /// \endcode
4.332 + /// If \c comment is not empty, then it will be printed in the first line
4.333 + /// prefixed by 'c'.
4.334 + template<typename Digraph>
4.335 + void writeDimacsMat(std::ostream& os, const Digraph &g,
4.336 + std::string comment="") {
4.337 + typedef typename Digraph::NodeIt NodeIt;
4.338 + typedef typename Digraph::ArcIt ArcIt;
4.339 +
4.340 + if(!comment.empty())
4.341 + os << "c " << comment << std::endl;
4.342 + os << "p mat " << g.nodeNum() << " " << g.arcNum() << std::endl;
4.343 +
4.344 + typename Digraph::template NodeMap<int> nodes(g);
4.345 + int i = 1;
4.346 + for(NodeIt v(g); v != INVALID; ++v) {
4.347 + nodes.set(v, i);
4.348 + ++i;
4.349 + }
4.350 + for(ArcIt e(g); e != INVALID; ++e) {
4.351 + os << "a " << nodes[g.source(e)] << " " << nodes[g.target(e)]
4.352 + << std::endl;
4.353 + }
4.354 + }
4.355 +
4.356 + /// @}
4.357 +
4.358 +} //namespace lemon
4.359 +
4.360 +#endif //LEMON_DIMACS_H
5.1 --- a/tools/Makefile.am Sun Nov 30 00:51:20 2008 +0100
5.2 +++ b/tools/Makefile.am Sun Nov 30 09:39:34 2008 +0000
5.3 @@ -1,6 +1,10 @@
5.4 if WANT_TOOLS
5.5
5.6 -bin_PROGRAMS +=
5.7 +bin_PROGRAMS += \
5.8 + tools/dimacs-to-lgf
5.9 +
5.10 dist_bin_SCRIPTS += tools/lemon-0.x-to-1.x.sh
5.11
5.12 endif WANT_TOOLS
5.13 +
5.14 +tools_dimacs_to_lgf_SOURCES = tools/dimacs-to-lgf.cc
6.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
6.2 +++ b/tools/dimacs-to-lgf.cc Sun Nov 30 09:39:34 2008 +0000
6.3 @@ -0,0 +1,149 @@
6.4 +/* -*- mode: C++; indent-tabs-mode: nil; -*-
6.5 + *
6.6 + * This file is a part of LEMON, a generic C++ optimization library.
6.7 + *
6.8 + * Copyright (C) 2003-2008
6.9 + * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
6.10 + * (Egervary Research Group on Combinatorial Optimization, EGRES).
6.11 + *
6.12 + * Permission to use, modify and distribute this software is granted
6.13 + * provided that this copyright notice appears in all copies. For
6.14 + * precise terms see the accompanying LICENSE file.
6.15 + *
6.16 + * This software is provided "AS IS" with no warranty of any kind,
6.17 + * express or implied, and with no claim as to its suitability for any
6.18 + * purpose.
6.19 + *
6.20 + */
6.21 +
6.22 +///\ingroup tools
6.23 +///\file
6.24 +///\brief DIMACS to LGF converter.
6.25 +///
6.26 +/// This program converts various DIMACS formats to the LEMON Digraph Format
6.27 +/// (LGF).
6.28 +///
6.29 +/// See
6.30 +/// \verbatim
6.31 +/// dimacs-to-lgf --help
6.32 +/// \endverbatim
6.33 +/// for more info on usage.
6.34 +///
6.35 +
6.36 +#include <iostream>
6.37 +#include <fstream>
6.38 +#include <cstring>
6.39 +
6.40 +#include <lemon/smart_graph.h>
6.41 +#include <lemon/dimacs.h>
6.42 +#include <lemon/lgf_writer.h>
6.43 +
6.44 +#include <lemon/arg_parser.h>
6.45 +#include <lemon/error.h>
6.46 +
6.47 +using namespace std;
6.48 +using namespace lemon;
6.49 +
6.50 +
6.51 +int main(int argc, const char *argv[]) {
6.52 + typedef SmartDigraph Digraph;
6.53 +
6.54 + typedef Digraph::Arc Arc;
6.55 + typedef Digraph::Node Node;
6.56 + typedef Digraph::ArcIt ArcIt;
6.57 + typedef Digraph::NodeIt NodeIt;
6.58 + typedef Digraph::ArcMap<double> DoubleArcMap;
6.59 + typedef Digraph::NodeMap<double> DoubleNodeMap;
6.60 +
6.61 + std::string inputName;
6.62 + std::string outputName;
6.63 +
6.64 + ArgParser ap(argc, argv);
6.65 + ap.other("[INFILE [OUTFILE]]",
6.66 + "If either the INFILE or OUTFILE file is missing the standard\n"
6.67 + " input/output will be used instead.")
6.68 + .run();
6.69 +
6.70 + ifstream input;
6.71 + ofstream output;
6.72 +
6.73 + switch(ap.files().size())
6.74 + {
6.75 + case 2:
6.76 + output.open(ap.files()[1].c_str());
6.77 + if (!output) {
6.78 + throw IoError("Cannot open the file for writing", ap.files()[1]);
6.79 + }
6.80 + case 1:
6.81 + input.open(ap.files()[0].c_str());
6.82 + if (!input) {
6.83 + throw IoError("File cannot be found", ap.files()[0]);
6.84 + }
6.85 + case 0:
6.86 + break;
6.87 + default:
6.88 + cerr << ap.commandName() << ": too many arguments\n";
6.89 + return 1;
6.90 + }
6.91 + istream& is = (ap.files().size()<1 ? cin : input);
6.92 + ostream& os = (ap.files().size()<2 ? cout : output);
6.93 +
6.94 + DimacsDescriptor desc = dimacsType(is);
6.95 + switch(desc.type)
6.96 + {
6.97 + case DimacsDescriptor::MIN:
6.98 + {
6.99 + Digraph digraph;
6.100 + DoubleArcMap lower(digraph), capacity(digraph), cost(digraph);
6.101 + DoubleNodeMap supply(digraph);
6.102 + readDimacsMin(is, digraph, lower, capacity, cost, supply, desc);
6.103 + DigraphWriter<Digraph>(digraph, os).
6.104 + nodeMap("supply", supply).
6.105 + arcMap("lower", lower).
6.106 + arcMap("capacity", capacity).
6.107 + arcMap("cost", cost).
6.108 + attribute("problem","min").
6.109 + run();
6.110 + }
6.111 + break;
6.112 + case DimacsDescriptor::MAX:
6.113 + {
6.114 + Digraph digraph;
6.115 + Node s, t;
6.116 + DoubleArcMap capacity(digraph);
6.117 + readDimacsMax(is, digraph, capacity, s, t, desc);
6.118 + DigraphWriter<Digraph>(digraph, os).
6.119 + arcMap("capacity", capacity).
6.120 + node("source", s).
6.121 + node("target", t).
6.122 + attribute("problem","max").
6.123 + run();
6.124 + }
6.125 + break;
6.126 + case DimacsDescriptor::SP:
6.127 + {
6.128 + Digraph digraph;
6.129 + Node s;
6.130 + DoubleArcMap capacity(digraph);
6.131 + readDimacsSp(is, digraph, capacity, s, desc);
6.132 + DigraphWriter<Digraph>(digraph, os).
6.133 + arcMap("capacity", capacity).
6.134 + node("source", s).
6.135 + attribute("problem","sp").
6.136 + run();
6.137 + }
6.138 + break;
6.139 + case DimacsDescriptor::MAT:
6.140 + {
6.141 + Digraph digraph;
6.142 + readDimacsMat(is, digraph,desc);
6.143 + DigraphWriter<Digraph>(digraph, os).
6.144 + attribute("problem","mat").
6.145 + run();
6.146 + }
6.147 + break;
6.148 + default:
6.149 + break;
6.150 + }
6.151 + return 0;
6.152 +}