1 /* -*- mode: C++; indent-tabs-mode: nil; -*-
3 * This file is a part of LEMON, a generic C++ optimization library.
5 * Copyright (C) 2003-2009
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
26 #include <lemon/maps.h>
27 #include <lemon/error.h>
29 /// \ingroup dimacs_group
31 /// \brief DIMACS file format reader.
35 /// \addtogroup dimacs_group
38 /// DIMACS file type descriptor.
39 struct DimacsDescriptor
44 NONE, MIN, MAX, SP, MAT
48 ///The number of nodes in the graph
50 ///The number of edges in the graph
53 /// Constructor. Sets the type to NONE.
54 DimacsDescriptor() : type(NONE) {}
57 ///Discover the type of a DIMACS file
59 ///It starts seeking the beginning of the file for the problem type
60 ///and size info. The found data is returned in a special struct
61 ///that can be evaluated and passed to the appropriate reader
63 DimacsDescriptor dimacsType(std::istream& is)
66 std::string problem,str;
73 if(is >> problem >> r.nodeNum >> r.edgeNum)
77 if(problem=="min") r.type=DimacsDescriptor::MIN;
78 else if(problem=="max") r.type=DimacsDescriptor::MAX;
79 else if(problem=="sp") r.type=DimacsDescriptor::SP;
80 else if(problem=="mat") r.type=DimacsDescriptor::MAT;
81 else throw FormatError("Unknown problem type");
86 throw FormatError("Missing or wrong problem type declaration.");
94 throw FormatError("Unknown DIMACS declaration.");
96 throw FormatError("Missing problem type declaration.");
101 /// DIMACS minimum cost flow reader function.
103 /// This function reads a minimum cost flow instance from DIMACS format,
104 /// i.e. from a DIMACS file having a line starting with
108 /// At the beginning, \c g is cleared by \c g.clear(). The supply
109 /// amount of the nodes are written to the \c supply node map
110 /// (they are signed values). The lower bounds, capacities and costs
111 /// of the arcs are written to the \c lower, \c capacity and \c cost
114 /// If the capacity of an arc is less than the lower bound, it will
115 /// be set to "infinite" instead. The actual value of "infinite" is
116 /// contolled by the \c infty parameter. If it is 0 (the default value),
117 /// \c std::numeric_limits<Capacity>::infinity() will be used if available,
118 /// \c std::numeric_limits<Capacity>::max() otherwise. If \c infty is set to
119 /// a non-zero value, that value will be used as "infinite".
121 /// If the file type was previously evaluated by dimacsType(), then
122 /// the descriptor struct should be given by the \c desc parameter.
123 template <typename Digraph, typename LowerMap,
124 typename CapacityMap, typename CostMap,
126 void readDimacsMin(std::istream& is,
129 CapacityMap& capacity,
132 typename CapacityMap::Value infty = 0,
133 DimacsDescriptor desc=DimacsDescriptor())
136 std::vector<typename Digraph::Node> nodes;
137 typename Digraph::Arc e;
138 std::string problem, str;
141 if(desc.type==DimacsDescriptor::NONE) desc=dimacsType(is);
142 if(desc.type!=DimacsDescriptor::MIN)
143 throw FormatError("Problem type mismatch");
145 nodes.resize(desc.nodeNum + 1);
146 for (int k = 1; k <= desc.nodeNum; ++k) {
147 nodes[k] = g.addNode();
148 supply.set(nodes[k], 0);
151 typename SupplyMap::Value sup;
152 typename CapacityMap::Value low;
153 typename CapacityMap::Value cap;
154 typename CostMap::Value co;
155 typedef typename CapacityMap::Value Capacity;
157 infty = std::numeric_limits<Capacity>::has_infinity ?
158 std::numeric_limits<Capacity>::infinity() :
159 std::numeric_limits<Capacity>::max();
163 case 'c': // comment line
166 case 'n': // node definition line
169 supply.set(nodes[i], sup);
171 case 'a': // arc definition line
172 is >> i >> j >> low >> cap >> co;
174 e = g.addArc(nodes[i], nodes[j]);
177 capacity.set(e, cap);
179 capacity.set(e, infty);
186 template<typename Digraph, typename CapacityMap>
187 void _readDimacs(std::istream& is,
189 CapacityMap& capacity,
190 typename Digraph::Node &s,
191 typename Digraph::Node &t,
192 typename CapacityMap::Value infty = 0,
193 DimacsDescriptor desc=DimacsDescriptor()) {
196 std::vector<typename Digraph::Node> nodes;
197 typename Digraph::Arc e;
200 typename CapacityMap::Value _cap;
202 nodes.resize(desc.nodeNum + 1);
203 for (int k = 1; k <= desc.nodeNum; ++k) {
204 nodes[k] = g.addNode();
206 typedef typename CapacityMap::Value Capacity;
209 infty = std::numeric_limits<Capacity>::has_infinity ?
210 std::numeric_limits<Capacity>::infinity() :
211 std::numeric_limits<Capacity>::max();
215 case 'c': // comment line
218 case 'n': // node definition line
219 if (desc.type==DimacsDescriptor::SP) { // shortest path problem
224 if (desc.type==DimacsDescriptor::MAX) { // max flow problem
227 if (d == 's') s = nodes[i];
228 if (d == 't') t = nodes[i];
231 case 'a': // arc definition line
232 if (desc.type==DimacsDescriptor::SP) {
233 is >> i >> j >> _cap;
235 e = g.addArc(nodes[i], nodes[j]);
236 capacity.set(e, _cap);
238 else if (desc.type==DimacsDescriptor::MAX) {
239 is >> i >> j >> _cap;
241 e = g.addArc(nodes[i], nodes[j]);
243 capacity.set(e, _cap);
245 capacity.set(e, infty);
250 g.addArc(nodes[i], nodes[j]);
257 /// DIMACS maximum flow reader function.
259 /// This function reads a maximum flow instance from DIMACS format,
260 /// i.e. from a DIMACS file having a line starting with
264 /// At the beginning, \c g is cleared by \c g.clear(). The arc
265 /// capacities are written to the \c capacity arc map and \c s and
266 /// \c t are set to the source and the target nodes.
268 /// If the capacity of an arc is negative, it will
269 /// be set to "infinite" instead. The actual value of "infinite" is
270 /// contolled by the \c infty parameter. If it is 0 (the default value),
271 /// \c std::numeric_limits<Capacity>::infinity() will be used if available,
272 /// \c std::numeric_limits<Capacity>::max() otherwise. If \c infty is set to
273 /// a non-zero value, that value will be used as "infinite".
275 /// If the file type was previously evaluated by dimacsType(), then
276 /// the descriptor struct should be given by the \c desc parameter.
277 template<typename Digraph, typename CapacityMap>
278 void readDimacsMax(std::istream& is,
280 CapacityMap& capacity,
281 typename Digraph::Node &s,
282 typename Digraph::Node &t,
283 typename CapacityMap::Value infty = 0,
284 DimacsDescriptor desc=DimacsDescriptor()) {
285 if(desc.type==DimacsDescriptor::NONE) desc=dimacsType(is);
286 if(desc.type!=DimacsDescriptor::MAX)
287 throw FormatError("Problem type mismatch");
288 _readDimacs(is,g,capacity,s,t,infty,desc);
291 /// DIMACS shortest path reader function.
293 /// This function reads a shortest path instance from DIMACS format,
294 /// i.e. from a DIMACS file having a line starting with
298 /// At the beginning, \c g is cleared by \c g.clear(). The arc
299 /// lengths are written to the \c length arc map and \c s is set to the
302 /// If the file type was previously evaluated by dimacsType(), then
303 /// the descriptor struct should be given by the \c desc parameter.
304 template<typename Digraph, typename LengthMap>
305 void readDimacsSp(std::istream& is,
308 typename Digraph::Node &s,
309 DimacsDescriptor desc=DimacsDescriptor()) {
310 typename Digraph::Node t;
311 if(desc.type==DimacsDescriptor::NONE) desc=dimacsType(is);
312 if(desc.type!=DimacsDescriptor::SP)
313 throw FormatError("Problem type mismatch");
314 _readDimacs(is, g, length, s, t, 0, desc);
317 /// DIMACS capacitated digraph reader function.
319 /// This function reads an arc capacitated digraph instance from
320 /// DIMACS 'max' or 'sp' format.
321 /// At the beginning, \c g is cleared by \c g.clear()
322 /// and the arc capacities/lengths are written to the \c capacity
325 /// In case of the 'max' format, if the capacity of an arc is negative,
327 /// be set to "infinite" instead. The actual value of "infinite" is
328 /// contolled by the \c infty parameter. If it is 0 (the default value),
329 /// \c std::numeric_limits<Capacity>::infinity() will be used if available,
330 /// \c std::numeric_limits<Capacity>::max() otherwise. If \c infty is set to
331 /// a non-zero value, that value will be used as "infinite".
333 /// If the file type was previously evaluated by dimacsType(), then
334 /// the descriptor struct should be given by the \c desc parameter.
335 template<typename Digraph, typename CapacityMap>
336 void readDimacsCap(std::istream& is,
338 CapacityMap& capacity,
339 typename CapacityMap::Value infty = 0,
340 DimacsDescriptor desc=DimacsDescriptor()) {
341 typename Digraph::Node u,v;
342 if(desc.type==DimacsDescriptor::NONE) desc=dimacsType(is);
343 if(desc.type!=DimacsDescriptor::MAX && desc.type!=DimacsDescriptor::SP)
344 throw FormatError("Problem type mismatch");
345 _readDimacs(is, g, capacity, u, v, infty, desc);
348 template<typename Graph>
349 typename enable_if<lemon::UndirectedTagIndicator<Graph>,void>::type
350 _addArcEdge(Graph &g, typename Graph::Node s, typename Graph::Node t,
355 template<typename Graph>
356 typename disable_if<lemon::UndirectedTagIndicator<Graph>,void>::type
357 _addArcEdge(Graph &g, typename Graph::Node s, typename Graph::Node t,
363 /// DIMACS plain (di)graph reader function.
365 /// This function reads a (di)graph without any designated nodes and
366 /// maps from DIMACS format, i.e. from DIMACS files having a line
371 /// At the beginning, \c g is cleared by \c g.clear().
373 /// If the file type was previously evaluated by dimacsType(), then
374 /// the descriptor struct should be given by the \c desc parameter.
375 template<typename Graph>
376 void readDimacsMat(std::istream& is, Graph &g,
377 DimacsDescriptor desc=DimacsDescriptor())
379 if(desc.type==DimacsDescriptor::NONE) desc=dimacsType(is);
380 if(desc.type!=DimacsDescriptor::MAT)
381 throw FormatError("Problem type mismatch");
384 std::vector<typename Graph::Node> nodes;
388 nodes.resize(desc.nodeNum + 1);
389 for (int k = 1; k <= desc.nodeNum; ++k) {
390 nodes[k] = g.addNode();
395 case 'c': // comment line
398 case 'n': // node definition line
400 case 'a': // arc definition line
403 _addArcEdge(g,nodes[i], nodes[j]);
409 /// DIMACS plain digraph writer function.
411 /// This function writes a digraph without any designated nodes and
412 /// maps into DIMACS format, i.e. into DIMACS file having a line
417 /// If \c comment is not empty, then it will be printed in the first line
419 template<typename Digraph>
420 void writeDimacsMat(std::ostream& os, const Digraph &g,
421 std::string comment="") {
422 typedef typename Digraph::NodeIt NodeIt;
423 typedef typename Digraph::ArcIt ArcIt;
426 os << "c " << comment << std::endl;
427 os << "p mat " << g.nodeNum() << " " << g.arcNum() << std::endl;
429 typename Digraph::template NodeMap<int> nodes(g);
431 for(NodeIt v(g); v != INVALID; ++v) {
435 for(ArcIt e(g); e != INVALID; ++e) {
436 os << "a " << nodes[g.source(e)] << " " << nodes[g.target(e)]
445 #endif //LEMON_DIMACS_H