1 /* -*- mode: C++; indent-tabs-mode: nil; -*-
3 * This file is a part of LEMON, a generic C++ optimization library.
5 * Copyright (C) 2003-2008
6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
7 * (Egervary Research Group on Combinatorial Optimization, EGRES).
9 * Permission to use, modify and distribute this software is granted
10 * provided that this copyright notice appears in all copies. For
11 * precise terms see the accompanying LICENSE file.
13 * This software is provided "AS IS" with no warranty of any kind,
14 * express or implied, and with no claim as to its suitability for any
19 #ifndef LEMON_DIMACS_H
20 #define LEMON_DIMACS_H
25 #include <lemon/maps.h>
26 #include <lemon/error.h>
28 /// \ingroup dimacs_group
30 /// \brief DIMACS file format reader.
34 ///@defgroup dimacs_group DIMACS format
35 ///\brief Read and write files in DIMACS format
37 ///Tools to read a digraph from or write it to a file in DIMACS format
41 /// \addtogroup dimacs_group
45 /// DIMACS file type descriptor.
46 struct DimacsDescriptor
51 NONE, MIN, MAX, SP, MAT
55 ///The number of nodes on the graph
57 ///The number of edges on the graph
60 /// Constructor. Sets the type to NONE.
61 DimacsDescriptor() : type(NONE) {}
64 ///Discover the type of a DIMACS file
66 ///It starts seeking the begining of the file for the problem type
67 ///and size info. The found date is returned in a special struct
68 ///that can be evaluated and passed to the appropriate reader
70 DimacsDescriptor dimacsType(std::istream& is)
73 std::string problem,str;
80 if(is >> problem >> r.nodeNum >> r.edgeNum)
84 if(problem=="min") r.type=DimacsDescriptor::MIN;
85 else if(problem=="max") r.type=DimacsDescriptor::MAX;
86 else if(problem=="sp") r.type=DimacsDescriptor::SP;
87 else if(problem=="mat") r.type=DimacsDescriptor::MAT;
88 else throw FormatError("Unknown problem type");
93 throw FormatError("Missing or wrong problem type declaration.");
101 throw FormatError("Unknown DIMACS declaration.");
103 throw FormatError("Missing problem type declaration.");
108 /// DIMACS min cost flow reader function.
110 /// This function reads a min cost flow instance from DIMACS format,
111 /// i.e. from DIMACS files having a line starting with
115 /// At the beginning, \c g is cleared by \c g.clear(). The supply
116 /// amount of the nodes are written to \c supply (signed). The
117 /// lower bounds, capacities and costs of the arcs are written to
118 /// \c lower, \c capacity and \c cost.
120 /// If the file type was previously evaluated by dimacsType(), then
121 /// the descriptor struct should be given by the \c dest parameter.
122 template <typename Digraph, typename LowerMap,
123 typename CapacityMap, typename CostMap,
125 void readDimacsMin(std::istream& is,
128 CapacityMap& capacity,
131 DimacsDescriptor desc=DimacsDescriptor())
134 std::vector<typename Digraph::Node> nodes;
135 typename Digraph::Arc e;
136 std::string problem, str;
139 if(desc.type==DimacsDescriptor::NONE) desc=dimacsType(is);
140 if(desc.type!=DimacsDescriptor::MIN)
141 throw FormatError("Problem type mismatch");
143 nodes.resize(desc.nodeNum + 1);
144 for (int k = 1; k <= desc.nodeNum; ++k) {
145 nodes[k] = g.addNode();
146 supply.set(nodes[k], 0);
149 typename SupplyMap::Value sup;
150 typename CapacityMap::Value low;
151 typename CapacityMap::Value cap;
152 typename CostMap::Value co;
155 case 'c': // comment line
158 case 'n': // node definition line
161 supply.set(nodes[i], sup);
163 case 'a': // arc (arc) definition line
164 is >> i >> j >> low >> cap >> co;
166 e = g.addArc(nodes[i], nodes[j]);
169 capacity.set(e, cap);
178 template<typename Digraph, typename CapacityMap>
179 void _readDimacs(std::istream& is,
181 CapacityMap& capacity,
182 typename Digraph::Node &s,
183 typename Digraph::Node &t,
184 DimacsDescriptor desc=DimacsDescriptor()) {
187 std::vector<typename Digraph::Node> nodes;
188 typename Digraph::Arc e;
191 typename CapacityMap::Value _cap;
193 nodes.resize(desc.nodeNum + 1);
194 for (int k = 1; k <= desc.nodeNum; ++k) {
195 nodes[k] = g.addNode();
200 case 'c': // comment line
203 case 'n': // node definition line
204 if (desc.type==DimacsDescriptor::SP) { // shortest path problem
209 if (desc.type==DimacsDescriptor::MAX) { // max flow problem
212 if (d == 's') s = nodes[i];
213 if (d == 't') t = nodes[i];
216 case 'a': // arc (arc) definition line
217 if (desc.type==DimacsDescriptor::SP ||
218 desc.type==DimacsDescriptor::MAX) {
219 is >> i >> j >> _cap;
221 e = g.addArc(nodes[i], nodes[j]);
222 capacity.set(e, _cap);
226 g.addArc(nodes[i], nodes[j]);
233 /// DIMACS max flow reader function.
235 /// This function reads a max flow instance from DIMACS format,
236 /// i.e. from DIMACS files having a line starting with
240 /// At the beginning, \c g is cleared by \c g.clear(). The arc
241 /// capacities are written to \c capacity and \c s and \c t are
242 /// set to the source and the target nodes.
244 /// If the file type was previously evaluated by dimacsType(), then
245 /// the descriptor struct should be given by the \c dest parameter.
246 template<typename Digraph, typename CapacityMap>
247 void readDimacsMax(std::istream& is,
249 CapacityMap& capacity,
250 typename Digraph::Node &s,
251 typename Digraph::Node &t,
252 DimacsDescriptor desc=DimacsDescriptor()) {
253 if(desc.type==DimacsDescriptor::NONE) desc=dimacsType(is);
254 if(desc.type!=DimacsDescriptor::MAX)
255 throw FormatError("Problem type mismatch");
256 _readDimacs(is,g,capacity,s,t,desc);
259 /// DIMACS shortest path reader function.
261 /// This function reads a shortest path instance from DIMACS format,
262 /// i.e. from DIMACS files having a line starting with
266 /// At the beginning, \c g is cleared by \c g.clear(). The arc
267 /// lengths are written to \c lenght and \c s is set to the
270 /// If the file type was previously evaluated by dimacsType(), then
271 /// the descriptor struct should be given by the \c dest parameter.
272 template<typename Digraph, typename LengthMap>
273 void readDimacsSp(std::istream& is,
276 typename Digraph::Node &s,
277 DimacsDescriptor desc=DimacsDescriptor()) {
278 typename Digraph::Node t;
279 if(desc.type==DimacsDescriptor::NONE) desc=dimacsType(is);
280 if(desc.type!=DimacsDescriptor::SP)
281 throw FormatError("Problem type mismatch");
282 _readDimacs(is, g, length, s, t,desc);
285 /// DIMACS capacitated digraph reader function.
287 /// This function reads an arc capacitated digraph instance from
288 /// DIMACS 'mat' or 'sp' format.
289 /// At the beginning, \c g is cleared by \c g.clear()
290 /// and the arc capacities/lengths are written to \c capacity.
292 /// If the file type was previously evaluated by dimacsType(), then
293 /// the descriptor struct should be given by the \c dest parameter.
294 template<typename Digraph, typename CapacityMap>
295 void readDimacsCap(std::istream& is,
297 CapacityMap& capacity,
298 DimacsDescriptor desc=DimacsDescriptor()) {
299 typename Digraph::Node u,v;
300 if(desc.type==DimacsDescriptor::NONE) desc=dimacsType(is);
301 if(desc.type!=DimacsDescriptor::MAX || desc.type!=DimacsDescriptor::SP)
302 throw FormatError("Problem type mismatch");
303 _readDimacs(is, g, capacity, u, v, desc);
306 /// DIMACS plain digraph reader function.
308 /// This function reads a digraph without any designated nodes and
309 /// maps from DIMACS format, i.e. from DIMACS files having a line
314 /// At the beginning, \c g is cleared by \c g.clear().
316 /// If the file type was previously evaluated by dimacsType(), then
317 /// the descriptor struct should be given by the \c dest parameter.
318 template<typename Digraph>
319 void readDimacsMat(std::istream& is, Digraph &g,
320 DimacsDescriptor desc=DimacsDescriptor()) {
321 typename Digraph::Node u,v;
322 NullMap<typename Digraph::Arc, int> n;
323 if(desc.type==DimacsDescriptor::NONE) desc=dimacsType(is);
324 if(desc.type!=DimacsDescriptor::MAT)
325 throw FormatError("Problem type mismatch");
326 _readDimacs(is, g, n, u, v, desc);
329 /// DIMACS plain digraph writer function.
331 /// This function writes a digraph without any designated nodes and
332 /// maps into DIMACS format, i.e. into DIMACS file having a line
337 /// If \c comment is not empty, then it will be printed in the first line
339 template<typename Digraph>
340 void writeDimacsMat(std::ostream& os, const Digraph &g,
341 std::string comment="") {
342 typedef typename Digraph::NodeIt NodeIt;
343 typedef typename Digraph::ArcIt ArcIt;
346 os << "c " << comment << std::endl;
347 os << "p mat " << g.nodeNum() << " " << g.arcNum() << std::endl;
349 typename Digraph::template NodeMap<int> nodes(g);
351 for(NodeIt v(g); v != INVALID; ++v) {
355 for(ArcIt e(g); e != INVALID; ++e) {
356 os << "a " << nodes[g.source(e)] << " " << nodes[g.target(e)]
365 #endif //LEMON_DIMACS_H