COIN-OR::LEMON - Graph Library

source: lemon/lemon/dimacs.h @ 1064:40bbb450143e

Last change on this file since 1064:40bbb450143e was 631:33c6b6e755cd, checked in by Peter Kovacs <kpeter@…>, 16 years ago

Small doc improvements (#263)

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