COIN-OR::LEMON - Graph Library

source: lemon/lemon/dimacs.h @ 614:3314f58e7b25

Last change on this file since 614:3314f58e7b25 was 608:6e0525ec5355, checked in by Alpar Juttner <alpar@…>, 15 years ago

Accept negative values as unbounded capacity in dimacs readers (#243)
and some doc improvements.

File size: 14.3 KB
Line 
1/* -*- mode: C++; indent-tabs-mode: nil; -*-
2 *
3 * This file is a part of LEMON, a generic C++ optimization library.
4 *
5 * Copyright (C) 2003-2009
6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
7 * (Egervary Research Group on Combinatorial Optimization, EGRES).
8 *
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.
12 *
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
15 * purpose.
16 *
17 */
18
19#ifndef LEMON_DIMACS_H
20#define LEMON_DIMACS_H
21
22#include <iostream>
23#include <string>
24#include <vector>
25#include <limits>
26#include <lemon/maps.h>
27#include <lemon/error.h>
28/// \ingroup dimacs_group
29/// \file
30/// \brief DIMACS file format reader.
31
32namespace lemon {
33
34  /// \addtogroup dimacs_group
35  /// @{
36
37  /// DIMACS file type descriptor.
38  struct DimacsDescriptor
39  {
40    ///File type enum
41    enum Type
42      {
43        NONE, MIN, MAX, SP, MAT
44      };
45    ///The file type
46    Type type;
47    ///The number of nodes in the graph
48    int nodeNum;
49    ///The number of edges in the graph
50    int edgeNum;
51    int lineShift;
52    /// Constructor. Sets the type to NONE.
53    DimacsDescriptor() : type(NONE) {}
54  };
55
56  ///Discover the type of a DIMACS file
57
58  ///It starts seeking the beginning of the file for the problem type
59  ///and size info. The found data is returned in a special struct
60  ///that can be evaluated and passed to the appropriate reader
61  ///function.
62  DimacsDescriptor dimacsType(std::istream& is)
63  {
64    DimacsDescriptor r;
65    std::string problem,str;
66    char c;
67    r.lineShift=0;
68    while (is >> c)
69      switch(c)
70        {
71        case 'p':
72          if(is >> problem >> r.nodeNum >> r.edgeNum)
73            {
74              getline(is, str);
75              r.lineShift++;
76              if(problem=="min") r.type=DimacsDescriptor::MIN;
77              else if(problem=="max") r.type=DimacsDescriptor::MAX;
78              else if(problem=="sp") r.type=DimacsDescriptor::SP;
79              else if(problem=="mat") r.type=DimacsDescriptor::MAT;
80              else throw FormatError("Unknown problem type");
81              return r;
82            }
83          else
84            {
85              throw FormatError("Missing or wrong problem type declaration.");
86            }
87          break;
88        case 'c':
89          getline(is, str);
90          r.lineShift++;
91          break;
92        default:
93          throw FormatError("Unknown DIMACS declaration.");
94        }
95    throw FormatError("Missing problem type declaration.");
96  }
97
98
99
100  /// DIMACS minimum cost flow reader function.
101  ///
102  /// This function reads a minimum cost flow instance from DIMACS format,
103  /// i.e. from a DIMACS file having a line starting with
104  /// \code
105  ///   p min
106  /// \endcode
107  /// At the beginning, \c g is cleared by \c g.clear(). The supply
108  /// amount of the nodes are written to the \c supply node map
109  /// (they are signed values). The lower bounds, capacities and costs
110  /// of the arcs are written to the \c lower, \c capacity and \c cost
111  /// arc maps.
112  ///
113  /// If the capacity of an arc is less than the lower bound, it will
114  /// be set to "infinite" instead. The actual value of "infinite" is
115  /// contolled by the \c infty parameter. If it is 0 (the default value),
116  /// \c std::numeric_limits<Capacity>::infinity() will be used if available,
117  /// \c std::numeric_limits<Capacity>::max() otherwise. If \c infty is set to
118  /// a non-zero value, that value will be used as "infinite".
119  ///
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,
124            typename SupplyMap>
125  void readDimacsMin(std::istream& is,
126                     Digraph &g,
127                     LowerMap& lower,
128                     CapacityMap& capacity,
129                     CostMap& cost,
130                     SupplyMap& supply,
131                     typename CapacityMap::Value infty = 0,
132                     DimacsDescriptor desc=DimacsDescriptor())
133  {
134    g.clear();
135    std::vector<typename Digraph::Node> nodes;
136    typename Digraph::Arc e;
137    std::string problem, str;
138    char c;
139    int i, j;
140    if(desc.type==DimacsDescriptor::NONE) desc=dimacsType(is);
141    if(desc.type!=DimacsDescriptor::MIN)
142      throw FormatError("Problem type mismatch");
143
144    nodes.resize(desc.nodeNum + 1);
145    for (int k = 1; k <= desc.nodeNum; ++k) {
146      nodes[k] = g.addNode();
147      supply.set(nodes[k], 0);
148    }
149
150    typename SupplyMap::Value sup;
151    typename CapacityMap::Value low;
152    typename CapacityMap::Value cap;
153    typename CostMap::Value co;
154    typedef typename CapacityMap::Value Capacity;
155    if(infty==0)
156      infty = std::numeric_limits<Capacity>::has_infinity ?
157        std::numeric_limits<Capacity>::infinity() :
158        std::numeric_limits<Capacity>::max();
159
160    while (is >> c) {
161      switch (c) {
162      case 'c': // comment line
163        getline(is, str);
164        break;
165      case 'n': // node definition line
166        is >> i >> sup;
167        getline(is, str);
168        supply.set(nodes[i], sup);
169        break;
170      case 'a': // arc definition line
171        is >> i >> j >> low >> cap >> co;
172        getline(is, str);
173        e = g.addArc(nodes[i], nodes[j]);
174        lower.set(e, low);
175        if (cap >= low)
176          capacity.set(e, cap);
177        else
178          capacity.set(e, infty);
179        cost.set(e, co);
180        break;
181      }
182    }
183  }
184
185  template<typename Digraph, typename CapacityMap>
186  void _readDimacs(std::istream& is,
187                   Digraph &g,
188                   CapacityMap& capacity,
189                   typename Digraph::Node &s,
190                   typename Digraph::Node &t,
191                   typename CapacityMap::Value infty = 0,
192                   DimacsDescriptor desc=DimacsDescriptor()) {
193    g.clear();
194    s=t=INVALID;
195    std::vector<typename Digraph::Node> nodes;
196    typename Digraph::Arc e;
197    char c, d;
198    int i, j;
199    typename CapacityMap::Value _cap;
200    std::string str;
201    nodes.resize(desc.nodeNum + 1);
202    for (int k = 1; k <= desc.nodeNum; ++k) {
203      nodes[k] = g.addNode();
204    }
205    typedef typename CapacityMap::Value Capacity;
206
207    if(infty==0)
208      infty = std::numeric_limits<Capacity>::has_infinity ?
209        std::numeric_limits<Capacity>::infinity() :
210        std::numeric_limits<Capacity>::max();
211 
212    while (is >> c) {
213      switch (c) {
214      case 'c': // comment line
215        getline(is, str);
216        break;
217      case 'n': // node definition line
218        if (desc.type==DimacsDescriptor::SP) { // shortest path problem
219          is >> i;
220          getline(is, str);
221          s = nodes[i];
222        }
223        if (desc.type==DimacsDescriptor::MAX) { // max flow problem
224          is >> i >> d;
225          getline(is, str);
226          if (d == 's') s = nodes[i];
227          if (d == 't') t = nodes[i];
228        }
229        break;
230      case 'a': // arc definition line
231        if (desc.type==DimacsDescriptor::SP) {
232          is >> i >> j >> _cap;
233          getline(is, str);
234          e = g.addArc(nodes[i], nodes[j]);
235          capacity.set(e, _cap);
236        }
237        else if (desc.type==DimacsDescriptor::MAX) {
238          is >> i >> j >> _cap;
239          getline(is, str);
240          e = g.addArc(nodes[i], nodes[j]);
241          if (_cap >= 0)
242            capacity.set(e, _cap);
243          else
244            capacity.set(e, infty);
245        }
246        else {
247          is >> i >> j;
248          getline(is, str);
249          g.addArc(nodes[i], nodes[j]);
250        }
251        break;
252      }
253    }
254  }
255
256  /// DIMACS maximum flow reader function.
257  ///
258  /// This function reads a maximum flow instance from DIMACS format,
259  /// i.e. from a DIMACS file having a line starting with
260  /// \code
261  ///   p max
262  /// \endcode
263  /// At the beginning, \c g is cleared by \c g.clear(). The arc
264  /// capacities are written to the \c capacity arc map and \c s and
265  /// \c t are set to the source and the target nodes.
266  ///
267  /// If the capacity of an arc is negative, it will
268  /// be set to "infinite" instead. The actual value of "infinite" is
269  /// contolled by the \c infty parameter. If it is 0 (the default value),
270  /// \c std::numeric_limits<Capacity>::infinity() will be used if available,
271  /// \c std::numeric_limits<Capacity>::max() otherwise. If \c infty is set to
272  /// a non-zero value, that value will be used as "infinite".
273  ///
274  /// If the file type was previously evaluated by dimacsType(), then
275  /// the descriptor struct should be given by the \c dest parameter.
276  template<typename Digraph, typename CapacityMap>
277  void readDimacsMax(std::istream& is,
278                     Digraph &g,
279                     CapacityMap& capacity,
280                     typename Digraph::Node &s,
281                     typename Digraph::Node &t,
282                     typename CapacityMap::Value infty = 0,
283                     DimacsDescriptor desc=DimacsDescriptor()) {
284    if(desc.type==DimacsDescriptor::NONE) desc=dimacsType(is);
285    if(desc.type!=DimacsDescriptor::MAX)
286      throw FormatError("Problem type mismatch");
287    _readDimacs(is,g,capacity,s,t,infty,desc);
288  }
289
290  /// DIMACS shortest path reader function.
291  ///
292  /// This function reads a shortest path instance from DIMACS format,
293  /// i.e. from a DIMACS file having a line starting with
294  /// \code
295  ///   p sp
296  /// \endcode
297  /// At the beginning, \c g is cleared by \c g.clear(). The arc
298  /// lengths are written to the \c length arc map and \c s is set to the
299  /// source node.
300  ///
301  /// If the file type was previously evaluated by dimacsType(), then
302  /// the descriptor struct should be given by the \c dest parameter.
303  template<typename Digraph, typename LengthMap>
304  void readDimacsSp(std::istream& is,
305                    Digraph &g,
306                    LengthMap& length,
307                    typename Digraph::Node &s,
308                    DimacsDescriptor desc=DimacsDescriptor()) {
309    typename Digraph::Node t;
310    if(desc.type==DimacsDescriptor::NONE) desc=dimacsType(is);
311    if(desc.type!=DimacsDescriptor::SP)
312      throw FormatError("Problem type mismatch");
313    _readDimacs(is, g, length, s, t, 0, desc);
314  }
315
316  /// DIMACS capacitated digraph reader function.
317  ///
318  /// This function reads an arc capacitated digraph instance from
319  /// DIMACS 'max' or 'sp' format.
320  /// At the beginning, \c g is cleared by \c g.clear()
321  /// and the arc capacities/lengths are written to the \c capacity
322  /// arc map.
323  ///
324  /// In case of the 'max' format, if the capacity of an arc is negative,
325  /// it will
326  /// be set to "infinite" instead. The actual value of "infinite" is
327  /// contolled by the \c infty parameter. If it is 0 (the default value),
328  /// \c std::numeric_limits<Capacity>::infinity() will be used if available,
329  /// \c std::numeric_limits<Capacity>::max() otherwise. If \c infty is set to
330  /// a non-zero value, that value will be used as "infinite".
331  ///
332  /// If the file type was previously evaluated by dimacsType(), then
333  /// the descriptor struct should be given by the \c dest parameter.
334  template<typename Digraph, typename CapacityMap>
335  void readDimacsCap(std::istream& is,
336                     Digraph &g,
337                     CapacityMap& capacity,
338                     typename CapacityMap::Value infty = 0,
339                     DimacsDescriptor desc=DimacsDescriptor()) {
340    typename Digraph::Node u,v;
341    if(desc.type==DimacsDescriptor::NONE) desc=dimacsType(is);
342    if(desc.type!=DimacsDescriptor::MAX || desc.type!=DimacsDescriptor::SP)
343      throw FormatError("Problem type mismatch");
344    _readDimacs(is, g, capacity, u, v, infty, desc);
345  }
346
347  template<typename Graph>
348  typename enable_if<lemon::UndirectedTagIndicator<Graph>,void>::type
349  _addArcEdge(Graph &g, typename Graph::Node s, typename Graph::Node t,
350              dummy<0> = 0)
351  {
352    g.addEdge(s,t);
353  }
354  template<typename Graph>
355  typename disable_if<lemon::UndirectedTagIndicator<Graph>,void>::type
356  _addArcEdge(Graph &g, typename Graph::Node s, typename Graph::Node t,
357              dummy<1> = 1)
358  {
359    g.addArc(s,t);
360  }
361 
362  /// DIMACS plain (di)graph reader function.
363  ///
364  /// This function reads a (di)graph without any designated nodes and
365  /// maps from DIMACS format, i.e. from DIMACS files having a line
366  /// starting with
367  /// \code
368  ///   p mat
369  /// \endcode
370  /// At the beginning, \c g is cleared by \c g.clear().
371  ///
372  /// If the file type was previously evaluated by dimacsType(), then
373  /// the descriptor struct should be given by the \c dest parameter.
374  template<typename Graph>
375  void readDimacsMat(std::istream& is, Graph &g,
376                     DimacsDescriptor desc=DimacsDescriptor())
377  {
378    if(desc.type==DimacsDescriptor::NONE) desc=dimacsType(is);
379    if(desc.type!=DimacsDescriptor::MAT)
380      throw FormatError("Problem type mismatch");
381
382    g.clear();
383    std::vector<typename Graph::Node> nodes;
384    char c;
385    int i, j;
386    std::string str;
387    nodes.resize(desc.nodeNum + 1);
388    for (int k = 1; k <= desc.nodeNum; ++k) {
389      nodes[k] = g.addNode();
390    }
391   
392    while (is >> c) {
393      switch (c) {
394      case 'c': // comment line
395        getline(is, str);
396        break;
397      case 'n': // node definition line
398        break;
399      case 'a': // arc definition line
400        is >> i >> j;
401        getline(is, str);
402        _addArcEdge(g,nodes[i], nodes[j]);
403        break;
404      }
405    }
406  }
407
408  /// DIMACS plain digraph writer function.
409  ///
410  /// This function writes a digraph without any designated nodes and
411  /// maps into DIMACS format, i.e. into DIMACS file having a line
412  /// starting with
413  /// \code
414  ///   p mat
415  /// \endcode
416  /// If \c comment is not empty, then it will be printed in the first line
417  /// prefixed by 'c'.
418  template<typename Digraph>
419  void writeDimacsMat(std::ostream& os, const Digraph &g,
420                      std::string comment="") {
421    typedef typename Digraph::NodeIt NodeIt;
422    typedef typename Digraph::ArcIt ArcIt;
423
424    if(!comment.empty())
425      os << "c " << comment << std::endl;
426    os << "p mat " << g.nodeNum() << " " << g.arcNum() << std::endl;
427
428    typename Digraph::template NodeMap<int> nodes(g);
429    int i = 1;
430    for(NodeIt v(g); v != INVALID; ++v) {
431      nodes.set(v, i);
432      ++i;
433    }
434    for(ArcIt e(g); e != INVALID; ++e) {
435      os << "a " << nodes[g.source(e)] << " " << nodes[g.target(e)]
436         << std::endl;
437    }
438  }
439
440  /// @}
441
442} //namespace lemon
443
444#endif //LEMON_DIMACS_H
Note: See TracBrowser for help on using the repository browser.