COIN-OR::LEMON - Graph Library

source: lemon-1.2/lemon/dimacs.h @ 540:9db62975c32b

Last change on this file since 540:9db62975c32b was 525:635a8375227d, checked in by Alpar Juttner <alpar@…>, 15 years ago

dimacs.h reads MAT files to both dir and undir graphs (#231)

File size: 12.0 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 <lemon/maps.h>
26#include <lemon/error.h>
27
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 begining 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 \c supply (signed). The
109  /// lower bounds, capacities and costs of the arcs are written to
110  /// \c lower, \c capacity and \c cost.
111  ///
112  /// If the file type was previously evaluated by dimacsType(), then
113  /// the descriptor struct should be given by the \c dest parameter.
114  template <typename Digraph, typename LowerMap,
115            typename CapacityMap, typename CostMap,
116            typename SupplyMap>
117  void readDimacsMin(std::istream& is,
118                     Digraph &g,
119                     LowerMap& lower,
120                     CapacityMap& capacity,
121                     CostMap& cost,
122                     SupplyMap& supply,
123                     DimacsDescriptor desc=DimacsDescriptor())
124  {
125    g.clear();
126    std::vector<typename Digraph::Node> nodes;
127    typename Digraph::Arc e;
128    std::string problem, str;
129    char c;
130    int i, j;
131    if(desc.type==DimacsDescriptor::NONE) desc=dimacsType(is);
132    if(desc.type!=DimacsDescriptor::MIN)
133      throw FormatError("Problem type mismatch");
134
135    nodes.resize(desc.nodeNum + 1);
136    for (int k = 1; k <= desc.nodeNum; ++k) {
137      nodes[k] = g.addNode();
138      supply.set(nodes[k], 0);
139    }
140
141    typename SupplyMap::Value sup;
142    typename CapacityMap::Value low;
143    typename CapacityMap::Value cap;
144    typename CostMap::Value co;
145    while (is >> c) {
146      switch (c) {
147      case 'c': // comment line
148        getline(is, str);
149        break;
150      case 'n': // node definition line
151        is >> i >> sup;
152        getline(is, str);
153        supply.set(nodes[i], sup);
154        break;
155      case 'a': // arc (arc) definition line
156        is >> i >> j >> low >> cap >> co;
157        getline(is, str);
158        e = g.addArc(nodes[i], nodes[j]);
159        lower.set(e, low);
160        if (cap >= 0)
161          capacity.set(e, cap);
162        else
163          capacity.set(e, -1);
164        cost.set(e, co);
165        break;
166      }
167    }
168  }
169
170  template<typename Digraph, typename CapacityMap>
171  void _readDimacs(std::istream& is,
172                   Digraph &g,
173                   CapacityMap& capacity,
174                   typename Digraph::Node &s,
175                   typename Digraph::Node &t,
176                   DimacsDescriptor desc=DimacsDescriptor()) {
177    g.clear();
178    s=t=INVALID;
179    std::vector<typename Digraph::Node> nodes;
180    typename Digraph::Arc e;
181    char c, d;
182    int i, j;
183    typename CapacityMap::Value _cap;
184    std::string str;
185    nodes.resize(desc.nodeNum + 1);
186    for (int k = 1; k <= desc.nodeNum; ++k) {
187      nodes[k] = g.addNode();
188    }
189
190    while (is >> c) {
191      switch (c) {
192      case 'c': // comment line
193        getline(is, str);
194        break;
195      case 'n': // node definition line
196        if (desc.type==DimacsDescriptor::SP) { // shortest path problem
197          is >> i;
198          getline(is, str);
199          s = nodes[i];
200        }
201        if (desc.type==DimacsDescriptor::MAX) { // max flow problem
202          is >> i >> d;
203          getline(is, str);
204          if (d == 's') s = nodes[i];
205          if (d == 't') t = nodes[i];
206        }
207        break;
208      case 'a': // arc (arc) definition line
209        if (desc.type==DimacsDescriptor::SP ||
210            desc.type==DimacsDescriptor::MAX) {
211          is >> i >> j >> _cap;
212          getline(is, str);
213          e = g.addArc(nodes[i], nodes[j]);
214          capacity.set(e, _cap);
215        } else {
216          is >> i >> j;
217          getline(is, str);
218          g.addArc(nodes[i], nodes[j]);
219        }
220        break;
221      }
222    }
223  }
224
225  /// DIMACS maximum flow reader function.
226  ///
227  /// This function reads a maximum flow instance from DIMACS format,
228  /// i.e. from a DIMACS file having a line starting with
229  /// \code
230  ///   p max
231  /// \endcode
232  /// At the beginning, \c g is cleared by \c g.clear(). The arc
233  /// capacities are written to \c capacity and \c s and \c t are
234  /// set to the source and the target nodes.
235  ///
236  /// If the file type was previously evaluated by dimacsType(), then
237  /// the descriptor struct should be given by the \c dest parameter.
238  template<typename Digraph, typename CapacityMap>
239  void readDimacsMax(std::istream& is,
240                     Digraph &g,
241                     CapacityMap& capacity,
242                     typename Digraph::Node &s,
243                     typename Digraph::Node &t,
244                     DimacsDescriptor desc=DimacsDescriptor()) {
245    if(desc.type==DimacsDescriptor::NONE) desc=dimacsType(is);
246    if(desc.type!=DimacsDescriptor::MAX)
247      throw FormatError("Problem type mismatch");
248    _readDimacs(is,g,capacity,s,t,desc);
249  }
250
251  /// DIMACS shortest path reader function.
252  ///
253  /// This function reads a shortest path instance from DIMACS format,
254  /// i.e. from a DIMACS file having a line starting with
255  /// \code
256  ///   p sp
257  /// \endcode
258  /// At the beginning, \c g is cleared by \c g.clear(). The arc
259  /// lengths are written to \c length and \c s is set to the
260  /// source node.
261  ///
262  /// If the file type was previously evaluated by dimacsType(), then
263  /// the descriptor struct should be given by the \c dest parameter.
264  template<typename Digraph, typename LengthMap>
265  void readDimacsSp(std::istream& is,
266                    Digraph &g,
267                    LengthMap& length,
268                    typename Digraph::Node &s,
269                    DimacsDescriptor desc=DimacsDescriptor()) {
270    typename Digraph::Node t;
271    if(desc.type==DimacsDescriptor::NONE) desc=dimacsType(is);
272    if(desc.type!=DimacsDescriptor::SP)
273      throw FormatError("Problem type mismatch");
274    _readDimacs(is, g, length, s, t,desc);
275  }
276
277  /// DIMACS capacitated digraph reader function.
278  ///
279  /// This function reads an arc capacitated digraph instance from
280  /// DIMACS 'mat' or 'sp' format.
281  /// At the beginning, \c g is cleared by \c g.clear()
282  /// and the arc capacities/lengths are written to \c capacity.
283  ///
284  /// If the file type was previously evaluated by dimacsType(), then
285  /// the descriptor struct should be given by the \c dest parameter.
286  template<typename Digraph, typename CapacityMap>
287  void readDimacsCap(std::istream& is,
288                     Digraph &g,
289                     CapacityMap& capacity,
290                     DimacsDescriptor desc=DimacsDescriptor()) {
291    typename Digraph::Node u,v;
292    if(desc.type==DimacsDescriptor::NONE) desc=dimacsType(is);
293    if(desc.type!=DimacsDescriptor::MAX || desc.type!=DimacsDescriptor::SP)
294      throw FormatError("Problem type mismatch");
295    _readDimacs(is, g, capacity, u, v, desc);
296  }
297
298  template<typename Graph>
299  typename enable_if<lemon::UndirectedTagIndicator<Graph>,void>::type
300  _addArcEdge(Graph &g, typename Graph::Node s, typename Graph::Node t,
301              dummy<0> = 0)
302  {
303    g.addEdge(s,t);
304  }
305  template<typename Graph>
306  typename disable_if<lemon::UndirectedTagIndicator<Graph>,void>::type
307  _addArcEdge(Graph &g, typename Graph::Node s, typename Graph::Node t,
308              dummy<1> = 1)
309  {
310    g.addArc(s,t);
311  }
312 
313  /// DIMACS plain (di)graph reader function.
314  ///
315  /// This function reads a (di)graph without any designated nodes and
316  /// maps from DIMACS format, i.e. from DIMACS files having a line
317  /// starting with
318  /// \code
319  ///   p mat
320  /// \endcode
321  /// At the beginning, \c g is cleared by \c g.clear().
322  ///
323  /// If the file type was previously evaluated by dimacsType(), then
324  /// the descriptor struct should be given by the \c dest parameter.
325  template<typename Graph>
326  void readDimacsMat(std::istream& is, Graph &g,
327                     DimacsDescriptor desc=DimacsDescriptor())
328  {
329    if(desc.type==DimacsDescriptor::NONE) desc=dimacsType(is);
330    if(desc.type!=DimacsDescriptor::MAT)
331      throw FormatError("Problem type mismatch");
332
333    g.clear();
334    std::vector<typename Graph::Node> nodes;
335    char c;
336    int i, j;
337    std::string str;
338    nodes.resize(desc.nodeNum + 1);
339    for (int k = 1; k <= desc.nodeNum; ++k) {
340      nodes[k] = g.addNode();
341    }
342   
343    while (is >> c) {
344      switch (c) {
345      case 'c': // comment line
346        getline(is, str);
347        break;
348      case 'n': // node definition line
349        break;
350      case 'a': // arc (arc) definition line
351        is >> i >> j;
352        getline(is, str);
353        _addArcEdge(g,nodes[i], nodes[j]);
354        break;
355      }
356    }
357  }
358
359  /// DIMACS plain digraph writer function.
360  ///
361  /// This function writes a digraph without any designated nodes and
362  /// maps into DIMACS format, i.e. into DIMACS file having a line
363  /// starting with
364  /// \code
365  ///   p mat
366  /// \endcode
367  /// If \c comment is not empty, then it will be printed in the first line
368  /// prefixed by 'c'.
369  template<typename Digraph>
370  void writeDimacsMat(std::ostream& os, const Digraph &g,
371                      std::string comment="") {
372    typedef typename Digraph::NodeIt NodeIt;
373    typedef typename Digraph::ArcIt ArcIt;
374
375    if(!comment.empty())
376      os << "c " << comment << std::endl;
377    os << "p mat " << g.nodeNum() << " " << g.arcNum() << std::endl;
378
379    typename Digraph::template NodeMap<int> nodes(g);
380    int i = 1;
381    for(NodeIt v(g); v != INVALID; ++v) {
382      nodes.set(v, i);
383      ++i;
384    }
385    for(ArcIt e(g); e != INVALID; ++e) {
386      os << "a " << nodes[g.source(e)] << " " << nodes[g.target(e)]
387         << std::endl;
388    }
389  }
390
391  /// @}
392
393} //namespace lemon
394
395#endif //LEMON_DIMACS_H
Note: See TracBrowser for help on using the repository browser.