gravatar
alpar (Alpar Juttner)
alpar@cs.elte.hu
Merge
0 4 2
merge default
1 file changed with 522 insertions and 1 deletions:
↑ Collapse diff ↑
Ignore white space 8 line context
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-2008
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

	
32
namespace 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
  /// DIMACS plain digraph reader function.
299
  ///
300
  /// This function reads a digraph without any designated nodes and
301
  /// maps from DIMACS format, i.e. from DIMACS files having a line
302
  /// starting with
303
  /// \code
304
  ///   p mat
305
  /// \endcode
306
  /// At the beginning, \c g is cleared by \c g.clear().
307
  ///
308
  /// If the file type was previously evaluated by dimacsType(), then
309
  /// the descriptor struct should be given by the \c dest parameter.
310
  template<typename Digraph>
311
  void readDimacsMat(std::istream& is, Digraph &g,
312
                     DimacsDescriptor desc=DimacsDescriptor()) {
313
    typename Digraph::Node u,v;
314
    NullMap<typename Digraph::Arc, int> n;
315
    if(desc.type==DimacsDescriptor::NONE) desc=dimacsType(is);
316
    if(desc.type!=DimacsDescriptor::MAT)
317
      throw FormatError("Problem type mismatch");
318
    _readDimacs(is, g, n, u, v, desc);
319
  }
320

	
321
  /// DIMACS plain digraph writer function.
322
  ///
323
  /// This function writes a digraph without any designated nodes and
324
  /// maps into DIMACS format, i.e. into DIMACS file having a line
325
  /// starting with
326
  /// \code
327
  ///   p mat
328
  /// \endcode
329
  /// If \c comment is not empty, then it will be printed in the first line
330
  /// prefixed by 'c'.
331
  template<typename Digraph>
332
  void writeDimacsMat(std::ostream& os, const Digraph &g,
333
                      std::string comment="") {
334
    typedef typename Digraph::NodeIt NodeIt;
335
    typedef typename Digraph::ArcIt ArcIt;
336

	
337
    if(!comment.empty()) 
338
      os << "c " << comment << std::endl;
339
    os << "p mat " << g.nodeNum() << " " << g.arcNum() << std::endl;
340

	
341
    typename Digraph::template NodeMap<int> nodes(g);
342
    int i = 1;
343
    for(NodeIt v(g); v != INVALID; ++v) {
344
      nodes.set(v, i);
345
      ++i;
346
    }
347
    for(ArcIt e(g); e != INVALID; ++e) {
348
      os << "a " << nodes[g.source(e)] << " " << nodes[g.target(e)]
349
         << std::endl;
350
    }
351
  }
352

	
353
  /// @}
354

	
355
} //namespace lemon
356

	
357
#endif //LEMON_DIMACS_H
Ignore white space 8 line context
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-2008
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
///\ingroup tools
20
///\file
21
///\brief DIMACS to LGF converter.
22
///
23
/// This program converts various DIMACS formats to the LEMON Digraph Format
24
/// (LGF).
25
///
26
/// See
27
/// \verbatim
28
///  dimacs-to-lgf --help
29
/// \endverbatim
30
/// for more info on usage.
31
///
32

	
33
#include <iostream>
34
#include <fstream>
35
#include <cstring>
36

	
37
#include <lemon/smart_graph.h>
38
#include <lemon/dimacs.h>
39
#include <lemon/lgf_writer.h>
40

	
41
#include <lemon/arg_parser.h>
42
#include <lemon/error.h>
43

	
44
using namespace std;
45
using namespace lemon;
46

	
47

	
48
int main(int argc, const char *argv[]) {
49
  typedef SmartDigraph Digraph;
50

	
51
  typedef Digraph::Arc Arc;
52
  typedef Digraph::Node Node;
53
  typedef Digraph::ArcIt ArcIt;
54
  typedef Digraph::NodeIt NodeIt;
55
  typedef Digraph::ArcMap<double> DoubleArcMap;
56
  typedef Digraph::NodeMap<double> DoubleNodeMap;
57

	
58
  std::string inputName;
59
  std::string outputName;
60

	
61
  ArgParser ap(argc, argv);
62
  ap.other("[INFILE [OUTFILE]]",
63
           "If either the INFILE or OUTFILE file is missing the standard\n"
64
           "     input/output will be used instead.")
65
    .run();
66

	
67
  ifstream input;
68
  ofstream output;
69

	
70
  switch(ap.files().size())
71
    {
72
    case 2:
73
      output.open(ap.files()[1].c_str());
74
      if (!output) {
75
        throw IoError("Cannot open the file for writing", ap.files()[1]);
76
      }
77
    case 1:
78
      input.open(ap.files()[0].c_str());
79
      if (!input) {
80
        throw IoError("File cannot be found", ap.files()[0]);
81
      }
82
    case 0:
83
      break;
84
    default:
85
      cerr << ap.commandName() << ": too many arguments\n";
86
      return 1;
87
  }
88
  istream& is = (ap.files().size()<1 ? cin : input);
89
  ostream& os = (ap.files().size()<2 ? cout : output);
90

	
91
  DimacsDescriptor desc = dimacsType(is);
92
  switch(desc.type)
93
    {
94
    case DimacsDescriptor::MIN:
95
      {
96
        Digraph digraph;
97
        DoubleArcMap lower(digraph), capacity(digraph), cost(digraph);
98
        DoubleNodeMap supply(digraph);
99
        readDimacsMin(is, digraph, lower, capacity, cost, supply, desc);
100
        DigraphWriter<Digraph>(digraph, os).
101
          nodeMap("supply", supply).
102
          arcMap("lower", lower).
103
          arcMap("capacity", capacity).
104
          arcMap("cost", cost).
105
          attribute("problem","min").
106
          run();
107
      }
108
      break;
109
    case DimacsDescriptor::MAX:
110
      {
111
        Digraph digraph;
112
        Node s, t;
113
        DoubleArcMap capacity(digraph);
114
        readDimacsMax(is, digraph, capacity, s, t, desc);
115
        DigraphWriter<Digraph>(digraph, os).
116
          arcMap("capacity", capacity).
117
          node("source", s).
118
          node("target", t).
119
          attribute("problem","max").
120
          run();
121
      }
122
      break;
123
    case DimacsDescriptor::SP:
124
      {
125
        Digraph digraph;
126
        Node s;
127
        DoubleArcMap capacity(digraph);
128
        readDimacsSp(is, digraph, capacity, s, desc);
129
        DigraphWriter<Digraph>(digraph, os).
130
          arcMap("capacity", capacity).
131
          node("source", s).
132
          attribute("problem","sp").
133
          run();
134
      }
135
      break;
136
    case DimacsDescriptor::MAT:
137
      {
138
        Digraph digraph;
139
        readDimacsMat(is, digraph,desc);
140
        DigraphWriter<Digraph>(digraph, os).
141
          attribute("problem","mat").
142
          run();
143
      }
144
      break;
145
    default:
146
      break;
147
    }
148
  return 0;
149
}
Ignore white space 8 line context
... ...
@@ -35,8 +35,9 @@
35 35
^autom4te.cache/.*
36 36
^build-aux/.*
37 37
^objs.*/.*
38 38
^test/[a-z_]*$
39
^tools/[a-z-_]*$
39 40
^demo/.*_demo$
40 41
^build/.*
41 42
^doc/gen-images/.*
42 43
CMakeFiles
Ignore white space 8 line context
... ...
@@ -481,11 +481,20 @@
481 481
graph exporting tools.
482 482
*/
483 483

	
484 484
/**
485
@defgroup dimacs_group DIMACS format
486
@ingroup io_group
487
\brief Read and write files in DIMACS format
488

	
489
Tools to read a digraph from or write it to a file in DIMACS format data.
490
*/
491

	
492
/**
485 493
@defgroup nauty_group NAUTY Format
486 494
@ingroup io_group
487 495
\brief Read \e Nauty format
496

	
488 497
Tool to read graphs from \e Nauty format data.
489 498
*/
490 499

	
491 500
/**
Ignore white space 8 line context
... ...
@@ -26,8 +26,9 @@
26 26
	lemon/core.h \
27 27
        lemon/dfs.h \
28 28
        lemon/dijkstra.h \
29 29
        lemon/dim2.h \
30
        lemon/dimacs.h \
30 31
	lemon/elevator.h \
31 32
	lemon/error.h \
32 33
	lemon/full_graph.h \
33 34
        lemon/graph_to_eps.h \
Ignore white space 8 line context
1 1
if WANT_TOOLS
2 2

	
3
bin_PROGRAMS +=
3
bin_PROGRAMS += \
4
	tools/dimacs-to-lgf
5

	
4 6
dist_bin_SCRIPTS += tools/lemon-0.x-to-1.x.sh
5 7

	
6 8
endif WANT_TOOLS
9

	
10
tools_dimacs_to_lgf_SOURCES = tools/dimacs-to-lgf.cc
0 comments (0 inline)