COIN-OR::LEMON - Graph Library

source: lemon-1.2/lemon/dimacs.h @ 1006:332627dd249e

Last change on this file since 1006:332627dd249e was 1006:332627dd249e, checked in by Peter Kovacs <kpeter@…>, 7 years ago

Fixes in API doc of DIMACS reader methods

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
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    ///File type enum
42    enum Type
43      {
44        NONE, MIN, MAX, SP, MAT
45      };
46    ///The file type
47    Type type;
48    ///The number of nodes in the graph
49    int nodeNum;
50    ///The number of edges in the graph
51    int edgeNum;
52    int lineShift;
53    /// Constructor. Sets the type to NONE.
54    DimacsDescriptor() : type(NONE) {}
55  };
56
57  ///Discover the type of a DIMACS file
58
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
62  ///function.
63  DimacsDescriptor dimacsType(std::istream& is)
64  {
65    DimacsDescriptor r;
66    std::string problem,str;
67    char c;
68    r.lineShift=0;
69    while (is >> c)
70      switch(c)
71        {
72        case 'p':
73          if(is >> problem >> r.nodeNum >> r.edgeNum)
74            {
75              getline(is, str);
76              r.lineShift++;
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");
82              return r;
83            }
84          else
85            {
86              throw FormatError("Missing or wrong problem type declaration.");
87            }
88          break;
89        case 'c':
90          getline(is, str);
91          r.lineShift++;
92          break;
93        default:
94          throw FormatError("Unknown DIMACS declaration.");
95        }
96    throw FormatError("Missing problem type declaration.");
97  }
98
99
100
101  /// DIMACS minimum cost flow reader function.
102  ///
103  /// This function reads a minimum cost flow instance from DIMACS format,
104  /// i.e. from a DIMACS file having a line starting with
105  /// \code
106  ///   p min
107  /// \endcode
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
112  /// arc maps.
113  ///
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".
120  ///
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,
125            typename SupplyMap>
126  void readDimacsMin(std::istream& is,
127                     Digraph &g,
128                     LowerMap& lower,
129                     CapacityMap& capacity,
130                     CostMap& cost,
131                     SupplyMap& supply,
132                     typename CapacityMap::Value infty = 0,
133                     DimacsDescriptor desc=DimacsDescriptor())
134  {
135    g.clear();
136    std::vector<typename Digraph::Node> nodes;
137    typename Digraph::Arc e;
138    std::string problem, str;
139    char c;
140    int i, j;
141    if(desc.type==DimacsDescriptor::NONE) desc=dimacsType(is);
142    if(desc.type!=DimacsDescriptor::MIN)
143      throw FormatError("Problem type mismatch");
144
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);
149    }
150
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;
156    if(infty==0)
157      infty = std::numeric_limits<Capacity>::has_infinity ?
158        std::numeric_limits<Capacity>::infinity() :
159        std::numeric_limits<Capacity>::max();
160
161    while (is >> c) {
162      switch (c) {
163      case 'c': // comment line
164        getline(is, str);
165        break;
166      case 'n': // node definition line
167        is >> i >> sup;
168        getline(is, str);
169        supply.set(nodes[i], sup);
170        break;
171      case 'a': // arc definition line
172        is >> i >> j >> low >> cap >> co;
173        getline(is, str);
174        e = g.addArc(nodes[i], nodes[j]);
175        lower.set(e, low);
176        if (cap >= low)
177          capacity.set(e, cap);
178        else
179          capacity.set(e, infty);
180        cost.set(e, co);
181        break;
182      }
183    }
184  }
185
186  template<typename Digraph, typename CapacityMap>
187  void _readDimacs(std::istream& is,
188                   Digraph &g,
189                   CapacityMap& capacity,
190                   typename Digraph::Node &s,
191                   typename Digraph::Node &t,
192                   typename CapacityMap::Value infty = 0,
193                   DimacsDescriptor desc=DimacsDescriptor()) {
194    g.clear();
195    s=t=INVALID;
196    std::vector<typename Digraph::Node> nodes;
197    typename Digraph::Arc e;
198    char c, d;
199    int i, j;
200    typename CapacityMap::Value _cap;
201    std::string str;
202    nodes.resize(desc.nodeNum + 1);
203    for (int k = 1; k <= desc.nodeNum; ++k) {
204      nodes[k] = g.addNode();
205    }
206    typedef typename CapacityMap::Value Capacity;
207
208    if(infty==0)
209      infty = std::numeric_limits<Capacity>::has_infinity ?
210        std::numeric_limits<Capacity>::infinity() :
211        std::numeric_limits<Capacity>::max();
212 
213    while (is >> c) {
214      switch (c) {
215      case 'c': // comment line
216        getline(is, str);
217        break;
218      case 'n': // node definition line
219        if (desc.type==DimacsDescriptor::SP) { // shortest path problem
220          is >> i;
221          getline(is, str);
222          s = nodes[i];
223        }
224        if (desc.type==DimacsDescriptor::MAX) { // max flow problem
225          is >> i >> d;
226          getline(is, str);
227          if (d == 's') s = nodes[i];
228          if (d == 't') t = nodes[i];
229        }
230        break;
231      case 'a': // arc definition line
232        if (desc.type==DimacsDescriptor::SP) {
233          is >> i >> j >> _cap;
234          getline(is, str);
235          e = g.addArc(nodes[i], nodes[j]);
236          capacity.set(e, _cap);
237        }
238        else if (desc.type==DimacsDescriptor::MAX) {
239          is >> i >> j >> _cap;
240          getline(is, str);
241          e = g.addArc(nodes[i], nodes[j]);
242          if (_cap >= 0)
243            capacity.set(e, _cap);
244          else
245            capacity.set(e, infty);
246        }
247        else {
248          is >> i >> j;
249          getline(is, str);
250          g.addArc(nodes[i], nodes[j]);
251        }
252        break;
253      }
254    }
255  }
256
257  /// DIMACS maximum flow reader function.
258  ///
259  /// This function reads a maximum flow instance from DIMACS format,
260  /// i.e. from a DIMACS file having a line starting with
261  /// \code
262  ///   p max
263  /// \endcode
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.
267  ///
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".
274  ///
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,
279                     Digraph &g,
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);
289  }
290
291  /// DIMACS shortest path reader function.
292  ///
293  /// This function reads a shortest path instance from DIMACS format,
294  /// i.e. from a DIMACS file having a line starting with
295  /// \code
296  ///   p sp
297  /// \endcode
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
300  /// source node.
301  ///
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,
306                    Digraph &g,
307                    LengthMap& length,
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);
315  }
316
317  /// DIMACS capacitated digraph reader function.
318  ///
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
323  /// arc map.
324  ///
325  /// In case of the 'max' format, if the capacity of an arc is negative,
326  /// it will
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".
332  ///
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,
337                     Digraph &g,
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);
346  }
347
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,
351              dummy<0> = 0)
352  {
353    g.addEdge(s,t);
354  }
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,
358              dummy<1> = 1)
359  {
360    g.addArc(s,t);
361  }
362 
363  /// DIMACS plain (di)graph reader function.
364  ///
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
367  /// starting with
368  /// \code
369  ///   p mat
370  /// \endcode
371  /// At the beginning, \c g is cleared by \c g.clear().
372  ///
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())
378  {
379    if(desc.type==DimacsDescriptor::NONE) desc=dimacsType(is);
380    if(desc.type!=DimacsDescriptor::MAT)
381      throw FormatError("Problem type mismatch");
382
383    g.clear();
384    std::vector<typename Graph::Node> nodes;
385    char c;
386    int i, j;
387    std::string str;
388    nodes.resize(desc.nodeNum + 1);
389    for (int k = 1; k <= desc.nodeNum; ++k) {
390      nodes[k] = g.addNode();
391    }
392   
393    while (is >> c) {
394      switch (c) {
395      case 'c': // comment line
396        getline(is, str);
397        break;
398      case 'n': // node definition line
399        break;
400      case 'a': // arc definition line
401        is >> i >> j;
402        getline(is, str);
403        _addArcEdge(g,nodes[i], nodes[j]);
404        break;
405      }
406    }
407  }
408
409  /// DIMACS plain digraph writer function.
410  ///
411  /// This function writes a digraph without any designated nodes and
412  /// maps into DIMACS format, i.e. into DIMACS file having a line
413  /// starting with
414  /// \code
415  ///   p mat
416  /// \endcode
417  /// If \c comment is not empty, then it will be printed in the first line
418  /// prefixed by 'c'.
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;
424
425    if(!comment.empty())
426      os << "c " << comment << std::endl;
427    os << "p mat " << g.nodeNum() << " " << g.arcNum() << std::endl;
428
429    typename Digraph::template NodeMap<int> nodes(g);
430    int i = 1;
431    for(NodeIt v(g); v != INVALID; ++v) {
432      nodes.set(v, i);
433      ++i;
434    }
435    for(ArcIt e(g); e != INVALID; ++e) {
436      os << "a " << nodes[g.source(e)] << " " << nodes[g.target(e)]
437         << std::endl;
438    }
439  }
440
441  /// @}
442
443} //namespace lemon
444
445#endif //LEMON_DIMACS_H
Note: See TracBrowser for help on using the repository browser.