COIN-OR::LEMON - Graph Library

source: lemon-main/lemon/dimacs.h

Last change on this file was 1160:bc571f16e1e9, checked in by Alpar Juttner <alpar@…>, 2 years ago

Merge bugfix #607

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